Announcing the first SHA-1 collision • Hacker News Board

Re: Announcing the first SHA-1 collision

#521

Post by davidron » Sat, Feb 25, 2017, 6:01 AM UTC

digikata wrote: post #512

benaiah wrote: post #465

Earlier quoted context omitted.

> The best thing would be if one could prove a mathmatically incompatible set of counter functions where data colliding in the hash of one function would prevent the other function from validating correctly. I'm a rank amateur, so this is completely outside of my wheelhouse, but this sounds suspect. I don't think you can make hash collision impossible, even with multiple functions, unless the combined hashes contain…

I'm an amateur in this area too, but I'm not suggesting to avoid collisions, I'm suggesting adding a validation function for the hashed data so that if one were to generate an intentional collision, you would still have to contend with generating it in a way that also validated. For Git, Linus basically says the validation function is a prepended type/length. https://news.ycombinator.com/item?id=13719368

The composition of the result of the original hash function and the result of that validation function can be taken together to be some larger function. Call that an uberhash. Such an uberhash is created by putting some number of bits in and getting some smaller number of bits out. There will unfortunately still be collisions. That trick is an improvement, and newer hashing algorithms contain similarly useful improvements to make creating collisions difficult.

Re: Announcing the first SHA-1 collision

#522

Post by drkstr » Sat, Feb 25, 2017, 9:57 PM UTC

spdustin wrote: post #437

nneonneo wrote: post #398

Earlier quoted context omitted.

I used Hachoir ( https://github.com/haypo/hachoir3 ), a Python library that I've contributed to. Hachoir disassembles files using a library of parsers, with the intent of describing the function of every single bit in the file. You can see the resulting disassemblies (rendered with the hachoir-wx GUI) here: http://imgur.com/a/F1cnV

Woah, that's a fascinating tool! What other sorts of things could Hachoir be used for?

Funny, I had no idea it could do all that. I've been using it in production for years to extract width/height/duration of media files at compile time so my loading placeholders are perfectly sized at runtime in a basic web app.

Re: Announcing the first SHA-1 collision

#523

Post by ritmatter » Sun, Feb 26, 2017, 4:46 AM UTC

spiznnx wrote: post #510

nneonneo wrote: post #469

Earlier quoted context omitted.

The notion of "document security" is a common desire in business and legal contexts. PDFs are a standard representation of documents, whereas JPGs are less common (TIFF might count since it's a somewhat common scanned document format, but I digress). Subverting the most popular document format, one which even provides built-in support for digital signatures is probably much more interesting than subverting the JPG fo…

I wonder if this is the 'standard' thing to do when you have a broken hash function. I took a introductory course in computer security a year ago and we had to create MD5 hash-colliding documents for homework[0]. [0] https://courses.engr.illinois.edu/cs461/sp2015/static/proj1.... (see part 4)

I'm interested in taking a look at this assignment for my own learning, but it looks like there are a bunch of files you need. It would be cool if you put them in a git repo!

Re: Announcing the first SHA-1 collision

#524

Post by mcdavex » Mon, Feb 27, 2017, 9:24 AM UTC

digikata wrote: post #512

benaiah wrote: post #465

Earlier quoted context omitted.

> The best thing would be if one could prove a mathmatically incompatible set of counter functions where data colliding in the hash of one function would prevent the other function from validating correctly. I'm a rank amateur, so this is completely outside of my wheelhouse, but this sounds suspect. I don't think you can make hash collision impossible, even with multiple functions, unless the combined hashes contain…

I'm an amateur in this area too, but I'm not suggesting to avoid collisions, I'm suggesting adding a validation function for the hashed data so that if one were to generate an intentional collision, you would still have to contend with generating it in a way that also validated. For Git, Linus basically says the validation function is a prepended type/length. https://news.ycombinator.com/item?id=13719368

Issue with that is we already addressed that during the MD5/cert collision era; the final cert, as delivered, would by definition contain additional data over the CSR (the signer reference and the start/end dates) but because that information was predictable, the collision could be generated for the expected emitted cert, rather than the input data. Same would apply to git; if you were building the submitted data block, you would know what type and length it was going to be, so could build it with that in mind while colliding.