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
http://en.wikipedia.org/wiki/Cryptographic_hash_function. 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
[email protected]
http://lists.gnu.org/mailman/listinfo/gnumed-devel
_______________________________________________
Gnumed-devel mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/gnumed-devel
_______________________________________________
Gnumed-devel mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/gnumed-devel
