Talk:Birthday attack
From Wikipedia, the free encyclopedia
 |
This article is part of WikiProject Cryptography, an attempt to build a comprehensive and detailed guide to cryptography in the Wikipedia. If you would like to participate, you can choose to edit the article attached to this page, or visit the project page, where you can join the project and see a list of open tasks. |
- Copied from User talk:Matt Crypto:
Contents |
[edit] 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)
-
- OK, I added that reference. --68.0.120.35 20:02, 9 March 2007 (UTC)
[edit] 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)
- It's my fault, I changed Bob and Alice around, because I thought it wouldn't be fair if Bob is always portrayed as trying to trick Alice. But I forgot to change one instance of her <-> him. Sorry Bob!
-
- What kind of editor are you?!?
[edit] modifying the contract is no solution
It doesn't matter whether it was Alice or Bob who last modified the contract - if this attack is possible, either could suspect the other of attempting to defraud her or him. So, Bob, altering the contract yourself is no solution, now Alice suspects you of trying to trick her into a fraudulent contract!
- I removed the sentence
However, this does not solve the problem, because now Alice suspects Bob of attempting to use a birthday attack.
- Yes, it is true that no matter which person "last" modifies the contract, the other could suspect that person of specially crafting it.
- But what about this alternative:
- Alice signs ( hash( fair contract with Alice's cosmetic modifications ) )
- Bob signs ( hash( fair contract with Bob's cosmetic modifications ) )
- Each person stores both versions of the contract (and the signatures).
- This makes it impossible for Alice to use a birthday attack to "prove" that Bob signed some other contract, and it makes it impossible for Bob to use a birthday attack to "prove" that Alice signed some other contract. (But plausible deniability is a different issue).
- Should we add more clarification that *each* person adds cosmetic modifications,
- and each person only signs the version that she modified?
- --68.0.120.35 20:02, 9 March 2007 (UTC)
-
- No. Any such proposal would be original research. Cosmetic modifications to documents is not used in practice, unless you count probabilistic signature schemes. The usual way to defeat birthday attacks is -- as already stated in the article -- to use large enough collision resistant hashes. 85.2.115.82 10:50, 10 March 2007 (UTC)
[edit] Hard to understand
While I understand the mathmatics behind the Birthday Paradox, I'm having trouble seeing its application to the Birthday Attack. I think I understand a bit of it, but the article isn't very clear.
- Agreed! I'm finding this all a bit confusing. The Birthday Paradox page is simple to understand however it seems that a clear example hasn't been applied to this topic.
- I added a derivation of the probability and added an example. Removed the 'confusing' tag.--Kbk 18:14, 2 May 2006 (UTC)
