摘要

  • RFC 1186 报告 MD4 在 Sun SPARC 上每秒处理 1,450,000 字节，在 DEC MicroVAX II 上约 70,000 字节，在 20 MHz 80286 上约 32,000 字节；抗碰撞难度是作者的推测。
  • RFC 1320 于 1992 年以更便于移植的参考实现取代原文件。RFC 6150 于 2011 年在列明攻击结果后，将 MD4 文件转为 Historic 状态。

密码算法的简历里，最容易填满的一栏往往是速度。Ronald Rivest 在 1990 年 10 月的 RFC 1186 中介绍 MD4：输入任意长度的消息，输出 128 位摘要，拟用于大文件的数字签名。文档没有只说“快”，而是列出三台机器和各自的处理量。把摘要算法装进签名程序的人，可以拿着这些数字估算成本。

Sun SPARC 的数据是每秒 1,450,000 字节；DEC MicroVAX II 约 70,000；20 MHz 的 80286 约 32,000。文件还说 MD4 无需大型替换表，代码可以写得紧凑。附录提供 C 语言接口、实现、驱动程序和运行样例。32 位字、512 位分组、填充和原消息长度的编码，也都写成可供别人复现的规则。性能这一栏有机器、有程序、有记录。

另一栏在同一份文件里，却明确标作“推测”。作者估计，找出两条摘要相同的不同消息，大约需要 2^64 次操作；针对指定摘要找出一条消息，大约需要 2^128 次。他同时指出 MD4 还新，需要继续接受安全分析。处理一份文件花多少秒，可以按下秒表；攻击者将来能否找到捷径，秒表答不上来。两种数字看着都精确，证据地位却不同。

RFC 1186 将算法置于公共领域，供人审查和考虑标准化，文件本身属于信息性 RFC。公开的实现让程序员更容易采用 MD4，也让研究者可以围绕同一套精确规则寻找缺口。1992 年 4 月的 RFC 1320 取代了 1990 年版本，自述主要改动是参考实现更便于移植，还给 OSI 应用补上算法标识符与参数约定。搬运代码的手续变顺了，抗碰撞的那一问仍要交给攻击检验。

2011 年 3 月的 RFC 6150 把后来的检验写进正式记录。它列出 1996 年约需 2^20 次 MD4 运算的实用碰撞攻击，以及 2004 年降至 2^8 的结果。相对于 1990 年的 2^64 推测，差距大到足以改变算法的用途判断。IETF 将 RFC 1320 转为 Historic，并建议用 SHA-256 等现有算法替代 MD4。

退役公告也记录了遗留用途，包括微软的一条兼容路径。标准目录里的状态可以在文件发布时改变，部署中的程序和通信对手则要逐个迁移。MD4 的故事因此有两份账：采用时，人们看得到速度与源码；退出时，人们必须清点依赖。前一份账好算，后一份账用了二十多年才写清。

来源