20 ms·

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

279 points by ofou 5y ago

deleted 5y ago
[deleted]
bjarneh 5y ago
> The technique that the researchers developed is quite complex and required two months of computations on 900 individual GPUs.
- motohagiography 5y ago
  I only half joke when I ask, when you break a cryptogrpahic hash, does it mean that now it's just a really amazing compression algorithm, but with a very heavy compute requirement? The non-joking half is speculating what data compression in a post-quantum compute world looks like.
  - FartyMcFarter 5y ago
    Compression algorithms must encode data in a reversible way, which hash functions can't do in general. For example, SHA-1 outputs a 160 bit hash, which means some input of 161 or more bits will definitely have the same hash as some other input of the same size. Even smaller inputs may have collisions too.
  - fwip 5y ago
    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.
    - ganzuul 5y ago
      Natural data is easily identifiable.
      - __s 5y ago
        That's because natural data has low entropy But let's say every paragraph only offers 1 bit of entropy. Then a 160 bit hash gives you fuzzy accuracy up to 160 paragraphs. After that you'll have to extend the hash with hints to guide which sequence of paragraphs you're looking for, & hints for where the typos are ofc, 100x compression of English text doesn't require this amount of compute to decompress: https://en.wikipedia.org/wiki/Hutter_Prize https://en.wikipedia.org/wiki/Hutter_Prize It's also impractical since most compression use cases want to put the work in compression, & have decompression be straight forward edit: 100x was misreading, it's currently 8.6x http://prize.hutter1.net/#prev http://prize.hutter1.net/#prev
        AnimalMuppet 5y ago
        "Paragraph" is highly optimistic. IIRC, each English character has about 1 bit of entropy.
        __s 5y ago
        Shannon estimated 0.6 to 1.3: https://cs.fit.edu/~mmahoney/dissertation/entropy1.html https://cs.fit.edu/~mmahoney/dissertation/entropy1.html For the sake of argument I figured I'd be highly optimistic. The linked prize shows practical evidence of 1GB of Wikipedia being compressed below 1 bit per character (& that's with a limit of 50 hours cpu time, 10GB memory, & 100GB disk)
        ganzuul 5y ago
        This is very abstract, but I believe that since both input and output are very close in program space compared to the total size of PS, the heuristics to map between them are going to be of a manageable size. This is based on an intuition about a single source for all activity in this universe.
      - dTal 5y ago
        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.
    - akomtu 5y ago
      Not so simple. A hash corresponds to infinitely many messages, but how many of them are in ASCII charset under 1KB long? It may happen that each hash has a unique message within these constraints.
      - hyperpape 5y ago
        Ignoring punctuation, capitalization and spaces, you have (26 ^ 1024) / (2 ^ 160) ascii texts, which is too large for python to do the division. Thinking harder, that's: >>> (13 * (160)) * (26 ** (1024 - 160)) 586015382205826960727672544401463871212215837535709025412643135464856100047507808667927549205890681326798481562717865671371914861707033271010401105757243098374422354323280335989456977123883814519788789676409601028611595593846201622073508573113400508407626532918150795408521721900638322896979964584478287370459866751451622413984067802115006844002721198098126119299044037305285971873899685570443731713584345786693414215895940310733413089663439828136700053588516077484775302179979357918243214847406310224703621807862576801557249657421436718532619781248154845297450962161296162654285951879462181582579086975207170674079727507724939279192338763731562331681240184746490930657625088527012496974579965412172847315257089070105214466289197177909463176672954181773739345690793807307314187284671422149249630372138364687234076394633405015375177710973043617082884089261346079718819448519032937091364439564690325014717871376537803759701695837030040255807318892621674241958398030180530294671920834183657715967728968579955163053146309746677182369005157209730333605691785063279407829717681098919238400049142795696195708090541066855775773950462556018168019660329830112434789524857886670766484791538540247307849949305926757172442880517278313785940979709167536140659937329357336156000509320395656047604973761134700992358740522602445520136787846575269569119611476145342798153931437530464566322510167663230985347176517861376 If you restrict it to words, assume that there's only 1000 words in the English language, averaging 5 letters each, you get: (1000 ^ 200) / (2 ^ 160) which becomes: >>> (500 ** 160) * (1000 ** 40) 684227765783602085411977335590779360976690401306892466678255997993062052092705371819647552911192178726196289062500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 There will be massive numbers of realistic texts that match any given hash.
    - motohagiography 5y ago
      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 probably a distance where the latency in light years is longer than it takes for a quantum processor with some shortcuts to exhaust the search space for the collision on the hash - and potential hashing algorithms that contain information and hints about a hyperplane that generates the original data over the field of possibilities. To a quantum computer with sufficient qbits at a long enough latency distance away, the 32-bit hash of a 2048bit RSA key may "arrive" faster than transmitting the whole key. It feels like a fundamental misunderstanding of something in communication theory, but this was the thinking that prompted it.
      - mypalmike 5y ago
        Using the pigeonhole principle, consider how many 100 megabit values must, on average, hash to the same 32 bit value. The answer is a huge number (I could be wrong but it seems to me it might be 2 ^ (100,000,000 - 32)?). This is a bit of a paradox in cryptographic hashing, where finding a collision is difficult, but the number of collisions is enormous.
      - fwip 5y ago
        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". ]
  - deleted 5y ago
    [deleted]
  - tomsmeding 5y ago
    These hashes, regardless of their actual cryptographic strength, are intended to be indistinguishable from a random generator keyed with the input, kind of. Assuming that they succeed in that, hashes should be quite well distributed. That means that that for each hash n-bit hash output, there will be about two (n+1)-bit input strings that produce that hash, about four (n+2)-bit input strings, eight (n+3)-bit input strings, etc. So while there are probably few ASCII input strings that map to one particular hash, for example, there will be loads and loads of arbitrary bitstrings that map to that hash. Hashes are very bad compressors. :)
  - kazinator 5y ago
    The compression joke evokes a misconception (as STEM jokes often do) which, in this case, is that breaking a hash means finding a way to recover the full text of a multi-megabyte document, from a 100-something byte hash. Whereas all it means is that it's become feasible for someone to produce a fake document with the same hash as the genuine one; the attack depends on the existence of collisions, which depend on the hash being one-way, such that an infinite set of documents could be "recovered" from the hash. Most of the documents you could "decompress" from a hash are going to be gibberish, but some of them are going to be legit. If a hash is "broken", that means it's somehow unduly easy to search that ocean of gibberish collisions to find a chosen text which goes to a certain desired hash. Nothing quantum can redefine a function that isn't one-to-one and onto into one that is. The hashing function remains ever the mathematical object that it is: a one-way function. But calculations of or searches through that function can be faster. In a post-quantum world, pre-quantum crypto and hashing could well turn out to be "for shit" as such, but not due to ruses like suddenly reversing irreversible functions. Not saying that the joke isn't funny! We can imagine some hard-core computer science or math sitcom in which the fall characters say things like this, and only the very narrow target audience gets it.
- asdfman123 5y ago
  I wonder how much money in Bitcoin they would have made if they had used those hashes to mine instead. Speaking of which, it would be funny if they were pretending to do security research but added a secret backdoor to mine bitcoin instead, somehow exporting those hashes or using the partial results of SHA-1 calculations (BTC isn't SHA-1). I'm just joking, but I wonder if that's possible. If anyone is Machiavellian enough for that, it's security researchers.
  - fsckboy 5y ago
    mining bitcoin on one GPU is uneconomical, so mining bitcoin an a large number of them is... also.
    - FredPret 5y ago
      Unless your research grant pays for the electricity
      - asdfman123 5y ago
        Ding ding ding
        gjs278 5y ago
        wrong wrong wrong. the hash rate is so low on a gpu they wouldn’t even make a penny.
    - valec 5y ago
      this is a retarded and pedantic comment. op clearly meant cryptocurrency and put bitcoin as a stand in instead of ethereum, maybe out of ignorance. this comment doesn't address the meat of their comment and contributes nothing.
      - exciteabletom 5y ago
        > When disagreeing, please reply to the argument instead of calling names. "That is idiotic; 1 + 1 is 2, not 3" can be shortened to "1 + 1 is 2, not 3." > Be kind. Don't be snarky. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
- lallysingh 5y ago
  Or roughly 1.3M GPU hours. Less as GPUs get upgraded. Not sure how many AWS F1 (FPGA) hours it would take.
  - wongarsu 5y ago
    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.
    - lallysingh 5y ago
      Consumer GPUs could be run from a botnet, actually... Yikes.
rgovostes 5y ago
(Jan 7, 2020)
ImJasonH 5y ago
Reminder that GitHub has blocked Git commit collisions since 2017, and as far as anybody is aware hasn't seen one in the wild. https://github.blog/2017-03-20-sha-1-collision-detection-on-github-com/ https://github.blog/2017-03-20-sha-1-collision-detection-on-...
- api 5y ago
  Random collisions in 160-bit space are incredibly unlikely. This is talking about intentional collision, and means that it's entirely feasible for someone with significant compute power to create a git commit that has the exact same hash as another git commit. This could allow someone to silently modify a git commit history to e.g. inject malware or a known "bug" into a piece of software. The modified repository would be indistinguishable if you're only using git hashes. Git's uses SHA-1 for unique identifiers, which is technically okay as long as they are not considered secure. If git were designed today it would probably use SHA2 or SHA3 but it's probably not going to change due to the massive install base. Edit: anyone know if git's PGP signing feature creates a larger hash of the data in the repo? If not maybe git should add a feature where signing is done after the computation of a larger hash such as SHA-512 over all commits since the previous signature.
  - asdfman123 5y ago
    > Random collisions in 160-bit space are incredibly unlikely Just for fun: to get a 5% chance of a hash collision between ANY two numbers in an 160 bit space, you'd have to generate 3.9e23 hashes. So you'd have to generate 1000 hashes per second for *12 trillion years.* Formula: n = sqrt(2 * 2^160 * ln(1/(1-0.05)) https://en.wikipedia.org/wiki/Birthday_problem#Probability_of_a_shared_birthday_(collision) https://en.wikipedia.org/wiki/Birthday_problem#Probability_o...
  - throw_away 5y ago
    Looks like there's a migration plan for git to SHA-256: https://git-scm.com/docs/hash-function-transition/ https://git-scm.com/docs/hash-function-transition/
lifthrasiir 5y ago
The chosen-prefix collision with a complexity of 2^63.4 (2020).
- akomtu 5y ago
  Looks like they needed 1.5 millions GPU hours to find a collision with a random hash.
smegcicle 5y ago
thats it, it's over, git is finished
r0f1 5y ago
Obligatory link: https://shattered.io/ https://shattered.io/
- TravisHusky 5y ago
  Of course it has its own website ;)
- nikeee 5y ago
  The article states that the collision found is something different than that one found by Google et al. It's a chosen-prefix attack.
- fanf2 5y ago
  That was an earlier break; this article is about https://sha-mbles.github.io/ https://sha-mbles.github.io/
cletus 5y ago
Git was created 16 years ago. The impending breakage of SHA-1 was known even at that time, just like how MD5 had been broken before it. I'm honestly still shocked that updating the hashing algorithm wasn't built into Git from day one. I really wonder why. Did people think this wouldn't happen? Were they so in love with the performance of C/C++ being able to pass around 20 byte hashes on the stack without worrying about a more complicated structure (eg a collection of variable length hashes)? It just seems like such a massive and foreseeable oversight that's going to cause pain for some time to come for really no reason at all.
- tantalor 5y ago
  > going to cause pain What kind of attack on a git repo are you worried about?
  - snovv_crash 5y ago
    Subrepo hash substitution could enable a supply-chain attack
- renewiltord 5y ago
  It is a law of nature that all successful products find themselves not accounting for some predictable problems.
- alerighi 5y ago
  SHA-1 will still work fine for the purpose of git. It is just no longer considered secure for cryptographic operations, such as digital signature, that doesn't mean that you can't use it for other purposes, like git does. Using it is still fine and will ever be fine. Making the hashing algorithm exchangeable would have introduces complexity in a software that is already complex, and also less efficient (one of the reasons git was created was speed for large project like the Linux kernel) for no real purpose. If you want to change the algorithm, given that you will break compatibility with all existing repositories, tools, and clients, you make a fork of git because you are changing too much. I don't see why migrating to SHA-256. The collisions are still very unlikely to generate accidentally, and sure, if you want to do damage to a repository you can create one on purpose, as you can as well commit some hooks that contains malware, or alter the git history in any way you want, so what's the point?
john_alan 5y ago
> Our work show that SHA-1 is now fully and practically broken for use in digital signatures Yet 2nd preimage resistance is intact. Zzz.
ofou 5y ago
For the ones interested, you can use SHA-256 today. Warning: Still in experimental mode. # .gitconfig file [extensions] objectFormat = sha256
- garmaine 5y ago
  Does GitHub support this?
  - ofou 5y ago
    Not yet [1]. "However, conversations around its implementation are ongoing and looks like it will be on the horizon." [1]: https://github.community/t/support-for-sha-256-hashes/157493/2 https://github.community/t/support-for-sha-256-hashes/157493...
dang 5y ago
Some past threads: SHA-1 collisions now cost $45k [pdf] - https://news.ycombinator.com/item?id=23350223 https://news.ycombinator.com/item?id=23350223 - May 2020 (62 comments) The first chosen-prefix collision for SHA-1 - https://news.ycombinator.com/item?id=21979333 https://news.ycombinator.com/item?id=21979333 - Jan 2020 (352 comments) Abusing SHA-1 collisions for Chromium updates - https://news.ycombinator.com/item?id=20114809 https://news.ycombinator.com/item?id=20114809 - June 2019 (36 comments) A SHA-1 chosen-prefix collision attack - https://news.ycombinator.com/item?id=19907127 https://news.ycombinator.com/item?id=19907127 - May 2019 (71 comments) From Collisions to Chosen-Prefix Collisions Application to Full SHA-1 [pdf] - https://news.ycombinator.com/item?id=19878917 https://news.ycombinator.com/item?id=19878917 - May 2019 (18 comments) SHA-1 Collision Detection on GitHub.com - https://news.ycombinator.com/item?id=13917990 https://news.ycombinator.com/item?id=13917990 - March 2017 (90 comments) Linus' reply on Git and SHA-1 collision - https://news.ycombinator.com/item?id=13719368 https://news.ycombinator.com/item?id=13719368 - Feb 2017 (262 comments) When Will We See Collisions for SHA-1? (2012) - https://news.ycombinator.com/item?id=13719079 https://news.ycombinator.com/item?id=13719079 - Feb 2017 (1 comment) Announcing the first SHA-1 collision - https://news.ycombinator.com/item?id=13713480 https://news.ycombinator.com/item?id=13713480 - Feb 2017 (485 comments) How would Git handle a SHA-1 collision on a blob? - https://news.ycombinator.com/item?id=13547348 https://news.ycombinator.com/item?id=13547348 - Feb 2017 (5 comments) Why it’s harder to forge a SHA-1 certificate than to find a SHA-1 collision - https://news.ycombinator.com/item?id=10778773 https://news.ycombinator.com/item?id=10778773 - Dec 2015 (43 comments) The Cost of Creating Collisions Using SHA-1 - https://news.ycombinator.com/item?id=8629906 https://news.ycombinator.com/item?id=8629906 - Nov 2014 (9 comments) When Will We See Collisions for SHA-1? - https://news.ycombinator.com/item?id=4618069 https://news.ycombinator.com/item?id=4618069 - Oct 2012 (51 comments)
musicale 5y ago
Old collision (2020). ;-)
1ncorrect 5y ago
I’ve wondered for a while if it is viable to use multiple hashes, or nested hashes, to mitigate these vulnerabilities, for example: message+hash1(message)+hash2(message) message+hash1(hash1(message)) To my lay understanding, it would provide multiple chained validation steps, but I’m curious if there are any obvious flaws with this model.
- jiggawatts 5y ago
  This a common lay-person approach to "strengthening" cryptography, but is not as effective as using a better algorithm instead. For example, SHA256 and SHA512 require approximately the same number of "cycles per byte" when using modern CPU instruction sets. So 2× SHA256 is 2× slower than 1× SHA512. On some processor models, 1× SHA512 is faster than 1× SHA256! Of course, things aren't always this simple, but you get the idea. Similarly, for some class of attacks, it's only 2× as much work to crack 2× SHA256 as it would take to crack 1×SHA256. However, for these attacks it is (2^256)× more work to crack SHA512, which takes the difficulty increase from "slightly more" to "absolutely impossible in this physical universe".
- garmaine 5y ago
  If the hash function does its job at mixing input, this is no different than applying just the final hash. (With the technical caveat that doing at least two serial hashes does improve the properties of the hash function by defending against length extension attacks. That's why things like HMAC do multiple chained hashes. But it does zilch for collision or preimage resistance.
simpleguitar 5y ago
I have a question. Is it not possible to create a good cryptographic hashing algorithm that results in 128bit or 160bit hash? It seems all the modern, secure ones are 256 bits or larger. Is that because 160 bits is too easy to compute collisions for any algorithm, or are we just not able to fully realize the entropy that can be recorded into 160 (or even 128) bits?
- garmaine 5y ago
  > Is it not possible to create a good cryptographic hashing algorithm that results in 128bit or 160bit hash? No, it is provably not possible to do that. A N-bit hash function has maximum N/2-bits of collision resistance. So a 128-bit hash function (like MD5) has a maximum of 2^64 bits of security against a classical attacker, even if it wasn't broken in other ways (as MD5 is). A 160-bit hash function like SHA-1 would have 2^80 bits of security against collision attacks on a classical computer. Both MD5 and SHA-1 are broken in other ways, but you could for example use SHA-2 or SHA-3 in truncated mode if you wanted a "secure" 128-bit or 160-bit hash output. Indeed there are standard operating modes for doing so, meant for when you need a drop-in replacement for MD5 or SHA-1. But fundamentally, 64-bit or 80-bit security is too low for any except some highly specified use cases. And even then the extra bits of a stronger hash will rarely kill you, so why bother? Just use SHA-2 or SHA-3 and not worry about it. In cases where you can demonstrate that you only care about preimage resistance and not collision resistance, then a 128-bit hash would be sufficient. However often collision attacks crop in in unexpected places or when your protocol is used in ways you didn't design for. Better to just double the hash size and not worry about it.
zzo38computer 5y ago
Fortunately, Fossil can now use SHA3-256 as well as SHA-1 (even in the same repository if necessary, perhaps due to upgrading an older repository), and I think it also has a hard mode to detect if SHA-1 collisions seem likely. (I think git doesn't allow a repository to have multiple kind of hashes; from what I understand, only a single algorithm must be used.) Since SHA-1 and SHA3-256 have different hash length, you can tell which one it is. It doesn't work so well if the length is the same; one way to fix it would be use a multicodec prefix. (My own implementation (currently incomplete) internally uses the multicodec numbers to identify the hash algorithms, but these multicodec numbers are never stored in the repository; instead, it is only applicable for the argument for the function to compute the hash, which can also be used in other programs.)
- b3n 5y ago
  Unfortunately Fossil uses a fast SHA hash for the password hashes of user accounts in the database, rather than a key derivation function, which is disappointing.
  - tashbarg 5y ago
    My fossil knowledge might be a fossil itself, but isn’t the database used for everything? If someone gets hold of the hashes, they already have everything. So, whats the threat that is enabled by poor pw hashing? Anyways, passwords should always be hashed with good password hashing functions (not all kdf are good for that) even if it is not strictly necessary. Just in case.
zzo38computer 5y ago
My idea is a different hash construction, which is 2D construction, which has a infinite internal state and infinite output length. Each row and each column also has a sequence number input, and then there are two mixing up functions (each of which has a finite input and output of equal size than the input); part of the result is propagated horizontally and part of it vertically, so each cell has two inputs and the input includes both the message block and the sequence number, which overwrites a part of the internal state (the rest of which has been mixed with the other state). Each output block (the output blocks are vertical and the message blocks are horizontal, which is why it is slow) is then truncated and concatenated to produce the final output, after adding padding at the end of the message (including the length of the message) to mix it up even more. If the message length is m and the hash length is h, then it requires O(h) space and O(mh) time. If ChaCha20 is in use, then it is easy to see (by the kind of calculations made by ChaCha20) that if the input is zero then the output will also be zero; therefore, the initial sequence number should be 1 and not 0. You can also compute a secondary hash which must be misaligned with the first one, so that in case a collision is found in one block that the collision will not be propagated with the other blocks too (unless a collision can be found within two consecutive blocks, in which case you would hope that the extra dimension (since it is a 2D construction) can avoid the collision).
- brirec 5y ago
  Reading your post I’m sure you know far more about information theory than I do, so forgive me if this is a stupid question, but… 1. How is infinite internal state and output size possible? There has to be some actual limit for internal state, at least, right? Or else you’ll just run out of memory? 2. Wouldn’t a larger output size risk leaking data? The chance of collision becomes lower, but it also seems to toy with what I understand about why we use cryptographic hashes without ridiculous output size. 3A. What happens if you want a 1 MB hash of a 1 KB file? 3B. How predictable does a super long hash become? At what point is it no longer a one-way hash?
  - zzo38computer 5y ago
    1. Because you will probably be truncating the output to a short finite hash, and because each block of internal state only leads in one direction (it affects all later ("up") blocks of internal state for all later ("right") message blocks, but not previous ("left" and "down")), you can optimize it by only implementing the part that you need. So, yes, an actual implementation will be limited, but if you have enough memory and enough time then the limit can be as high as you want to be. (Maybe a diagram might explain it better; I am not sure that this explanation is any good.) (SHAKE also has infinite output (but finite internal state), and when using SHAKE also you would truncate the output to a finite size.) 2. A larger output size might risk leaking data, although I would think it would be difficult. 3A. Like I described, it then needs O(1MB) space and O(1GB) time, so it will be slow. However, I do not expect you should need a hash that long. 3B. I don't know; probably about as predictable as any random number generator, if the hash is designed correctly. (I only describe a construction, and the hash algorithm design involves more than that.)

279 points by ofou 5y ago

deleted 5y ago

[deleted]

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

motohagiography 5y ago
I only half joke when I ask, when you break a cryptogrpahic hash, does it mean that now it's just a really amazing compression algorithm, but with a very heavy compute requirement? The non-joking half is speculating what data compression in a post-quantum compute world looks like.
- FartyMcFarter 5y ago
  Compression algorithms must encode data in a reversible way, which hash functions can't do in general. For example, SHA-1 outputs a 160 bit hash, which means some input of 161 or more bits will definitely have the same hash as some other input of the same size. Even smaller inputs may have collisions too.
- fwip 5y ago
  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.
  - ganzuul 5y ago
    Natural data is easily identifiable.
    - __s 5y ago
      That's because natural data has low entropy But let's say every paragraph only offers 1 bit of entropy. Then a 160 bit hash gives you fuzzy accuracy up to 160 paragraphs. After that you'll have to extend the hash with hints to guide which sequence of paragraphs you're looking for, & hints for where the typos are ofc, 100x compression of English text doesn't require this amount of compute to decompress: https://en.wikipedia.org/wiki/Hutter_Prize https://en.wikipedia.org/wiki/Hutter_Prize It's also impractical since most compression use cases want to put the work in compression, & have decompression be straight forward edit: 100x was misreading, it's currently 8.6x http://prize.hutter1.net/#prev http://prize.hutter1.net/#prev
      - AnimalMuppet 5y ago
        "Paragraph" is highly optimistic. IIRC, each English character has about 1 bit of entropy.
        __s 5y ago
        Shannon estimated 0.6 to 1.3: https://cs.fit.edu/~mmahoney/dissertation/entropy1.html https://cs.fit.edu/~mmahoney/dissertation/entropy1.html For the sake of argument I figured I'd be highly optimistic. The linked prize shows practical evidence of 1GB of Wikipedia being compressed below 1 bit per character (& that's with a limit of 50 hours cpu time, 10GB memory, & 100GB disk)
      - ganzuul 5y ago
        This is very abstract, but I believe that since both input and output are very close in program space compared to the total size of PS, the heuristics to map between them are going to be of a manageable size. This is based on an intuition about a single source for all activity in this universe.
    - dTal 5y ago
      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.
  - akomtu 5y ago
    Not so simple. A hash corresponds to infinitely many messages, but how many of them are in ASCII charset under 1KB long? It may happen that each hash has a unique message within these constraints.
    - hyperpape 5y ago
      Ignoring punctuation, capitalization and spaces, you have (26 ^ 1024) / (2 ^ 160) ascii texts, which is too large for python to do the division. Thinking harder, that's: >>> (13 * (160)) * (26 ** (1024 - 160)) 586015382205826960727672544401463871212215837535709025412643135464856100047507808667927549205890681326798481562717865671371914861707033271010401105757243098374422354323280335989456977123883814519788789676409601028611595593846201622073508573113400508407626532918150795408521721900638322896979964584478287370459866751451622413984067802115006844002721198098126119299044037305285971873899685570443731713584345786693414215895940310733413089663439828136700053588516077484775302179979357918243214847406310224703621807862576801557249657421436718532619781248154845297450962161296162654285951879462181582579086975207170674079727507724939279192338763731562331681240184746490930657625088527012496974579965412172847315257089070105214466289197177909463176672954181773739345690793807307314187284671422149249630372138364687234076394633405015375177710973043617082884089261346079718819448519032937091364439564690325014717871376537803759701695837030040255807318892621674241958398030180530294671920834183657715967728968579955163053146309746677182369005157209730333605691785063279407829717681098919238400049142795696195708090541066855775773950462556018168019660329830112434789524857886670766484791538540247307849949305926757172442880517278313785940979709167536140659937329357336156000509320395656047604973761134700992358740522602445520136787846575269569119611476145342798153931437530464566322510167663230985347176517861376 If you restrict it to words, assume that there's only 1000 words in the English language, averaging 5 letters each, you get: (1000 ^ 200) / (2 ^ 160) which becomes: >>> (500 ** 160) * (1000 ** 40) 684227765783602085411977335590779360976690401306892466678255997993062052092705371819647552911192178726196289062500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 There will be massive numbers of realistic texts that match any given hash.
  - motohagiography 5y ago
    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 probably a distance where the latency in light years is longer than it takes for a quantum processor with some shortcuts to exhaust the search space for the collision on the hash - and potential hashing algorithms that contain information and hints about a hyperplane that generates the original data over the field of possibilities. To a quantum computer with sufficient qbits at a long enough latency distance away, the 32-bit hash of a 2048bit RSA key may "arrive" faster than transmitting the whole key. It feels like a fundamental misunderstanding of something in communication theory, but this was the thinking that prompted it.
    - mypalmike 5y ago
      Using the pigeonhole principle, consider how many 100 megabit values must, on average, hash to the same 32 bit value. The answer is a huge number (I could be wrong but it seems to me it might be 2 ^ (100,000,000 - 32)?). This is a bit of a paradox in cryptographic hashing, where finding a collision is difficult, but the number of collisions is enormous.
    - fwip 5y ago
      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". ]
- deleted 5y ago
  [deleted]
- tomsmeding 5y ago
  These hashes, regardless of their actual cryptographic strength, are intended to be indistinguishable from a random generator keyed with the input, kind of. Assuming that they succeed in that, hashes should be quite well distributed. That means that that for each hash n-bit hash output, there will be about two (n+1)-bit input strings that produce that hash, about four (n+2)-bit input strings, eight (n+3)-bit input strings, etc. So while there are probably few ASCII input strings that map to one particular hash, for example, there will be loads and loads of arbitrary bitstrings that map to that hash. Hashes are very bad compressors. :)
- kazinator 5y ago
  The compression joke evokes a misconception (as STEM jokes often do) which, in this case, is that breaking a hash means finding a way to recover the full text of a multi-megabyte document, from a 100-something byte hash. Whereas all it means is that it's become feasible for someone to produce a fake document with the same hash as the genuine one; the attack depends on the existence of collisions, which depend on the hash being one-way, such that an infinite set of documents could be "recovered" from the hash. Most of the documents you could "decompress" from a hash are going to be gibberish, but some of them are going to be legit. If a hash is "broken", that means it's somehow unduly easy to search that ocean of gibberish collisions to find a chosen text which goes to a certain desired hash. Nothing quantum can redefine a function that isn't one-to-one and onto into one that is. The hashing function remains ever the mathematical object that it is: a one-way function. But calculations of or searches through that function can be faster. In a post-quantum world, pre-quantum crypto and hashing could well turn out to be "for shit" as such, but not due to ruses like suddenly reversing irreversible functions. Not saying that the joke isn't funny! We can imagine some hard-core computer science or math sitcom in which the fall characters say things like this, and only the very narrow target audience gets it.
asdfman123 5y ago
I wonder how much money in Bitcoin they would have made if they had used those hashes to mine instead. Speaking of which, it would be funny if they were pretending to do security research but added a secret backdoor to mine bitcoin instead, somehow exporting those hashes or using the partial results of SHA-1 calculations (BTC isn't SHA-1). I'm just joking, but I wonder if that's possible. If anyone is Machiavellian enough for that, it's security researchers.
- fsckboy 5y ago
  mining bitcoin on one GPU is uneconomical, so mining bitcoin an a large number of them is... also.
  - FredPret 5y ago
    Unless your research grant pays for the electricity
    - asdfman123 5y ago
      Ding ding ding
      - gjs278 5y ago
        wrong wrong wrong. the hash rate is so low on a gpu they wouldn’t even make a penny.
  - valec 5y ago
    this is a retarded and pedantic comment. op clearly meant cryptocurrency and put bitcoin as a stand in instead of ethereum, maybe out of ignorance. this comment doesn't address the meat of their comment and contributes nothing.
    - exciteabletom 5y ago
      > When disagreeing, please reply to the argument instead of calling names. "That is idiotic; 1 + 1 is 2, not 3" can be shortened to "1 + 1 is 2, not 3." > Be kind. Don't be snarky. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
lallysingh 5y ago
Or roughly 1.3M GPU hours. Less as GPUs get upgraded. Not sure how many AWS F1 (FPGA) hours it would take.
- wongarsu 5y ago
  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.
  - lallysingh 5y ago
    Consumer GPUs could be run from a botnet, actually... Yikes.

rgovostes 5y ago

(Jan 7, 2020)

ImJasonH 5y ago

Reminder that GitHub has blocked Git commit collisions since 2017, and as far as anybody is aware hasn't seen one in the wild. https://github.blog/2017-03-20-sha-1-collision-detection-on-github-com/ https://github.blog/2017-03-20-sha-1-collision-detection-on-...

api 5y ago
Random collisions in 160-bit space are incredibly unlikely. This is talking about intentional collision, and means that it's entirely feasible for someone with significant compute power to create a git commit that has the exact same hash as another git commit. This could allow someone to silently modify a git commit history to e.g. inject malware or a known "bug" into a piece of software. The modified repository would be indistinguishable if you're only using git hashes. Git's uses SHA-1 for unique identifiers, which is technically okay as long as they are not considered secure. If git were designed today it would probably use SHA2 or SHA3 but it's probably not going to change due to the massive install base. Edit: anyone know if git's PGP signing feature creates a larger hash of the data in the repo? If not maybe git should add a feature where signing is done after the computation of a larger hash such as SHA-512 over all commits since the previous signature.
- asdfman123 5y ago
  > Random collisions in 160-bit space are incredibly unlikely Just for fun: to get a 5% chance of a hash collision between ANY two numbers in an 160 bit space, you'd have to generate 3.9e23 hashes. So you'd have to generate 1000 hashes per second for *12 trillion years.* Formula: n = sqrt(2 * 2^160 * ln(1/(1-0.05)) https://en.wikipedia.org/wiki/Birthday_problem#Probability_of_a_shared_birthday_(collision) https://en.wikipedia.org/wiki/Birthday_problem#Probability_o...
- throw_away 5y ago
  Looks like there's a migration plan for git to SHA-256: https://git-scm.com/docs/hash-function-transition/ https://git-scm.com/docs/hash-function-transition/

lifthrasiir 5y ago

The chosen-prefix collision with a complexity of 2^63.4 (2020).

akomtu 5y ago
Looks like they needed 1.5 millions GPU hours to find a collision with a random hash.

smegcicle 5y ago

thats it, it's over, git is finished

r0f1 5y ago

Obligatory link: https://shattered.io/ https://shattered.io/

TravisHusky 5y ago
Of course it has its own website ;)
nikeee 5y ago
The article states that the collision found is something different than that one found by Google et al. It's a chosen-prefix attack.
fanf2 5y ago
That was an earlier break; this article is about https://sha-mbles.github.io/ https://sha-mbles.github.io/

cletus 5y ago

Git was created 16 years ago. The impending breakage of SHA-1 was known even at that time, just like how MD5 had been broken before it. I'm honestly still shocked that updating the hashing algorithm wasn't built into Git from day one. I really wonder why. Did people think this wouldn't happen? Were they so in love with the performance of C/C++ being able to pass around 20 byte hashes on the stack without worrying about a more complicated structure (eg a collection of variable length hashes)? It just seems like such a massive and foreseeable oversight that's going to cause pain for some time to come for really no reason at all.

tantalor 5y ago
> going to cause pain What kind of attack on a git repo are you worried about?
- snovv_crash 5y ago
  Subrepo hash substitution could enable a supply-chain attack
renewiltord 5y ago
It is a law of nature that all successful products find themselves not accounting for some predictable problems.
alerighi 5y ago
SHA-1 will still work fine for the purpose of git. It is just no longer considered secure for cryptographic operations, such as digital signature, that doesn't mean that you can't use it for other purposes, like git does. Using it is still fine and will ever be fine. Making the hashing algorithm exchangeable would have introduces complexity in a software that is already complex, and also less efficient (one of the reasons git was created was speed for large project like the Linux kernel) for no real purpose. If you want to change the algorithm, given that you will break compatibility with all existing repositories, tools, and clients, you make a fork of git because you are changing too much. I don't see why migrating to SHA-256. The collisions are still very unlikely to generate accidentally, and sure, if you want to do damage to a repository you can create one on purpose, as you can as well commit some hooks that contains malware, or alter the git history in any way you want, so what's the point?

john_alan 5y ago

> Our work show that SHA-1 is now fully and practically broken for use in digital signatures Yet 2nd preimage resistance is intact. Zzz.

ofou 5y ago

For the ones interested, you can use SHA-256 today. Warning: Still in experimental mode. # .gitconfig file [extensions] objectFormat = sha256

garmaine 5y ago
Does GitHub support this?
- ofou 5y ago
  Not yet [1]. "However, conversations around its implementation are ongoing and looks like it will be on the horizon." [1]: https://github.community/t/support-for-sha-256-hashes/157493/2 https://github.community/t/support-for-sha-256-hashes/157493...

dang 5y ago

Some past threads: SHA-1 collisions now cost $45k [pdf] - https://news.ycombinator.com/item?id=23350223 https://news.ycombinator.com/item?id=23350223 - May 2020 (62 comments) The first chosen-prefix collision for SHA-1 - https://news.ycombinator.com/item?id=21979333 https://news.ycombinator.com/item?id=21979333 - Jan 2020 (352 comments) Abusing SHA-1 collisions for Chromium updates - https://news.ycombinator.com/item?id=20114809 https://news.ycombinator.com/item?id=20114809 - June 2019 (36 comments) A SHA-1 chosen-prefix collision attack - https://news.ycombinator.com/item?id=19907127 https://news.ycombinator.com/item?id=19907127 - May 2019 (71 comments) From Collisions to Chosen-Prefix Collisions Application to Full SHA-1 [pdf] - https://news.ycombinator.com/item?id=19878917 https://news.ycombinator.com/item?id=19878917 - May 2019 (18 comments) SHA-1 Collision Detection on GitHub.com - https://news.ycombinator.com/item?id=13917990 https://news.ycombinator.com/item?id=13917990 - March 2017 (90 comments) Linus' reply on Git and SHA-1 collision - https://news.ycombinator.com/item?id=13719368 https://news.ycombinator.com/item?id=13719368 - Feb 2017 (262 comments) When Will We See Collisions for SHA-1? (2012) - https://news.ycombinator.com/item?id=13719079 https://news.ycombinator.com/item?id=13719079 - Feb 2017 (1 comment) Announcing the first SHA-1 collision - https://news.ycombinator.com/item?id=13713480 https://news.ycombinator.com/item?id=13713480 - Feb 2017 (485 comments) How would Git handle a SHA-1 collision on a blob? - https://news.ycombinator.com/item?id=13547348 https://news.ycombinator.com/item?id=13547348 - Feb 2017 (5 comments) Why it’s harder to forge a SHA-1 certificate than to find a SHA-1 collision - https://news.ycombinator.com/item?id=10778773 https://news.ycombinator.com/item?id=10778773 - Dec 2015 (43 comments) The Cost of Creating Collisions Using SHA-1 - https://news.ycombinator.com/item?id=8629906 https://news.ycombinator.com/item?id=8629906 - Nov 2014 (9 comments) When Will We See Collisions for SHA-1? - https://news.ycombinator.com/item?id=4618069 https://news.ycombinator.com/item?id=4618069 - Oct 2012 (51 comments)

musicale 5y ago

Old collision (2020). ;-)

1ncorrect 5y ago

I’ve wondered for a while if it is viable to use multiple hashes, or nested hashes, to mitigate these vulnerabilities, for example: message+hash1(message)+hash2(message) message+hash1(hash1(message)) To my lay understanding, it would provide multiple chained validation steps, but I’m curious if there are any obvious flaws with this model.

jiggawatts 5y ago
This a common lay-person approach to "strengthening" cryptography, but is not as effective as using a better algorithm instead. For example, SHA256 and SHA512 require approximately the same number of "cycles per byte" when using modern CPU instruction sets. So 2× SHA256 is 2× slower than 1× SHA512. On some processor models, 1× SHA512 is faster than 1× SHA256! Of course, things aren't always this simple, but you get the idea. Similarly, for some class of attacks, it's only 2× as much work to crack 2× SHA256 as it would take to crack 1×SHA256. However, for these attacks it is (2^256)× more work to crack SHA512, which takes the difficulty increase from "slightly more" to "absolutely impossible in this physical universe".
garmaine 5y ago
If the hash function does its job at mixing input, this is no different than applying just the final hash. (With the technical caveat that doing at least two serial hashes does improve the properties of the hash function by defending against length extension attacks. That's why things like HMAC do multiple chained hashes. But it does zilch for collision or preimage resistance.

simpleguitar 5y ago

I have a question. Is it not possible to create a good cryptographic hashing algorithm that results in 128bit or 160bit hash? It seems all the modern, secure ones are 256 bits or larger. Is that because 160 bits is too easy to compute collisions for any algorithm, or are we just not able to fully realize the entropy that can be recorded into 160 (or even 128) bits?

garmaine 5y ago
> Is it not possible to create a good cryptographic hashing algorithm that results in 128bit or 160bit hash? No, it is provably not possible to do that. A N-bit hash function has maximum N/2-bits of collision resistance. So a 128-bit hash function (like MD5) has a maximum of 2^64 bits of security against a classical attacker, even if it wasn't broken in other ways (as MD5 is). A 160-bit hash function like SHA-1 would have 2^80 bits of security against collision attacks on a classical computer. Both MD5 and SHA-1 are broken in other ways, but you could for example use SHA-2 or SHA-3 in truncated mode if you wanted a "secure" 128-bit or 160-bit hash output. Indeed there are standard operating modes for doing so, meant for when you need a drop-in replacement for MD5 or SHA-1. But fundamentally, 64-bit or 80-bit security is too low for any except some highly specified use cases. And even then the extra bits of a stronger hash will rarely kill you, so why bother? Just use SHA-2 or SHA-3 and not worry about it. In cases where you can demonstrate that you only care about preimage resistance and not collision resistance, then a 128-bit hash would be sufficient. However often collision attacks crop in in unexpected places or when your protocol is used in ways you didn't design for. Better to just double the hash size and not worry about it.

zzo38computer 5y ago

Fortunately, Fossil can now use SHA3-256 as well as SHA-1 (even in the same repository if necessary, perhaps due to upgrading an older repository), and I think it also has a hard mode to detect if SHA-1 collisions seem likely. (I think git doesn't allow a repository to have multiple kind of hashes; from what I understand, only a single algorithm must be used.) Since SHA-1 and SHA3-256 have different hash length, you can tell which one it is. It doesn't work so well if the length is the same; one way to fix it would be use a multicodec prefix. (My own implementation (currently incomplete) internally uses the multicodec numbers to identify the hash algorithms, but these multicodec numbers are never stored in the repository; instead, it is only applicable for the argument for the function to compute the hash, which can also be used in other programs.)

b3n 5y ago
Unfortunately Fossil uses a fast SHA hash for the password hashes of user accounts in the database, rather than a key derivation function, which is disappointing.
- tashbarg 5y ago
  My fossil knowledge might be a fossil itself, but isn’t the database used for everything? If someone gets hold of the hashes, they already have everything. So, whats the threat that is enabled by poor pw hashing? Anyways, passwords should always be hashed with good password hashing functions (not all kdf are good for that) even if it is not strictly necessary. Just in case.

zzo38computer 5y ago

My idea is a different hash construction, which is 2D construction, which has a infinite internal state and infinite output length. Each row and each column also has a sequence number input, and then there are two mixing up functions (each of which has a finite input and output of equal size than the input); part of the result is propagated horizontally and part of it vertically, so each cell has two inputs and the input includes both the message block and the sequence number, which overwrites a part of the internal state (the rest of which has been mixed with the other state). Each output block (the output blocks are vertical and the message blocks are horizontal, which is why it is slow) is then truncated and concatenated to produce the final output, after adding padding at the end of the message (including the length of the message) to mix it up even more. If the message length is m and the hash length is h, then it requires O(h) space and O(mh) time. If ChaCha20 is in use, then it is easy to see (by the kind of calculations made by ChaCha20) that if the input is zero then the output will also be zero; therefore, the initial sequence number should be 1 and not 0. You can also compute a secondary hash which must be misaligned with the first one, so that in case a collision is found in one block that the collision will not be propagated with the other blocks too (unless a collision can be found within two consecutive blocks, in which case you would hope that the extra dimension (since it is a 2D construction) can avoid the collision).

brirec 5y ago
Reading your post I’m sure you know far more about information theory than I do, so forgive me if this is a stupid question, but… 1. How is infinite internal state and output size possible? There has to be some actual limit for internal state, at least, right? Or else you’ll just run out of memory? 2. Wouldn’t a larger output size risk leaking data? The chance of collision becomes lower, but it also seems to toy with what I understand about why we use cryptographic hashes without ridiculous output size. 3A. What happens if you want a 1 MB hash of a 1 KB file? 3B. How predictable does a super long hash become? At what point is it no longer a one-way hash?
- zzo38computer 5y ago
  1. Because you will probably be truncating the output to a short finite hash, and because each block of internal state only leads in one direction (it affects all later ("up") blocks of internal state for all later ("right") message blocks, but not previous ("left" and "down")), you can optimize it by only implementing the part that you need. So, yes, an actual implementation will be limited, but if you have enough memory and enough time then the limit can be as high as you want to be. (Maybe a diagram might explain it better; I am not sure that this explanation is any good.) (SHAKE also has infinite output (but finite internal state), and when using SHAKE also you would truncate the output to a finite size.) 2. A larger output size might risk leaking data, although I would think it would be difficult. 3A. Like I described, it then needs O(1MB) space and O(1GB) time, so it will be slow. However, I do not expect you should need a hash that long. 3B. I don't know; probably about as predictable as any random number generator, if the hash is designed correctly. (I only describe a construction, and the hash algorithm design involves more than that.)