Re: How thorough are the hash breaks, anyway?
certificates. The public key data is public, and it's a random bitpattern where nobody would ever notice a few different bits. If someone finds a collision for microsoft's windows update cert (or a number of other possibilities), and the fan is well and truly buried in it. Correct me if I'm wrong ... but once finding a hash collision on a public key, you'd also need to find a matching private key, right? But the odds are that you'd get an easy-to-factor modulus. Would the casual relying party ever notice that? I think not. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: How thorough are the hash breaks, anyway?
My understanding is that once you've used trial division to get rid of all the extremely short divisors, a random number of length n is about as hard to factor as an RSA modulus of the same length. I don't think there are a lot of easy-to-factor moduli around. William -Original Message- From: Matt Crawford [mailto:[EMAIL PROTECTED] Sent: Monday, August 30, 2004 11:47 AM To: Ian Grigg Cc: Daniel Carosone; crypto Subject: Re: How thorough are the hash breaks, anyway? certificates. The public key data is public, and it's a random bitpattern where nobody would ever notice a few different bits. If someone finds a collision for microsoft's windows update cert (or a number of other possibilities), and the fan is well and truly buried in it. Correct me if I'm wrong ... but once finding a hash collision on a public key, you'd also need to find a matching private key, right? But the odds are that you'd get an easy-to-factor modulus. Would the casual relying party ever notice that? I think not. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: How thorough are the hash breaks, anyway?
To be more precise: Your odds of getting a modulus that you can divide by something are very high. Your odds of getting a modulus that you can factor efficiently are very low. William -Original Message- From: Matt Crawford [mailto:[EMAIL PROTECTED] Sent: Monday, August 30, 2004 11:47 AM To: Ian Grigg Cc: Daniel Carosone; crypto Subject: Re: How thorough are the hash breaks, anyway? certificates. The public key data is public, and it's a random bitpattern where nobody would ever notice a few different bits. If someone finds a collision for microsoft's windows update cert (or a number of other possibilities), and the fan is well and truly buried in it. Correct me if I'm wrong ... but once finding a hash collision on a public key, you'd also need to find a matching private key, right? But the odds are that you'd get an easy-to-factor modulus. Would the casual relying party ever notice that? I think not. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: How thorough are the hash breaks, anyway?
Dan Carosone wrote: There is one application of hashes, however, that fits these limitations very closely and has me particularly worried: certificates. The public key data is public, and it's a random bitpattern where nobody would ever notice a few different bits. If someone finds a collision for microsoft's windows update cert (or a number of other possibilities), and the fan is well and truly buried in it. A more likely attack along these lines would be to create two certificates which collided and had identical keys but different identification information or other attributes. If you could create a situation where a cert on microsoft.com collided with one on jf8l23fzq.com, you could easily get the second one certified, and the signature on it would also validate when you substituted microsoft.com. Presto, you could successfully masquerade as Microsoft. This is a collision attack rather than a second preimage attack as you propose and so should be far easier to mount. The attack requires being able to predict the exact form of the cert, including validity dates and serial number. The latter is chosen by the CA and depending on its policies, may be easy or hard to predict. The name serial number suggests a degree of sequentiality and some CAs may follow such a policy, which could allow a motivated attacker to predict the value with considerable accuracy. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
finding key pairs with colliding fingerprints (Re: How thorough are the hash breaks, anyway?)
You would have to either: - search for candidate collisions amongst public keys you know the private key for (bit more expensive) - factorize the public key after you found a collision the 2nd one isn't as hard as it sounds because the public key would be essentially random and have non-negligible chance of finding trivial factors. (Not a secure backdoor, but still create a pretty good mess in DoS terms if such a key pair were published). The latter approach is what I used to create a sample dead-fingerprint attack on a PGP 2.x fingerprints. http://cypherpunks.venona.com/date/1997/06/msg00523.html (No need to find hash collision even tho' md5 because it has another bug: the serialization has multiple candidate inputs). So I just searched through the candidate inputs for one I can factor in a few minutes. Adam On Fri, Aug 27, 2004 at 12:22:26AM +0100, Ian Grigg wrote: Correct me if I'm wrong ... but once finding a hash collision on a public key, you'd also need to find a matching private key, right? If someone finds a collision for microsoft's windows update cert (or a number of other possibilities), and the fan is well and truly buried in it. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: How thorough are the hash breaks, anyway?
At 16:09 26/08/2004, Trei, Peter wrote: [snip] Looking over the recent work on hash collisions, one thing that struck me was that they all seem to be attacks on known plaintext - the 'plaintexts' which collided were very close to each other, varying in only a few bits. While any weakness is a concern, and I'm not going to use any of the compromised algorithms in new systems, this type of break seems to be of limited utility. It allows you (if you're fortunate) to modify a signed message and have the signature still check out. However, if you don't know the original plaintext it does not seem to allow you construct a second message with the same hash. [snip] From a lawyer's perspective, it seems worrying that a message into which the word not has been inserted might still have the same hash as the original (assuming the hash to be a component of an electronic signature) Regards Nicholas Bohm Salkyns, Great Canfield, Takeley, Bishops Stortford CM22 6SX, UK Phone 01279 871272(+44 1279 871272) Fax 020 7788 2198 (+44 20 7788 2198) Mobile 07715 419728(+44 7715 419728) PGP RSA 1024 bit public key ID: 0x08340015. Fingerprint: 9E 15 FB 2A 54 96 24 37 98 A2 E0 D1 34 13 48 07 PGP DSS/DH 1024/3072 public key ID: 0x899DD7FF. Fingerprint: 5248 1320 B42E 84FC 1E8B A9E6 0912 AE66 899D D7FF - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: How thorough are the hash breaks, anyway?
On Thu, 26 Aug 2004, Trei, Peter wrote: While any weakness is a concern, and I'm not going to use any of the compromised algorithms in new systems, this type of break seems to be of limited utility. It allows you (if you're fortunate) to modify a signed message and have the signature still check out. However, if you don't know the original plaintext it does not seem to allow you construct a second message with the same hash. The Wikipedia article on hashes is pretty good on this topic: http://en.wikipedia.org/wiki/Cryptographic_hash_function So far, we know that the affected hashes are not collision resistant. They may still be at least somewhat one way and second preimage resistant, in which case systems which only require those properties might still be safe. But any system which specifies a secure hash in the general sense would have to come under very close scrutiny to see if it makes any assumptions at all about collision resistance. -J - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
