Talk:Birthday attack

Copied from User talk:Matt Crypto:

Birthday attack recommendation

Hi, re Birthday attack, you removed the recommendation of changing a foreign-supplied text befor signing, saying that using a longer hash is better. While using a long hash is certainly good, it seems to me that changing the text can only help: it squares the time your adversary needs, especially since you never know whether the hashes are long enough for the adversary's hardware, or whether the adversary has discovered a weakness in the hash function. Do you know any downsides to changing the text before signing? Thanks, AxelBoldt 11:44, 18 Aug 2004 (UTC)

The text I removed was, "to avoid this birthday attack, it is recommended that Alice slightly modify any digital contract that's presented to her, before signing it.". The downside is that Alice has to modify any digital contract presented to her; the user should be able to treat the crypto primitives as "black boxes", to the greatest possible extent — this is a point brought out in, say, Ferguson and Schneier's Practical Cryptography. The birthday attack is defeated at the minor cost of an extra, say, 80 bits in the hash length; the user shouldn't have to worry about modifying her actions at a higher level of abstraction. — Matt 21:07, 18 Aug 2004 (UTC)

Matt is right. It would be possible to imagine a signing system in which a document is randomly "salted" before hashing, which would provide similar security, but I don't know of any analysis of the security of such signing. As seems to be the case inevitably with hash functions, it's easy to prove the security of such a measure in the random oracle model, but very hard to state the properties a hash function would have to have to make such a measure secure. Universal one-way hash functions are a distinct but related idea. ciphergoth 10:32, 2004 Dec 8 (UTC)

I just wanted to check in regarding "It has also been recommended that Alice slightly change any contract presented to her before signing" — has this practice actually been recommended to any degree? — Matt Crypto 09:02, 24 Feb 2005 (UTC)

Sorry for the late reply. It's on page 430 of Schneier's Applied Cryptography, 2nd ed.. After describing the birthday attack, he writes: "This is a big problem. (One Moral is to always make a cosmetic change to any document you sign.)". I know that I initially read the recommendation somewhere else, but now I don't remember where, and that source probably got it from Schneier anyway. Cheers, AxelBoldt 05:38, 5 Mar 2005 (UTC)

bob's a she?

"It has also been recommended that Bob cosmetically modify any contract presented to her before signing." now, i guess this is related to the other discussion, since it seems this sentence used to be about alice. but now it's about bob, who is apparently having a gender crisis. is this common among cryptographers? is mallory involved? pauli 11:53, 12 Apr 2005 (UTC)