3

Why is it big news to find a hash collision like https://news.ycombinator.com/item?id=13713480? I'm not asking about the implications.

It seems like all you'd have to do to find a collision would be to calculate the hash of 0000000000000000000000000000000000000000, 0000000000000000000000000000000000000001, etc all the way up to ffffffffffffffffffffffffffffffffffffffff, and then any hash you calculate after that would have to have a collision one of the previously calculated ones because there are only 16^40 possible sha-1s.

  • 16
    "All you'd have to..." --- hehehe that's a good one. Hehehehe – RoboKaren Jul 1 '17 at 3:36
8

You're missing a lot.

  1. The space of things to generate hashes for is infinite, what you listed is the space of hashed values. They are two very different things.
  2. Even generating the list of hashes for the space you noted in your post would be extremely time consuming. "All you'd have to do ..." doesn't come close to doing it justice. It's sort of like saying "If you want to find a missing person, just go around the world until you find them."

In any case, getting back to your main question: Why are hash collisions a big deal? Because many crypto related things depend on there not being collisions, at least not that can be readily found. For example, digital signatures hash a document and then encrypt the hash. If you can generate hash collisions you can make it appear that someone digitally signed a document that they did not in fact sign. That's bad, very bad.

The irony is that hash collisions are inevitable, as a hash maps an infinite space to a finite space. In fact, there must be an infinite number of collisions. But being able to generate collisions is scary from a crypto perspective.

  • 4
    Checking every person on Earth is only about 2^33, tiny in comparison to the range of SHA-1. Checking every atom is just about right. – dave_thompson_085 Jul 1 '17 at 6:55
  • Im not sure I understand this. Say you digitally signed a document. But 3000 other conceivable documents of reasonable length have the same hash. 2999 of those documents are going to be chaotic nonsense and none of them are going to say "I give all my money to mr scammer" – Richard Tingle Apr 9 '18 at 21:29
  • In other words, a single collision is not a worry at all, but being able to generate them on command is? – Pro Q Feb 24 at 3:19
2

There are two questions here - why does it matter and why is/isn't it easy anyway. Of course they're linked answers.

A hash is a long number produced by "hashing" some data. The original data could be the contents of your password, a jpeg file with a photo, a book, a security key, anything at all that can be represented as digital data. What makes a hash interesting is its properties:

  • Hashes are designed to be easy to work out but extremely difficult to work out "backwards". So hashing the file IMG_2017070.JPG that I took on holiday might take millionths of a second. But working out from that hash, what the JPG file was, that was used to get the hash (the original data), will probably take decades, centuries or "a few billion times longer than the universe has existed", depending on the hash used and the resources and technology available, unless researchers work out a way to "break" the hash using mathematics to make the problem a few billion billion times easier. But that's not easy.
  • Hashes are designed to be extremely random, and change a lot even if the data only changes a tiny amount, so they can't be easily reversed by guesswork and two similar hashes don't mean the data was similar. If I change just one part of a single pixel in the photo, the hash will be utterly different and you're back to square 1 in working out the data.
  • Hashes are big numbers, so its incredibly unlikely to accidentally have (or work out) 2 different pieces of data which have identical hashes. This means if the hashes agree, we can usually assume the data hashed was the same, without any checking of the data itself.
  • Mathematicians can prove the first two statements, so it isn't a matter of "crossing fingers and hoping it's so". (The third statement follows from the first two so it doesn't need proving as such)

Hashes are very useful because they (virtually) guarantee that the original data can be confirmed correct, and uniquely identified, without needing to have the original data. Examples:

  • If I store your password to check your identity when you login on a website, someone could steal it from me and fake being you. If I store a hash of your password,I can check its you (the hash of the password you give matches, and I don't keep the password once checked) but nobody who steals the hash can work out the password to give me, to fake being you. This is incredibly important in encryption and security.
  • I can produce a file and prove something about it (that I'm the author, or that I was responsible for it) by using hashes, because it would be hard to virtually impossible for someone else to work back from hashes made public, to the data only I know was used to create those hashes. This is the basis for "digital (electronic) signatures", and why they are usually seen as good evidence of who signed.
  • If I have in future a 100,000 gigabyte hard disk in England and another in America, I can check their contents match by working out the hashes on each of hem where they are, and seeing if they are the same, instead of sending all 100,000 gigabytes from one place to the other to directly compare. Or if I want to check that data I sent to someone was correctly received, or data stored hasn't been changed since I stored it, we can compare hashes rather than sending the data again to check its the same in full. This is incredibly important in backing up and verifying data, sending and receiving data, and for certainty of evidence and data storage.

The reason a collision matters is that a "collision" shows someone has found a mathematical technique that does what should be almost impossible by any "brute force" method - they have worked back from a hash to the original data that led to it, or can find data that gives a specific hash.

More exactly, they can give us 2 different pieces of data (say two PDF files as happened not long ago) with the same hash. (Which is why its called a collision').

That proves the hash method used cannot be relied on any more to identify different data and keep data and hash isolated, and its time to move to a more advanced hash instead.

As hashes are extremely hard to engineer mathematically, and so relied on, its a big deal when researchers prove that they can get round one of the well known currently used hash methods (or "hash functions"). It happens about every 5-15 years. Usually we can tell some years in advance if a hash is looking like it might go down, and technology tries to move on before that time.

Usually, even though we move on from one hash function, its still reasonably secure for a while, because technology moves on at the first serious sign it's vulnerable, rather than waiting another 5 or 15 years until its so broken that "anyone" can do it. The recent breaking of SHA1 was slightly unusual because it was broken in a way that could be taken up almost immediately by almost "anyone", which is about as fatal as it gets for a hash function in general use. But it was known vulnerable for quite a few years before that, so peoples devices were already migrating to newer hashes, and the actual breaking of SHA1 just added urgency to that trend for many cases (and severe headaches for a few others!)

  • You will never find the original input if it is as large as a photo as the number of possible inputs that map to the same hash will be vast. You may be able to find some other input that has the hash of the photo, but not the photo itself. Think about it... otherwise people could create an intentionally broken hash function and use it to compress an unlimited amount of data. Also, I envy whatever computer you have that can generate the hash of an image in millionths of a second! – forest Mar 24 '18 at 6:41
  • Time it. You'll find that on a modern processor, hashing an image file can indeed be of the order of microseconds. – Stilez Mar 24 '18 at 10:51
  • For a 2.6 GHz processor, one microsecond is 2,600 cycles. A very modest 100 KB image file would thus need to be processed at 0.026 cycles per byte to fit into one microsecond. – forest Mar 24 '18 at 19:23
  • There's a difference between what I wrote ("might take millionths of a second") and what you wrote ("one microsecond"). Even < 1 ms would be fair to describe that way. And of course, modern processors don't hash at one byte at a time, and it depends on your choice of algorithm. That's why you're having difficulty here. Time it. – Stilez Mar 25 '18 at 5:57

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.