如何计算这样一类文件的md5

flw

原帖由 ppcl 于 2006-6-13 14:29 发表

其实这个不是想象中那么难，山东大学的某位教授已经破解了MD5，将寻找MD5冲突的时间缩短了若干个数量级，现在貌似已经能在40分钟的时间内找到MD5的一个冲突，所以伪造这个字符串已经是可能的了。

如果你学过数学的话，
你就会知道，
解方程

1. md5(data) = md5(x)  data 为常量  (1)

复制代码

和解方程

1. md5(data + foo(x)) = x                  (2)

复制代码

有多大区别。

为了能够让你更加容易理解我想要表达的意思，
我们不妨把上面的两个方程做个变换：
对于 (1) 式，它其实等价于下面这个式子：

1. md5(x) = str      str 为常量    (1')

复制代码

对于 (2) 式，它其实包含了下面这种情况：

1. md5(foo(x)) = x                     (2')

复制代码

你现在再比较一下 (1') 和 (2')，到底后者比前者复杂多少。

[ 本帖最后由 flw 于 2006-6-13 15:02 编辑 ]

ppcl

原帖由 flw 于 2006-6-13 14:56 发表

如果你学过数学的话，
你就会知道，
解方程
md5(data) = md5(x)  data 为常量
也即
md5(x) = str      str 为常量
和解方程
md5(data + foo(x)) = x
有多大区别。

我的数学水平不需要楼上来评价,不见得比楼上差.

不偏离问题了,先看楼主的原文:
-----------------
问题是我们现在需要在文件本身里写入这个文件的md5信息，而不是用外部文件来表达，举例来说，有一个文本文件，我们在最后告诉读者这个文件的md5为xxxxxxxxxxxx，而你通过md5sum计算这个文件的时候恰好是文件内容中的md5编码。
还有一例，比如制作了电影文件到后期处理，需要添加字幕显示当前电影文件的md5码以便观众确认这个版本的文件是正版，这个字幕本身包含了md5信息，只是表现方式是图形方式。
-----------------


首先假设已经存在一个寻找MD5冲突的算法: 即,给定初始的MD5 state,通过计算加入一些字节,最终可以得出需要的MD5值.
以第二个问题为例,只需要事先任意选定一个MD5 值,将其做入字幕之中,得到最终可播放的文件,计算当前文件的MD5,得出一个MD5 state, 然后以这个MD5 state为起始,执行上述的冲突寻找算法,在文件后面附加算法得出的填充内容.即得到楼主想要的结果.

当然,这个解法是理论上的,寻找MD5冲突的算法是否能够达到我说的程度也未可见,所以具体实现起来也不见得能成功,还是建议楼主使用其它的方法.

[ 本帖最后由 ppcl 于 2006-6-13 17:16 编辑 ]

JohnBull

LZ的思路不可行，换。

flw

在文件后面附加算法得出的填充内容
-------------
不知道附加之后能不能显示成字幕？

assiss

原帖由 ppcl 于 2006-6-13 14:29 发表

其实这个不是想象中那么难，山东大学的某位教授已经破解了MD5，将寻找MD5冲突的时间缩短了若干个数量级，现在貌似已经能在40分钟的时间内找到MD5的一个冲突，所以伪造这个字符串已经是可能的了。

即便用王教授的方法，楼主的问题可能仍然无法得到解决。
找到冲突！=按指定的前提字串找到冲突

gnap

大家是不是偏题了哦？我觉得LZ是否考虑把文件的格式分为header和body。只对body进行散列，结果放在header里面。这样不就行了？

gnap

晕哦！各位是不是把问题复杂化了？

其实不散列文件头不就行了。RPM包里面不是有分header、signature、archive的吗？。散列时候只散列header和archive,散列的值存储在signature里面。此在PGP的签名也在signature里面。

[ 本帖最后由 gnap 于 2006-6-15 15:20 编辑 ]

isjfk

lz 已经把楼上的方法否定了~

算啦，lz 自己研究去吧，我等还是等他研究出来再去膜拜好了