요약

  • RFC 1186은 MD4가 Sun SPARC에서 초당 1,450,000바이트, DEC MicroVAX II에서 약 70,000바이트, 20MHz 80286에서 약 32,000바이트를 처리한다고 기록했다. 서로 다른 메시지가 같은 요약값을 만드는 데 드는 비용은 추정치였다.
  • RFC 1320은 1992년 더 이식하기 쉬운 참조 구현으로 앞선 문서를 대체했다. RFC 6150은 확인된 공격들을 거쳐 2011년 MD4를 Historic으로 옮겼다.

파일의 디지털 서명에 붙는 짧은 지문이 있다. 그 지문을 다른 파일도 만들 수 있다면 서명을 믿는 사람은 곤란해진다. Ronald Rivest의 1990년 10월 RFC 1186은 MD4를 임의 길이 메시지를 128비트 요약값으로 줄이는 알고리즘으로 소개했다. 큰 파일을 RSA로 서명하기 전에 쓰는 것이 제안된 용도 중 하나였다. 짧게 계산할 수 있어야 했고, 다른 파일이 같은 값을 만들어서는 곤란했다.

첫 번째 조건에는 실측값이 붙었다. Sun SPARC는 초당 1,450,000바이트, DEC MicroVAX II는 약 70,000바이트, 20MHz 80286은 약 32,000바이트를 처리했다. 큰 치환표가 필요하지 않다는 설명도 있었다. 부록에는 C 언어 인터페이스와 구현, 시험용 프로그램, 실행 예시가 실렸다. 32비트 단어와 512비트 블록, 채움 비트와 원래 메시지 길이를 넣는 방식까지 정해 두었다. 누구나 같은 계산을 구현하고 속도를 확인할 수 있었다.

두 번째 조건의 숫자는 실측과 달랐다. 문서는 두 메시지가 같은 요약값을 만드는 충돌을 찾으려면 약 2^64회, 특정 요약값을 내는 메시지를 찾으려면 약 2^128회의 연산이 필요하다고 추정했다. 알고리즘이 새롭기 때문에 추가 보안 분석이 필요하다고도 썼다. 한 번 계산하는 데 걸리는 시간은 측정할 수 있다. 아직 발견되지 않은 공격법의 지름길은 그 측정표에 나타나지 않는다.

MD4는 검토와 향후 표준 채택을 위해 공개됐고, 1990년 RFC 자체는 정보 제공 문서였다. 공개된 정확한 규칙은 구현자와 공격을 연구하는 사람 모두에게 같은 대상을 줬다. 1992년 4월 RFC 1320은 RFC 1186을 대체했다. 문서가 밝힌 주된 변화는 참조 구현의 이식성 개선이었다. OSI 응용을 위한 알고리즘 식별자와 매개변수 규칙도 추가됐다. 더 많은 환경에서 같은 함수를 실행할 수 있게 됐지만, 충돌에 관한 가정은 계속 검증을 받아야 했다.

그 검증 결과가 2011년 3월 RFC 6150에 모였다. 1996년의 실용적인 충돌 공격은 약 2^20회의 MD4 계산을, 2004년의 결과는 약 2^8회를 요구했다고 기록했다. 최초의 2^64 추정과 차이는 아주 컸다. IETF는 RFC 1320을 Historic으로 옮기고 SHA-256 같은 기존 대안으로 바꾸도록 권고했다.

퇴역 문서는 Microsoft의 호환 경로를 비롯한 남은 사용처도 살폈다. RFC 상태표는 하루에 고칠 수 있지만, 설치된 소프트웨어와 상대 시스템은 각각 바꿔야 한다. MD4의 빠른 실행 시간이 남긴 가장 느린 일은 그 의존성을 찾아 걷어 내는 작업이었다.

출처