MD6 그리고 약간의 자랑질

모종의 코드에서 특정 메시지에 대한 응답이, 정말로 응답이 맞는지(…) 확인하려고 몇 개의 cryptographic hash funciton ((몇 가지 암호학적으로 좋은 성질을 갖는 해쉬 함수들) 을 뒤지다가 SHA-3 프로포졀로 올라가 있는 MD6를 좀 끄적거려봤다. ((MD5는 참 많이도 썼지만 이젠 좀 불안하기에…)) 

MD5와는 달리 digest 크기를 조절 할 수 있고 ((MD5는 128bits=32Bytes 지만 MD6는 최대 512bits 이하의 모든 크기에 대해 만들어낼 수 있다)) , multi/many-core를 염두에 두고 작성된 알고리즘이다. 여튼 이 녀석의 reference implmenetaion을 구해다가 몇 가지 테스트를 했다. 

다른 해쉬 알고리즘은 — 예를 들어 MD5나 SHA-2 의 SHA-256 같은 녀석들 — 그냥 python hashlib 가지고 예제값을 만들어다가 테스트했는데, MD6는 나온지 얼마 되지도 않았기에 그런게 없다(일단 OpenSSL에 없으니…). 그래서 웹에 있던 MD6 계산기로 값을 계산하고, 이걸 참조 구현체랑 비교하는데 값이 다르게 나오는게 아닌가 Orz

 

처음엔 내가 뭘 잘못했나하고 거의 반나절 넘게 디버깅했는데 도저희 잘못을 찾을 수가 없어서 참조 구현체를 까봤다(…). 그랬더니 버그가 보이더라. md6_mode.c의 memcpy()와 trim_hashval() 호출순서가 바뀌어 있었다 Orz.

값을 다 계산 안하고 이걸 출력 버퍼에 보냈으니 값이 같을리가. 반대로 hex-string 형태로 만들어내는 부분은 저 순서보다 뒤에 있는 거라 문자열 출력엔 아무문제도 없었다(…).

여기까진 삽질기. 이제 자랑질(?)

저런 버그가 있다고 알고리즘의 주 저자인 R. Rivest 교수 — 학교 다닐 때 열심히 읽었던 CLRS의 Intro. to Algorithm의 그 R 이다 ((덤으로 RSA의 R이다)) — 에게 메일을 보냈더니, 

Thank you for reporting the bug in md6_mode.c.
I very much appreciate your bringing this to our attention.

You are correct that the trim_hashval call should precede the memcpy call.

We will be issuing a bug report on this shortly, with the obvious fix.

(For the record: you are the second person to have reported this bug to us.  But in any case: thank you very much for doing so!)

Sincerely,
Ronald L. Rivest

라고 메일이 왔다 :$ 하지만 두번째라니 Orz

여튼 그제 골머리를 썩이던 문제는 해결.

여튼 세줄 요약.

  • 유명한 프로그래머/교수의 코드라고 버그가 없는건 아니다. MD6에는 이미 해결된거지만 버퍼오버플로우 문제도 있었다.
  • 충분한 리뷰를 거친 코드가 아니면 완전히 신뢰하진 말아라. 리뷰가 아직 충분히 진행안 된 코드엔 버그가 숨어있을 수 있다.
  • 테스트 케이스를 확보하라. 모든 (알고있는) 버그를 순식간에 확인하는것만큼 좋은건 없다 ((MD5/MD6/SHA-256 래퍼를 만들어놓고 한 큐에 테스트하면서 진행했다)) 
Jinuk Kim
Jinuk Kim

SW Engineer / gamer / bookworm / atheist / feminist

Articles: 935

13 Comments

  1. MD5도 어떤 부분을 잘라써도 uniform한 특성을 가지는 걸 고려한 것으로 알고 있는데… (공식적인 문서 쪽에선 안나와있었던 것 같지만…)

  2. 그 문제(?)보다는 아무래도 MD5는 *현실적으로 collision을 찾을 수 있다*는 문제로 지금 쓰기엔 좀 그렇(?)죠~;

  3. 네, 그건 맞는 얘기죠. ^^ 저는 ‘MD5와는 달리 digest 크기를 조절 할 수 있고’라는 부분에 대해서 comment 한 내용입니다.

  4. 그런데, MD4/MD5/MD6의 저자가 Intro. to Algorithms의 저자 중 한명인 사실은 처음 알았네요. 그나저나 레퍼런스 구현에 버그도 찾아내고 인정도 받고… 자랑질할만 하네요. ^^ 마지막 요약에 대해서는 전적으로 동의합니다.

  5. 음 공부하는 학부생입니다.
    rein님 블로그 포스트는 항상 잘보고있습니다.
    우연히 MD6를 사용해볼려고 하는데 찾으신 버그는 수정이 된건가요?
    C는 안배우고 자바부터 배워서 난감합니다… 엄니 ㅠ.ㅠ

  6. pyrice / 해당 문제는 수정되었습니다. (2009-4-15일 패치)
    C 패밀리의 언어니까 문법적인건 괜찮을텐데, C가 저수준 언어 기능을 많이 포함한단걸 생각하면서 짜면 편할꺼에요;;

  7. 답변에 감사드립니다.
    안그래도 결국에는 C++이나 C로 가야될꺼 같다는 생각이..

Leave a Reply