{"version":"https://jsonfeed.org/version/1.1","title":"苏迟但到的主页","home_page_url":"https://kexohproject.pages.dev","feed_url":"https://kexohproject.pages.dev/json/","description":"

你好，欢迎访问个人主页！

擅长密码学，安全分析，数字水印等技术。

你可以联系我通过:findmykexin@gmail.com或者知乎私信。

我的知乎链接：苏迟但到 - 知乎 (zhihu.com)

我的github链接：kexinoh

","icon":"https://kexohcdn.gptapi.cyou/kexohproject/production/images/channel-2e54d141ee195646ca12a9d16507a908.jpg","favicon":"https://kexohcdn.gptapi.cyou/kexohproject/production/images/favicon-340a2925d02a0386f3b954a032834917.jpg","authors":[{"name":"苏迟但到"}],"language":"zh-cn","items":[{"id":"44Jgp-uEUnY","title":"王小云老师破解MD5算法到底是怎么回事啊，有没有人给我们这些外行科普下？","content_html":"

本人在两年前系统学过密码分析的相关内容，当时的确是懂了，不过现在已经有些忘记了，如果有误可以在评论区指出。

我们要首先脱去所有的hash函数的外壳，在不考虑特殊构造的hash的情况下，hash函数本质是一个布尔方程组。

这句话什么意思呢?我们定义如下的式子就叫做 苏迟但到hash 吧。

\"\\begin{align*}

我们假设 \"x_i\" 是代表第i项输入, \"output_i\" 是代表第i项输出。

hash函数的本质就是定义了若干个这个式子。

当然现实生活中的式子都特别长，长到里面的项数可能是2^80的级别。

1.为什么可以做到那么长？

这是由于hash函数的迭代性质产生的。你可以重新看上面的公式，在第二轮的时候output又会变成x重新输入，那么代入第一轮的式子是不是就变得非常长，相当于乘上了一个原有的系数项的数量。

2.王小云想要破解什么？

王小云想要构造出一个碰撞对，换句话说就是实现在不同的输入但是相同的输出。

3.在原来我们碰撞一个hash对需要多少的计算量?

我们不考虑某个具体hash函数的性质，假设它的输出是随机的，长度为n，它的输出空间是 \"2^n\" 。那么大概平均需要遍历 \"\\sqrt{2^n}\" 才能找到一个碰撞对。在这里就是 \"\\sqrt{2^3}\" .

有几点要声明：1.n要足够大的情况下，才符合这个近似公式。

2.平均是指多次实验之后求平均值，在某一次你可能第一次就抽中了一个碰撞对，也可能你遍历完所有空间才抽中。这是一个期望值。

4.差分是什么？

输入差分是指存在一对输入 \"\\Delta(x_0x_1x_2,x_0'x_1'x_2')=(m_0m_1m_2)\"

而这里的 \"m_i=x_i\\oplus 。

我们在这里要引入一个知识，就是mod2下的加法和异或等价。也就是上式子可以写作 \"m_i=x_i+x_i' 。

在后文我会省略mod2，同时加法和异或混用，你可以均看作加法即可(我主要是为了节约括号）。

我们会保持着m不变，而改变x的值，当然x'也会随之改变。

输出差分是指 \"\\Delta(O,O')=O\\oplus

注意，当m全部为0的时候，那么这个差分是平凡的差分，因为输出的值肯定相等，那么输出也全是0，所以我们不考虑这种情况。

5.魔力的一刻来了。

现在我们只关注output2.

\"Output_2

\"\\Delta

现在我们发现输出的差分值可以被表示为 \"x_1x_2\\oplus 。

而 \"x_1x_2\\oplus 有一个性质就是当 \"x_1=x'_2 的时候就等于0。

6.当我们设定了一个输入差分值为(0,1,1)。

我们惊奇的发现，在保持着这个差分的前提下，最后的一个输出值总是保持着0。

7.恭喜你.

你从密码学的角度成功破解了 苏迟但到hash 。

你成功发现了它的不均匀性，使得它不再是一个完美的hash函数。

因为我们保持这个输入差分的情况下，前面两个比特位的输出空间只有2*2，那么碰撞复杂度只需要根据生日攻击原理，对输出空间进行开根号，也就是 \"\\sqrt{2^2}=2\" 。

但是这一步还不能够破解。

8.遍历，我们需要将 \"x_0x_1x_2\" 从000遍历到111，当然我们也要同步计算 \"x'_0x'_1x'_2\" 。

那么你就可以成功找到一个碰撞对。

在实际情况中，对于某一个输入差分对的输出差分是一个概率分布。

我们可以通过数学分析也可以通过遍历来实现对这个概率分布求解。当这个偏差足够大的时候就可以为破解提供条件。

对于多轮而言，这个偏差就是乘积形式存在，所以当轮次过多的时候它就被搅拌的足够均匀了，那么差分攻击的威力就没有那么强了。

","content_text":"本人在两年前系统学过密码分析的相关内容，当时的确是懂了，不过现在已经有些忘记了，如果有误可以在评论区指出。\n\n我们要首先脱去所有的hash函数的外壳，在不考虑特殊构造的hash的情况下，hash函数本质是一个布尔方程组。\n\n这句话什么意思呢?我们定义如下的式子就叫做 苏迟但到hash 吧。\n\n\\begin{align*} Output_0 &= x_0 x_1 + x_1 x_2 + x_1 \\mod 2\\\\ Output_1 &= x_1 +\nx_1 x_2 x_0 + x_2\\mod 2 \\\\ Output_2 &= x_2 x_1 + x_1 + x_2 \\mod 2 \\end{align*}\n[https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+Output_0+%26%3D+x_0+x_1++%2B+x_1+x_2+%2B+x_1+%5Cmod+2%5C%5C+Output_1+%26%3D+x_1++%2B+x_1+x_2+x_0+%2B+x_2%5Cmod+2+%5C%5C+Output_2+%26%3D+x_2+x_1+%2B+x_1++%2B+x_2+%5Cmod+2+%5Cend%7Balign%2A%7D]\n\n我们假设 x_i [https://www.zhihu.com/equation?tex=x_i] 是代表第i项输入, output_i\n[https://www.zhihu.com/equation?tex=output_i] 是代表第i项输出。\n\nhash函数的本质就是定义了若干个这个式子。\n\n当然现实生活中的式子都特别长，长到里面的项数可能是2^80的级别。\n\n1.为什么可以做到那么长？\n\n这是由于hash函数的迭代性质产生的。你可以重新看上面的公式，在第二轮的时候output又会变成x重新输入，那么代入第一轮的式子是不是就变得非常长，相当于乘上了一个原有的系数项的数量。\n\n2.王小云想要破解什么？\n\n王小云想要构造出一个碰撞对，换句话说就是实现在不同的输入但是相同的输出。\n\n3.在原来我们碰撞一个hash对需要多少的计算量?\n\n我们不考虑某个具体hash函数的性质，假设它的输出是随机的，长度为n，它的输出空间是 2^n\n[https://www.zhihu.com/equation?tex=2%5En] 。那么大概平均需要遍历 \\sqrt{2^n}\n[https://www.zhihu.com/equation?tex=%5Csqrt%7B2%5En%7D] 才能找到一个碰撞对。在这里就是\n\\sqrt{2^3} [https://www.zhihu.com/equation?tex=%5Csqrt%7B2%5E3%7D] .\n\n有几点要声明：1.n要足够大的情况下，才符合这个近似公式。\n\n2.平均是指多次实验之后求平均值，在某一次你可能第一次就抽中了一个碰撞对，也可能你遍历完所有空间才抽中。这是一个期望值。\n\n4.差分是什么？\n\n输入差分是指存在一对输入 \\Delta(x_0x_1x_2,x_0'x_1'x_2')=(m_0m_1m_2)\n[https://www.zhihu.com/equation?tex=%5CDelta%28x_0x_1x_2%2Cx_0%27x_1%27x_2%27%29%3D%28m_0m_1m_2%29]\n\n而这里的 m_i=x_i\\oplus x_i'\n[https://www.zhihu.com/equation?tex=m_i%3Dx_i%5Coplus+x_i%27] 。\n\n我们在这里要引入一个知识，就是mod2下的加法和异或等价。也就是上式子可以写作 m_i=x_i+x_i' \\mod 2\n[https://www.zhihu.com/equation?tex=m_i%3Dx_i%2Bx_i%27+%5Cmod+2] 。\n\n在后文我会省略mod2，同时加法和异或混用，你可以均看作加法即可(我主要是为了节约括号）。\n\n我们会保持着m不变，而改变x的值，当然x'也会随之改变。\n\n输出差分是指 \\Delta(O,O')=O\\oplus O'\n[https://www.zhihu.com/equation?tex=%5CDelta%28O%2CO%27%29%3DO%5Coplus+O%27]\n\n注意，当m全部为0的时候，那么这个差分是平凡的差分，因为输出的值肯定相等，那么输出也全是0，所以我们不考虑这种情况。\n\n5.魔力的一刻来了。\n\n现在我们只关注output2.\n\nOutput_2 = x_2 x_1 + x_1 + x_2 \\mod 2\n[https://www.zhihu.com/equation?tex=Output_2+%3D+x_2+x_1+%2B+x_1++%2B+x_2+%5Cmod+2+]\n\n\\Delta O_2=O_2\\oplus O_2'=( x_1x_2 + x_1 + x_2 )\\oplus( x'_1x'_2 + x'_1 +\nx'_2)\\\\ =x_1x_2\\oplus x'_1x'_2+x_1\\oplus x'_1+x_2\\oplus x'_2\\\\ =x_1x_2\\oplus\nx'_1x'_2+m_1+m_2\n[https://www.zhihu.com/equation?tex=%5CDelta+O_2%3DO_2%5Coplus+O_2%27%3D%28+x_1x_2+%2B+x_1++%2B+x_2+%29%5Coplus%28+x%27_1x%27_2+%2B+x%27_1++%2B+x%27_2%29%5C%5C+%3Dx_1x_2%5Coplus+x%27_1x%27_2%2Bx_1%5Coplus+x%27_1%2Bx_2%5Coplus+x%27_2%5C%5C+%3Dx_1x_2%5Coplus+x%27_1x%27_2%2Bm_1%2Bm_2]\n\n现在我们发现输出的差分值可以被表示为 x_1x_2\\oplus x'_1x'_2+m_1+m_2\n[https://www.zhihu.com/equation?tex=x_1x_2%5Coplus+x%27_1x%27_2%2Bm_1%2Bm_2] 。\n\n而 x_1x_2\\oplus x'_1x'_2\n[https://www.zhihu.com/equation?tex=x_1x_2%5Coplus+x%27_1x%27_2] 有一个性质就是当\nx_1=x'_2 \\& x'_1=x_2\n[https://www.zhihu.com/equation?tex=x_1%3Dx%27_2+%5C%26+x%27_1%3Dx_2] 的时候就等于0。\n\n6.当我们设定了一个输入差分值为(0,1,1)。\n\n我们惊奇的发现，在保持着这个差分的前提下，最后的一个输出值总是保持着0。\n\n7.恭喜你.\n\n你从密码学的角度成功破解了 苏迟但到hash 。\n\n你成功发现了它的不均匀性，使得它不再是一个完美的hash函数。\n\n因为我们保持这个输入差分的情况下，前面两个比特位的输出空间只有2*2，那么碰撞复杂度只需要根据生日攻击原理，对输出空间进行开根号，也就是\n\\sqrt{2^2}=2 [https://www.zhihu.com/equation?tex=%5Csqrt%7B2%5E2%7D%3D2] 。\n\n但是这一步还不能够破解。\n\n8.遍历，我们需要将 x_0x_1x_2 [https://www.zhihu.com/equation?tex=x_0x_1x_2]\n从000遍历到111，当然我们也要同步计算 x'_0x'_1x'_2\n[https://www.zhihu.com/equation?tex=x%27_0x%27_1x%27_2] 。\n\n那么你就可以成功找到一个碰撞对。\n\n--------------------------------------------------------------------------------\n\n在实际情况中，对于某一个输入差分对的输出差分是一个概率分布。\n\n我们可以通过数学分析也可以通过遍历来实现对这个概率分布求解。当这个偏差足够大的时候就可以为破解提供条件。\n\n--------------------------------------------------------------------------------\n\n对于多轮而言，这个偏差就是乘积形式存在，所以当轮次过多的时候它就被搅拌的足够均匀了，那么差分攻击的威力就没有那么强了。\n\n","date_published":"2024-04-06T15:47:00.000Z","_microfeed":{"web_url":"https://kexohproject.pages.dev/i/md5-44Jgp-uEUnY/","json_url":"https://kexohproject.pages.dev/i/44Jgp-uEUnY/json/","rss_url":"https://kexohproject.pages.dev/i/44Jgp-uEUnY/rss/","guid":"44Jgp-uEUnY","status":"published","itunes:title":"New Article Title for iTunes","date_published_short":"Sat Apr 06 2024","date_published_ms":1712418420000}}],"_microfeed":{"microfeed_version":"0.1.2","base_url":"https://kexohproject.pages.dev","categories":[{"name":"Education","categories":[{"name":"Language Learning"}]},{"name":"Technology"}],"subscribe_methods":[{"name":"RSS","type":"rss","url":"https://kexohproject.pages.dev/rss/","image":"https://kexohproject.pages.dev/assets/brands/subscribe/rss.png","enabled":true,"editable":false,"id":"4KlfbtkEfzy"},{"name":"JSON","type":"json","url":"https://kexohproject.pages.dev/json/","image":"https://kexohproject.pages.dev/assets/brands/subscribe/json.png","enabled":true,"editable":false,"id":"DVFm7TYiNSq"}],"description_text":"你好，欢迎访问个人主页！\n\n擅长密码学，安全分析，数字水印等技术。\n\n你可以联系我通过:findmykexin@gmail.com或者知乎私信。\n\n我的知乎链接：苏迟但到 - 知乎 (zhihu.com)\n\n我的github链接：kexinoh","copyright":"©2024","itunes:type":"episodic","items_sort_order":"newest_first"}}