生日攻击算法相关软件,生日攻击针对什么算法

作者:hacker | 分类:破解 | 浏览:109 | 日期:2022年07月16日

md5 破解现状

一.MD5的由来

MD5的全称是message-digest algorithm 5（报文摘要算法）。是由Ron Rivest（RSA中的“R”）于90年代初提出，经md2、md3和md4发展而来的。Rivest最早于1989年提出了MD2算法，它是面向8位机的而作了优化。为了提高算法的安全性，Rivest在1990年又开发出MD4算法。Den Boer和Bosselaers以及其他人很快的发现了攻击md4版本中之一步和第三步的漏洞。Dobbertin向大家演示了如何利用一部普通的个人电脑在几分钟内找到md4完整版本中的冲突（这个冲突实际上是一种漏洞，它将导致对不同的内容进行加密却可能得到相同的加密后结果）。一年以后，即1991 年，Rivest开发出技术上更为趋近成熟的MD5算法。它在MD4的基础上增加了"安全-带子"（safety-belts）的概念。

下面简单介绍一下MD5比MD4改进的地方：

1． MD4使用三次循环处理，而MD5使用四次循环处理。每次循环仍是16步

2． MD4中，每一步都采用相同的附加限制，而MD5的四次循环分别采用了64个不同的附加限制；

3．在第二次循环中，函数g从（XY v XZ v YZ）改成了（XZ v Y not(Z)），使得g更对称；

4．每步运算结果都会加入下一步的运算中。如步骤1的结果更新了缓存A，步骤2的结果存在B中由A与循环左移的结果相加而得，以此类推，Rivest 认为这样加快了“雪崩效应”；

1993年，美国国家标准和技术协会（NIST）提出了安全散列算法（SHA）。1995年又发

布了一个修订版，即SHA-1。SHA-1与MD5均由MD4导出，所以彼此很相似。相应的，他们的强度和其他特性也是相似的。

1．对强行攻击的安全性：最显著和最重要的区别是SHA-1摘要比MD5摘要长32bit。使用强行技术，产生任何一个报文使其摘要等于给定报文摘要的难度对 MD5是2的123次方数量级的操作，而对SHA-1则是2的160次方数量级的操作。此外，使用强行技术，产生具有相同报文摘要的两个报文的难度对 MD5是264数量级的操作，而对SHA-1则是2的80次方数量级的操作。所以，SHA-1对强行攻击有更大的强度。

2．对密码分析的安全性：由于MD5他的设计，它易受密码分析的攻击。SHA-1则显得不易手这样的攻击。由于有关SHA-1的设计标准几乎没有公开，因此很难判断其强度。

3．速度：因为两个算法都在上以来模2的32次方的加法，因此两者在32bit结构的机器上速度均很好。SHA-1有更多的步骤（80对64）且要处理 160bit的缓存，相比之下MD5仅处理128bit的缓存。这样在相同的硬件上，SHA-1的行速度应该比MD5慢。

4．简单性和紧凑性：两个算法均描述简单、易于实现，并且无须冗长的程序或很大的替换表。

5．小数在前结构与大数在前结构：MD5使用小数在前方案来解释以32bit字序列的报文，SHA-1则使用大数在前。当然，这两种结构并没有更突出的优点。

二．MD5的强度

Rivest 曾猜想MD5作为128bit的散列码是足够强的，即提出具有相同散列码的两个报文需要2^64数量级的操作，而找报文摘要等于与给定摘要的报文需要 2^128数量级的操作。从密码分析的角度看，MD5是被认为易受攻击的。从强行攻击的角度上看，MD5也易受生日攻击，所需的数量级是2^64。对 MD5攻击的历程：

1． Berson表明，对单循环的MD5，使用不同的密码分析可能在合理的时间内找出能够产生相同摘要的两个报文，这个结果被证明对四个循环中的任意一循环也成立。然而，作者还没有能够提出如何攻击包含全部四个循环MD5的攻击。

2． Boer和Bosselaers显示了如何找到一个报文分组X和两个相关链接变量来产生相同的状态，也就是即使缓存ABCD有不同的输入值，MD5对单个512bit分组的执行将得到相同的输出。这就是伪冲突。

3． Dobbertin提出了使MD5的压缩函数产生冲突的技术，即通过寻找另一个分组来产生相同的128bit的输出，攻击将针对MD5对单个512bit的输入分组的操作进行。

4．而现在王小云教授的发现使得MD5堡垒轰然倒塌。加拿大CertainKey公司早前宣布将给予发现MD5算法之一个碰撞人员一定的奖励， CertainKey的初衷是利用并行计算机通过生日攻击来寻找碰撞，而王小云教授等的攻击相对生日攻击需要更少的计算时间。以下是王教授在 “Crypto’2004”上有关攻击MD5的部分

IV0: A0 = 0x67452301， B0 = 0xEFCDAB89， C0 = 098BADEFD， D0 = 0x10325476

M' = M + ΔC1， ΔC1 = (0， 0， 0， 0， 231， ...， 215， ...， 231， 0)

Ni' = Ni + ΔC2， ΔC2 = (0， 0， 0， 0 231， ...， -215， ...， 231， 0)

（位置4、11和14非零）

此时，

MD5(M， Ni) = MD5(M'， Ni')

在IBMP690 上，要用将近一个小时的时间来寻找这样的M和M’，之后只需要15秒至5分钟的时间就可以找到Ni 和 Ni'，此时的(M， Ni) 和 (M'， Ni')将产生相同的散列值。此外，这样的攻击可以工作于任意给定的初始值。我的理解是对给定的报文M，用王教授的 *** 可以在一个可接受的时间内（1小时左右）找到伪报文M’使得二者的Hash值是相同的。

下面是会产生碰撞的1024位消息，这两个例子具有相同的前半部512位。

X1 M 2dd31d1 c4eee6c5 69a3d69 5cf9af98 87b5ca2f ab7e4612 3e580440 897ffbb8

634ad55 2b3f409 8388e483 5a417125 e8255108 9fc9cdf7 f2bd1dd9 5b3c3780

N1 d11d0b96 9c7b41dc f497d8e4 d555655a c79a7335 cfdebf0 66f12930 8fb109d1

797f2775 eb5cd530 baade822 5c15cc79 ddcb74ed 6dd3c55f d80a9bb1 e3a7cc35

X1' M' 2dd31d1 c4eee6c5 69a3d69 5cf9af98 7b5ca2f ab7e4612 3e580440 897ffbb8

634ad55 2b3f409 8388e483 5a41f125 e8255108 9fc9cdf7 72bd1dd9 5b3c3780

N1 d11d0b96 9c7b41dc f497d8e4 d555655a 479a7335 cfdebf0 66f12930 8fb109d1

797f2775 eb5cd530 baade822 5c154c79 ddcb74ed 6dd3c55f 580a9bb1 e3a7cc35

H 9603161f f41fc7ef 9f65ffbc a30f9dbf

X2 M 2dd31d1 c4eee6c5 69a3d69 5cf9af98 87b5ca2f ab7e4612 3e580440 897ffbb8

634ad55 2b3f409 8388e483 5a417125 e8255108 9fc9cdf7 f2bd1dd9 5b3c3780

N2 313e82d8 5b8f3456 d4ac6dae c619c936 b4e253dd fd03da87 6633902 a0cd48d2

42339fe9 e87e570f 70b654ce 1e0da880 bc2198c6 9383a8b6 2b65f996 702af76f

X2' M' 2dd31d1 c4eee6c5 69a3d69 5cf9af98 7b5ca2f ab7e4612 3e580440 897ffbb8

634ad55 2b3f409 8388e483 5a41f125 e8255108 9fc9cdf7 72bd1dd9 5b3c3780

N2 313e82d8 5b8f3456 d4ac6dae c619c936 34e253dd fd03da87 6633902 a0cd48d2

42339fe9 e87e570f 70b654ce 1e0d2880 bc2198c6 9383a8b6 ab65f996 702af76f

H 8d5e7019 6324c015 715d6b58 61804e08

表1 MD5 的两对碰撞

至此，作为一个安全的摘要算法在设计时必须满足两个要求——其一是寻找两个输入得到相同的输出值在计算上是不可行的，这就是我们通常所说的抗碰撞的；其二是找一个输出，能得到给定的输入在计算上是不可行的，即不可从结果推导出它的初始状态——MD5已经无法满足之一个条件，。也就是说MD5已经不安全了，但并没有完全被破解。

三．王教授的发现对MD5的应用的影响

首先我们先来看看MD5的应用领域：

对一段信息（message）产生信息摘要（message-digest），以防止被篡改。比如，在unix下有很多软件在下载的时候都有一个文件名相同，文件扩展名为.MD5的文件，在这个文件中通常只有一行文本，大致结构如：

MD5 (tanajiya.tar.gz) = 0ca175b9c0f726a831d895e269332461

这就是tanajiya.tar.gz文件的数字签名。MD5将整个文件当作一个大文本信息，通过其不可逆的字符串变换算法，产生了这个唯一的MD5信息摘要。如果在以后传播这个文件的过程中，无论文件的内容发生了任何形式的改变（包括人为修改或者下载过程中线路不稳定引起的传输错误等），只要你对这个文件重新计算MD5时就会发现信息摘要不相同，由此可以确定你得到的只是一个不正确的文件。如果再有一个第三方的认证机构，用MD5还可以防止文件作者的 "抵赖"，这就是所谓的数字签名应用。

MD5还广泛用于加密和解密技术上。比如在unix，linux系统中用户的密码就是以MD5（或其它类似的算法）经加密后存储在文件系统中。当用户登录的时候，系统把用户输入的密码计算成MD5值，然后再去和保存在文件系统中的MD5值进行比较，进而确定输入的密码是否正确。通过这样的步骤，系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。这不但可以避免用户的密码被具有系统管理员权限的用户知道，而且还在一定程度上增加了密码被破解的难度。

下面我们讨论一下王教授的发现对MD5的应用的影响。

应该可以认为在unix，linux系统中用户身份验证还是安全的，并不象 *** 上一些人指出的出现安全漏洞。从王教授给出的对伪报文的计算 *** ：

M' = M + ΔC1， ΔC1 = (0， 0， 0， 0， 231， ...， 215， ...， 231， 0)

Ni' = Ni + ΔC2， ΔC2 = (0， 0， 0， 0 231， ...， -215， ...， 231， 0)

可以看出如果想得到M’，N’必须有原文M，N。而在unix，linux的用户身份验证中，攻击的一方即使找到的了用户的密码文件（存有密码的MD5值）也不可能从中得到与原密码产生碰撞的报文。不过作为一个摘要算法而言，MD5已经是不安全的了。

而在文件的数字签名方面，我们也暂时不用过于恐慌。王教授的算法找到了相同原始初值的1024位的MD5消息，但是对于任意给定的文件未必就可以找到碰撞的文件。所以暂时还没有对文件行之有效的攻击手段。

综上所述，王教授的算法对于实际应用中破解MD5算法并无太大的帮助。不过他们四人的研究成果，是若干年来密码学获得的重大突破，通过他们的研究，使密码研究者认识到对于MD5这样的算法，自身存在很大缺陷，未来的密码设计人员，要避开这些缺陷，设计出更强大，更安全，更保密的算法。

四．对其他散列函数的影响

王教授的论文还对除MD5外的三种算法MD4、HAVAL-128 和 RIPEMD进行了破解。同时她还提出其他一些散列函数也并不具有理想的安全性。例如，SHA-0 [6] 的碰撞就可以通过大约 240 次 SHA-0 计算找到，以及 HAVAL-160 的一个概率为 1/232 的碰撞也是可以被找到的。对此Francois Grieu说：“王小云、冯登国、来学嘉和于红波的最新成果表明他们已经成功破译了MD4、MD5、HAVAL-128、RIPEMD-128。并且有望以更低的复杂度完成对SHA-0的攻击。一些初步的问题已经解决。他们赢得了非常热烈的掌声。”而美国国家技术与标准局（NIST）于2004年8月24 日发表专门评论，评论的主要内容为：“在最近的国际密码学会议（Crypto 2004）上，研究人员宣布他们发现了破解数种HASH算法的 *** ，其中包括MD4，MD5，HAVAL-128，RIPEMD还有 SHA-0。分析表明，于1994年替代SHA-0成为联邦信息处理标准的SHA-1的减弱条件的变种算法能够被破解；但完整的SHA-1并没有被破解，也没有找到SHA-1的碰撞。研究结果说明SHA-1的安全性暂时没有问题，但随着技术的发展，技术与标准局计划在2010年之前逐步淘汰SHA-1，换用其他更长更安全的算法（如SHA-224、SHA-256、SHA-384和SHA-512）来替代。”

生日攻击算法相关软件,生日攻击针对什么算法

能表示算法的软件有哪些

你好！现能申请专利的软件只有两种情况： 1.您的软件可以解决问题生产工艺上的某些技术问题，可以申请发明专利。 2.您的软件有硬件作为载体，即可做发明也可做实用。但如果是纯算法，专利法的定义是智力活动，专利是不保护的！可以考虑申请软件著作权！谢谢！

智能算法通过什么软件实现

只需要MATLAB就可以了，算法的研究通常是需要在测试模型上进行有效性验证的，公认的一些测试模型用MATLAB比较容易实现，而且算法研究涉及到大量的矩阵运算，因此如果做算法研究的话，MATLAB肯定是你主要的使用工具

基本算法编程软件

当然可以用记事本。任何程序都可以用记事本写生日攻击算法相关软件，但是还是要用专门生日攻击算法相关软件的compiler或者interpreter去跑程序。

简单生日攻击算法相关软件的数学实验建议用matlab。

讲讲md5加密

一、MD5是何方神圣？

所谓MD5，即"Message-Digest Algorithm 5（信息-摘要算法）"，它由MD2、MD3、MD4发展而来的一种单向函数算法（也就是HASH算法），它是国际著名的公钥加密算法标准RSA的之一设计者R.Rivest于上个世纪90年代初开发出来的。MD5的更大作用在于，将不同格式的大容量文件信息在用数字签名软件来签署私人密钥前"压缩"成一种保密的格式，关键之处在于——这种"压缩"是不可逆的。

为了让读者朋友对MD5的应用有个直观的认识，笔者以一个比方和一个实例来简要描述一下其工作过程：

大家都知道，地球上任何人都有自己独一无二的指纹，这常常成为公安机关鉴别罪犯身份最值得信赖的 *** ；与之类似，MD5就可以为任何文件（不管其大小、格式、数量）产生一个同样独一无二的"数字指纹"，如果任何人对文件做了任何改动，其MD5值也就是对应的"数字指纹"都会发生变化。

我们常常在某些软件下载站点的某软件信息中看到其MD5值，它的作用就在于我们可以在下载该软件后，对下载回来的文件用专门的软件（如Windows MD5 Check等）做一次MD5校验，以确保我们获得的文件与该站点提供的文件为同一文件。利用MD5算法来进行文件校验的方案被大量应用到软件下载站、论坛数据库、系统文件安全等方面。

笔者上面提到的例子只是MD5的一个基本应用，实际上MD5还被用于加密解密技术上，如Unix、各类BSD系统登录密码（在MD5诞生前采用的是DES加密算法，后因MD5安全性更高，DES被淘汰）、通信信息加密（如大家熟悉的即时通信软件MyIM）、数字签名等诸多方面。

二、MD5的消亡之路

实际上，从MD5诞生之日起，来自美国名为Van Oorschot和Wiener的两位密码学专家就发现了一个暴力搜寻冲突的函数，并预算出"使用一个专门用来搜索MD5冲突的机器可以平均每24天就找到一个冲突"。不过由于该方案仅仅从理论上证明了MD5的不安全性，且实现的代价及其夸张（当时要制造这种专门的计算机，成本需要100万美元），于是MD5自其诞生十多年来一直未有新版本或者被其它算法彻底取代。

在接下来的日子里，有关MD5的破译又诞生了"野蛮攻击"，也就是用"穷举法"从所有可能产生的结果中找到被MD5加密的原始明文，不过由于MD5采用128位加密 *** ，即使一台机器每秒尝试10亿条明文，那么要破译出原始明文大概需要10的22次方年，而一款名为"MD5爆破工具"的软件，每秒进行的运算仅仅为2万次！

经过无数MD5算法研究专家的努力，先后又诞生了"生日攻击"、"微分攻击"等多种破译 *** （相关信息大家可以参考研究成果，大大推进了md5算法消亡的进程。尽管在研究报告中并没有提及具体的实现 *** ，我们可以认为，md5被彻底攻破已经扫除了技术上的障碍，剩下的仅仅是时间和精力上的问题。/" target=_blank）。此次山东大学几位教授的最新研究成果，大大推进了MD5算法消亡的进程。尽管在研究报告中并没有提及具体的实现 *** ，我们可以认为，MD5被彻底攻破已经扫除了技术上的障碍，剩下的仅仅是时间和精力上的问题。