4 ms·

Didn't Dan Kaminsky and others have tools to produce nearly arbitray collisions by the early 2000s?

tialaramex 6y ago
Perhaps? I can't find any evidence easily that Dan did have such tool, but "by the early 2000s" it's not at all unthinkable certainly. If you have a link that'd be great. However the trouble is MD5 collision isn't like that hilarious "Send all zeroes" Microsoft bug from a few weeks back where you just try it a few times then it works because someone was very stupid - the MD5 collision is pretty hard, the Merkle–Damgård construction actually works, your attack avenue is hammering on the compression function, everything else in MD5 (and any other Merkle–Damgård construction) works because of mathematics unless you can break that compression function - so having a program that when you run it spits out an MD5 collision with your preferred shape is great, it's a cryptographic breakthrough - but maybe it'll take 5000 years to run on a typical home PC. If you're a government or a big crime boss then money turns that into 5 days or (if you've enough of it) 5 hours instead, but if you're a bored teenager or small time crook not so much. And like I said, Flame depends on a never before seen collision, so it isn't like they just re-used work somebody else had done.
- HexagonalKitten 6y ago
  Do you have any idea what time window they had to generate collisions in? The MS article on the collision says the attack required knowledge of, among other things, the predictable serial numbers. They could have had as little as the usual inter-cert issuance time, or in the worst-case scenario with entirely predictable numbers could have had months or more. Depending on the window the funds required would change dramatically.
  - bun_at_work 6y ago
    I agree that there is a wide range of costs for the attack, however for the sake of the discussion I would point out that the lower bound of that cost is likely to still be prohibitive for a teenager.
raxxorrax 6y ago
As far as I know you can reliably change a few bits and get a collision, not create arbitrary data with padded info whose hash collides with the original data.
birktj 6y ago
The HashClash tool [1] was written back in 2006 and can construct chosen-prefix md5 collisions. Don't know if it has anything to do with Dan Kaminsky though. [1]: https://www.win.tue.nl/hashclash/ https://www.win.tue.nl/hashclash/

Perhaps? I can't find any evidence easily that Dan did have such tool, but "by the early 2000s" it's not at all unthinkable certainly. If you have a link that'd be great. However the trouble is MD5 collision isn't like that hilarious "Send all zeroes" Microsoft bug from a few weeks back where you just try it a few times then it works because someone was very stupid - the MD5 collision is pretty hard, the Merkle–Damgård construction actually works, your attack avenue is hammering on the compression function, everything else in MD5 (and any other Merkle–Damgård construction) works because of mathematics unless you can break that compression function - so having a program that when you run it spits out an MD5 collision with your preferred shape is great, it's a cryptographic breakthrough - but maybe it'll take 5000 years to run on a typical home PC. If you're a government or a big crime boss then money turns that into 5 days or (if you've enough of it) 5 hours instead, but if you're a bored teenager or small time crook not so much. And like I said, Flame depends on a never before seen collision, so it isn't like they just re-used work somebody else had done.

HexagonalKitten 6y ago
Do you have any idea what time window they had to generate collisions in? The MS article on the collision says the attack required knowledge of, among other things, the predictable serial numbers. They could have had as little as the usual inter-cert issuance time, or in the worst-case scenario with entirely predictable numbers could have had months or more. Depending on the window the funds required would change dramatically.
- bun_at_work 6y ago
  I agree that there is a wide range of costs for the attack, however for the sake of the discussion I would point out that the lower bound of that cost is likely to still be prohibitive for a teenager.

raxxorrax 6y ago

As far as I know you can reliably change a few bits and get a collision, not create arbitrary data with padded info whose hash collides with the original data.

birktj 6y ago

The HashClash tool [1] was written back in 2006 and can construct chosen-prefix md5 collisions. Don't know if it has anything to do with Dan Kaminsky though. [1]: https://www.win.tue.nl/hashclash/ https://www.win.tue.nl/hashclash/