md5를 해부해보다.

오늘 2주전부터 계획해오던 해쉬(Hash) 세미나를 했다.

세미나의 부주제는 MD5 였다.

mining the web 이라는 책을 보면 md5는 문서 중복 검사에 쓰일 수 있다고 나온다. 그리고 실제 내가 실무를 그동안 해오면서 알게 모르게 md5를 써왔었던게 사실이다.

뭐 튜플로 (h(u), v), (h(u’), v’)의 형식으로 문서의 지문을 추출해서 그 지문을 키로 사용해 문서의 중복 여부를 판단하는데 이곳에는 조금의 문제가 있긴 하다. 왜냐면 문서에서 구석의 작은 날짜만 바뀌더라도 hash값은 영 다른게 나와버리기 때문이다. 그래서 실무에서는 숫자를 제거한 text만으로 해싱을 해서 쓰기도 하지만 여러 다른 방법이 mining the web에는 나와 있다. (edit distance나 q-gram방법 등등)

이야기가 어디로 셌는데…

md5는 대략 이렇다.

전체 데이터를 512비트의 블록으로 나누고 512비트의 한 블록을 32비트서브블록 16개로 나누어 각 블록의 데이터를 이용해 initial register 값 a,b,c,d 를 업데이트 해나간다. 각 512비트 블록한개에서 레지스터 각각은 4번씩 업데이트 되는 격이다.(그러나 sha-1 알고리즘은 12번의 업데이트를 한다. 그래서 보안성이 더 좋다 한다)
처음부터 모든 메시지 블록들을 거치며 변환된 a,b,c,d 값에 다시 initial register값을 더한 것이 md5 해싱 값이다.

512비트 단위로 연산하기 때문에 연산시 모든 데이터를 로딩할 필요가 없어서 대용량 데이터를 해싱하는데 좋지만 한계는 2^64 정도의 길이 데이터가 한계이다.(해싱 파일 분할시 마지막 512비트의 마지막 64 비트에 데이터 길이 정보를 추가로 넣는다. 이걸로 한계가 정해진건가??)

간단하게 말하면 initial register값 a,b,c,d를 데이터를 비롯 비트연산, sin(i) 값을 등등을 이용해 계속 업데이트 해나가는 것이다. 32비트 연산이 기반이기 때문에 요즘 PC에서 빠르게 돌아가는 장점이 있다.

그런데 알고리즘을 분석하면서 왜 이게 충돌이 적게 일어나는 알고리즘인지 잘 이해가 안간다. 여러 문서를 보면 +연산과 clock wise 쉬프트 연산 그리고 불린 연산을 조합하는게 보안성이 좋다라고만 연구결과로 나와 있기는 하다. 그치만 솔직히 피부에 와닿지 않기는 매한가지이다. ㅡㅡ;

대안으로 나온 sha-1은 160비트로 해싱을 하는데 md5보다 속도는 떨어지지만 더 충돌이 덜 나는 해싱을 값을 가져온다는 연구 결과도 있다. sha-256, sha-512 등등 충돌을 예상한다면 위의 sha 계열을 쓰던가 md5를 재해싱하는 방법을 사용하는게 좋을거 같다.

재미있는 사내 세미나 이만 정리 끝.~~~~~

ps. 재미난 해싱 함수 있으면 코멘트 달아주심 좋아할겁니다. ^^;