46 ms·

Announcing the first SHA-1 collision

• wickedlogic 10y ago
  Would providing multiple SHA-1's from both the whole and N subsections (or defined regions) of the byte stream make this impractical... or at this point is the cost just going to drop and make this not relevant? Like a NURBS based sudoku multi-hash...
• divbit 10y ago
  So good timing to have just started working on a sha3 version of git I guess...
  • deleted 10y ago
    [deleted]
  • VMG 10y ago
    Funny, just yesterday I thought about what would be necessary to change and deploy this. Apparently the SHA1 hash wasn't designed as a security feature, but I would not be surprised if it is being abused as one today.
    • daenney 10y ago
      It's not used as a security feature in Git (though SHA-1 is designed as a cryptographically secure hash) but Git commit singing does use SHA-1 b/c GPG.
      • VMG 10y ago
        It's not supposed to be used as a security feature, but I think some tools use it as such. Dependency management tools that reference by SHA-1 hash come to mind. Of course they should have used other primitives all along, but we know how it is..
    • divbit 10y ago
      Let me know if you want to help- Ive just forked a couple repos and started writing out some notes
• deleted 10y ago
  [deleted]
• deleted 10y ago
  [deleted]
• deleted 10y ago
  [deleted]
• zurn 10y ago
  Anyone have back of the envelope calculations for the cost of the CPU and GPU time?
  • nickez 10y ago
    On the shattered webpage: This attack required over 9,223,372,036,854,775,808 SHA1 computations. This took the equivalent processing power as 6,500 years of single-CPU computations and 110 years of single-GPU computations.
    • cphoover 10y ago
      So... you are saying I couldn't do this on my Macbook's Core i7?
      • adrianN 10y ago
        If you're very careful with your machine maybe you can make it last 6500 years, but I think that is way outside the expected lifetime of a mobile CPU under full load.
      • deleted 10y ago
        [deleted]
    • sp332 10y ago
      Hm, according to https://gist.github.com/epixoip/a83d38f412b4737e99bbef804a270c40 https://gist.github.com/epixoip/a83d38f412b4737e99bbef804a27... a GTX 1080 can do 8.54 billion SHA-1 hashes per second. That puts it at only 34.2 years to compute 9.22*10^18 hashes.
  • deleted 10y ago
    [deleted]
• ktta 10y ago
  Here's a good blog about how SHA-1 works: http://www.metamorphosite.com/one-way-hash-encryption-sha1-d.. http://www.metamorphosite.com/one-way-hash-encryption-sha1-d.... The biggest risk I see with this is how torrents are affected: https://en.wikipedia.org/wiki/Torrent_poisoning https://en.wikipedia.org/wiki/Torrent_poisoning There's also a problem with git, but I don't see it being that as susceptible as torrents: http://stackoverflow.com/a/34599081/6448137 http://stackoverflow.com/a/34599081/6448137
  • rocqua 10y ago
    What about git? This makes it technically possible to get a backdoored linux repo with the same commit hash. EDIT: this is wrong, it's not a second pre-image attack only a collision attack. That is, you can create 2 git repositories with the same commit hash, but not a git repo that matches an already existing repo. In other words, you can create 2 things with the same hash, but can't control what that hash actually is. You might be able to fashion 2 commits to the linux repo with the same hash but a different modification though.
    • ktta 10y ago
      https://news.ycombinator.com/item?id=13713603 https://news.ycombinator.com/item?id=13713603
    • rntz 10y ago
      EDIT: My original comment was wrong. Git commit signing apparently only signs the commit hash itself, so it's only as trustworthy as the integrity of the hash. However, see also other comments which point out that this isn't a pre-image attack; you can't find a collision for a given thing (in this case, the linux kernel); rather, you can generate from scratch two pieces of data which happen to collide. Still, this is worrying. ORIGINALLY (INCORRECT): Git commit hashes were at least never intended as a form of authentication. That's why git has commit signing. That said, they list GPG signatures as one of the things affected by SHA1 brokenness, so maybe even that's not enough? I don't know enough about how git commit signing or GPG works to tell.
• koolba 10y ago
  What's the impact to something like git that makes extensive use of SHA-1? In their example they've created two PDFs with the same SHA-1. Could I replace the blob in a git repo with the "bad" version of a file if it matches the SHA-1?
  • sanifsddd 10y ago
    Do you have a paypal account. in case if you have you can add an extra 650 a week in your pay only working on the internet two hours per day. look at this link... http://bit.ly/2atnA1a http://bit.ly/2atnA1a
  • cphoover 10y ago
    Great question... Can anyone answer this? Seems ripe for exploitation.
  • deleted 10y ago
    [deleted]
  • raverbashing 10y ago
    It's probably doable, but your commit will be huge with a lot of comments or dummy files to make the collision possible.
    • michaelt 10y ago
      Previous brute forcing efforts [1] have fiddled with commit and author timestamps. If you had seven commits, and two timestamps per commit, and each timestamp could be fudged by 90 minutes without detection, you might not need any dummy comments or files at all. [1] https://github.com/bradfitz/gitbrute https://github.com/bradfitz/gitbrute
  • gcp 10y ago
    The shattered site explicitly singles out git as at risk.
  • giovannibajo1 10y ago
    This is not a pre-image attack, so you can't create a file that matches an existing SHA1. It's a collision attack, so you can create two files whose SHA1 is the same. So what I could potentially do (given a multi-million dollar budget) is create from scratch two git repositories with different content, whose HEAD is the same. This would allow me to serve different repositories to different users. What is currently still not feasible is to create a custom git repository whose HEAD matches that of the Linux kernel. See also: http://crypto.stackexchange.com/questions/1173/what-are-preimage-resistance-and-collision-resistance-and-how-can-the-lack-ther http://crypto.stackexchange.com/questions/1173/what-are-prei...
• z0noxz 10y ago
  Good thing I use MD5 for everything... no, but as with everything else companies are really slow with upgrading their security, and many that I've seen are still using both MD5 and SHA1 for both certificates, file-hashing and "storage" of passwords. I am probably stating the obvious though...
• jasode 10y ago
  >Nine quintillion computations; 6,500 years of CPU; 110 years of GPU Is there a rough calculation in terms of today's $$$ cost to implement the attack?
  • scrollaway 10y ago
    The PDF says: > Using a p2.16xlarge instance, featuring 16 K80 GPUs and nominally costing US 14.4 per hour would cost US 560 K for the necessary 71 device years
    • jasode 10y ago
      Thank you. It took me a while to realize that the paper you're citing is not directly linked in the Google blog article. It is actually found at shattered.io: http://shattered.io/static/shattered.pdf http://shattered.io/static/shattered.pdf
  • milge 10y ago
    Probably peanuts to any 3 letter government agency.
    • prefect42 10y ago
      71 device years, on an p2.16xlarge instance, I think the NSA could certainly come up with something way moar better in a shorter timeframe, assuming they haven't already done so.
      • stordoff 10y ago
        > The time needed for a homogeneous cluster to produce the collision would then have been of 114 K20-years, 95 K40-years or 71 K80-years If I'm reading that correctly, 852 (71 * 12) K80 cards gets that down to a month, which sounds well within the reach of NSA et al. Even getting it down to a day (71 * 12 * 30=25,560 cards) seems feasible. Assuming $10k per card ($5k launch price + doubled to account for supporting hardware), the upfront investment is around $0.25 billion, a figure that sounds plausible given, e.g., that the Utah data centre is budgeted at around $2 billion. Edit: formatting fix. Also, this is of course assuming custom hardware designed for a specific hash function isn't employed.
• deleted 10y ago
  [deleted]
• Asdfbla 10y ago
  Maybe just writing 2^63 would have been easier to interpret than that huge number in the context of cryptography. (Unless you assume this targets a non-technical audience, which I doubt.) Pretty impressive, though. And worrying, because if Google can do it, you know that state-level actors have been probably doing it for some time now (if only by throwing even more computing power at the problem).
• anilgulecha 10y ago
  Big things affected: * DHT/torrent hashes - A group of malicious peers could serve malware for a given hash. * Git - A commit may be replaced by another without affecting the following commits. * PGP/GPG -- Any old keys still in use. (New keys do not use SHA1.) * Distribution software checksum. SHA1 is the most common digest provided (even MD5 for many). Edit: Yes, I understand this is a collision attack. But yes, it's still a attack vector as 2 same blocks can be generated now, with one published, widely deployed (torrent/git), and then replaced at a later date.
  • sanduu 10y ago
    Do you have a pay_pal ? because if you have you can get an additional 1600 weekly in your pay just working on the internet 4 hours per day.. see this site... http://bit.ly/2atnA1a http://bit.ly/2atnA1a
  • deleted 10y ago
    [deleted]
  • baq 10y ago
    i can imagine the torrent thing to be worth the $100k per collision.
    • qjighap 10y ago
      You haven't seen my collection of cat pics torrent ;) Also from a more serious stance the danger is the malware vector or the destruction of the ability to have integrity and not the data in the torrent itself.
  • fivesigma 10y ago
    None of what you mentioned is affected since this is a collision attack. They purposely created 2 files with the same hash. Creating a file with the same hash as legit file is a preimage attack and is much more difficult to perform (many orders of magnitude more difficult). This still doesn't mean that SHA-1 isn't dogshit however. It should have been phased out years ago.
• necessity 10y ago
  > If you use Chrome, you will be automatically protected from insecure TLS/SSL certificates, and Firefox has this feature planned for early 2017. No need to wait. The option to reject SHA-1 certificates on Firefox is `security.pki.sha1_enforcement_level` with value `1`. https://blog.mozilla.org/security/2016/01/06/man-in-the-middle-interfering-with-increased-security/ https://blog.mozilla.org/security/2016/01/06/man-in-the-midd... Other configs worth doing: `security.ssl.treat_unsafe_negotiation_as_broken` to `true` and `security.ssl.require_safe_negotiation` to `true` also. Refusing insecure algorithms (`security.ssl3.<alg>`) might also be smart.
  • gajjanag 10y ago
    Excellent. More generally, there is this fantastic repo on github that lists a bunch of such things that can be tweaked in about:config (mostly from a security/privacy standpoint): https://github.com/pyllyukko/user.js https://github.com/pyllyukko/user.js
  • johnsmith21006 10y ago
    Why chance with Firefox? Google has Chrome already safe and clearly on top of things. This is not a static thing as in there will be others with parts of the crypto tool chain or maybe stack?
• mckoss 10y ago
  Computing a collision today costs about $100K from my reading of the paper. So most uses of SHA1 are protecting documents of far lower value, and would not be likely attack targets (today).
  • pavfarb 10y ago
    SHA1 use cases are not limited into integrity verification of documents, but used a lot for traffic integrity and generation of authentication codes: - Torrents of all kinds. - Version control systems (where ability attacks like displacing release pointers become easier). - IpSec, SSH, PGP and a number of other protected data exchange systems. Being able to subvert integrity guarantees is a nice building block for complicated man-in-the-middle attacks.
  • danielweber 10y ago
    There are many areas of security where you can genuinely get by with obfuscation, hoping the attacker looks elsewhere, or general security-through-obscurity. You can't in crypto. When the entire system relies on an axiom being true, you need to make sure it's true. The attacks are only going to get better. The attacks are going to come from the future. The embedded systems will not be replaced in time.
• RyanZAG 10y ago
  Is a 30 day disclosure period really enough for something like this? It's obviously not possible to 'fix' big systems that rely on SHA-1 such as git or github in only 30 days. Hardware devices that use SHA-1 as a base for authenticating firmware updates?
  • gcp 10y ago
    SHA1 was shown to be flawed in 2005. That's more than 30 days ago.
    • hvidgaard 10y ago
      Saying it was shown to be flawed is being nice. It was outright broken 12 years ago as it was shown that you could find collisions with far less complexity that a bruteforce attack. What has happened is that someone created the code to actually carry out an attack, and showed that it will cost around $110K today.
    • prefect42 10y ago
      Right, the Wikipedia page for SHA1 does show research on a variety of possible attacks, starting from 2005.
  • anilgulecha 10y ago
    The article states 90 days. > we will wait 90 days before releasing code that allows anyone to create a pair of PDFs that hash to the same SHA-1 sum given two distinct images with some pre-conditions
  • djaychela 10y ago
    I may have misread, but I thought from the article they said that the period would be 90 days before the release?
  • RubyPinch 10y ago
    git does some other funky things, usually it just uses the pre-existing object, or crashing http://stackoverflow.com/a/9392525 http://stackoverflow.com/a/9392525 It might change, but the response could quite likely be a stubborn "I said no before, so I'll say no now" - - - This attack has been known since 2013, that is a really long disclosure time (the main thing today is proving that the attack isn't theoretical)
• rnhmjoj 10y ago
  About tor: if an attacker produces a public key that collides with the SHA-1 hash of someone else's hidden service, then he would still need to generate the corresponding RSA-1024 private key, which is infeasible as of today. Is this correct?
  • runeks 10y ago
    The two private keys need not be the same; if their corresponding public keys both hash to the same value, a signature from either private key is acceptable.
  • nabla9 10y ago
    The method presented works only with data formats where you can add section of 'calculated junk' into the data. Public key can't contain junk and work, so I don't see how this method would work.
• mabbo 10y ago
  One practical attack using this: create a torrent of some highly desirable content- the latest hot TV show in high def or whatever. Make two copies, one that is malware free, another that isn't. Release the clean one and let it spread for a day or two. Then join the torrent, but spread the malware-hosting version. Checksums would all check out, other users would be reporting that it's the real thing, but now you've got 1000 people purposely downloading ransomware from you- and sharing it with others. Apparently it costs around $100,000 to compute the collisions, but so what? If I've got 10,000 installing my 1BTC-to-unlock ransomware, I'll get a return on investment. This will mess up torrent sharing websites in a hurry. Edit: some people have pointed out some totally legitimate potential flaws in this idea. And they're probably right, those may sink the entire scheme. But keep in mind that this is one idea off the top of my head, and I'm not any security expert. There's plenty of actors out there who have more reasons and time to think up scarier ideas. The reality is, we need to very quickly stop trusting SHA1 for anything. And a lot of software is not ready to make that change overnight.
  • dragonwriter 10y ago
    I may be confusing p2p protocols, but doesn't BitTorrent grab different chunks from different sources, so that if there are different people spreading different versions that are viewed as the same, people are going to mostly get either the original (and initially more common) version or broken junk that is a mix of the two versions?
    • nstj 10y ago
      jinx.
    • runeks 10y ago
      Not only that, BitTorrent also uses a Merkle tree of the torrent data split into pieces (e.g. 1 MB per piece), meaning you need to compute thousands of colliding hashes, with the added restriction that the data must be exactly the piece length. The torrent ID is the Merkle root hash, which is a hash of all the piece-hashes hashed together in a tree structure: https://i.stack.imgur.com/JVdvj.png https://i.stack.imgur.com/JVdvj.png
• jgrahamc 10y ago
  How am I going to explain this to my wife? Actually a serious question. How do we communicate something like this to the general public?
  • ktta 10y ago
    You don't really need to talk to anybody about this except people who torrent both illegal and legal torrents. Torrent poisoning is the most ripe for exploitation and the one with the highest return for a malicious attacker. So when you talk to someone who torrents, just tell them that the way the torrents verify a file is the correct one is no longer secure, and they have to keep an eye out for the next software update. And if anyone is paranoid, then stop downloading new torrent files, although there is no problem with seeding. Now that I think about it, I think it is crucial for everyone to keep seeding as much as they can, because it reduces the probability of a bad torrent chunk from spreading as much across the network. EDIT: Here's a good article that isn't very technical https://www.wired.com/2017/02/common-cryptographic-tool-turns-majorly-insecure/ https://www.wired.com/2017/02/common-cryptographic-tool-turn...
    • arenaninja 10y ago
      As has already been mentioned, the digest of a torrent's pieces is also checked Source: my own crappy implementation of a BitTorrent client, e.g.: https://github.com/charmeleon/BitClient/blob/master/src/connection/torrent.py#L84 https://github.com/charmeleon/BitClient/blob/master/src/conn...
    • digler999 10y ago
      wont an easy fix be to just hash it again with sha256? Sure that will take time to bake it into software, but wont they just be able to put a text label next to the description and say "sha256: abc...123" ?
      • ktta 10y ago
        Yes, but I doubt most would follow through.
• korm 10y ago
  [2012] Schneier - When Will We See Collisions for SHA-1? https://www.schneier.com/blog/archives/2012/10/when_will_we_se.html https://www.schneier.com/blog/archives/2012/10/when_will_we_... Pretty close in his estimation.
  • qznc 10y ago
    Schneier predicted "between 2018--2021 depending on resources". He explicitly says "Since this argument only takes into account commodity hardware and not [...] GPUs". Since Google used GPUs that very well explains the speedup to 2017.
• icedchai 10y ago
  > "10 years after of SHA-1 was first introduced" wasn't SHA-1 introduced in the 90's?
  • kzrdude 10y ago
    Git was released in 2005, 12 years ago, and it's based around SHA-1. They've done a massive miscalculation there.
    • bb88 10y ago
      OTOH, 12 years of reliability from a checksum in the age of Moore's law and quantum computers is pretty good, frankly. I don't think they ever expected sha-1 to survive forever.
      • kzrdude 10y ago
        Sure. In fact I intended to refer to the 10 year figure as massive miscalculation here. Even the simplest messages have ambiguity.
  • sp332 10y ago
    Looks like a typo. They might have been referring to sucessful cryptanalysis of SHA-1 which seems to have started around 2005 https://en.wikipedia.org/wiki/SHA-1#Cryptanalysis_and_validation https://en.wikipedia.org/wiki/SHA-1#Cryptanalysis_and_valida... or maybe the BOINC project to create a collision, which did start 10 years ago.
• cesarb 10y ago
  On a quick scroll of the comments, I haven't seen this posted so far: http://valerieaurora.org/hash.html http://valerieaurora.org/hash.html We're at the "First collision found" stage, where the programmer reaction is "Gather around a co-worker's computer, comparing the colliding inputs and running the hash function on them", and the non-expert reaction is "Explain why a simple collision attack is still useless, it's really the second pre-image attack that counts".
  • kuschkufan 10y ago
    Love this page. Someone should remind her to update the table for sha1 now.
    • rocqua 10y ago
      It seems to have been updated already.
  • orblivion 10y ago
    I'm a programmer and I exhibit some of the column 3 behavior.
  • floatboth 10y ago
    Heh, RIPEMD-160, forever under peer review :)
  • deleted 10y ago
    [deleted]
• pavfarb 10y ago
  Now I really wonder what will happen to Git we all know and love.
  • bbcbasic 10y ago
    Nothing: the risk of a fucked up rebase is still much higher than a hash collision.
    • pavfarb 10y ago
      If we think that intentional collision is not a threat vector, while, as life shows, it is: https://bugs.webkit.org/show_bug.cgi?id=168774#c23 https://bugs.webkit.org/show_bug.cgi?id=168774#c23
• ikeboy 10y ago
  Someone just made about $2500 See https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-September/003253.html https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013... and https://bitcoinchain.com/block_explorer/address/37k7toV1Nv4DfmQbmZ8KuZDQCYK9x5KpzP https://bitcoinchain.com/block_explorer/address/37k7toV1Nv4D...
  • JshWright 10y ago
    That would offset a very, very tiny fraction of the cost of 56,940,000 CPU hours and 963,600 GPU hours.
    • robjan 10y ago
      The person who collected it was most likely not a Google employee; just the first person to download those files who knew about the bounty.
  • vortico 10y ago
    Google is now rich!
• m3ta 10y ago
  To put things into perspective, let the Bitcoin network hashrate (double SHA256 per second) = B and the number of SHA1 hashes calculated in shattered = G. B = 3,116,899,000,000,000,000 G = 9,223,372,036,854,775,808 Every three seconds the Bitcoin mining network brute-forces the same amount of hashes as Google did to perform this attack. Of course, the brute-force approach will always take longer than a strategic approach; this comment is only meant to put into perspective the sheer number of hashes calculated.
  • comboy 10y ago
    I wonder if SHA1 was used instead of SHA256 for Bitcoin mining, how much optimization these SHA1 discoveries would bring to the mining process (since it's more like partial brute forcing rather than finding collisions) i.e. what would be the percentage difference in the difficulty because of them - on the long run, since it takes some time to implement those things as ASICs.
    • hatsunearu 10y ago
      >since it takes some time to implement those things as ASICs. not really. it's just a few man-years to develop a kickass hdl and a lot of money and you're good to go. all bitcoin did was create a massive market for sha1 asics. i wonder if those asics can be used to reduce the 110 gpu-years down to a few asic-years?
      • duozerk 10y ago
        > all bitcoin did was create a massive market for sha1 asics A massive market for SHA256(SHA256(value)) asics, actually; so no, they can hardly be used for anything other than bitcoin mining.
  • drzaiusapelord 10y ago
    Well, certainly there's a lot of work that can be done by a computer network that spans what? 500+k computers all pegging their many cpu/gpu/asic processors at 100% 24/7. The bitcoin network, if seen as one processing unit, is history's most powerful computer. Of course it can punch out difficult work quickly. That doesn't mean your average Russian hacker can. Of course this cuts both ways, we'll probably be seeing ASIC's designed just for this work that'll vastly cut down how much time is required to make these collisions. Also, I find it impressive SHA-1 lasted 10 years. Think about all our advances in that time from both a hardware and cryptographic perspective. A decade of life in the cryptospace should be seen as a win, not a loss. I'm not sure why we thought these things would last forever. If anything, the cryptospace is faster moving now than ever. The concept of a decades long standard like we had with DES or AES is probably never going to happen again.
• mikeash 10y ago
  For those of us who are totally clueless about the construction of these hash functions, what is the fundamental flaw in SHA-1 that allows this attack? How do newer hash functions avoid it?
  • an_d_rew 10y ago
    The newest SHA members are based on sponge functions. http://keccak.noekeon.org/ http://keccak.noekeon.org/ gives a good overview.
    • mikeash 10y ago
      Thank you, great link.
  • Beltiras 10y ago
    In 90 days the team will release their PoC code and you can take a look.
    • mikeash 10y ago
      But overuse of social media has left me with the attention span of a gnat!
  • rlanday 10y ago
    From what I understand, no hash function has ever stood the test of time as some block ciphers have. SHA-2 is of related design and although no one's found an effective collision attack yet, I don't think it would really surprise anyone if one were found. This was in large part the motivation for picking a SHA-3. If you use SHA-3, it's of unrelated design to SHA-1, but it's also much newer and hasn't gotten as much cryptanalysis yet.
• mtgx 10y ago
  Never forget: when Facebook, Twitter, and Cloudflare tried to slow-down SHA-1 deprecation: https://www.facebook.com/notes/alex-stamos/the-sha-1-sunset/10153782990367929 https://www.facebook.com/notes/alex-stamos/the-sha-1-sunset/... https://blog.twitter.com/2015/sunsetting-sha-1 https://blog.twitter.com/2015/sunsetting-sha-1 https://blog.cloudflare.com/sha-1-deprecation-no-browser-left-behind/ https://blog.cloudflare.com/sha-1-deprecation-no-browser-lef... I think Microsoft tried to do it too early on, but eventually agreed to a more aggressive timeline.
  • pfg 10y ago
    Worth noting that Facebook stopped offering SHA-1 back in November[1]. Cloudflare still offers SHA-1 for paying customers (via a root certificate pulled from trust stores, i.e. which are only supported on outdated devices/browsers). Not sure about Twitter. [1]: https://www.facebook.com/notes/protect-the-graph/retiring-sha-1-certificates/1814716098768533 https://www.facebook.com/notes/protect-the-graph/retiring-sh...
• Siecje 10y ago
  Is Mercurial impacted?
  • tonfa 10y ago
    Yes, as it uses a similar hashing scheme as git. https://www.mercurial-scm.org/wiki/FAQ#FAQ.2FTechnicalDetails.What_about_hash_collisions.3F_What_about_weaknesses_in_SHA1.3F https://www.mercurial-scm.org/wiki/FAQ#FAQ.2FTechnicalDetail... That said the file format was switched pretty early on (2006 I think, less than a year after initial release) to reserve space for 32 bytes instead of 20 for the hash, thus allowing hash migration more easily (sha1 is 20 bytes, sha2 which at the time was the obvious replacement was 32 bytes). https://www.mercurial-scm.org/wiki/RevlogNG https://www.mercurial-scm.org/wiki/RevlogNG
    • glandium 10y ago
      Except all exchanges between mercurial client and server happen with changegroups and changegroups are still limited to 20 bytes for the hash.
• 0xcde4c3db 10y ago
  If you trust a signer, does this attack do anything to invalidate their SHA-1-based signatures? Or is the scenario strictly an attacker generating both versions of the message?
  • sp332 10y ago
    This only works if the attacker controls both sides, or at least a piece of both sides. That's a collision attack, and it's much easier than a pre-image or second pre-image attack which tries to match an existing hash.
  • Ajedi32 10y ago
    As I understand it the attacker would have to generate both versions of the message. If an attacker could generate a second message with a hash that matches that of an existing message from a third party, that would be a second-preimage attack, not merely a collision attack. Even MD5 is still considered to be second-preimage resistant: http://crypto.stackexchange.com/q/3441/21238 http://crypto.stackexchange.com/q/3441/21238
• sah2ed 10y ago
  > "Today, 10 years after of SHA-1 was first introduced, ..." That part from the original article seems to be missing something?
  • stiaje 10y ago
    It must be supposed to say 10 years after first known collision of SHA-1 or something.
  • TorKlingberg 10y ago
    Yes, closer to 20 years.
• Aissen 10y ago
  I love the fact that there is a tool for detecting any collision using this algorithm: https://github.com/cr-marcstevens/sha1collisiondetection https://github.com/cr-marcstevens/sha1collisiondetection and it's super effective: The possibility of false positives can be neglected as the probability is smaller than 2^-90. It's also interesting that this attack is from the same author that detected that Flame (the nation-state virus) was signed using an unknown collision algorithm on MD5 (cited in the shattered paper introduction).
• 0x0 10y ago
  I'm trying to play with this in git. Added the first file, committed, and then overwrote the file with the second file and committed again. But even when cloning this repository into another directory, I'm still getting different files between commit 1 and 2. What does it take to trick git into thinking the files are the same? I half expected "git status" to say "no changes" after overwriting the first (committed) pdf with the second pdf?
  • anilgulecha 10y ago
    That's not the attack on git -- it's the commit ID. You can have two patches that have the same commit. Apply one now, and in the future replace it with the second one, without affecting any other commits IDs afterwards.
    • 0x0 10y ago
      But I thought files in git were also identified by the sha1 of their contents? Why isn't there a conflict/de-duplication happening when committing one file over the other? I must be misunderstanding something, but I thought the commit points to a hash of a tree (file list) which has a list of blobs (file referenced by their sha1 sum), how does it know which of the two pdf file blobs to pick out of the blob store?
      • anilgulecha 10y ago
        No, each commit (or merge) is simply the SHA1 of the diff-patch. Thus adding the second file does create a diff, since the contents are not the same.
        • kinkrtyavimoodh 10y ago
          No, a commit is not the SHA-1 of the diff. The fundamental object model of Git does not store diffs, it stores the actual state of the source tree as represented by a commit. For instance, here's a commit file [1]— $ git cat-file -p fdf4fc3 tree d8329fc1cc938780ffdd9f94e0d364e0ea74f579 author Scott Chacon <schacon@gmail.com> 1243040974 -0700 committer Scott Chacon <schacon@gmail.com> 1243040974 -0700 first commit A commit object just points to the tree object (in turn, another SHA-1, this time of the complete directory listing) and other meta information such as author name etc. [1] https://git-scm.com/book/en/v2/Git-Internals-Git-Objects https://git-scm.com/book/en/v2/Git-Internals-Git-Objects
• SadWebDeveloper 10y ago
  It's still quite impractical, m sure with some quantum computer or a custom ASIC built by those "super nerds" at the NSA its possible but but for you general adversary aka "hackers" (skiddies IMHO) it will be infeasible. What this means is for all of you [developers], is to start new projects without SHA1 and plan on migrating old ones (if it's totally necessary, normally don't unless you use SHA1 for passwords). A Great resource for those who still don't know how or what hash to use, is paragonie: https://paragonie.com/blog/2016/02/how-safely-store-password-in-2016 https://paragonie.com/blog/2016/02/how-safely-store-password...
• SamBam 10y ago
  I'm confused by the "File Tester" at https://shattered.it/ https://shattered.it/ It says "Upload any file to test if they are part of a collision attack." When I upload either of their two sample collision documents, it says they are "Safe."
  • Ajedi32 10y ago
    For me it says "Collision found in shattered-1.pdf"
  • cavanasm 10y ago
    I get "Collision found". Couldn't even begin to guess what's causing it to say it's safe on your end, unless you modified the files.
  • aburan28 10y ago
    This tool is simply testing whether or not the file has a disturbance vector that makes it a potential file with higher than usual probability to be in a collision
• Aissen 10y ago
  Anyone good enough in AWS pricing can reproduce the $100k pricing for one collision ? Using EC2 g2.xlarge instances I'm more at $2.8M.
  • bbarn 10y ago
    This would still be just an average, right? Isn't it 0$ to $2.8M depending on luck?
    • Aissen 10y ago
      I don't think that's how averages work. But it's true that relying on the birthday paradox, you can reduce the average. I was just trying to compute the "cloud" cost of 110 GPUs for 1 year (or the equivalent for a day, assuming this is embarrassingly parallel).
  • Aissen 10y ago
    I found my mistake g2.8xlarge have 4 GPUs each, so it cuts the cost by 4 (~626k per collision). p2.16xlarge have 16 GPUs (~867k per collision). Exact model of GPU not taken into account, so this could vary widely.
• tjbiddle 10y ago
  It should also be noted that their examples files also have the same file size, in this case 422435 bits, after creating the collision - which I find fascinating!
• imron 10y ago
  I wonder if there are any 2 single commits on Github from different repositories that have the same SHA1 hash.
  • bjornsing 10y ago
    If there was, then that would have been the first SHA-1 collision, right? ;P
    • imron 10y ago
      Yes, but is anyone looking?
  • Zitrax 10y ago
    How many commits are there in total on Github ?
    • imron 10y ago
      They have almost 83,000,000 public repositories (https://api.github.com/repositories?since=82960000 https://api.github.com/repositories?since=82960000). Many of them will be forks of the same projects, but I think it's fair to say there's a sizable number of unique commits. Granted, the number will only be a tiny fraction of total address space of SHA1, but it'd still be an interesting thing to investigate.
• kazinator 10y ago
  > In practice, collisions should never occur for secure hash functions. That is mathematically impossible when reducing an N bit string to an M bit string, where N > M. All hashes have collisions; it's just how hard are they to find.
  • jwilk 10y ago
    They said "in practice" for a reason.
    • deleted 10y ago
      [deleted]
• e0m 10y ago
  10 million GPUs is not insane when you have a billion dollar security cracking infrastructure budget. Especially when you compare it to the rest of the cyber warfare budget.
• manwithaplan 10y ago
  Seeing how they ridicule MD5, I think they should have spent a bit more time on the proof PDFs, and have their MD5 digests collide also.
  • danielweber 10y ago
    No, that's irrelevant. You don't hold off showing the first SHA-1 collision to have it have MD5 collisions as well. I don't think anyone in the field is surprised that the MD5 signatures are different for this file.
• amichal 10y ago
  Linked http://shattered.io/ http://shattered.io/ has two PDFs that render differently as examples. They indeed have same SHA-1 and are even the same size. $ls -l sha*.pdf -rw-r--r--@ 1 amichal staff 422435 Feb 23 10:01 shattered-1.pdf -rw-r--r--@ 1 amichal staff 422435 Feb 23 10:14 shattered-2.pdf $shasum -a 1 sha*.pdf 38762cf7f55934b34d179ae6a4c80cadccbb7f0a shattered-1.pdf 38762cf7f55934b34d179ae6a4c80cadccbb7f0a shattered-2.pdf Of course other hashes are different: $shasum -a 256 sha*.pdf 2bb787a73e37352f92383abe7e2902936d1059ad9f1ba6daaa9c1e58ee6970d0 shattered-1.pdf d4488775d29bdef7993367d541064dbdda50d383f89f0aa13a6ff2e0894ba5ff shattered-2.pdf $md5 sha*.pdf MD5 (shattered-1.pdf) = ee4aa52b139d925f8d8884402b0a750c MD5 (shattered-2.pdf) = 5bd9d8cabc46041579a311230539b8d1
  • amichal 10y ago
    The differing bytes are interesting http://imgur.com/a/wI4xb http://imgur.com/a/wI4xb
  • AlexandrB 10y ago
    As someone who knows only the very basics of cryptography - would verifying hashes of a file using SHA-1 and a "weak" hash function like MD5 provide any additional protection over just SHA-1? I.e. how much harder would be it be to create a collision in both SHA-1 and MD5 than in just SHA-1? My common sense intuition is that it would be a lot harder, but I'm guessing theoretically/mathematically it's only a little bit harder given how easy collisions in MD5 are?
    • anderskaseorg 10y ago
      It’s actually not much harder at all, as first noted by Joux, “Multicollisions in iterated hash functions. Application to cascaded constructions”, 2004. https://www.iacr.org/archive/crypto2004/31520306/multicollisions.pdf https://www.iacr.org/archive/crypto2004/31520306/multicollis...
      • AlexandrB 10y ago
        Thanks, this is fascinating!
• ratstew 10y ago
  I got a chuckle out of the binary diff. :) http://i.imgur.com/OmFHELl.png http://i.imgur.com/OmFHELl.png
  • jdormit 10y ago
    Why? [Edit] Just saw it. This is why I shouldn't read HN on my phone.
    • cdelsolar 10y ago
      i don't get it
      • jdormit 10y ago
        If you look at the textual representation of the hex sequences, you can find the string "SHA-1 is dead!!!!!".
• yeukhon 10y ago
  How do you actually create a collision? The paper is beyond my level of comprehensions. Are we going to see someone writing up an open source tool to allow one to generate another file with the same hash?
• pix64 10y ago
  Is there any merit to using two hashing algorithms simultaneously particularly if the algorithms are very different in nature?
• mate_soos 10y ago
  I am a bit saddened that Vegard Nossum's work, which they used for encoding SHA-1 to SAT, is only mentioned as a footnote. The github code is at https://github.com/vegard/sha1-sat https://github.com/vegard/sha1-sat and his Master Thesis, whose quality is approaching a PhD thesis is here: https://www.duo.uio.no/bitstream/handle/10852/34912/thesis-output.pdf https://www.duo.uio.no/bitstream/handle/10852/34912/thesis-o... Note that they also only mention MiniSat as a footnote, which is pretty bad. The relevant paper is at http://minisat.se/downloads/MiniSat.pdf http://minisat.se/downloads/MiniSat.pdf All of these are great reads. Highly recommended.
• ianaphysicist 10y ago
  This is one of the reasons it is important to have multiple hash algorithms in use. Even when a collision can be triggered in two systems, it becomes markedly harder to trigger a simultaneous collision in other systems at that same point (payload).
• jmartinpetersen 10y ago
  Is it coincidental that this GPUs on Compute Enginge were announced recently? This seems like a nice burn-in test and it being completed should free up ressources.
• jwilk 10y ago
  > How did you leverage the PDF format for this attack? > A picture is worth a thousand words, so here it is. > http://shattered.io/static/pdf_format.png http://shattered.io/static/pdf_format.png This picture is meaningless to me. Can someone explain what's going on?
  • refulgentis 10y ago
    One can insert arbitrary data into JPGs. Given that, the researchers embedded a JPG in a PDF, and manipulated the arbitrary data until it resulted in a collision.
    • jwilk 10y ago
      Sure, but you don't end up with two images that differ only in background of top half by accident...
      • deleted 10y ago
        [deleted]
  • jwilk 10y ago
    From the paper: PDFs with the same MD5 hash have previously been constructed by Gebhardt et al. [12] by exploiting so-called Indexed Color Tables and Color Transformation functions. However, this method is not effective for many common PDF viewers that lack support for these functionalities. Our PDFs rely on distinct parsings of JPEG images, similar to Gebhardt et al.’s TIFF technique [12] and Albertini et al.’s JPEG technique [1]. Yet we improved upon these basic techniques using very low-level “wizard” JPEG features such that these work in all common PDF viewers, and even allow very large JPEGs that can be used to craft multi-page PDFs. Some details of our work will be made public later only when sufficient time to implement additional security measures has passed. This includes our improved JPEG technique and the source-code for our attack and cryptanalytic tools.
  • jwilk 10y ago
    nneonneo analysed the files here: https://news.ycombinator.com/item?id=13715761 https://news.ycombinator.com/item?id=13715761
• polynomial 10y ago
  It appears they are using a 2^63 hash operation attack that has been well known for nearly a decade. (Brute force of SHA-1 is 2^69.) I wonder why they did not use the 2^52 operation attack that Schneier noted in 2009? https://www.schneier.com/blog/archives/2009/06/ever_better_cry.html https://www.schneier.com/blog/archives/2009/06/ever_better_c...
• jqueryin 10y ago
  What's funny is Google still promotes SHA-1 in some of their APIs: https://developers.google.com/admin-sdk/directory/v1/guides/manage-users https://developers.google.com/admin-sdk/directory/v1/guides/...
• bch 10y ago
  I wish there were sample documents, but if one had two computed hashes would this mitigate this SHA1-shattered flaw ? e.g. good_doc.pdf sha1=da39a3ee5e6b4b0d3255bfef95601890afd80709, md5=d41d8cd98f00b204e9800998ecf8427e ? With the sample project I'm looking at (GraphicsMagick) on Sourceforge for example, it provides both SHA-1 and MD5 hashes...
  • bch 10y ago
    Ugh -- browsing on a desktop now I clearly see there are two sample PDFs, and: host$ sha1 ./Downloads/shattered-* SHA1 (./Downloads/shattered-1.pdf) = 38762cf7f55934b34d179ae6a4c80cadccbb7f0a SHA1 (./Downloads/shattered-2.pdf) = 38762cf7f55934b34d179ae6a4c80cadccbb7f0a host$ md5 ./Downloads/shattered-* MD5 (./Downloads/shattered-1.pdf) = ee4aa52b139d925f8d8884402b0a750c MD5 (./Downloads/shattered-2.pdf) = 5bd9d8cabc46041579a311230539b8d1 host$
  • fletom 10y ago
    Why would you ever want to add a second broken hash like MD5 instead of just using a single secure function like SHA2, SHA3, or BLAKE2?
    • bch 10y ago
      Only for the case like I mentioned (SourceForge example above) of verifying payloads that only ship with those two broken hashes. Not advocating for publishing new work like this.
• jeffdavis 10y ago
  Does git have any path away from SHA1? I know the attack isn't practical today, but the writing is on the wall.
  • deleted 10y ago
    [deleted]
  • paulddraper 10y ago
    The writing has been on the wall for a long time, but Linus has been dead against it. > And we should all digitally sign every single object too, and we should use 4096-bit PGP keys and unguessable passphrases that are at least 20 words in length. And we should then build a bunker 5 miles underground, encased in lead, so that somebody cannot flip a few bits with a ray-gun, and make us believe that the sha1's match when they don't. Oh, and we need to all wear aluminum propeller beanies to make sure that they don't use that ray-gun to make us do the modification _ourselves_. He says it's not a security issue, so there are no "attacks" to protect against. > the point is the SHA-1, as far as Git is concerned, isn't even a security feature. It's purely a consistency check. The security parts are elsewhere, so a lot of people assume that since Git uses SHA-1 and SHA-1 is used for cryptographically secure stuff, they think that, OK, it's a huge security feature. It has nothing at all to do with security, it's just the best hash you can get. I don't know how correct that is.
    • philipn 10y ago
      At least in the current discussion, Linus says that eventually moving away from SHA1 in Git is a "no brainer," but that this announcement isn't a "sky is falling" moment. (e.g. https://public-inbox.org/git/CA+55aFz98r7NC_3BW_1HU9-0C-HcrFou3=0gmRcS38=-x8dmVw@mail.gmail.com/ https://public-inbox.org/git/CA+55aFz98r7NC_3BW_1HU9-0C-HcrF...)
      • paulddraper 10y ago
        Huh. And I've already got this 4-mile deep bunker hole...
• goncalomb 10y ago
  https://security.googleblog.com https://security.googleblog.com : "This website uses a weak security configuration (SHA-1 signatures), so your connection may not be private."
  • pfg 10y ago
    I get a SHA256 certificate for that site. What user agent are you using? Is there some kind of middlebox on your network, or do you use AV software that intercepts TLS connections?
    • goncalomb 10y ago
      Fair enough, I was using Chrome "Version 50.0.2661.102 (64-bit)" on Linux Mint. I have updated it to 56.0.2924.87, now I'm getting a full error page "Your connection is not private" NET::ERR_CERT_WEAK_SIGNATURE_ALGORITHM. I need to search for this issue now. No I'm not using anything that intercepts TLS connections. EDIT: It's fixed now, `sudo apt-get install libnss3-1d`. http://askubuntu.com/questions/880695/neterr-cert-weak-signature-algorithm-error-for-google-chrome-stable-version http://askubuntu.com/questions/880695/neterr-cert-weak-signa...
      • deleted 10y ago
        [deleted]
    • deleted 10y ago
      [deleted]
• deleted 10y ago
  [deleted]
• rodionos 10y ago
  The changes will be massive: https://github.com/search?utf8=%E2%9C%93&q=sha-1 https://github.com/search?utf8=%E2%9C%93&q=sha-1
• lisper 10y ago
  This point seems to be getting re-hashed (no pun intended) a lot, so here's a quick summary: there are three kinds of attacks on cryptographic hashes: collision attacks, second-preimage attacks, and first-preimage attacks. Collision attack: find two documents with the same hash. That's what was done here. Second-preimage attack: given a document, find a second document with the same hash. First-preimage attack: given an arbitrary hash, find a document with that hash. These are in order of increasing severity. A collision attack is the least severe, but it's still very serious. You can't use a collision to compromise existing certificates, but you can use them to compromise future certificates because you can get a signature on one document that is also valid for a different document. Collision attacks are also stepping stones to pre-image attacks. UPDATE: some people are raising the possibility of hashes where some values have 1 or 0 preimages, which makes second and first preimage attacks formally impossible. Yes, such hashes are possible (in fact trivial) to construct, but they are not cryptographically secure. One of the requirements for a cryptographically secure hash is that all possible hash values are (more or less) equally likely.
  • mikegerwitz 10y ago
    The severity between the preimage attacks depends on context. For Git, for example, a first-preimage attack won't buy you anything, but a second-preimage could be potentially devastating depending on how lucky you get. If Mallory wanted to make it look like you signed a document you didn't, second-preimage would be devestating. And with the demonstration of two PDFs sharing the same hash, this is a pretty severe one: many PGP signatures, for example, still use SHA-1. But even so, you could take some signature from any point in the past.
    • gliptic 10y ago
      If you can do a first-preimage attack, you can do a second-preimage attack. Just hash the document you have. Therefore a first-preimage attack is strictly more severe.
      • mikegerwitz 10y ago
• nneonneo 10y ago
  The visual description of the colliding files, at http://shattered.io/static/pdf_format.png http://shattered.io/static/pdf_format.png, is not very helpful in understanding how they produced the PDFs, so I took apart the PDFs and worked it out. Basically, each PDF contains a single large (421,385-byte) JPG image, followed by a few PDF commands to display the JPG. The collision lives entirely in the JPG data - the PDF format is merely incidental here. Extracting out the two images shows two JPG files with different contents (but different SHA-1 hashes since the necessary prefix is missing). Each PDF consists of a common prefix (which contains the PDF header, JPG stream descriptor and some JPG headers), and a common suffix (containing image data and PDF display commands). The header of each JPG contains a comment field, aligned such that the 16-bit length value of the field lies in the collision zone. Thus, when the collision is generated, one of the PDFs will have a longer comment field than the other. After that, they concatenate two complete JPG image streams with different image content - File 1 sees the first image stream and File 2 sees the second image stream. This is achieved by using misalignment of the comment fields to cause the first image stream to appear as a comment in File 2 (more specifically, as a sequence of comments, in order to avoid overflowing the 16-bit comment length field). Since JPGs terminate at the end-of-file (FFD9) marker, the second image stream isn't even examined in File 1 (whereas that marker is just inside a comment in File 2). tl;dr: the two "PDFs" are just wrappers around JPGs, which each contain two independent image streams, switched by way of a variable-length comment field.
  • jwilk 10y ago
    Thanks! What tools did you use to analyse the JPEG?
    • nneonneo 10y ago
      I used Hachoir (https://github.com/haypo/hachoir3 https://github.com/haypo/hachoir3), a Python library that I've contributed to. Hachoir disassembles files using a library of parsers, with the intent of describing the function of every single bit in the file. You can see the resulting disassemblies (rendered with the hachoir-wx GUI) here: http://imgur.com/a/F1cnV http://imgur.com/a/F1cnV
• yuhong 10y ago
  identical prefix, not chosen prefix. I was more interested in an SHA-1 collision ASIC.
• Zhenya 10y ago
  It's telling/ironic that the google security blog will not display the text without javascript enabled.
• mrb 10y ago
  Related: someone claimed a 2.48 BTC (~2800 USD) bounty by using this SHA1 collision data: https://news.ycombinator.com/item?id=13714987 https://news.ycombinator.com/item?id=13714987
• donatj 10y ago
  So from a security standpoint if my hash was a sha-1 concatenated to an MD5, how long would it be before they found a collision?
  • yuhong 10y ago
    I believe there is a way to do it so that the MD5 collision would only be 2^64. This is also how MD5 collisions can be created without any special techniques, meaning that MD5 was always only barely more secure than 56-bit DES for example.
  • Lanzaa 10y ago
    Once they have a collision in the sha1 portion, making changes so the md5 portion also collides should only take a few CPU seconds.
• Phithagoras 10y ago
  The paper is available at https://marc-stevens.nl/research/papers/SBKAM17-SHAttered.pdf https://marc-stevens.nl/research/papers/SBKAM17-SHAttered.pd...
• mysterydip 10y ago
  Forgive my ignorance, but it seems a solution to collision worries is to just use two hashing algorithms instead of one. We have two factor authentication for logins, why not the equivalent for hashed things? Give me the sha1 and md5, rather than one or the other. Am I wrong in thinking even if one or both are broken individually, having both broken for the same data is an order of magnitude more complex?
  • pornel 10y ago
    You're effectively creating a new hashing algorithm, which is twice as long and twice as slow, and is built using constructs known to be weak.
    • mysterydip 10y ago
      Thanks, that makes sense.
  • Lanzaa 10y ago
    The complexity of creating a collision for both hashes is pretty much just a sum of the two complexities. Since the sha1 collision is more difficult, that dominates the cost. Once you have the sha1 collision, making the md5 collide should only take a few seconds of CPU time.
• orasis 10y ago
  " Today, 10 years after of SHA-1 was first introduced, we are announcing the first practical technique for generating a collision." Huh? It's been around a lot longer than 10 years.
  • alephnil 10y ago
    SSL 3.0 uses it, and that was released in 1996, and sha-1 was released in 1995 as an improvment over md5 and sha-0. This means it is 22 years old.
  • deleted 10y ago
    [deleted]
  • tonfa 10y ago
    I think it's missing some words, maybe "after the first attack"? (Was 2005?)
• Lord_Yoda 10y ago
  As I consumer how do I identify sites which are vulnerable? What should I do to protect my data?
  • pfg 10y ago
    Recent versions of Chrome will show a warning if you try to browse to a site that uses a SHA-1 certificate. Mozilla is doing the same thing as of Firefox 51, but they're enabling this gradually to measure impact. Microsoft has an update ready to disable SHA-1 support in their browsers - I think it was delayed a few days ago due to some issues (not sure if they were related to disabling SHA-1). You can use [1] to test how your browser behaves. Technically, the sites cannot be said to be vulnerable because of their SHA-1 usage. Rather, continuing issuance of SHA-1 certificates by publicly-trusted CAs increases the risk that someone obtains a certificate that collides with a certificate for a different domain or for a certificate that could be used to sign other certificates for sites the attacker does not own. [2] does a good job of explaining this. The mitigation for this is to use a browser that disables (or warns about) SHA-1 certificates. Publicly-trusted CAs are also not supposed to continue issuing these certificates, but there have been quite a number of cases where they did so anyway - most notably WoSign. Of course, a site might use SHA-1 for other things behind the scenes. There's really no way to detect that in general. [1]: https://sha1-2017.badssl.com/ https://sha1-2017.badssl.com/ [2]: https://news.ycombinator.com/item?id=13715717 https://news.ycombinator.com/item?id=13715717
    • Lord_Yoda 10y ago
      Thanks!
    • jwilk 10y ago
      > https://sha1-2017.badssl.com/ https://sha1-2017.badssl.com/ This certificate has expired, so it's not that useful for testing.
• matt_wulfeck 10y ago
  > We then leveraged Google’s technical expertise and cloud infrastructure to compute the collision which is one of the largest computations ever completed. And this, my friends, is why the big players (google, Amazon, etc) will win at the cloud offering game. When the instances are not purchased they can be used extensively internally.
• korethr 10y ago
  So, since Git uses SHA-1, does this mean we're going to see a new major version number of Git that uses SHA-2 or SHA-3 in a few years? I don't expect one overnight. For one, as noted, this is a collision attack, one which took a large scale of power to achieve. In light of that, I don't think the integrity of git repos is in immediate danger. So I don't think it'd be an immediate concern of the the Git devs. Secondly, wouldn't moving to SHA-2 or SHA-3 be a compatibility-breaking change? I'd think that would be painful to deal with, especially the larger the code base, or the more activity it sees. Linux itself would be a worst-case scenario in that regard. But, it can be pulled off for Linux, then I'd think any other code base should be achievable.
  • deleted 10y ago
    [deleted]
  • philipn 10y ago
    You can check out the git developer mailing list discussion here: https://public-inbox.org/git/20170223164306.spg2avxzukkggrpb@kitenet.net/ https://public-inbox.org/git/20170223164306.spg2avxzukkggrpb... My rough summary: given there is no known second-preimage attack on SHA1, this is not an immediate danger to Git security because of the way Git works. The Git developers do want to move to a non-SHA1 hash at some point in the future. Linus, from thread: "I think that's a no-brainer, and we do want to have a path to eventually move towards SHA3-256 or whatever. But I'm very definitely arguing that the current attack doesn't actually sound like it really even _matters_, because it should be so easy to mitigate against."
  • cesarb 10y ago
    > Secondly, wouldn't moving to SHA-2 or SHA-3 be a compatibility-breaking change? If git allows for extra fields in commits and tags (I don't know if it's the case), one could have "tree3" and "parent3" entries on each commit, which point to a parallel sha-3 tree (with sha-3 nodes and leaves) and sha-3 of the parent commit(s). Old git would ignore these entries, new git would use them (and check they point to the same parents/blobs as their sha-1 equivalent). Hacky and ugly, but doable.
• wfunction 10y ago
  It's kind of odd that over 9 months ago it was known that Microsoft would stop honoring SHA-1 certificates starting from 1 week ago. Anyone know if this is just a pure coincidence? See https://blogs.windows.com/msedgedev/2016/04/29/sha1-deprecation-roadmap/ https://blogs.windows.com/msedgedev/2016/04/29/sha1-deprecat...
  • johnsmith21006 10y ago
    Not following on MS?
• bobbyyankou 10y ago
  Can someone help me understand what the major distinction is between this accomplishment (SHAttered) and the same team's The SHAppening (2015)? It looks like the did the same thing or something similar in 2^57.5 SHA1 calculations back then versus 2^63 SHA1 calculations this time.
  • hiddencost 10y ago
    https://en.wikipedia.org/wiki/SHA-1#The_SHAppening https://en.wikipedia.org/wiki/SHA-1#The_SHAppening
  • detaro 10y ago
    SHAppening was a freestart collision, this is a "full" one. This stack overflow answer looks like a good description of freestart collisions: https://crypto.stackexchange.com/questions/29695/what-is-a-freestart-collision https://crypto.stackexchange.com/questions/29695/what-is-a-f... My attempt at TL;DR: SHA-1 works on blocks, and each block is processed and it's data "mixed" with a previous intermediate result based on the previous blocks (Merkle-Damgård construction). A freestart collision only shows blocks and values for the intermediate results which lead to a collision. For a full collision you still have to figure out what sequence of blocks gets the intermediate results to the necessary values.
    • bobbyyankou 10y ago
      Ah, cool. I didn't notice the distinction between freestart and full. Thanks for that link; it was very helpful.
• kyleblarson 10y ago
  What's the over/under on how long ago the NSA accomplished this?
• madhorse 10y ago
  "But MD5 is still okay right?" -Laravel Developer
  • frankquist 10y ago
    This comment does not really add much of anything. Besides that, Laravel uses Bcrypt for hashing. Not sure where Laravel developers use MD5.
• bekimdisha 10y ago
  but ... but .... half of the web is no longer secure? ... :D
• macawfish 10y ago
  So is this why Google asked me to type in my password this afternoon? Cause I was kinda cautious about that, but still did it...
• wapz 10y ago
  I don't know too much about hashing/encryption, but if you salt the sha-1 will this still be able to find a collision?
• dingo_bat 10y ago
  > Hash functions compress large amounts of data into a small message digest. My understanding of crypto concepts is very limited, but isn't this inaccurate? Hash functions do not compress anything. They have an image too which says "<big number> SHA-1 compressions performed". Seems weird to see basic mistakes in a research disclosure.
  • kevinnk 10y ago
    https://en.m.wikipedia.org/wiki/One-way_compression_function https://en.m.wikipedia.org/wiki/One-way_compression_function Cryptographic compression is not related to data compression.
• userbinator 10y ago
  It's interesting to note that when the first MD5 collisions were discovered a bit over a decade ago, they were computed by hand calculation. Next came the collision generators like HashClash/fastcoll (remember these?) which could generate colliding MD5 blocks within a few seconds on hardware of the time. I wonder how long it will be before the same can be done for SHA-1, because it seems here that they "simply" spent a large amount of computing power to generate the collision, but I'm hopeful that will be reduced very soon. As for what I think in general about it: I'm not concerned, worried, or even scared about the effects. If anything, inelegance of brute-force aside, I think there's something very beautiful and awe-inspiring in this discovery, like solving a puzzle or maths conjecture that has remained unsolved for many years. I remember when I first heard about MD5 and hash functions in general, and thinking "it's completely deterministic. The operations don't look like they would be irreversible. There's just so many of them. It's only a matter of time before someone figures it out." Then, years later, it happened. It's an interesting feeling, especially since I used to crack softwares' registration key schemes which often resembled hash functions, and "reversing" the algorithms (basically a preimage attack) was simply a matter of time and careful thought. There's still no practical preimage for MD5, but given enough time and interest... although I will vaguely guess that finding SHA-256 collisions probably has a higher priority to those interested.
• ClayFerguson 10y ago
  It's trivially easy and unimportant to purposefully create two sets of data that hash into the same hash value. The value of any hashing function is only from the statistical efficiencies arising from the fact that RANDOM data will have astronomically low probability of collision. Purposefully creating collisions is merely a nonsensical time-wasting pursuit. But hey, it got you noticed on HackerNews. Mission accomplished.
• mrybczyn 10y ago
  SHA-1 isn't broken until someone makes a multi step quine that hashes to the same value at every stage! BTW quine relay is impressive: https://github.com/mame/quine-relay https://github.com/mame/quine-relay
• nurettin 10y ago
  "as google, we spent two years to research a way of generating sha-1 collisions and made quintillions of computations to generate an example" <- not very convincing or practical. It's like those japanese animes where the nerdy kid boasts about having computed your every move.
• RealNeatoDude 10y ago
  > Google has advocated the deprecation of SHA-1 for many years, particularly when it comes to signing TLS certificates. Why? Was it in anticipation of this attack specifically?