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 래퍼를 만들어놓고 한 큐에 테스트하면서 진행했다))