PlayStation 3 predicts next US president

[James A. Donald]

Francois Grieu wrote:
 >> That's because if Tn is known (including chosen) to
 >> "some person", then (due to the weakness in MD5 we
 >> are talking about), she can generate Dp and Dp' such
 >> that
 >>   S( MD5(Tn || Dp || Cp || Cn) ) = S( MD5(Tn || Dp'
 >>   || Cp || Cn) )
 >> whatever Cp, Cn and S() are.

William Allen Simpson wrote:
 > First of all, the weakness in MD5 (computational
 > feasibility over time) that "we are talking about" is
 > not (yet) a preimage or second preimage attack.
 > Please don't extrapolate your argument.

I don't think you know what a preimage or second
preimage attack is.

A preimage attack is a method of finding a document that
hashes to an arbitrary given hash.  A second preimage
attack is a method of finding a document that hashes to
the same hash as arbitrary given document. Your proposed
workaround protocol fails because the adversary can
construct multiple documents containing some arbitrary
text and some chosen text that hash to the same hash -
the fact that some of the arbitrary text comes from the
good guys is irrelevant.  The fact that the bad guys get
to choose some of the text in all of the documents makes
it fail.

 > Second of all, you need to read my messages more
 > carefully.  No good canonical format allows random
 > hidden fields or images.

There is no canonical format that suppresses human
ignorable data, other than plain ascii or suchlike which
is unlikely to be acceptable.  Any format capable of
displaying arbitrary well formatted documents is capable
of containing data that humans are likely to ignore.
What is ignorable is necessarily a human judgment.

A canonical format is in practice going to be PDF or
RTF, which does allow hidden fields and images.
Further, even a visible image can be made to work.
Further, it is quite subtle to decide what constitutes
"hidden" - for example a gently irregular low intensity
background on HTML pages is quite pleasing to the eye,
so surely our format should allow such backgrounds.

Further, what you propose is strengthening the protocol
to work around known weaknesses in MD5.  Whenever we
strengthen a protocol to get around known weaknesses in
an algorithm, we rarely do it right - consider the long
succession of debacles surrounding RC4.  SSH uses RC4
correctly, but consider all the protocols that used it
incorrectly, and then issued incompatible updates to fix
the flaws, updates that were even more flawed than the
protocol they supposedly fixed.

Further, if you want your protocol to work around the
known weaknesses of MD5, "canonicalizing" the document
is not the way to go.

Instead, allow arbitrary documents, but precede them by
salt which is randomly determined after the document is
submitted.

That will work a lot better than canonicalization, but
it is still a workaround for a known weakness.  Far
better to avoid the weakness.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com