On 06/04/2019 03.01, Lijun Liao via dev-security-policy wrote: > 5. Related to how the MD5 attacks you might be right. But theoretically, > and also in practice, if you have enough bits to play and the hash > algorithm is not cryptographically secure, you can find a collision with > less complexity than the claimed one.
No, not in practice. There are different levels of "not cryptographically secure". What you are talking about is preimage resistance - the ability to construct an input to the hash algorithm that produces a given, fixed, arbitrary output. There are no such practical attacks on MD5 or SHA-1. What the serial number entropy requirement seeks to mitigate are collision attacks, in particular chosen-prefix collision attacks. This is the attack that was used to break MD5. This means that you can construct two messages with the same hash, by modifying both, given a chosen (known, not modifiable) prefix for each message. Due to the Merkle-Damgård construction of MD5 and SHA-1, these collisions are also inherently arbitrary-suffix (after you get two partial messages to collide, you can append the same arbitrary data to both and they will still collide). The serial number entropy requirement effectively mitigates collision attacks, because the serial number is one of the first pieces of information in the certificate, well before any attacker-controlled data. In order to implement a chosen-prefix collision attack, you need to predict the serial number. If the serial number has at least 64 bits of entropy, then you would have to try to obtain around 2^63 colliding certificates on average to match a precomputed collision. Note that the birthday paradox does not apply here, because any given certificate can only be obtained for any given collision attempt; it doesn't matter if you compute 2^32 collisions and then try to get 2^32 certificates, because *each one* of those certificates has to be obtained for a *single* collision attempt embedded into it. Note that the practical SHA-1 attack that was demonstrated was even weaker than this, as it wasn't a chosen-prefix attack (each message has a different prefix), but rather an identical-prefix attack (each message has the *same* prefix, and the messages only differ in the collision-generating blocks). This is less powerful, but still sufficient for practical attacks, e.g. I bet you could combine it with the x.509 structure to yield useful conditional parsing, much like the demonstrated SHA-1 collision combined it with the JPEG structure to yield conditional parsing. The serial number entropy requirement also mitigates this weaker attack, of course. -- Hector Martin "marcan" (mar...@marcan.st) Public Key: https://mrcn.st/pub _______________________________________________ dev-security-policy mailing list dev-security-policy@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-security-policy
