Hacker News Reader

Comment by mongol | Hacker News Reader

What does chosen-prefix mean?

Chosen prefix means somebody doing this attack gets to pick the start of both the colliding documents. For example maybe I want two children's stories, one which starts "Donald was an innocent young boy," and the other begins "Steve was a corrupt old gangster,"

The attack will calculate suffixes for these two documents such that both documents have the same hash result.

This means the attacker can then show some people a document about Donald, and others the one about Steve and if they rely on the same hash to validate that they're the same document they'd be fooled.

Digital certificates are the most prominent way computers deliberately depend on this assumption which a collision attack makes untrustworthy.

Honest question: has this any relevance outside of academia?

Sure.

Consider the Web PKI ("SSL Certificates"). Suppose you have a web site pmf.example it is of course pretty easy to get yourself a certificate to make https://pmf.example/ work, today for free but even many years ago it was pretty affordable from several commercial vendors.

The way those certificates work is they use a digital signature based on a hash algorithm, the CA uses its private key to sign the hash, and that's how computers can immediately tell a real certificate from a bogus one and be sure this is really news.ycombinator.com and not say, your ISP's advertising front end injecting a "special offer". The CA will refuse to give you a certificate for google.com or news.ycombinator.com because those aren't yours.

But using a chosen prefix attack you can create two documents with the same hash. One of them might be a fairly ordinary looking certificate for pmf.example that you're entitled to, the other says you're google.com

You get a CA to sign the first certificate, then you simply snip off their signature and attach it to the second one, since their hashes are the same the signature matches. You now have a valid certificate for google.com. Not theory, practice, this was really done with an earlier broken hash, MD5.

e.g. https://hackaday.com/2008/12/30/25c3-hackers-completely-brea...

A similar trick, probably done by or on behalf of the US and/or Israeli governments makes Flame work by colliding MD5 for code signing. That uses a collision nobody publicly knew about, which is a weird and expensive thing to do but of course governments have lots of money.

https://en.wikipedia.org/wiki/Flame_(malware)

Very enlightening. Thank you for explaining this. Are there any resources you might recommend to someone looking to learn this stuff more in depth?

Ange Albertini's work on collisions is pretty great and he makes lots of example images and illustrations.

https://corkami.github.io/

In particular he works on/with the PoC||GTFO team and is responsible for the MD5 collision cover art in a past issue:

https://github.com/angea/pocorgtfo

For SHA-1 (and others) you might find more at his github project:

https://github.com/corkami/collisions

hth,

adric

It means that you can influence the result by controlling the first part of the input. In other words, you can find an x such that H(x) == H(y) (for x != y) if you get to control the beginning bytes of x and know (or control) the beginning bytes of y.

Nope. That's a second pre-image attack.

Reply on news.ycombinator.com