Recently a paper has been released about SHA-1 chosen prefix collision.

They present what a chosen prefix collision is, but I don't understand how is it more interesting than a standard collision ? They briefly mention x509 rogue certificate, but I still can't get the point.

Can anyone explain to me how interesting it is compared to standard collisions ? Hopefully with an example a bit more detailed ?

Thanks in advance !


In a chosen-prefixes collision attack, the adversary is able to freely choose two distinct prefixes $P$ and $P'$ of arbitrary content, and is able to find suffixes $S$ and $S'$ with $H(P\mathbin\|S)=H(P'\mathbin\|S')$.
Note: It is common to write chosen-prefix when that logically should be chosen-prefixes.

In other types of collision attack the adversary freely chooses only one prefix $P$ (possibly empty) and is able to find distinct suffixes $S$ and $S'$ with $H(P\mathbin\|S)=H(P\mathbin\|S')$.

That makes a critical difference: only chosen-prefixes attacks allow the attacker to freely choose different meaningful content where the colliding messages differ.

Chosen-prefixes attack thus are much more flexible for the attacker. For example, in a pure text document, the prefixes could be the meaningful part of the text at start, with the suffix in the end after a few hundred space characters so that it never shows. That allows the attacker to prepare documents with vastly different contents of his choice (except for the end which does not show), and so that the signature of one will be valid for the other.

By contrast, in other types of collision attack, the attacker typically is unable to make similar forgeries for pure text files, and more generally data formats where insignificant data can only be at the end. Attacks can only target more flexible data formats (like Portable Document Format, Postscript, some compressed image formats, some executable file formats..) such that it is possible to turn the alteration in the suffix into an operationally meaningful difference. This is often hard or infeasible (depending heavily on details of the data format and attack context).

In particular, a chosen-prefixes attack is a near necessity to attack certificate issuance (but this is mostly theoretical: certification authorities could foil all such attacks by using an unpredictable Certificate Serial Number at start of the certificate; and powerful adversaries obtain practically working certificates under any identity they desire without any cryptographic attack, by using complacent certification authorities).

Addition: in practice a trailer can easily be added, so that $H(P\mathbin\|S\mathbin\|T)=H(P'\mathbin\|S'\mathbin\|T)$. The attacker is able to freely choose $P,P',T$, with the constraint $P=P'$ for non-chosen-prefixes collision attacks.

| improve this answer | |

When you find a collision, it will not help you in some meaningful way. Yes, you find a collision, forged a certificate, however, the document is not going to be meaningful. In short, you have little control over the hash collision.

The chosen-prefix collision the attackers look for a stronger collision where H(P, M) = H(P',M') the prefix can be arbitrary. The ad-hoc chosen-prefix collision attacks are harder than plain collision attacks.

From Chosen-prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities

The example presented in the next section, namely colliding X.509 certificates with different fields before the appended bitstrings that cause the collision. Those bitstrings are ‘perfectly’ hidden inside the RSA moduli, where ‘perfect’ means that inspection of either one of the RSA moduli does not give away anything about the way it is constructed (namely, crafted such that it collides with the other one).

| improve this answer | |
  • $\begingroup$ Can you expand on the practical implications of that? For example, does it mean that if someone got a seemingly legitimate SHA-1 SSL certificate signed by a certificate authority, they could then use that signature on a malicious SHA-1 certificate instead? $\endgroup$ – Harry Johnston Jan 10 at 0:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.