" Today, 10 years after of SHA-1 was first introduced, we are announcing the first practical technique for generating a collision." Huh? It's been around a lot longer than 10 years.
[deleted]
Announcing the first SHA-1 collision
461–470 of 524 posts
Re: Announcing the first SHA-1 collision
#462The visual description of the colliding files, at http://shattered.io/static/pdf_format.png , is not very helpful in understanding how they produced the PDFs, so I took apart the PDFs and worked it out. Basically, each PDF contains a single large (421,385-byte) JPG image, followed by a few PDF commands to display the JPG. The collision lives entirely in the JPG data - the PDF format is merely incidental here. Extract…
So if one were hashing data or a document format that also contained a bit of self-referential integrity data, e.g. the end of the data has a CRC of the rest of the block, or maybe a cryptographic signature using some other hash, wouldn't that further constrain the search space? Then not only would one need to back out the random bits needed to complete the SHA-1 collision, it would also have to satisfy a some other constraint within the other data in the block.
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.
Re: Announcing the first SHA-1 collision
#463Earlier quoted context omitted.
This says more about the Bitcoin network than it does about the ease with which one can create a SHA-1 collision. From the article: Nine quintillion (9,223,372,036,854,775,808) SHA1 computations in total. 6,500 years of CPU computation for 1st phase of attack. 110 years of GPU computation for 2nd phase of attack.
It certainly raises an interesting question. The go-to response when anybody discusses brute forcing bitcoin is that the sheer number of possibilities makes finding a collision infinitesimally small. And that's true. Same for .onion certificates. But Google certainly haven't been attacking this for the last 6,500 years. With a sufficiently obscene amount of resources, it IS feasible to create an index of every possib…
Check my math.
42U, 4 sockets, 8 cores = 1344 CPUs per rack. two PCIe slots per U = 84 GPUs per rack That's not even that exotic of hardware. fifteen racks = 20160 CPUs and 1260 GPUsyum info So five months or so assuming the GPUs can't be fed until the CPUs complete processing, give or take, in 15 racks of decently higher-end off-the-shelf stuff.
Re: Announcing the first SHA-1 collision
#464As I consumer how do I identify sites which are vulnerable? What should I do to protect my data?
Recent versions of Chrome will show a warning if you try to browse to a site that uses a SHA-1 certificate. Mozilla is doing the same thing as of Firefox 51, but they're enabling this gradually to measure impact. Microsoft has an update ready to disable SHA-1 support in their browsers - I think it was delayed a few days ago due to some issues (not sure if they were related to disabling SHA-1). You can use [1] to test…
> https://sha1-2017.badssl.com/
This certificate has expired, so it's not that useful for testing.
Re: Announcing the first SHA-1 collision
#465The visual description of the colliding files, at http://shattered.io/static/pdf_format.png , is not very helpful in understanding how they produced the PDFs, so I took apart the PDFs and worked it out. Basically, each PDF contains a single large (421,385-byte) JPG image, followed by a few PDF commands to display the JPG. The collision lives entirely in the JPG data - the PDF format is merely incidental here. Extract…
So if one were hashing data or a document format that also contained a bit of self-referential integrity data, e.g. the end of the data has a CRC of the rest of the block, or maybe a cryptographic signature using some other hash, wouldn't that further constrain the search space? Then not only would one need to back out the random bits needed to complete the SHA-1 collision, it would also have to satisfy a some other…
> 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 as much data as the originals or the combined functions have restricted inputs. The point of hashes is making collisions hard, not mathematically impossible - the latter is, I believe, itself impossible.
Like I said, I'm totally unqualified to speak on this, so I may well be missing something here.
Re: Announcing the first SHA-1 collision
#466The visual description of the colliding files, at http://shattered.io/static/pdf_format.png , is not very helpful in understanding how they produced the PDFs, so I took apart the PDFs and worked it out. Basically, each PDF contains a single large (421,385-byte) JPG image, followed by a few PDF commands to display the JPG. The collision lives entirely in the JPG data - the PDF format is merely incidental here. Extract…
So if one were hashing data or a document format that also contained a bit of self-referential integrity data, e.g. the end of the data has a CRC of the rest of the block, or maybe a cryptographic signature using some other hash, wouldn't that further constrain the search space? Then not only would one need to back out the random bits needed to complete the SHA-1 collision, it would also have to satisfy a some other…
It's a good thought, but if the functions have bounded-length outputs (as with all major hash functions), then your combined hash value is still a bounded length. A collision must therefore exist because there are many more potential messages than potential hash values.
If your functions produce unbounded-length hashes, then you may as well just be compressing your input to guarantee there are no collisions in your "hash".
Re: Announcing the first SHA-1 collision
#467Earlier quoted context omitted.
> What is currently still not feasible is to create a custom git repository whose HEAD matches that of the Linux kernel. Hang on, that doesn't matter though, does it? I was under the impression that git's SHAs were to be treated as repo-wise unique; not universally. There must non-adversarial 'collisions' across repositories already, surely? I thought this attack potentially allows creating two commits in the same re…
I don't think there's ever been an example of two different pieces of content hashing to the same SHA-1 before. An infinite number of such examples obviously must exist but they're incredibly improbably to encounter by accident.
Yep, sorry, it was far too early in the day for me to appreciate the magnitude of 2^{160}.
If I could downvote myself...
Re: Announcing the first SHA-1 collision
#468Is Mercurial impacted?
Yes, as it uses a similar hashing scheme as git. https://www.mercurial-scm.org/wiki/FAQ#FAQ.2FTechnicalDetail... That said the file format was switched pretty early on (2006 I think, less than a year after initial release) to reserve space for 32 bytes instead of 20 for the hash, thus allowing hash migration more easily (sha1 is 20 bytes, sha2 which at the time was the obvious replacement was 32 bytes). https://www.m…
Except all exchanges between mercurial client and server happen with changegroups and changegroups are still limited to 20 bytes for the hash.
Re: Announcing the first SHA-1 collision
#469The visual description of the colliding files, at http://shattered.io/static/pdf_format.png , is not very helpful in understanding how they produced the PDFs, so I took apart the PDFs and worked it out. Basically, each PDF contains a single large (421,385-byte) JPG image, followed by a few PDF commands to display the JPG. The collision lives entirely in the JPG data - the PDF format is merely incidental here. Extract…
Great analysis. So why did Google choose to use PDFs instead of JPGs directly?
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 format.
Open challenge: build two signed PDFs with identical signatures and different contents - it's not necessarily hard, and it would definitely drive the point home.
Re: Announcing the first SHA-1 collision
#470Earlier 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?
I use Hachoir for a lot of tasks - digital forensics (examining file tables on a filesystem, discovering slack space taken up by hidden data, etc.); for metadata extraction (for which the hachoir-metadata subproject is designed); for file carving (either with hachoir-subfile or manually); and just to geek out about file formats (did you know .doc/.ppt is secretly a FAT filesystem?).