해시(Hash) 알고리즘

해시 알고리즘이란?

해시 알고리즘은 Key와 Value로 구성된 Array 형태의 테이블이라는 것이 제가 알고 있던 전부였습니다. 어떤 값을 입력하면 Hash function을 통해 어떤 출력값을 가지는 것입니다. 아래 그림을 예로 들면 John Smith를 입력하면 해시값으로 02가 튀어나오는 거라 생각하면 됩니다.

<출처> 위키백과(https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98)

가장 손쉽게 Hash function을 만드는 방법은 아스키 코드값을 사용하는 것입니다. John Smith 라는 입력을 받아 각각의 문자의 아스키코드값을 다 더해주는 것입니다. 아스키 코드값을 사용하는 것은 예를 든것이고 이것보다 더 복잡하고 보안에 강력하게 만들어져 있습니다.

해시 충돌

위에서 John Smith와 Sandra Dee의 해시값이 같은것을 알 수 있습니다. 이것을 충돌(Collision)이라고 하는데 같은 해시값이 생길 수 있습니다. 아스키 코드값을 더하다보면 합이 같은 경우가 나올 수 있는 것과 같습니다. 

좋은 해시 함수는 이와같은 충돌이 잘 안나타 날수록 좋은 함수 입니다. 해시를 검색에 사용할 때에는 충돌이 없어야 검색이 빠릅니다. 보통 해시 알고리즘의 검색 속도는 O(1)이라고 합니다. 그도 그럴것이 문자를 해시 함수를 통해 어떤 일정한 값으로 바꾸고, 그 값을 인덱스로 하는 테이블에서 찾기 때문에 따로 검색 알고리즘을 사용할 필요가 없습니다. 하지만 만약 충돌이 많이 일어나게 되면 촤악의 경우 O(n)의 시간 복잡도를 가지게 된다고 합니다. 

검색 뿐만 아니라 보안에 있어서도 충돌은 좋지 않습니다. MD5라는 해시 함수의 경우 해시 충돌을 통해 해커들이 보안을 뚫었습니다. 가령 위에서 John Smith가 비밀번호라고 하겠습니다. 다른 어떤 이름을 넣어도 02라는 해시 코드가 나오지 않겠지만 Sandra Dee를 넣으면 02라는 해시코드를 얻게됩니다. 해시 알고리즘 입장에서는 John Smith나 Sandra Dee나 같은 입력이라 생각하는 것입니다.

SHA-2 같은 해시함수는 아직 뚫리지 않은 안전한 해시 함수라 합니다. 이 함수는 Secure Hash Algorithm의 약자로 모든 입력에 대해 256비트의 결과로 리턴합니다. 위 그림에서 모든 해시를 16개로 나눈 것보다 훨씬 많은 경우의 수를 가지게 되는 것입니다. 그래서 이 SHA-2 는 블록체인의 해시함수로 사용되고 있습니다. 

해시의 단방향성

그럼 해시의 특징에 대해 알아보겠습니다. 해시는 믹서기로 과일 주스를 만드는 것과 같습니다. 

과일을 믹서기에 넣고 과일주스를 만들고 나면 과일주스로 다시 원래의 과일을 만들 수 없습니다. 이것을 암호학에서는 단방향성을 가지고 있다고 합니다. 어떤 문장을 해시 함수로 암호화 하면 더이상 원래 문장을 찾을 수 없는 것입니다. 이런 특징으로 암호를 저장해 놓을 때 좋습니다. 데이터베이스에 암호가 저장되어야 하는데 이 값이 평문으로 저장된다면 해커들이 암호를 바로 알 수 있습니다. 하지만 해시값으로 저장되어 있다면 암호의 원래 값을 알 수 없게 됩니다.

해시의 무결성

단방향성은 암호로써 의미가 없는 것 아닌가 생각될 수 있습니다. 기껏 문장을 암호화 해놨는데 원래 문장을 찾지 못한다면 쓰레기를 만드는 것과 똑같이 느낄 수 있습니다. 하지만 이러한 특징으로 무결성을 검증할 수 있습니다. 무결성이란 조작되지 않고 원본과 같다는 것을 증명할 수 있다는 것입니다. 해시 코드는 값의 일부분만 바뀌어도 완전히 다른 해시코드를 가지게 됩니다. 따라서 원본 데이터에 수정을 가하면 전혀 다른 해시값을 가지게 될 것이고, 무결성은 깨지게 되는 것입니다. 디지털 포렌식에서 증거의 위변조 방지를 위해 해시 함수를 사용합니다. 수집된 증거의 해시값과 나중에 제출된 증거의 해시값을 비교하여 같으면 위 변조가 없었다고 여기는 것입니다.

 

우리가 많이 사용하는 전자서명에도 해시값을 사용합니다. 문서의 해시값을 비교하여 전자문서가 다르지 않다는 것을 알 수 있습니다. 이렇게 공인인증서의 데이터 무결성이나 발신자의 신원 확인에 해시 함수가 사용됩니다.

 

해시의 취약점

해시 함수는 처음에 검색 목적으로 만들어졌습니다. 위에서도 어떻게 해시 함수를 사용해 검색을 하는지 알아 보았습니다. 위의 장점들 때문에 보안에서 꾸준히 활용되고 있습니다. 하지만 위에서도 언급한 내용들로 보안에 취약한 점이 많이 있습니다.

생일 역설(Birthday Paradox)

생일 역설(Birthday Paradox)이란 수 많은 사람들이 있으면 그 안에 생일이 같은 사람들이 존재할 확률이 점점 올라간다는 내용 입니다. 해시 값이 많으면 많을수록 같은 값이 존재할 확률이 있습니다. 위에서 해시 충돌의 경우가 생일 역설에 속합니다. John Smith가 비밀번호였는데 Sandra Dee도 비밀번호로 사용 가능한 경우와 같습니다.

무지개 테이블 공격(Rainbow Table Attack)

무식하게 해시값을 대입해 보는 것을 무지개 테이블 공격이라 합니다. 모든 해시의 쌍을 미리 계산해 놓고 저장해 놓습니다. 그리고 하나하나 대입해서 비밀번호를 찾는 것입니다. 이것으로 소문자 + 대문자 + 숫자 형태의 7자리 암호는 순식간에 해킹이 가능하다고 합니다. 아마 이래서 요즘 암호는 최소 12자리를 요구하는 것 같습니다.

 

취약점 해결 방안 

위에서 언급한 취약점의 해결 방안으로 Salt와 키 스트레칭 기법이 있습니다.

해시 솔트(Hash Salt)

솔트(Salt)는 우리가 알고 있는 소금이 맞습니다. 아까 해시는 원문에 작은 변화를 주어도 결과값이 확 틀려진다고 이야기 했습니다. 이것을 활용하여 원문에 소금을 치는 것입니다. 원문과 함께 랜덤한 Salt값을 저장합니다. 그리고 원문과 Salt값을 결합하여 해시를 만들면 전혀 다른 값이 나오게 되어 암호화 하는데 도움이 됩니다.

해시 키 스트레칭

키 스트레칭은 해시값을 빠르게 만들 수 있다는 것에 착안합니다. 원문이 같다면 해시 결과는 같습니다. 따라서 어떤 평문을 해시로 만들고, 그 해시로 다시 해시를 만드는 것입니다. 이것을 몇 번 시행할지만 정해 반복한다면 원래의 해시값을 찾는 것은 힘들게 됩니다. 어떤 문장을 7번 해시 함수로 돌린다면 해커들은 횟수를 모르면 원문을 찾기 힘들 것입니다. 반대로 7이란 숫자를 알고 있다면 원문을 7번 해시 함수로 돌리면 같은 값을 얻게 되는 것입니다.

 

마무리

간단하게 해시 함수에 대해 알아보았습니다. 해시 함수가 자료구조, 블록체인, 보안등 다양한 분야에 쓰이기 때문에 특징에 대해 잘 알아두면 좋습니다. 해시 값으로 원문을 유추할 수 없는 단방향성, 조금만 바뀌어도 값이 확 바뀌는 특성을 이용한 무결성 체크, 이런 무결성 체크로 위변조 방지와 전자서명에 사용되고 디지털 증거로써 효력을 가지게 됩니다. 마지막으로 Salt나 키 스트레칭 기법을 사용하여 해시의 취약점을 막을 수 있습니다.