论文摘要
散列函数（Hash function），又称杂凑函数，是一种单向密码体制，是一个从明文到密文的不可逆映射，其将任意长度的的输入数据变换为固定长度的输出。散列函数主要用来生成数据的数字指纹，在随机数产生、数据完整性校验、影子密钥、挑战和响应、消息认证码、数字签名和数字证书等领域有广泛的应用。本论文对国际流行的以MD5为代表的迭代散列函数进行安全性分析，并结合这些散列函数在若干应用（如“挑战和响应”，消息认证码(MessageAuthenticationCode, MAC)）中存在的一系列安全问题进行分析，试图从散列函数自身安全、及其在若干应用中的安全需求两方面对散列函数的安全性进行分析、研究和论证。为了实现最优的碰撞攻击，我们提出一种选择MD5最优消息差分的方法，首先，根据充分条件满足的难易将其分类为强条件和弱条件；其次，利用MD5压缩函数存在的弱性质（消息扩展和差分继承），证明MD5在一定条件下仅在24步（1轮半）存在强条件；再次，根据状态字q25后的差分路径不应存在差分延展（保证每条路径的强条件数最少），导出每个可能消息差分模式的强条件分布；最后，选择具有最少强条件和最多自由消息字的消息差分。我们提出应用分而治之的策略对MD5的碰撞搜索进行分割以达到将搜索各阶段复杂度相加而不是相乘的目的，同时我们亦提出群满足方案在分而治之策略下最后一个通道确定性满足首三步强条件并利用通道剩余自由消息位进行强条件的随机满足，大大降低了MD5碰撞搜索的复杂度。因此，在构造相应差分路径时，应构造自由消息位多的路径以对分而治之策略和通道技术进行支撑。应用以上方法，我们实施了最为高效的MD5碰撞攻击，仅需218次MD5散列计算即可找到一个碰撞对。该方法同样适用于MD结构(Merkle-Damg rd construction)其他散列函数的安全性分析。为了控制MD5碰撞对的更多消息字，我们提出两个新的通道q′1和q1分别生成具有320位和352位信息确定的MD5碰撞对。应用q1通道，我们可以任意设定m5至m15的值，而仅通过修改m0至m4快速产生碰撞对。同时，结合分而治之和群满足方案，降低具有多位信息确定的MD5碰撞对搜索的复杂度。带认证邮局协议(Authentication Post Office Protocol, APOP)对密钥的散列方式为MD5(C P)，简化的摘要认证协议(Digest Access Authentication, DAA)对密钥的散列方式为MD5(MD5(C P))，其中C为挑战，P为用户和服务器之间的共享密钥。在普通的个人计算机上（2GCPU），生成恢复APOP所使用密钥的前11个字符的MD5碰撞对的平均时间为0.08秒，且在本地计算机上实施针对APOP的“切片”密钥恢复攻击，能够在不到1分钟的时间内恢复出长达11个字符的密钥内容，进一步论证了APOP的安全性已经完全破坏。由于DAA的外层散列无法隐藏内层散列碰撞的存在，因此“切片”密钥恢复攻击适用于DAA，经过8084次在线查询和235离线计算，能够恢复DAA中长达48个字符的密钥，DAA安全性也已经完全破坏。我们讨论了基于秘密后缀的R H(C P)方案的安全性，其中H为任意MD结构散列函数。我们以“切片”密钥恢复攻击的方式证明，即使随机产生的密钥P的长度大于或者等于散列函数的输出值，R的安全性还是依赖于散列函数的碰撞安全性，而不是使用密钥的强度。最后，为了抵御“切片”密钥恢复攻击，我们对输入消息C进行补齐操作使得密钥字位于最后一个分组块中（密钥不能被切分）从而完成对基于秘密后缀方案的H(C P)的安全增强，该方案不需对现有的散列函数进行修补。进行消息补齐后，H(C pad(x)P)能够抵御基于碰撞攻击的“切片”密钥恢复攻击，即不管底层散列函数H是否为碰撞安全，攻击者对密钥进行恢复攻击的最优方案都只能是密钥穷举搜索。由于MD结构散列函数的填充机制存在安全缺陷，针对以挑战握手认证协议（Challenge and Handshake Authentication Protocol, CHAP）为代表的基于MD结构散列函数的秘密前缀方案，我们提出一种已知长度密钥的快速破解方法：首先利用在线查询获得其密钥长度，然后利用基于概率的上下文无关文法进行快速离线密钥破解。结合假冒服务器攻击和MD结构散列函数的扩展攻击原理恢复出秘密前缀方案R H(P C)中使用密钥的长度。攻击者发送挑战C且得到响应R。若密钥P的长度猜测正确，且P C的填充值为pad0，根据扩展攻击原理，对于任意的消息r，等式H(P C pad0r) h(R r pad1)成立。对于长度为l个字符的密钥，攻击者仅需要发送l1次在线查询。结合已知的密钥长度和基于概率的上下文无关文法，进行已知长度密钥的快速破解。首先，我们从一些公开泄漏的密钥表（训练集）中收集固定长度密钥的基本结构和其对应的概率。其次，基于获得的密钥基本结构和对应的概率，自动生成一组基于概率的上下文无关文法，其中每个文法都是基于不同的密钥长度。最后，基于已知的挑战C和响应R，以及恢复出的密钥长度l，我们使用一个选定的字典文件并且利用基于概率的上下文无关文法以概率高低的次序来产生字符重整规则以极大提高密钥破解的效率。结合散列函数的通用扩展攻击和带两个分组的生日攻击，我们提出一种针对H2-MAC有效且通用的等价密钥恢复攻击方法，需要指出的是，该攻击方法适用于所有的以MD结构散列函数实例化的H2-MAC。H2-MAC是基于散列函数的消息认证码(Hash-based Message Authentication Code, HMAC)的无外部密钥版本，旨在解决HMAC存在的密钥管理问题并获得更高的处理效率，其如HMAC一样具有可证明安全性。设H2-MAC的密钥为K，在分组G1中存储r个n比特(不含填充值)不同的消息x和对应的H(x)值(通过离线计算获得)，在分组G2中存储s个b比特(含填充值)不同的消息M和对应的H2-MAC值(通过在线查询获得)。根据带两个分组的生日攻击原理，当r s2n时，以一定的概率存在一个解(M′x′)使得H(x′) H2-MAC(K)(M′)且对任意的消息有H(M′pad0) h(x′pad1)，其中pad0和pad1分别为消息M′和M′pad0的填充值。因此，x′为H2-MAC的等价密钥。在两个分组数据中G2的值为在线查询结果而G1的值为离线计算结果，由于在线查询只能串行进行而离线计算可以并行完成，因此，可以在增加离线计算次数并减少在线查询次数的同时保持攻击成功的概率不变，以增大该攻击实施的实用性。H2-MAC的等价密钥恢复攻击证明基于MD结构散列函数的H2-MAC不是一个安全的消息认证码。