Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

SHA-1 'fully and practically broken' by new collision (2020)

duo.com

Post reply on HN
Print view View original

101–110 of 210 posts

Re: SHA-1 'fully and practically broken' by new collision (2020)

#101

Post by contravariant »

ganzuul wrote: post #91
contravariant wrote: post #61

Earlier quoted context omitted.

Only if you count all natural looking data of which there is way more than you could possibly imagine. It is of course likely that humanity hasn't yet created more than 2^100 (~10^30) files, so in theory given a registry of all files in existence you might be able to identify it by its hash. However while this is simple it's definitely not easy.

I can imagine the output of program space. That's pretty big. All possible universes in fact. It's an issue of probability and bins. While natural data is infinite, there is vastly more unnatural data. At some point you have enough metadata (e.g. natural vs. random) to know that the original data came from Earth to pick out the right needle from the needle stack. Unless the data is from a completely alien source, we…

It's somewhat irrelevant how many unnatural data there is. The point is that there's way more plausible data (or sentences if we're restricting ourselves to natural language) than there are possible 160; 256 or 512 bit hashes.

Unless of course you enumerate all of human communication, but like I said that doesn't count as 'easy'.

Re: SHA-1 'fully and practically broken' by new collision (2020)

#102

Post by wongarsu »

lallysingh wrote: post #71
bjarneh wrote: post #9

> The technique that the researchers developed is quite complex and required two months of computations on 900 individual GPUs.

Or roughly 1.3M GPU hours. Less as GPUs get upgraded. Not sure how many AWS F1 (FPGA) hours it would take.

So somewhere between $300,000 (running consumer GPUs cheaply) and $30 million (paying AWS on-demand prices for Tesla V100).

Even the upper bound for that seems well worth it for well-funded attackers if the target is juicy enough.

Re: SHA-1 'fully and practically broken' by new collision (2020)

#103

Post by fwip »

ganzuul wrote: post #19
fwip wrote: post #14

Earlier quoted context omitted.

No, because reversing the hash has infinite possible answers (well, "very many" for bounded input size). You can't decompress 32 bytes into 1GB because you don't know which of the 1GB-sized answers is the intended one.

Natural data is easily identifiable.

Nope, not on these scales.

Say you have a 32 byte hash, that's 2^(328) possible values, right? Now say your input is 128 bytes, that means that (on average) each 32 byte hash maps to 2^(968) values.

"Natural looking" data will occur an astronomical number of times in a search space that large - which is, again, only 96 bytes larger than your hash.

Re: SHA-1 'fully and practically broken' by new collision (2020)

#104

Post by fwip »

ganzuul wrote: post #81
dTal wrote: post #24

Earlier quoted context omitted.

Not it's not. You can't distinguish the complete works of Shakespeare from the complete works of Shakespeare with the words changed a bit, or switching to Harry Potter for a bit in the middle, or a completely dazzling and original work of fiction. Any hash might generate all three of these, and essentially boundless other works. It's a library of Babel.

Your examples really fall out of the scope of the premise.

No, they're 100% correct.

Re: SHA-1 'fully and practically broken' by new collision (2020)

#106

Post by whoisburbansky »

lvh wrote: post #89
whoisburbansky wrote: post #88

Earlier quoted context omitted.

What do you mean by the `bis` and `cis` suffixes to your entry labels?

It's just a subdivision; it might as well have said 1a, 1b... -- but "bis" and "cis/tris" (and possibly tetrakis) tend to emphasize that they're addenda, not equal points.

Ah, gotcha. I thought I recognized the prefixes from Organic, but I don't think I've seen it used like this here. Neat!

Re: SHA-1 'fully and practically broken' by new collision (2020)

#107

Post by dTal »

ganzuul wrote: post #81
dTal wrote: post #24

Earlier quoted context omitted.

Not it's not. You can't distinguish the complete works of Shakespeare from the complete works of Shakespeare with the words changed a bit, or switching to Harry Potter for a bit in the middle, or a completely dazzling and original work of fiction. Any hash might generate all three of these, and essentially boundless other works. It's a library of Babel.

Your examples really fall out of the scope of the premise.

Forgive me if I've misunderstood - the premise was that, out of the infinite set of data that hashes to a particular hash/checksum, there is a unique data set that is "obviously" the real one? Or at least, that the set is meaningfully bounded? My reply is that this is not the case. There will be infinitely many "plausible" data sets as well.

You could collide every hash in existence merely by making undetectably tiny alterations to Shakespeare.

Re: SHA-1 'fully and practically broken' by new collision (2020)

#108

Post by atdt »

sverhagen wrote: post #100
DSMan195276 wrote: post #93

Earlier quoted context omitted.

I would think it's not that simple because `git push --force` doesn't do anything if it thinks the histories are the same, and in this case we've created a history that appears to be the same. You'd likely need a custom git client (which isn't a problem) but I don't know enough about the internals of a git push to know if the server would even accept objects if they match hashes of objects it already has (it may just…

If you can force push, why would you then not push a different commit before pushing your updated commit with the same, original hash, or does that also not work?

By default Git keeps inaccessible/orphaned objects for two weeks before they are garbage-collected.

Re: SHA-1 'fully and practically broken' by new collision (2020)

#109

Post by fwip »

motohagiography wrote: post #36
fwip wrote: post #14

Earlier quoted context omitted.

No, because reversing the hash has infinite possible answers (well, "very many" for bounded input size). You can't decompress 32 bytes into 1GB because you don't know which of the 1GB-sized answers is the intended one.

This is what made it a funny thought experiement to me. I was doing some space related stuff a while back and when you're dealing with something as small as 100mb, and you add the constraint of up to a light-year or more of latency, which makes error correction immensely costly, having a quantum processor reciever find the collision of a unique hash could be faster than transmitting the data with errors. There's prob…

Yeah, you're fundamentally missing what I wrote, as well as pigeonhole principle and the basics of information theory.

Let's say you replace the quantum computer with an oracle. You have an infinitely long dictionary, and you can turn to any page and see your hash, as well as every possible input that could form that hash. There's billions and billions of options that all match your hash - how could you pick which one is definitely the "right" one?

You're no closer to knowing what the transmitted message was, because of the astronomical number of inputs that you now have to sift through.

[ Technically, you're (length of hash in bits) closer. Say you have 10 bits of hash, or 1024 values. There are (on average), 2 11-bit inputs that create that hash, 4 12-bit inputs, 8 13-bit inputs, and so on, following the powers of 2. At input of N=30 bits, you have 2^20 =~ 1 million possible inputs with that exact same hash. 1KB? 2^990, or "one followed by 990 zeroes". ]

Re: SHA-1 'fully and practically broken' by new collision (2020)

#110

Post by DSMan195276 »

sverhagen wrote: post #100
DSMan195276 wrote: post #93

Earlier quoted context omitted.

I would think it's not that simple because `git push --force` doesn't do anything if it thinks the histories are the same, and in this case we've created a history that appears to be the same. You'd likely need a custom git client (which isn't a problem) but I don't know enough about the internals of a git push to know if the server would even accept objects if they match hashes of objects it already has (it may just…

If you can force push, why would you then not push a different commit before pushing your updated commit with the same, original hash, or does that also not work?

I wouldn't expect that to work reliably because git doesn't actively remove unused objects from the store, hence why you can do `git reflog` to go find stuff that's not actually referenced anywhere anymore. `git gc` is necessary to make them actually go away, and whether that ever happens and how often is up to the server. I know for example that Github practically never does it, and even if it did happen it would be hard to reliably ensure no references to the relevant object still exist anywhere on the server. For example, you would have to force push every branch on the server that references the object, and if the git server creates branches for internal use you might not be able to touch those or convince the server the object is unused. And even if all the references are gone if the object is never actually deleted from the server then it should just get used again if you try to do a `git push`.
Post reply on HN