[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Gnumed-devel] looking for Horst

From: Tim Churches
Subject: Re: [Gnumed-devel] looking for Horst
Date: Sat, 13 Aug 2005 17:30:43 +1000
User-agent: Mozilla Thunderbird 1.0.6-1.1.fc3 (X11/20050720)

Syan Tan wrote:

Could you explain what first pre-image and second pre-image attack is again ? It sounds like you're saying that because a hash functions are one-way functions, that there is no feasible way to get X efficiently if X is the message and you have Y, the hash , because there's no efficient inverse F. Also , the collision algorithms seem pretty trendy and incomprehensible.
Yes, that's correct. See The discussion on GPCG was about the ability to modify a digital photograph (of a car, taken by a radar speed camera) and still retain the same MD5 hash. An Australian court accepted the argument that because it was easy to find collisions in MD5, and since the MD5 hashes of the speed camera photos were used to assure their authenticity, then there is no way to be sure that the photos had not been tampered with. I argued that teh court was mistaken, because just because MD5 is vulnerable to collisionsattacks doesn't mean it is vulnerabile to second pre-image attacks (and no-one has demonstarted such vulnerability). Horst argued incorrectly that I was mistaken.

I looked up google, and the series of events seems to be: 1. Aug 2004, Chinese cryptographers brag that they have computed a collision for a message , using a super computer, and publish a 4 page result, without explaining how they did it. 2. Oct 2004, Australian researchers, miffed that they didn't get to publish their expertise, publish a 100 page paper outlining how they analysed the MD5 algorithm and found certain conditions how an algorithm could be found, but don't find the algorithm 3. March 2005, a czech researcher publishes his laptop algorithm for collision finding, and estimates that a laptop is about 25-100 times slower than a super computer, and that their algorithm is 10x faster than the chinese secret algorithm -Chinese researchers release their algorithm, after the czech researchers.
4. Daum and Lucks demonstrate two Postscript fields which hash to teh same MD5 value but which print two completely different documents. The technique is to use the Czech algorithm to find two "colliding" blocks of random bytes i.e. they both hash to teh same MD5 value. These are appended to a Postscript file which contains two different documents and some code which causes one or other of the documents to be rendered depending on which of the two MD5-colliding blocks of random bytes appears at the end of the file. Due to a block entension weakness in teh MD5 algorithm, if A and B are blocks of data which hash to the same MD5 value, then MD5(c + A) == MD5(c + B) where + means append.

Is it correct that the messages only differ at the end of the message, where a block of bytes that match a md5 processing boundary is appended, and that you were saying that the brute force search by inserting or changing random 'invisible' characters or bits in a maliciously modified original message is as hard a problem as reverse guessing a message from a hash ? How does this affect using a notary ?
It doesn't. I said "somewhat relevant", but I should have said "peripherally related".

Tim C

Apparently, the complaint was that MD5 is insecure, and the court disallowed a photograph's MD5 signature because MD5 was theoretically flawed, but also because the original MD5 signature did not take in all the bits of the photograph for signature generation, but just the timestamp and text attached to the photo, and that gnumed should always include the entirety of data for hashing. Also, there was an argument about how a postscript program was regarded as a document, and that it switched on the final collision matching block of bytes appended to the program, but it contained both the real message and the altered message anyway, and you argued that all documents should be inspectable as source, and then someone else argued that if it was easily provable a postscript document contained alternate messages by inspection, legally , the signature was non-binding anyway; someone else argued that if one could satisfy a court the intent of signing wasn't there or signing was done under duress or false pretences , then it was also non-binding. Rats, wished someone had told me that when I signed that ratfink real estate agent's document..

On Sat Aug 13 5:58 , Tim Churches sent:
Sebastian Hilbert wrote:
Hi all, Does anyone know if Horst is still reading this? I have tried to contact him regarding gnotary but he may be too busy to answer my mails. Any help is appreciated. Sebastian
He actively posts to the GPCG 9general practice computer group) mailing list - just yesterday I had a friendly online argument with him over collision versus pre-image attacks agianst the MD5 hash algorithm (which is somewhat relevant to gnotary, actually). Tim C

_______________________________________________ Gnumed-devel mailing list address@hidden

Gnumed-devel mailing list

reply via email to

[Prev in Thread] Current Thread [Next in Thread]