27 ms·

The first chosen-prefix collision for SHA-1

928 points by ynezz 7y ago

0x0 7y ago
Q: Does this make it even more urgent for git to move to a different hash?
- LeonM 7y ago
  A: (from the article) SHA-1 has been broken for 15 years, so there is no good reason to use this hash function in modern security software. Attacks only get better over time, and the goal of the cryptanalysis effort is to warn users so that they can deprecate algorithms before the attacks get practical. We actually expect our attack to cost just a couple thousand USD in a few years.
  - pathseeker 7y ago
    That's not a relevant answer. Git's use-case is very specific and it's quite possible that this attack won't be relevant. It needs analysis. >no good reason to use this hash function in modern security software This argument conveniently ignores the cost to switching existing software (i.e. it's completely detached from reality).
- EGreg 7y ago
  It may, because now an attacker can replace code with arbitrary other valid code as long as developers are willing to ignore the long weird random comment at the end ;-) I’m gonna say many developers will not care but and many compilers will not care either. So yeah, Linus’ main deterrent reason (code won’t compile) doesn’t apply anymore. HOWEVER! 1. A chosen-prefix attack still needs to compute TWO suffixes m1 and m2 so that h(a1+m1) = h(a2+m2). This does NOT mean that given a1 and a2 you can find a single m2 so that h(a1) = h(a2+m2). So that ONLY THE ORIGINAL AUTHOR OF THE COMMIT could spoof their own commit, by preparing in advance and attaching a long and weird comment in the end. And you could build tools to watch out for such commits in the first place 2. If git had used HMAC based on SHA1 then it would have been fine, even after this attack has become feasible. 3. Furthermore, it is likely still kinda fine because Merkle Trees have nodes referencing previous nodes. You’d have to spoof every historical node as well, to push malicious code. BitTorrent also requires computers to supply an entire merkle branch when serving file chunks. Maybe someone can elaborate on this.
  - rkangel 7y ago
    If you look in this 2017 (https://marc.info/?l=git&m=148787047422954 https://marc.info/?l=git&m=148787047422954) email from Linux, he discusses how git also encodes length. That would mean that you need a collision of the same length and the right functionality, so you can't just append data.
    - toyg 7y ago
      Now that you can arbitrarily produce collisions, the second step is easy enough for a skilled and well-funded attacker.
- rkangel 7y ago
  It adds to the weight of the argument, but there isn't a big issue. This article (https://www.zdnet.com/article/linus-torvalds-on-sha-1-and-git-the-sky-isnt-falling/ https://www.zdnet.com/article/linus-torvalds-on-sha-1-and-gi...) and the linked email (https://marc.info/?l=git&m=148787047422954 https://marc.info/?l=git&m=148787047422954) both seem to still apply.
  - groovybits 7y ago
    Further details as to why Torvalds is not concerned: From the email... "I haven't seen the attack yet, but git doesn't actually just hash the data, it does prepend a type/length field to it. That usually tends to make collision attacks much harder, because you either have to make the resulting size the same too, or you have to be able to also edit the size field in the header." [...] "I haven't seen the attack details, but I bet (a) the fact that we have a separate size encoding makes it much harder to do on git objects in the first place (b) we can probably easily add some extra sanity checks to the opaque data we do have, to make it much harder to do the hiding of random data that these attacks pretty much always depend on."
    - wyldfire 7y ago
      I think those are pretty practical approaches. But it sounds as if the cost of changing the hash algorithm is high. What are the impacts of this change? How many things would break if git just changed the algorithm with each new release? Does git assume that the hash algorithm is statically given to be SHA-1 or are there qualifiers on which algorithm is enabled/permitted/configured?
      - paulddraper 7y ago
        After making the actual code change, the biggest problem is breaking compatibility with decades of tools in the ecosystem that rely on historically consistent SHA-1 hashes. Git is moving to a flexible hash though. [1] [1] https://stackoverflow.com/questions/28159071/why-doesnt-git-use-more-modern-sha/47838703#47838703 https://stackoverflow.com/questions/28159071/why-doesnt-git-...
- mikepurvis 7y ago
  There is a migration path to SHA-256, see a good summary here: https://stackoverflow.com/a/47838703/109517 https://stackoverflow.com/a/47838703/109517 See a previous discussion here, regarding Linus's position on this in 2017: https://news.ycombinator.com/item?id=13719368 https://news.ycombinator.com/item?id=13719368
- rom1v 7y ago
  What happens if you actually get a SHA-1 collision in git? -> https://stackoverflow.com/questions/9392365/how-would-git-handle-a-sha-1-collision-on-a-blob https://stackoverflow.com/questions/9392365/how-would-git-ha... (This does not answer your question, but is still interesting.)
- mzs 7y ago
  https://news.ycombinator.com/item?id=21985773 https://news.ycombinator.com/item?id=21985773
deleted 7y ago
[deleted]
ebg13 7y ago
Quick question about the "What should I do" section. It says "use instead SHA-256". Isn't SHA-512 both better and faster on modern hardware?
- Spooky23 7y ago
  SHA-256 is on the approved FIPS lists and are faster on 32-bit operating systems, which were surprisingly common in enterprise environments until recently. People tend to be conservative in making changes for stuff like this, and don't do so until forced.
- akvadrako 7y ago
  I believe so also. Specifically, SHA-512/256 seems to be a better choice by almost every metric except 32-bit hashing speed.
- LeonM 7y ago
  Depends on your definition of 'better'. Theoretically SHA-512 is harder to brute force than SHA-256, but 256 bits is already extremely strong, so really there is no practical safety benefit of SHA-512 over SHA-256. On 64-bit capable processors SHA-512 has a slight performance gain over SHA-256, but only on larger inputs. However, the digest of SHA-512 is twice the size, so what you gain in processing time, you loose in storage.
  - quotemstr 7y ago
    You can truncate the SHA-512 digest down to 256 bits though. Cryptographic hash functions mix well and don't suffer from the truncation (except to the extent that the truncated digest is shorter, of course). You don't necessarily need more storage (after hashing completes) just because you're using a new hash function.
  - jlokier 7y ago
    > but 256 bits is already extremely strong The strength of hashes like SHA-256 doesn't just come from the number of output bits. The 256 bits there is relevant for brute force attacks, but not more sophisticated attacks that take into account the internal structure of the hash algorithm, and in some cases "weak" values. SHA-512 performs more "rounds" of computation than SHA-256. Although it's impossible to compare two different hashes on rounds alone, in general a large number of rounds of the same type of hash decreases the likelihood of non-brute-force attacks finding a collision. If you look at the literature for attacks on hashes, they will often say they could do it for a certain number of rounds, and that number increases over time as new methods are discovered. The number of rounds in the hash design is chosen with this in mind, trying to balance being more than sufficient for future attacks yet not too slow.
umvi 7y ago
Is "a Shambles" British or something? I've always heard it as "in Shambles"
- cpach 7y ago
  AFAICT ”a shambles” is correct usage. See https://brians.wsu.edu/2016/05/24/in-shambles-a-shambles/ https://brians.wsu.edu/2016/05/24/in-shambles-a-shambles/
  - OGWhales 7y ago
    Neat, but don't know if I can switch because of how it rolls off the tongue.
    - umvi 7y ago
      It got easier for me once I learned that "shambles" is a noun that is a synonym of "slaughterhouse". Once I learned that, I emphasized shambles slightly differently as I rolled the phrase off my tongue. "SHA-1 is a slaughterhouse" "SHA-1 is a shambles"
      - OGWhales 7y ago
        Yeah I got that from the link, I had no idea before. However, I feel like if it was "is a shamble" it would make more sense to me than "is a shambles".
  - umanwizard 7y ago
    Downvoted. There's no ISO standard for English, since language is a social phenomenon. "Correct" language is whatever the community of speakers uses in practice, not what someone claims is correct in a blog post (or even a book).
    - simias 7y ago
      And the linked article showed you that, in practice, "a shambles" is perfectly correct English. It is therefore correct in a descriptivist sense. Beyond that prefixing your comment by "downvoted" is frankly silly and only serves to derail the conversation IMO.
rustybolt 7y ago
> By renting a GPU cluster online, the entire chosen-prefix collision attack on SHA-1 costed us about 75k USD. So they just decided to try their attack and spend two years worth of salary on it?? That's crazy.
- oppositelock 7y ago
  That's dirt cheap for a government actor, and we can be sure that the big governments have been doing this sort of attack for years.
  - rustybolt 7y ago
    It's a lot of money for an academic researcher.
    - progval 7y ago
      Researchers in applied fields other than CS spend this kind of money on a regular basis. eg. https://www.quora.com/What-are-the-costs-for-lab-rat-testing-in-the-US https://www.quora.com/What-are-the-costs-for-lab-rat-testing...
    - CydeWeys 7y ago
      Is it? Multi-million grants are common in academia. A lot of research is expensive. When I worked in a lab the materials alone for a single day's experiment would frequently run into the thousands. E.g. the total human RNA samples we used cost many thousands of dollars per milligram. Admittedly this is a different field, but it's still academia.
      - klmr 7y ago
        > Multi-million grants are common in academia. Not in the way you explain. Multi-million dollar grants are usually awarded over multiple years, and pay for multiple researchers’ salaries, as well as other resources, some of which are expected to outlast the project (e.g. microscopes, or hardware for databases). Burning 75k on a single experiment (which is effectively what was done here) is rare. Note that this is true even for current hot topics such as biomedical (e.g. cancer) research, for which vast chunks of the federal budget have been allocated in multiple countries. Obtaining similar sums in less sexy fields is much harder. And even in biomedical research, multi-million dollar grants are considered large. Most grants are much smaller, they just don’t get talked about as much. Since you mention human RNA samples I assume you know this. You mention the per-milligram cost but this is pretty misleading if you mean to imply that “milligram” is somehow little, because it isn’t: yes, the samples are tiny (≤1 µg of RNA is more typical than milligrams!), but so what? It’s not like we need more.
bjornsing 7y ago
> We note that classical collisions and chosen-prefix collisions do not threaten all usages of SHA-1. In particular, HMAC-SHA-1 seems relatively safe, and preimage resistance (aka ability to invert the hash function) of SHA-1 remains unbroken as of today. Nice to see this bit of intellectual honesty. Would be even nicer if they had explained what that means in terms of PGP keys.
- _notreallyme_ 7y ago
  It means if someone you want to impersonate uses the Web Of Trust, i.e. their key is signed by other people whose keys have been signed the same way, you can generate a GPG key for which all of these signatures are still valid. For example, if an attacker gains access to a victim email account, they could send to their contacts a "trusted" key (as explained above) and then use it to send signed documents to the victim's contacts. This would defeat an adversary "paranoid" enough to check a key signature, but not paranoid enough to obtain a clear explaination/confirmation of why the key changed...
  - bjornsing 7y ago
    > It means if someone you want to impersonate uses the Web Of Trust, i.e. their key is signed by other people whose keys have been signed the same way, you can generate a GPG key for which all of these signatures are still valid. No... > For example, if an attacker gains access to a victim email account, they could send to their contacts a "trusted" key (as explained above) and then use it to send signed documents to the victim's contacts. Ok... But in this scenario the attacker has the victim’s new private key, so they don’t need to create a collision (using OP). They can just use the new private key to sign the documents. Right?
    - _notreallyme_ 7y ago
      > No... Why ? > in this scenario the attacker has the victim’s new private key You don't want to keep your private key in cleartext on your email provider servers, do you ?
emilfihlman 7y ago
>Can I try it out for myself? Since our attack on SHA-1 has pratical implications, in order to make sure proper countermeasures have been pushed we will wait for some time before releasing source code that allows to generate SHA-1 chosen-prefix collisions. Sigh. Again with this idiocy. All instances where the adversary is capable of launching this attack financially mean they also have the capability to write the exploit themselves.
- DarkWiiPlayer 7y ago
  It does make sense. Targets worth attacking at a high financial cost will most likely be the first to take measures against this attack. The kind of target that takes a longer time to switch most likely isn't worth attacking unless it's a very cheap and fast operation. And the longer you spend developing an exploit, the less viable the attack will become.
- lm28469 7y ago
  > All instances where the adversary is capable of launching this attack financially mean they also have the capability to write the exploit themselves. Iran will eventually create a nuclear bomb, why don't we gave them one now, it's the same thing isn't it ?
whatshisface 7y ago
>A countermeasure has been implemented in commit edc36f5, included in GnuPG version 2.2.18 (released on the 25th of November 2019): SHA-1-based identity signatures created after 2019-01-19 are now considered invalid. Since SHA-1 was always possible to break, and since NSA probably gets access to big computers and sophisticated techniques before researchers, why doesn't this invalidate every SHA-1 signature ever made and not just ones from last year?
- Boulth 7y ago
  Actually it's even worse than that: signature creation time is added by the signer so it's totally under control of the attacker. IMHO all SHA-1 based signatures should be ignored.
  - im3w1l 7y ago
    The signer is assumed to be trustworthy. That's why we care for their signature in the first place. It's the sign-ee that is presumed to be the attacker.
  - NieDzejkob 7y ago
    In this case, signature creation time isn't under control of the attacker. The attack scenario being considered is that Mallory can convince Alice to sign a key K1, provided by Mallory, such that it looks like Alice signed K2. The party creating the signature is honest here.
    - tialaramex 7y ago
      The problem is that the dates are part of the document being signed. Rather than keys, Alice will typically sign a document (e.g. an X.509 to-be-signed certificate) Mallory creates two documents, the legitimate seeming document A (a to-be-signed certificate Alice willingly signs) and document B (the content of which is controlled by Mallory to an extent depending on the details of the collision). In document A I'm sure Alice will insist on the date being roughly correct so you'd detect that. But Alice never sees document B, she isn't aware it exists, so it can specify any date, including one chosen not to set off alarms. For the Web PKI we were triply safe because: 1. We told Alice (the public CAs) never to sign anything at all with the dangerous algorithm after a set date. So long as Mallory wasn't able to develop and use a collision before that date and Alice did as she was told‡ this would be safe in perpetuity. 2. We already had a countermeasure in the documents, very early in each Web PKI X.509 certificate is the Serial Number, if you look at yours you'll notice it's a crazy huge number and seemingly not "serial" in any sense. It's random. Can't do a chosen prefix collision attack if you can't choose the prefix. 3. Since no more new documents were being signed clients in the Web PKI were able to stop recognising these signatures thus permanently ensuring the attack was impossible within about 18 months. ‡ A very small number of exceptions were explicitly granted, and a similarly small number of exceptional cases occurred for which no permission was asked. All investigated to everybody's satisfaction. As you may see if you poke around in the demo documents from this article, a collision document may not jump out as problematic from a crowd but it certainly isn't so innocuous as to survive careful scrutiny, and with such a small number of exceptions to look at this scrutiny was possible in a way it never would be for the wider Web PKI.
notlukesky 7y ago
> Responsible Disclosure We have tried to contact the authors of affected software before announcing this attack, but due to limited resources, we could not notify everyone. Is there a list of affected software out there?
- CiPHPerCoder 7y ago
  https://github.com/search?q=sha1&type=Code https://github.com/search?q=sha1&type=Code https://github.com/search?q=sha-1&type=Code https://github.com/search?q=sha-1&type=Code
- adminss 7y ago
  "> <script>alert()</script>
tambourine_man 7y ago
This kind of thing always brings me down a bit. It's not rational, but it does. I mean I truly admire these folks skills, the math involved is obviously remarkable. But I think the feeling is related to not being able to rely on anything in our field. Hard to justify going to the trouble of encrypting your backup. 10 years from now, it might be as good as plain text. It's not security only, nothing seems to work in the long term. Imagine an engineer receiving a call at midnight about his bridge because gravity changed during daylight saving in a leap year. That's our field.
- deleted 7y ago
  [deleted]
- wyday 7y ago
  >> "Hard to justify going to the trouble of encrypting your backup." Huh? If you're "encrypting" using SHA, I've got some bad news about those backups of yours.
  - tambourine_man 7y ago
    I'm refering to not being able to rely on encryption in the long term.
    - vbrandl 7y ago
      Hashing is a separate problem from encryption. There is no proof that one way functions (the idea behind hashing) even exist (by proving this, you would actually prove P!=NP, IIRC). Encryption has a slightly better track record of being broken. AES still holds its promise and is also secure against quantum computing (you might want longer keys, but that's it). And if you want really, provably unbreakable encryption, there is still OTP. But then you'd need a key, that is as long as the data you want to encrypt.
      - blattimwind 7y ago
        The best known attack against AES reduces attack complexity by about two bits over brute force. Given the history of block ciphers, the idea that AES might not be broken in this life time is not uncommon.
mehrdadn 7y ago
> SHA-1 has been broken for 15 years, so there is no good reason to use this hash function in modern security software. Why are cryptographers always exaggerating things and so out of touch with reality? The first actual collision was like 3 years ago. It's not like the world has been on fire in the meantime, and it's not like SHA-1 is broken for every single possible usage even now. And why the nonsense with "no good reason"? Obviously performance is one significant consideration for the unbroken use cases. Do they think painting a different reality than the one we live in somehow makes their case more compelling?
- ewidar 7y ago
  As stated, they are talking about "modern security software". So yeah, if you are building/improving software that has a clear focus on security, you should use a secure hash. Seems only natural to me.
- PeterisP 7y ago
  Past experience and documents that ceased being classified shows that serious attackers (e.g. NSA) are at least decade ahead of what's publicly known in cryptography; i.e. we know that pretty much always when new relevant groundbreaking math was published, the classified cryptographers had known that for a long, long time already. So if this attack is developed today, then you should assume that NSA has been able to execute this attack for at least ten years already whenever it suited them, including mass surveilance of random not-that-important people. The same applies for the collisions - the first published collision was 3 years ago, but we should assume that that's definitely not the first; I mean, only a minority of the world's cryptography researchers participate in the public, open, academic community; the majority of them are employed with a condition that they won't get to publish anything important. And since we know for the last ten years that such attacks were possible, there's no reasonable reason why SHA-1 would have been considered as safe.
  - dweekly 7y ago
    Are there materials that show a ten year head start?
deleted 7y ago
[deleted]
jlokier 7y ago
Just a curiosity, since people are talking about Git still using SHA-1 (despite work on SHA-256 since 2017). I see that Git doesn't actually use SHA-1 any more, it uses "hardened SHA-1": https://stackoverflow.com/questions/10434326/hash-collision-in-git/43355918#43355918 https://stackoverflow.com/questions/10434326/hash-collision-...
- FactolSarin 7y ago
  How would an attack on a git repo work? You create a repo with identical hashes but different content and next time the user clones from scratch they get your modified version?
  - flatiron 7y ago
    yeah my thoughts about git are similar. look at the two messages they have an an example: Key is part of a collision! It's a trap!yE'NsbK#ދW]{1gKmCx's/vr| -pJO_,1$)uB1qXv#U)9ESU;p~0G:Y ݕbBIjFra눰3&t'lB_!h5M([,˴QMK#|o5pv|i,+yYpݍD7_Rf\'GUZ,ϵdvAYAugV=Lk8_E 2 +nolBtxXoQt&+?Y3LP:'Qt(,ۛuԪWJm:A"M6<|B4kVv̨ޠA=M+m%殺j5N|EMA\Ed- s&@u@:a?pq^Xf0U?R} and Practical SHA-1 chosen-prefix collision!'lka}vbI3,·W]Ǟ+gK}Cxs/v&r| }-hRJO_ rO̳;bzC ,1&uRP-MXrU3aO;pr0:sY'2 l&r7#(A{oNyCJ_W,8 əbحBYީpFr2a8#&t+n_15q(_,ˤQMW#hzYMgVV=L,kO0E*N +oc@BpXoᯖd&?+?[{3LвP&'U t ( WJÏm\:A"6>>|SB(k;Vv̨ޠ^A=Y ;om%j-|cUAAۜEТ&@o@:La3psH^eXf0QJm ݶd they have the same sha1sum, but in all practicality its nonsense since both messages are pure trash. you couldn't have malicious C code that would have the same hash as non malicious C code in this example
    - saalweachter 7y ago
      Isn't that like incredibly simple? Dump your garbage string behind a // or inside an #if 0, restrict the garbage string character set to characters which will not disturb that, and your compiler will whistle while it works.
HashThis 7y ago
Quick, everyone bend over and cover your hashes
noja 7y ago
Is a collision impossible with two hashes, each using a different algorithm?
- femto113 7y ago
  Not impossible, but assuming there's not a mathematical flaw that affect both algorithms the difficulty is roughly the product of the difficulty of finding a collision in each. AFAIK no one has come up with a joint collision for MD5+SHA1 despite collisions in each being practical for several years.
  - noja 7y ago
    So should we do that, as well as keep finding new algorithms?
    - femto113 7y ago
      Concatenating two hashes is an algorithm. Mathematically concatenating two 128 bit hashes is not any stronger than a single 256 bit hash (and is likely weaker), but if it’s all you have (or all you can afford to compute) two weak hashes is definitely much better than one.
      - noja 7y ago
        Why is concatenating two 128 bit hashes (each with a different algorithm) not stronger than a single-algorithm 256 bit hash?
        femto113 7y ago
        One reason is that it is theoretically possible to use memory instead of computation to attack the combined hashes by pre-generating a large number of collisions under one algorithm and then simply checking those using the other one, which means you don't need to do both algorithms for every check. Can't say for sure if that works out cheaper in terms of money but if the memory is available it could definitely save a lot of time. Another reason is that for any given hash its theoretical maximum strength against any attack will be less than or equal to its bit length, but the practical strength always trends lower over time as attacks are found, and having two algorithms to attack increases the chances of finding flaws.
nvartolomei 7y ago
I assume there was a lot of work (read money) put in those collision attacks rather than it being discovered by accident. I'm wondering who is sponsoring this work and for what purpose? The argument about proving that an algorithm is broken and working on better cryptography wouldn't suffice in this case, as issues were shown before that. Here the purpose was to make the attack cheaper?
- tptacek 7y ago
  That is not how cryptographic research works, at all.
newscracker 7y ago
General questions: (edit: these are indeed general questions, not just about SHA1) Has anyone else been worried about data deduplication done by storage and/or backup systems, considering that they usually use hashes to detect data blocks that are "the same" (without additional metadata) and avoid storing those "duplicate data blocks" again? Doesn't this seem far worse when you also consider that systems like Dropbox deduplicate data across all their users (expanding the footprint for collisions)? Are there any research papers/articles/investigations about this?
- MichaelMoser123 7y ago
  are there any systems that do sha-1 for dedup? I am only aware of sha-256.
  - deleted 7y ago
    [deleted]
  - munificent 7y ago
    Git?
    - deleted 7y ago
      [deleted]
    - MichaelMoser123 7y ago
      git computes the sha1 checksum over the header that includes the length + the file data; also checks the length in the header as well as the the hash; Linus says that it would be less practical to find a collision that has the same length as the original data; I guess at some stage even that might become possible.
  - fanf2 7y ago
    Subversion's dedup was broken by the http://shattered.io/ http://shattered.io/ SHA-1 collision in 2017 https://medium.com/@hyrum/shattered-subversion-7edea4ba289c https://medium.com/@hyrum/shattered-subversion-7edea4ba289c
femto113 7y ago
While a meaningful accomplishment, suggesting the algorithm is in a "shambles" seems hyperbolic to me. For one thing there's a non-trivial practical leap between formulating two colliding identities and forging an existing one, and for another this was only modestly better than a pure brute force attack. If anything I'm somewhat reassured by the idea that it still costs $40,000+ of GPU time to pull something like this off while doing the same with MD5 is feasible on a mobile phone.
RcouF1uZ4gsC 7y ago
Does this affect Git? I believe it uses SHA-1 for commits. Is it possible to use this attack to add malicious code to a git repository without changing the hashes for the commits?
- LennyWhiteJr 7y ago
  Potentially. GitHub at least already started collision detection after Shattered was published. https://github.blog/2017-03-20-sha-1-collision-detection-on-github-com/ https://github.blog/2017-03-20-sha-1-collision-detection-on-...
kibwen 7y ago
Out of curiosity, can anyone explain in layman's terms the differences in design that make SHA-1's successors immune to the known attacks against SHA-1? Ultimately was this the result of an apparent flaw in SHA-1 that only became obvious in retrospect, or was it something totally unforeseeable?
- knorker 7y ago
  Partly this: Number of bits. This attack is almost 2^64, and SHA-1 is 160 bits. All else being equal (big big if) that means sha256 is 102 bits, meaning 362703572709.30493 times more expensive. Or about $16321 trillion USD.
- Zaak 7y ago
  SHA-2 is based on similar techniques to those in SHA-1, which prompted the SHA-3 competition when weaknesses in SHA-1 were first discovered (as they could conceivably have been present in SHA-2 as well). As it turns out, SHA-2 appears to be resistant to the attacks found thus far. SHA-3 (originally named Keccak) is built on an entirely different foundation (called a sponge function), so it is unlikely that any attack against SHA-1 will be relevant to SHA-3. However, sponge functions are a relatively new idea, and weaknesses in the basic principles could conceivably be found in the future, as could weaknesses in the Keccak algorithm specifically.
jwilk 7y ago
Link to the GnuPG commit: https://dev.gnupg.org/rGedc36f59fcfc https://dev.gnupg.org/rGedc36f59fcfc
eerrt 7y ago
The full paper is https://eprint.iacr.org/2020/014.pdf https://eprint.iacr.org/2020/014.pdf if anyone is interested
silasdavis 7y ago
Who paid for this?
- jessant 7y ago
  Judging by the paper[1], I would say any or all of Inria, Nanyang Technological University, and Temasek Laboratories. [1] https://eprint.iacr.org/2020/014.pdf https://eprint.iacr.org/2020/014.pdf
nneonneo 7y ago
So to be clear about what this is (because the website doesn’t quite clarify): this collision lets you pick two different prefixes P1, P2, then calculates some pseudorandom data C1, C2 such that SHA1(P1+C1) = SHA1(P2+C2). The length extension property of SHA1 (and MD5) means that now SHA1(P1+C1+X) = SHA1(P2+C2+X) for any X. A similar attack (which requires only a few hours on modest hardware nowadays) has been known for a long time for MD5, but this is the first time it’s been demonstrated for SHA-1. The previous attack, called Shattered (https://shattered.io https://shattered.io) was a regular collision, that is, they chose a single prefix P and found different C1, C2 such that SHA1(P+C1) = SHA1(P+C2). This can also be length extended, so that SHA1(P+C1+X) = SHA1(P+C2+X). However, this attack is more limited because there is little to no control over the pseudorandom C1 and C2 (the only differing parts of the messages). With a chosen prefix collision, though, things are way worse. Now you can create two documents that are arbitrarily different, pad them to the same length, and tack on some extra blocks to make them collide. Luckily, the first collision should have already warned people to get off of SHA1. It’s no longer safe to use for many applications. (Note, generally for basic integrity operations it might be OK since there’s no preimage attack, but I’d still be a bit wary myself).
- tptacek 7y ago
  Squeamish Osssifrage's answer to this Crypto Stack Exchange question does a predictably excellent job of putting these attacks in context. https://crypto.stackexchange.com/questions/60640/does-shattered-actually-show-sha-1-signed-certificates-are-unsafe https://crypto.stackexchange.com/questions/60640/does-shatte...
  - ReidZB 7y ago
    Agreed. It's a great loss to the community that they have decided to step away from Stack Exchange: https://crypto.meta.stackexchange.com/questions/1361/im-leaving-crypto-se-indefinitely https://crypto.meta.stackexchange.com/questions/1361/im-leav...
    - gowld 7y ago
      * that the owners of Stack Exchange drove them and others away.
jVinc 7y ago
So how would someone go about gaining more than 45k USD in profit from a single case of using the chosen-prefix collision? Not being candid here, I am honestly curious here. I'd guess that even in situations where you somehow get a signed e-mail sent off spoofing a CEO saying "Please pay these guys 50k$" the actual payout seems unlikely and that puts the attacker 45k in the red. But maybe there are some obvious avenues of abuse that I'm missing, or is this more a case of "In a decade it will become economical to abuse this for profit"?
- racingmars 7y ago
  I'm familiar with an organization that lost about $750,000 because someone spoofed an email from the CEO to the CFO asking to wire money to an account. The CFO fell for it. AFAIK, the money was never recovered (nor was the CFO fired... it was all just chalked up to 'the cost of doing business'). That was with NO crypto/signature spoofing involved... if the CFO has now been trained to not act on large dollar amount requests from the CEO without at least checking a digital signature... perhaps the CFO would be more likely to fall for it now since he has been "trained" that cryptographic signatures are a sign of authenticity?
  - jVinc 7y ago
    $750,000 is a lot of money, but seeing as some people will act on emails without signature, and that you would effectively have to invest that amount up front in order to attempt this attack on 15 individuals, and then hope that at least one falls for it just to make it even, I can't really see this being a viable attack vector. Maybe if the cost goes down significantly to the $100-$1000 range it might be something you would see in the wild.
- biggestdecision 7y ago
  At the current time this is much more likely to be abused for political/intelligence reasons, than for profitable criminal reasons. Sneaking a malicious commit with the same signature into a git repository for example.
- DaiPlusPlus 7y ago
LennyWhiteJr 7y ago
The root certificate authority for my company's Active Directory is signed using a sha1 hash. What are the practical implications of this chosen collision? How do I convince my IT department to update our CA to sha256?
- tatersolid 7y ago
  The signatures on trusted root certs do not matter and are ignored; it’s the public key you’re trusting. Many public trusted CA certain are self-signed with SHA-1. These keys sign using SHA-256
edwintorok 7y ago
> security level 2 (defined as 112-bit security) in the latest release (Debian Buster); this already prevents dangerous usage of SHA-1 FWIW this doesn't apply to Fedora currently, because it has a patch that re-enables SHA-1 in security level 2 in non-FIPS mode: https://src.fedoraproject.org/rpms/openssl/blob/master/f/openssl-1.1.1-seclevel.patch https://src.fedoraproject.org/rpms/openssl/blob/master/f/ope...
GhettoMaestro 7y ago
Lol and my engineering called me paranoid when I made us go from SHA1 to SHA256 (it was trivial for us). Guess I’m having the chuckle now.
perl4ever 7y ago
Let's say that you know that someone stores documents by SHA, and silently overwrites collisions. Is there any way this would help to deceive them after being forced to give them your data? It seems like once the data is out of your control, you can't match an existing SHA, and if you created a pair of documents that match SHAs, you can't predict which one will be overwritten.
tinus_hn 7y ago
Are there any crypto currencies that use SHA-1 for their proof of work?

928 points by ynezz 7y ago

0x0 7y ago

Q: Does this make it even more urgent for git to move to a different hash?

LeonM 7y ago
A: (from the article) SHA-1 has been broken for 15 years, so there is no good reason to use this hash function in modern security software. Attacks only get better over time, and the goal of the cryptanalysis effort is to warn users so that they can deprecate algorithms before the attacks get practical. We actually expect our attack to cost just a couple thousand USD in a few years.
- pathseeker 7y ago
  That's not a relevant answer. Git's use-case is very specific and it's quite possible that this attack won't be relevant. It needs analysis. >no good reason to use this hash function in modern security software This argument conveniently ignores the cost to switching existing software (i.e. it's completely detached from reality).
EGreg 7y ago
It may, because now an attacker can replace code with arbitrary other valid code as long as developers are willing to ignore the long weird random comment at the end ;-) I’m gonna say many developers will not care but and many compilers will not care either. So yeah, Linus’ main deterrent reason (code won’t compile) doesn’t apply anymore. HOWEVER! 1. A chosen-prefix attack still needs to compute TWO suffixes m1 and m2 so that h(a1+m1) = h(a2+m2). This does NOT mean that given a1 and a2 you can find a single m2 so that h(a1) = h(a2+m2). So that ONLY THE ORIGINAL AUTHOR OF THE COMMIT could spoof their own commit, by preparing in advance and attaching a long and weird comment in the end. And you could build tools to watch out for such commits in the first place 2. If git had used HMAC based on SHA1 then it would have been fine, even after this attack has become feasible. 3. Furthermore, it is likely still kinda fine because Merkle Trees have nodes referencing previous nodes. You’d have to spoof every historical node as well, to push malicious code. BitTorrent also requires computers to supply an entire merkle branch when serving file chunks. Maybe someone can elaborate on this.
- rkangel 7y ago
  If you look in this 2017 (https://marc.info/?l=git&m=148787047422954 https://marc.info/?l=git&m=148787047422954) email from Linux, he discusses how git also encodes length. That would mean that you need a collision of the same length and the right functionality, so you can't just append data.
  - toyg 7y ago
    Now that you can arbitrarily produce collisions, the second step is easy enough for a skilled and well-funded attacker.
rkangel 7y ago
It adds to the weight of the argument, but there isn't a big issue. This article (https://www.zdnet.com/article/linus-torvalds-on-sha-1-and-git-the-sky-isnt-falling/ https://www.zdnet.com/article/linus-torvalds-on-sha-1-and-gi...) and the linked email (https://marc.info/?l=git&m=148787047422954 https://marc.info/?l=git&m=148787047422954) both seem to still apply.
- groovybits 7y ago
  Further details as to why Torvalds is not concerned: From the email... "I haven't seen the attack yet, but git doesn't actually just hash the data, it does prepend a type/length field to it. That usually tends to make collision attacks much harder, because you either have to make the resulting size the same too, or you have to be able to also edit the size field in the header." [...] "I haven't seen the attack details, but I bet (a) the fact that we have a separate size encoding makes it much harder to do on git objects in the first place (b) we can probably easily add some extra sanity checks to the opaque data we do have, to make it much harder to do the hiding of random data that these attacks pretty much always depend on."
  - wyldfire 7y ago
    I think those are pretty practical approaches. But it sounds as if the cost of changing the hash algorithm is high. What are the impacts of this change? How many things would break if git just changed the algorithm with each new release? Does git assume that the hash algorithm is statically given to be SHA-1 or are there qualifiers on which algorithm is enabled/permitted/configured?
    - paulddraper 7y ago
      After making the actual code change, the biggest problem is breaking compatibility with decades of tools in the ecosystem that rely on historically consistent SHA-1 hashes. Git is moving to a flexible hash though. [1] [1] https://stackoverflow.com/questions/28159071/why-doesnt-git-use-more-modern-sha/47838703#47838703 https://stackoverflow.com/questions/28159071/why-doesnt-git-...
mikepurvis 7y ago
There is a migration path to SHA-256, see a good summary here: https://stackoverflow.com/a/47838703/109517 https://stackoverflow.com/a/47838703/109517 See a previous discussion here, regarding Linus's position on this in 2017: https://news.ycombinator.com/item?id=13719368 https://news.ycombinator.com/item?id=13719368
rom1v 7y ago
What happens if you actually get a SHA-1 collision in git? -> https://stackoverflow.com/questions/9392365/how-would-git-handle-a-sha-1-collision-on-a-blob https://stackoverflow.com/questions/9392365/how-would-git-ha... (This does not answer your question, but is still interesting.)
mzs 7y ago
https://news.ycombinator.com/item?id=21985773 https://news.ycombinator.com/item?id=21985773

deleted 7y ago

[deleted]

ebg13 7y ago

Quick question about the "What should I do" section. It says "use instead SHA-256". Isn't SHA-512 both better and faster on modern hardware?

Spooky23 7y ago
SHA-256 is on the approved FIPS lists and are faster on 32-bit operating systems, which were surprisingly common in enterprise environments until recently. People tend to be conservative in making changes for stuff like this, and don't do so until forced.
akvadrako 7y ago
I believe so also. Specifically, SHA-512/256 seems to be a better choice by almost every metric except 32-bit hashing speed.
LeonM 7y ago
Depends on your definition of 'better'. Theoretically SHA-512 is harder to brute force than SHA-256, but 256 bits is already extremely strong, so really there is no practical safety benefit of SHA-512 over SHA-256. On 64-bit capable processors SHA-512 has a slight performance gain over SHA-256, but only on larger inputs. However, the digest of SHA-512 is twice the size, so what you gain in processing time, you loose in storage.
- quotemstr 7y ago
  You can truncate the SHA-512 digest down to 256 bits though. Cryptographic hash functions mix well and don't suffer from the truncation (except to the extent that the truncated digest is shorter, of course). You don't necessarily need more storage (after hashing completes) just because you're using a new hash function.
- jlokier 7y ago
  > but 256 bits is already extremely strong The strength of hashes like SHA-256 doesn't just come from the number of output bits. The 256 bits there is relevant for brute force attacks, but not more sophisticated attacks that take into account the internal structure of the hash algorithm, and in some cases "weak" values. SHA-512 performs more "rounds" of computation than SHA-256. Although it's impossible to compare two different hashes on rounds alone, in general a large number of rounds of the same type of hash decreases the likelihood of non-brute-force attacks finding a collision. If you look at the literature for attacks on hashes, they will often say they could do it for a certain number of rounds, and that number increases over time as new methods are discovered. The number of rounds in the hash design is chosen with this in mind, trying to balance being more than sufficient for future attacks yet not too slow.

umvi 7y ago

Is "a Shambles" British or something? I've always heard it as "in Shambles"

cpach 7y ago
AFAICT ”a shambles” is correct usage. See https://brians.wsu.edu/2016/05/24/in-shambles-a-shambles/ https://brians.wsu.edu/2016/05/24/in-shambles-a-shambles/
- OGWhales 7y ago
  Neat, but don't know if I can switch because of how it rolls off the tongue.
  - umvi 7y ago
    It got easier for me once I learned that "shambles" is a noun that is a synonym of "slaughterhouse". Once I learned that, I emphasized shambles slightly differently as I rolled the phrase off my tongue. "SHA-1 is a slaughterhouse" "SHA-1 is a shambles"
    - OGWhales 7y ago
      Yeah I got that from the link, I had no idea before. However, I feel like if it was "is a shamble" it would make more sense to me than "is a shambles".
- umanwizard 7y ago
  Downvoted. There's no ISO standard for English, since language is a social phenomenon. "Correct" language is whatever the community of speakers uses in practice, not what someone claims is correct in a blog post (or even a book).
  - simias 7y ago
    And the linked article showed you that, in practice, "a shambles" is perfectly correct English. It is therefore correct in a descriptivist sense. Beyond that prefixing your comment by "downvoted" is frankly silly and only serves to derail the conversation IMO.

rustybolt 7y ago

> By renting a GPU cluster online, the entire chosen-prefix collision attack on SHA-1 costed us about 75k USD. So they just decided to try their attack and spend two years worth of salary on it?? That's crazy.

oppositelock 7y ago
That's dirt cheap for a government actor, and we can be sure that the big governments have been doing this sort of attack for years.
- rustybolt 7y ago
  It's a lot of money for an academic researcher.
  - progval 7y ago
    Researchers in applied fields other than CS spend this kind of money on a regular basis. eg. https://www.quora.com/What-are-the-costs-for-lab-rat-testing-in-the-US https://www.quora.com/What-are-the-costs-for-lab-rat-testing...
  - CydeWeys 7y ago
    Is it? Multi-million grants are common in academia. A lot of research is expensive. When I worked in a lab the materials alone for a single day's experiment would frequently run into the thousands. E.g. the total human RNA samples we used cost many thousands of dollars per milligram. Admittedly this is a different field, but it's still academia.
    - klmr 7y ago
      > Multi-million grants are common in academia. Not in the way you explain. Multi-million dollar grants are usually awarded over multiple years, and pay for multiple researchers’ salaries, as well as other resources, some of which are expected to outlast the project (e.g. microscopes, or hardware for databases). Burning 75k on a single experiment (which is effectively what was done here) is rare. Note that this is true even for current hot topics such as biomedical (e.g. cancer) research, for which vast chunks of the federal budget have been allocated in multiple countries. Obtaining similar sums in less sexy fields is much harder. And even in biomedical research, multi-million dollar grants are considered large. Most grants are much smaller, they just don’t get talked about as much. Since you mention human RNA samples I assume you know this. You mention the per-milligram cost but this is pretty misleading if you mean to imply that “milligram” is somehow little, because it isn’t: yes, the samples are tiny (≤1 µg of RNA is more typical than milligrams!), but so what? It’s not like we need more.

bjornsing 7y ago

> We note that classical collisions and chosen-prefix collisions do not threaten all usages of SHA-1. In particular, HMAC-SHA-1 seems relatively safe, and preimage resistance (aka ability to invert the hash function) of SHA-1 remains unbroken as of today. Nice to see this bit of intellectual honesty. Would be even nicer if they had explained what that means in terms of PGP keys.

_notreallyme_ 7y ago
It means if someone you want to impersonate uses the Web Of Trust, i.e. their key is signed by other people whose keys have been signed the same way, you can generate a GPG key for which all of these signatures are still valid. For example, if an attacker gains access to a victim email account, they could send to their contacts a "trusted" key (as explained above) and then use it to send signed documents to the victim's contacts. This would defeat an adversary "paranoid" enough to check a key signature, but not paranoid enough to obtain a clear explaination/confirmation of why the key changed...
- bjornsing 7y ago
  > It means if someone you want to impersonate uses the Web Of Trust, i.e. their key is signed by other people whose keys have been signed the same way, you can generate a GPG key for which all of these signatures are still valid. No... > For example, if an attacker gains access to a victim email account, they could send to their contacts a "trusted" key (as explained above) and then use it to send signed documents to the victim's contacts. Ok... But in this scenario the attacker has the victim’s new private key, so they don’t need to create a collision (using OP). They can just use the new private key to sign the documents. Right?
  - _notreallyme_ 7y ago
    > No... Why ? > in this scenario the attacker has the victim’s new private key You don't want to keep your private key in cleartext on your email provider servers, do you ?

emilfihlman 7y ago

>Can I try it out for myself? Since our attack on SHA-1 has pratical implications, in order to make sure proper countermeasures have been pushed we will wait for some time before releasing source code that allows to generate SHA-1 chosen-prefix collisions. Sigh. Again with this idiocy. All instances where the adversary is capable of launching this attack financially mean they also have the capability to write the exploit themselves.

DarkWiiPlayer 7y ago
It does make sense. Targets worth attacking at a high financial cost will most likely be the first to take measures against this attack. The kind of target that takes a longer time to switch most likely isn't worth attacking unless it's a very cheap and fast operation. And the longer you spend developing an exploit, the less viable the attack will become.
lm28469 7y ago
> All instances where the adversary is capable of launching this attack financially mean they also have the capability to write the exploit themselves. Iran will eventually create a nuclear bomb, why don't we gave them one now, it's the same thing isn't it ?

whatshisface 7y ago

>A countermeasure has been implemented in commit edc36f5, included in GnuPG version 2.2.18 (released on the 25th of November 2019): SHA-1-based identity signatures created after 2019-01-19 are now considered invalid. Since SHA-1 was always possible to break, and since NSA probably gets access to big computers and sophisticated techniques before researchers, why doesn't this invalidate every SHA-1 signature ever made and not just ones from last year?

Boulth 7y ago
Actually it's even worse than that: signature creation time is added by the signer so it's totally under control of the attacker. IMHO all SHA-1 based signatures should be ignored.
- im3w1l 7y ago
  The signer is assumed to be trustworthy. That's why we care for their signature in the first place. It's the sign-ee that is presumed to be the attacker.
- NieDzejkob 7y ago
  In this case, signature creation time isn't under control of the attacker. The attack scenario being considered is that Mallory can convince Alice to sign a key K1, provided by Mallory, such that it looks like Alice signed K2. The party creating the signature is honest here.
  - tialaramex 7y ago
    The problem is that the dates are part of the document being signed. Rather than keys, Alice will typically sign a document (e.g. an X.509 to-be-signed certificate) Mallory creates two documents, the legitimate seeming document A (a to-be-signed certificate Alice willingly signs) and document B (the content of which is controlled by Mallory to an extent depending on the details of the collision). In document A I'm sure Alice will insist on the date being roughly correct so you'd detect that. But Alice never sees document B, she isn't aware it exists, so it can specify any date, including one chosen not to set off alarms. For the Web PKI we were triply safe because: 1. We told Alice (the public CAs) never to sign anything at all with the dangerous algorithm after a set date. So long as Mallory wasn't able to develop and use a collision before that date and Alice did as she was told‡ this would be safe in perpetuity. 2. We already had a countermeasure in the documents, very early in each Web PKI X.509 certificate is the Serial Number, if you look at yours you'll notice it's a crazy huge number and seemingly not "serial" in any sense. It's random. Can't do a chosen prefix collision attack if you can't choose the prefix. 3. Since no more new documents were being signed clients in the Web PKI were able to stop recognising these signatures thus permanently ensuring the attack was impossible within about 18 months. ‡ A very small number of exceptions were explicitly granted, and a similarly small number of exceptional cases occurred for which no permission was asked. All investigated to everybody's satisfaction. As you may see if you poke around in the demo documents from this article, a collision document may not jump out as problematic from a crowd but it certainly isn't so innocuous as to survive careful scrutiny, and with such a small number of exceptions to look at this scrutiny was possible in a way it never would be for the wider Web PKI.

notlukesky 7y ago

> Responsible Disclosure We have tried to contact the authors of affected software before announcing this attack, but due to limited resources, we could not notify everyone. Is there a list of affected software out there?

CiPHPerCoder 7y ago
https://github.com/search?q=sha1&type=Code https://github.com/search?q=sha1&type=Code https://github.com/search?q=sha-1&type=Code https://github.com/search?q=sha-1&type=Code
adminss 7y ago
"> <script>alert()</script>

tambourine_man 7y ago

This kind of thing always brings me down a bit. It's not rational, but it does. I mean I truly admire these folks skills, the math involved is obviously remarkable. But I think the feeling is related to not being able to rely on anything in our field. Hard to justify going to the trouble of encrypting your backup. 10 years from now, it might be as good as plain text. It's not security only, nothing seems to work in the long term. Imagine an engineer receiving a call at midnight about his bridge because gravity changed during daylight saving in a leap year. That's our field.

deleted 7y ago
[deleted]
wyday 7y ago
>> "Hard to justify going to the trouble of encrypting your backup." Huh? If you're "encrypting" using SHA, I've got some bad news about those backups of yours.
- tambourine_man 7y ago
  I'm refering to not being able to rely on encryption in the long term.
  - vbrandl 7y ago
    Hashing is a separate problem from encryption. There is no proof that one way functions (the idea behind hashing) even exist (by proving this, you would actually prove P!=NP, IIRC). Encryption has a slightly better track record of being broken. AES still holds its promise and is also secure against quantum computing (you might want longer keys, but that's it). And if you want really, provably unbreakable encryption, there is still OTP. But then you'd need a key, that is as long as the data you want to encrypt.
    - blattimwind 7y ago
      The best known attack against AES reduces attack complexity by about two bits over brute force. Given the history of block ciphers, the idea that AES might not be broken in this life time is not uncommon.

mehrdadn 7y ago

> SHA-1 has been broken for 15 years, so there is no good reason to use this hash function in modern security software. Why are cryptographers always exaggerating things and so out of touch with reality? The first actual collision was like 3 years ago. It's not like the world has been on fire in the meantime, and it's not like SHA-1 is broken for every single possible usage even now. And why the nonsense with "no good reason"? Obviously performance is one significant consideration for the unbroken use cases. Do they think painting a different reality than the one we live in somehow makes their case more compelling?

ewidar 7y ago
As stated, they are talking about "modern security software". So yeah, if you are building/improving software that has a clear focus on security, you should use a secure hash. Seems only natural to me.
PeterisP 7y ago
Past experience and documents that ceased being classified shows that serious attackers (e.g. NSA) are at least decade ahead of what's publicly known in cryptography; i.e. we know that pretty much always when new relevant groundbreaking math was published, the classified cryptographers had known that for a long, long time already. So if this attack is developed today, then you should assume that NSA has been able to execute this attack for at least ten years already whenever it suited them, including mass surveilance of random not-that-important people. The same applies for the collisions - the first published collision was 3 years ago, but we should assume that that's definitely not the first; I mean, only a minority of the world's cryptography researchers participate in the public, open, academic community; the majority of them are employed with a condition that they won't get to publish anything important. And since we know for the last ten years that such attacks were possible, there's no reasonable reason why SHA-1 would have been considered as safe.
- dweekly 7y ago
  Are there materials that show a ten year head start?

deleted 7y ago

[deleted]

jlokier 7y ago

Just a curiosity, since people are talking about Git still using SHA-1 (despite work on SHA-256 since 2017). I see that Git doesn't actually use SHA-1 any more, it uses "hardened SHA-1": https://stackoverflow.com/questions/10434326/hash-collision-in-git/43355918#43355918 https://stackoverflow.com/questions/10434326/hash-collision-...

FactolSarin 7y ago
How would an attack on a git repo work? You create a repo with identical hashes but different content and next time the user clones from scratch they get your modified version?
- flatiron 7y ago
  yeah my thoughts about git are similar. look at the two messages they have an an example: Key is part of a collision! It's a trap!yE'NsbK#ދW]{1gKmCx's/vr| -pJO_,1$)uB1qXv#U)9ESU;p~0G:Y ݕbBIjFra눰3&t'lB_!h5M([,˴QMK#|o5pv|i,+yYpݍD7_Rf\'GUZ,ϵdvAYAugV=Lk8_E 2 +nolBtxXoQt&+?Y3LP:'Qt(,ۛuԪWJm:A"M6<|B4kVv̨ޠA=M+m%殺j5N|EMA\Ed- s&@u@:a?pq^Xf0U?R} and Practical SHA-1 chosen-prefix collision!'lka}vbI3,·W]Ǟ+gK}Cxs/v&r| }-hRJO_ rO̳;bzC ,1&uRP-MXrU3aO;pr0:sY'2 l&r7#(A{oNyCJ_W,8 əbحBYީpFr2a8#&t+n_15q(_,ˤQMW#hzYMgVV=L,kO0E*N +oc@BpXoᯖd&?+?[{3LвP&'U t ( WJÏm\:A"6>>|SB(k;Vv̨ޠ^A=Y ;om%j-|cUAAۜEТ&@o@:La3psH^eXf0QJm ݶd they have the same sha1sum, but in all practicality its nonsense since both messages are pure trash. you couldn't have malicious C code that would have the same hash as non malicious C code in this example
  - saalweachter 7y ago
    Isn't that like incredibly simple? Dump your garbage string behind a // or inside an #if 0, restrict the garbage string character set to characters which will not disturb that, and your compiler will whistle while it works.

HashThis 7y ago

Quick, everyone bend over and cover your hashes

noja 7y ago

Is a collision impossible with two hashes, each using a different algorithm?

femto113 7y ago
Not impossible, but assuming there's not a mathematical flaw that affect both algorithms the difficulty is roughly the product of the difficulty of finding a collision in each. AFAIK no one has come up with a joint collision for MD5+SHA1 despite collisions in each being practical for several years.
- noja 7y ago
  So should we do that, as well as keep finding new algorithms?
  - femto113 7y ago
    Concatenating two hashes is an algorithm. Mathematically concatenating two 128 bit hashes is not any stronger than a single 256 bit hash (and is likely weaker), but if it’s all you have (or all you can afford to compute) two weak hashes is definitely much better than one.
    - noja 7y ago
      Why is concatenating two 128 bit hashes (each with a different algorithm) not stronger than a single-algorithm 256 bit hash?
      - femto113 7y ago
        One reason is that it is theoretically possible to use memory instead of computation to attack the combined hashes by pre-generating a large number of collisions under one algorithm and then simply checking those using the other one, which means you don't need to do both algorithms for every check. Can't say for sure if that works out cheaper in terms of money but if the memory is available it could definitely save a lot of time. Another reason is that for any given hash its theoretical maximum strength against any attack will be less than or equal to its bit length, but the practical strength always trends lower over time as attacks are found, and having two algorithms to attack increases the chances of finding flaws.

nvartolomei 7y ago

I assume there was a lot of work (read money) put in those collision attacks rather than it being discovered by accident. I'm wondering who is sponsoring this work and for what purpose? The argument about proving that an algorithm is broken and working on better cryptography wouldn't suffice in this case, as issues were shown before that. Here the purpose was to make the attack cheaper?

tptacek 7y ago
That is not how cryptographic research works, at all.

newscracker 7y ago

General questions: (edit: these are indeed general questions, not just about SHA1) Has anyone else been worried about data deduplication done by storage and/or backup systems, considering that they usually use hashes to detect data blocks that are "the same" (without additional metadata) and avoid storing those "duplicate data blocks" again? Doesn't this seem far worse when you also consider that systems like Dropbox deduplicate data across all their users (expanding the footprint for collisions)? Are there any research papers/articles/investigations about this?

MichaelMoser123 7y ago
are there any systems that do sha-1 for dedup? I am only aware of sha-256.
- deleted 7y ago
  [deleted]
- munificent 7y ago
  Git?
  - deleted 7y ago
    [deleted]
  - MichaelMoser123 7y ago
    git computes the sha1 checksum over the header that includes the length + the file data; also checks the length in the header as well as the the hash; Linus says that it would be less practical to find a collision that has the same length as the original data; I guess at some stage even that might become possible.
- fanf2 7y ago
  Subversion's dedup was broken by the http://shattered.io/ http://shattered.io/ SHA-1 collision in 2017 https://medium.com/@hyrum/shattered-subversion-7edea4ba289c https://medium.com/@hyrum/shattered-subversion-7edea4ba289c

femto113 7y ago

While a meaningful accomplishment, suggesting the algorithm is in a "shambles" seems hyperbolic to me. For one thing there's a non-trivial practical leap between formulating two colliding identities and forging an existing one, and for another this was only modestly better than a pure brute force attack. If anything I'm somewhat reassured by the idea that it still costs $40,000+ of GPU time to pull something like this off while doing the same with MD5 is feasible on a mobile phone.

RcouF1uZ4gsC 7y ago

Does this affect Git? I believe it uses SHA-1 for commits. Is it possible to use this attack to add malicious code to a git repository without changing the hashes for the commits?

LennyWhiteJr 7y ago
Potentially. GitHub at least already started collision detection after Shattered was published. https://github.blog/2017-03-20-sha-1-collision-detection-on-github-com/ https://github.blog/2017-03-20-sha-1-collision-detection-on-...

kibwen 7y ago

Out of curiosity, can anyone explain in layman's terms the differences in design that make SHA-1's successors immune to the known attacks against SHA-1? Ultimately was this the result of an apparent flaw in SHA-1 that only became obvious in retrospect, or was it something totally unforeseeable?

knorker 7y ago
Partly this: Number of bits. This attack is almost 2^64, and SHA-1 is 160 bits. All else being equal (big big if) that means sha256 is 102 bits, meaning 362703572709.30493 times more expensive. Or about $16321 trillion USD.
Zaak 7y ago
SHA-2 is based on similar techniques to those in SHA-1, which prompted the SHA-3 competition when weaknesses in SHA-1 were first discovered (as they could conceivably have been present in SHA-2 as well). As it turns out, SHA-2 appears to be resistant to the attacks found thus far. SHA-3 (originally named Keccak) is built on an entirely different foundation (called a sponge function), so it is unlikely that any attack against SHA-1 will be relevant to SHA-3. However, sponge functions are a relatively new idea, and weaknesses in the basic principles could conceivably be found in the future, as could weaknesses in the Keccak algorithm specifically.

jwilk 7y ago

Link to the GnuPG commit: https://dev.gnupg.org/rGedc36f59fcfc https://dev.gnupg.org/rGedc36f59fcfc

eerrt 7y ago

The full paper is https://eprint.iacr.org/2020/014.pdf https://eprint.iacr.org/2020/014.pdf if anyone is interested

silasdavis 7y ago

Who paid for this?

jessant 7y ago
Judging by the paper[1], I would say any or all of Inria, Nanyang Technological University, and Temasek Laboratories. [1] https://eprint.iacr.org/2020/014.pdf https://eprint.iacr.org/2020/014.pdf

nneonneo 7y ago

So to be clear about what this is (because the website doesn’t quite clarify): this collision lets you pick two different prefixes P1, P2, then calculates some pseudorandom data C1, C2 such that SHA1(P1+C1) = SHA1(P2+C2). The length extension property of SHA1 (and MD5) means that now SHA1(P1+C1+X) = SHA1(P2+C2+X) for any X. A similar attack (which requires only a few hours on modest hardware nowadays) has been known for a long time for MD5, but this is the first time it’s been demonstrated for SHA-1. The previous attack, called Shattered (https://shattered.io https://shattered.io) was a regular collision, that is, they chose a single prefix P and found different C1, C2 such that SHA1(P+C1) = SHA1(P+C2). This can also be length extended, so that SHA1(P+C1+X) = SHA1(P+C2+X). However, this attack is more limited because there is little to no control over the pseudorandom C1 and C2 (the only differing parts of the messages). With a chosen prefix collision, though, things are way worse. Now you can create two documents that are arbitrarily different, pad them to the same length, and tack on some extra blocks to make them collide. Luckily, the first collision should have already warned people to get off of SHA1. It’s no longer safe to use for many applications. (Note, generally for basic integrity operations it might be OK since there’s no preimage attack, but I’d still be a bit wary myself).

tptacek 7y ago
Squeamish Osssifrage's answer to this Crypto Stack Exchange question does a predictably excellent job of putting these attacks in context. https://crypto.stackexchange.com/questions/60640/does-shattered-actually-show-sha-1-signed-certificates-are-unsafe https://crypto.stackexchange.com/questions/60640/does-shatte...
- ReidZB 7y ago
  Agreed. It's a great loss to the community that they have decided to step away from Stack Exchange: https://crypto.meta.stackexchange.com/questions/1361/im-leaving-crypto-se-indefinitely https://crypto.meta.stackexchange.com/questions/1361/im-leav...
  - gowld 7y ago
    * that the owners of Stack Exchange drove them and others away.

jVinc 7y ago

So how would someone go about gaining more than 45k USD in profit from a single case of using the chosen-prefix collision? Not being candid here, I am honestly curious here. I'd guess that even in situations where you somehow get a signed e-mail sent off spoofing a CEO saying "Please pay these guys 50k$" the actual payout seems unlikely and that puts the attacker 45k in the red. But maybe there are some obvious avenues of abuse that I'm missing, or is this more a case of "In a decade it will become economical to abuse this for profit"?

racingmars 7y ago
I'm familiar with an organization that lost about $750,000 because someone spoofed an email from the CEO to the CFO asking to wire money to an account. The CFO fell for it. AFAIK, the money was never recovered (nor was the CFO fired... it was all just chalked up to 'the cost of doing business'). That was with NO crypto/signature spoofing involved... if the CFO has now been trained to not act on large dollar amount requests from the CEO without at least checking a digital signature... perhaps the CFO would be more likely to fall for it now since he has been "trained" that cryptographic signatures are a sign of authenticity?
- jVinc 7y ago
  $750,000 is a lot of money, but seeing as some people will act on emails without signature, and that you would effectively have to invest that amount up front in order to attempt this attack on 15 individuals, and then hope that at least one falls for it just to make it even, I can't really see this being a viable attack vector. Maybe if the cost goes down significantly to the $100-$1000 range it might be something you would see in the wild.
biggestdecision 7y ago
At the current time this is much more likely to be abused for political/intelligence reasons, than for profitable criminal reasons. Sneaking a malicious commit with the same signature into a git repository for example.
DaiPlusPlus 7y ago

LennyWhiteJr 7y ago

The root certificate authority for my company's Active Directory is signed using a sha1 hash. What are the practical implications of this chosen collision? How do I convince my IT department to update our CA to sha256?

tatersolid 7y ago
The signatures on trusted root certs do not matter and are ignored; it’s the public key you’re trusting. Many public trusted CA certain are self-signed with SHA-1. These keys sign using SHA-256

edwintorok 7y ago

> security level 2 (defined as 112-bit security) in the latest release (Debian Buster); this already prevents dangerous usage of SHA-1 FWIW this doesn't apply to Fedora currently, because it has a patch that re-enables SHA-1 in security level 2 in non-FIPS mode: https://src.fedoraproject.org/rpms/openssl/blob/master/f/openssl-1.1.1-seclevel.patch https://src.fedoraproject.org/rpms/openssl/blob/master/f/ope...

GhettoMaestro 7y ago

Lol and my engineering called me paranoid when I made us go from SHA1 to SHA256 (it was trivial for us). Guess I’m having the chuckle now.

perl4ever 7y ago

Let's say that you know that someone stores documents by SHA, and silently overwrites collisions. Is there any way this would help to deceive them after being forced to give them your data? It seems like once the data is out of your control, you can't match an existing SHA, and if you created a pair of documents that match SHAs, you can't predict which one will be overwritten.

tinus_hn 7y ago

Are there any crypto currencies that use SHA-1 for their proof of work?