Hash函数MD5攻击技术研究(19)

Hash函数MD5攻击技术研究

第三章ＭＤ５的碰撞攻击１７

３．２比特跟踪技术

在ＭＤ５碰撞攻击的过程中，在差分引入之后，必须应用比特跟踪技术对差分进行比特级别的跟踪，以确保有效地控制差分路径，最终实现碰撞。

就ＭＤ５的第一轮而言，以四个连续步骤为例：

ａ＝ｂ＋（（ａ＋Ｆ（ｂ，Ｃ，ｄ）＋ｍｉ＋ｔｉ）＜＜＜ｓｉ）；

ｄ＝ａ＋（（ｄ＋Ｆ（ａ，ｂ，ｃ）＋ｍ“１＋ｔ“１）＜＜＜ｓ“１）；

ｃ＝ｄ＋（（ｃ＋Ｆ（ｄ，ａ，ｂ）＋ｍｉ＋２＋ｔｉ＋２）＜＜＜ｓｉ＋２）；

ｂ＝ｃ＋（（ｂ＋Ｆ（ｃ，ｄ，ａ）＋ｍｉ＋３＋ｔ“３）＜＜＜ｓｉ＋３）；式（３．１）式（３．２）式（３－３）式（３．４）

在这每一步中，只有Ｆ函数的运算是位运算，除此以外的运算都是模２３２的加法运算。因此，在Ｆ函数中，其三个参数某一比特的变化，最终只会影响Ｆ函数的相应的比特位；Ｆ函数以外的运算，由于可能存在进位的问题，所以影响的可能不只是变化的那一比特，而且可能是影响其周围的一连串的比特位，影响的范围可能很大，这就需要依靠比特跟踪技术来监控。在整个运算过程中，第３２比特位置特殊，其进位将会产生溢出，这个性质在比特跟踪过程中至关重要。下面将以文献ｆ１７１为例，介绍比特跟踪技术在碰撞攻击中的应用。

３．２．１符号说明

１．Ｍ＝（ｍｏ，ｍ。，…，ｍ。５）和Ｍ’＝（ｍｏ’，ｍ。’，…，ｍ。，Ｉ）代表相对应的两个５１２比特的明文块，ＡＭ＝（Ａｍ。，Ａｍｌ，．一，Ａｍ。，）代表两个相对应的明文块的差分，其中每个ｍ；为３２比特的字。

２．ａｉ，ｄｉ，ｃｉ，ｂｉ分别代表第（４ｉ．３）步，第（４ｉ．２）步，第（４ｉ．１）步，第４ｉ步的输出，其中１≤ｉ≤１６；同样的方法定义ａ；’，ｂ；’，ｃｉ＇，ｄ；’。

３．ａｉ，ｊ，ｂｉ，ｊ，ｃｉＪ，ｄｕ分别代表ａｉ，ｄｉ，ｃｉ，ｂｉ的第ｊ比特，其中，最高位为第３２比特，最低位为第１比特。

４．西舻ＩＩ／ｉｊ，分别表示ｍｉ和Ｅ的第ｊ比特，其中中；表示第ｉ步的逻辑函数，Ｖ；表示循环左移的整体的表达式。例如，第８步中，西７＝Ｆ（ｃ２，ｄ２，ａ２）＝（ｃ２Ａｄ２）Ｖ（－１ｃ２＾ａ２），１ｌ，７＝ｂｌ＋Ｆ（ｃ２，ｄ２，ａ２）＋ｍ７＋ｔ７。

５．△Ｘｉ，ｊ＝ｘ硒ｔ．ｘ硝＝－１，这是表示第ｊ比特的差分。如果值为１，说明ｘｉ’的第ｊＬｔ特是１而Ｘ；的第ｊ比特是０；如果值是０，说明ｘｉ７的第ｊ比特是０而ｘ；的第ｊ比特是１，其中Ｘ可以是ａ，ｂ，ｃ，ｄ，西，Ｖ。

６．Ａｘ；［ｊｌ，ｊ２，…，ｊｌ】＝Ｘｉ［ｊｌ，ｊ２，…＇ｊｌ】－Ｘ；，表示ｘ；的第ｊＬｊ２，…，ｊｌ比特的变化。ｘ；【ｊ１，ｊ２，…，ｊｌ】表示具体第ｊ１，ｊ２＂＂ｊｌ的比特的变化，其中“＋＂表示该比特从Ｏ变成了１；“．”表示该比特从１变成了０。