10 ms·
A SHA-1 chosen-prefix collision attack
- deleted 7y ago[deleted]
- ChrisSD 7y agoIt must be about time for SHA-4.
- CiPHPerCoder 7y agoNope. SHA-2 (known to developers as SHA224, SHA256, SHA384, and SHA512) was the replacement for SHA-1. SHA-3 was created as an insurance policy in case the SHA-2 family was broken too. So far, it hasn't been. We won't need a SHA-4 any time soon. SHA-2 is fine, BLAKE2 is fine (and faster), SHA-3 is fine.
- asdfv09s9d80fu9 7y agoNice try, NSA!
- optimiz3 7y agoAlso, SHA-2 underpins Bitcoin; it's the ultimate billion dollar pot of gold. SHA-2 is perhaps the most exhaustively researched (both publicly and privately) cryptographic hash because of this.
- JeremyBanks 7y agodeleted
- RL_Quine 7y agoSHA2 is used in many places in bitcoin. It’s collision resistance is used too, ie in merkel trees.
- mehrdadn 7y agoDo you know why it's said to be last-resort in the article?
- CiPHPerCoder 7y agoCatalin was quoting me in the article, so it's only fair that I elaborate here. There are four common flavors of the SHA2 family you're likely to run into: - SHA-224 - SHA-256 - SHA-384 - SHA-512 And then there are two more variants of "truncated SHA-512" (except they also use different initialization vectors than SHA-512, which is kind of an important detail) - SHA-512/256 - SHA-512/224 These latter two don't have nearly the cross-platform support as the first four. For example, in PHP, hash('sha256', 'some text') worked since PHP 5.1.2 (without PECL), but hash('sha512/256', 'some text') didn't work until PHP 7.1.0 (which is only a few years old). See for yourself: https://3v4l.org/A1dZc https://3v4l.org/A1dZc As a typical software developer, you might see SHA-{magic/numbers} and probably discover from Google/StackOverflow/etc. that they're in the SHA2 family and that the SHA2 family is secure, and then reason that whatever you're doing must also be also secure. But there's a problem. SHA-256 and SHA-512 (not the truncated varieties) are known to be vulnerable to length extension attacks. This is only a problem if you're using these hash functions in a vulnerable way. (Which isn't as uncommon as you'd think in homebrew crypto.) If you're using HMAC, length extension attacks are a moot point. There's a reason 'tptacek always recommends HMAC for symmetric authentication. SHA-224, SHA-384, SHA-512/224, and SHA-512/256 are not vulnerable to length extension attacks. BLAKE2 is not vulnerable to length-extension attacks. It's also at least as secure as SHA2, but faster than MD5. SHA3 is at least as secure as BLAKE2, but is significantly slower in software. Thus, the recommendations are: - BLAKE2 for speed and security - SHA-512/256 if you want speed, length-extension attack resistance, and arbitrary standards compliance - SHA3-256 if you care more about security and what the FIPS authors think than speed - SHA-384 if you're concerned about backwards compatibility but don't want to accidentally cause junior developers that poorly mimic your designs to introduce LEAs into their code - Any other SHA-2 family hash function if you're not interested in all of this nuance and want something guaranteed to be secure for the next few years that is widely implemented Of course, there should be a huge asterisk with this list: If you're not a crypto expert, you shouldn't be making this decision. Just stop using SHA1. It's also worth noting that Marc Stevens-- hash function breaker extraordinaire-- disagrees with my recommendation because BLAKE2 isn't a {NIST,FIPS,ISO,whateverStandardsBodyYouTrust}-approved hash function, and for better or worse, believes strongly in reinforcing public trust in standards organizations. https://twitter.com/realhashbreaker/status/1128381600146894848 https://twitter.com/realhashbreaker/status/11283816001468948... He has a point in general, but in this specific case, I think BLAKE2 is going to become the de jure SHA2 successor at least until SHA3 hardware acceleration becomes ubiquitous. Also, standards bodies have a nasty habit of digging in their heels on their mistakes, instead of issuing new guidance in response to research. See also: WPA3 and Dragonfly vs SPAKE2-EE or OPAQUE. For a higher-level example, look at the failures baked into the JOSE standards (JWT, etc.) versus PASETO. Fun fact: If you take JOSE and replace JSON with CBOR, without fixing any of the protocol security problems, you get COSE... which reared its ugly head in W3C's WebAuthn standard. Bad standards never die. Until we get a standards committee that isn't garbage, I don't entirely agree with Marc's appeal to faith here. While NIST et al. certainly do a better job at deciding on primitives than self-styled post-2010 cypherpunks (y'know, the ones that try to cascade a bunch of ciphers together in case one is broken but then use CRC32 for mixing files into the encryption key?), their failure to correct (let alone learn from) their mistakes and update recommendations in a timely manner is a problem that can't be dealt with through blind adherence to whatever they publish.
- aeneasmackenzie 7y agoIs there any reason not to just use SHA-3? It sounds like it's a real swiss army knife to hear the authors talk about it.
- wongarsu 7y agoRight now it has worse library support, worse hardware support, and isn't analysed as thouroughly as SHA512/SHA256. Also SHA-3 seems to be fighting with Blake2 for popularity, it's not immediatly clear to me that SHA-3 will be popular in 10 years (a point for usage in API design etc). But those are temporary problems that might not even matter to you.
- CiPHPerCoder 7y agoThere are reasons to prefer other functions, but none of those are disqualifying marks on SHA-3. If you have SHA-3 available, just use it. Everything listed in that article is secure today and will probably be secure 10 years from now.
- mzs 7y agopaper: https://eprint.iacr.org/2019/459.pdf https://eprint.iacr.org/2019/459.pdf
- zdw 7y agoFrom the paper, this doesn't seem to be able to create a collision while retaining the same length of input data. It seems that checking both the hash and input length would be a very cheap way of identifying attempts at hash collisions.
- chrisseaton 7y agoIf you're going to modify your code to add an extra check you might as well just switch to another algorithm entirely.
- Someone1234 7y agoA lot of existing schemes already check both. The above comment didn't mention modification explicitly and could be read as talking about the level of threat this poses.
- yardstick 7y agoThis is one reason why HMAC-SHA1 is still safe.
- chias 7y agoThis is incorrect, the safety of HMAC-SHA1 doesn't have anything to do with input length comparisons. HMAC-SHA1 is still safe because of how an HMAC operates: Among other operations, HMAC begins by taking the secret key, XOR'ing it with a magic value not under your control, and using this as the first block when calculating an initial hash. In order to guard against an unlikely but potential pathological key / magic value combination, a similar operation is performed as a second round using a different magic value, and this time operating over the hash output from the first round. As such, HMAC operations are safe against chosen prefix attacks against the underlying hash function, because the first block in either round of hashing is entirely outside of your control. See https://i.imgur.com/PPlVPr0.png https://i.imgur.com/PPlVPr0.png for a visual reference. In this diagram, Y is the value being HMAC'ed. As you can see, any attack on the hash function which requires control of the prefix of the value being hashed is a non-starter.
- arkadiyt 7y agoTheir attacks are based on previous chosen-prefix work from Marc Stevens, who tweeted this about the attack [1]: "Their $100K figure is based on as-of-yet undisclosed improvements. History shows many claims of low-cost SHA-1 attacks that have not stood up to peer review. I am very sceptical that their attack costs in total less than the $110K building block (SHAttered) that they use." [1]: https://twitter.com/realhashbreaker/status/1128260422786854913 https://twitter.com/realhashbreaker/status/11282604227868549...
- pslam 7y agoMarc Stevens quotes $500K, which is very much still a threat (even an order of magnitude more would be). Plenty of organizations would be willing to spend that much pocket change on a single attack. The game-changer is it's chosen-prefix. A vendor can produce a pair of entirely different binaries with the same hash, but most importantly, they look and behave sane except for the last few blocks of the file. This is easily hidden, especially if the binary is encrypted. It's not a stretch of the imagination to see how, for example, an IP camera vendor could do exactly this. Yes, it requires a nefarious/complicit vendor, or an insider who can pull this off undetected (not everyone has a fully automated build/release pipeline). So it changes the threat model. SHAtter was waived by many because the threat model didn't convincingly apply to them. Example: git. That analysis needs to be repeated. (All this assuming the attack described in the paper is correct and practical in real world implementation)
- bin0 7y agoGit isn't really designed for cryptographic security, is it? I have heard that Linus wants it mostly secure so people can verify the integrity of linux source code, but it's not its core competency, so to speak. Though I suppose a project the size of the linux kernel could be a serious target for a collision attack. Regardless, it's switching to SHA-256: https://stackoverflow.com/questions/28159071/why-doesnt-git-use-more-modern-sha/47838703#47838703 https://stackoverflow.com/questions/28159071/why-doesnt-git-...
- gnomewascool 7y ago
- macawfish 7y agoLast night I was pondering about future "compression" schemes that relied on hyper-powerful quantum computers that can resolve hash collisions very, very quickly, so that rather than literally compressing the data, you'd just share a hash and then this hyper-powerful computer will enumerate possible strings of data that give that hash, and then check them against some secondary condition (another hash?) to find the right one. I don't know how feasible this actually is, but it made for an interesting sci-fi thought. edit: Thanks for all of the enlightening replies!
- paulddraper 7y agoThe problem is that is a huge number of strings that becomes a hash. Each SHA-256 hash has 2^(8 * 1024 - 256) = 10^2389 possible 1KB inputs. So...perhaps it could be done, but the quantum computer would have programmed with a very good selection criteria.
- stouset 7y agoNo, there is no way this could be done, because there is no way to know which of multiple colliding inputs was the right one. Imagine a one-bit hash function. You start your “decompression” process and read in a 0. What input produced that bit? Literally fifty percent of all possible strings would produce that same output. Without more information, you cannot choose between them. And the information needed to choose correctly is exactly the same amount of information in the original input. https://en.m.wikipedia.org/wiki/Pigeonhole_principle https://en.m.wikipedia.org/wiki/Pigeonhole_principle
- greiskul 7y agoYup, the pigeonhole principle really defines a hard limit on compression, in that it is impossible to compress (make smaller) ALL files. The way compression algorithms get around that, is by abusing the fact that we rarely want to send around arbitrary data, real world data has lots of redundancy in it, so we can make algorithms where real world data gets mapped into compressed files smaller then they are (by finding the redundancies in the data), and purely random data gets mapped into files that are actually slightly longer than the data.
- wolf550e 7y agoprevious discussion: https://news.ycombinator.com/item?id=19878917 https://news.ycombinator.com/item?id=19878917
- evv 7y agoCan collision attacks provide the same size of data? I suspect it would be dramatically more difficult to produce a collision of equal data-size as the original. So perhaps, the easiest way to defend against a collision attack is to transmit the size of the data alongside the checksum. Like a checksum, it is extremely lightweight and easy to check. In my data framework project (where I use sha1 to identify blocks), I've been looking for an excuse to do this, because knowing size of a block is incredibly useful for applying performance heuristics. I suspect it is also a significant defense against collision attacks. Am I wrong?
- jlgaddis 7y agoOr you could just switch hash algorithms to something stronger.
- a1a 7y agoYes, if I interpret your suggestion correctly. How would you know that the attacker have not manipulated the size parameter? That's the best case. Worst case you end up with a memory vulernability (see heartbleed https://xkcd.com/1354/ https://xkcd.com/1354/)
- chias 7y ago> How would you know that the attacker have not manipulated the size parameter? This scenario doesn't make a lot of sense. Say I have a goodfile that is 512 bytes long and hashes to 3d8850e1, and someone else wants to produce badfile and convince you that it's my goodfile. GP's suggestion is that I publish a size-plus-hash value "512-3d8850e1" for you to check against. If the attacker is in a position to alter the size part, they're also in a position to alter the hash part, in which case why even bother with a collision? They can just change the hash to be whatever badfile hashes to. The true answer to GP is that if you do this, it's no longer a hash function. A hash function is defined as taking an arbitrary input and returning an n-bit output for some fixed value of n. By including the size of the input in your output, the size of your output grows logarithmically with the size of your input. This may seem pedantic, but fixed-size-output and arbitrary-size-input is extremely important for general usage of a hash function.
- anderskaseorg 7y ago“Everyone should switch to (in order of preference): • BLAKE2b / BLAKE2s • SHA-512/256 • …” You know, SHA-512/256 was a terrible name. For someone who’s not a cryptographer, it’s way too easy to confuse the single algorithm SHA-512/256, which resists length extension attacks, with the pair of algorithms SHA-512 / SHA-256, which do not.
- foobiekr 7y ago"truncated sha512" would be a much better way to talk about it.
- wiml 7y agoIt isn't exactly truncated SHA-512 — that is, you can't compute a SHA-512/256 hash by computing a SHA-512 hash and then truncating it. Although the algorithm is the same as doing that, the initial state of the hash context is different. (The same is true for SHA-224, which could be called SHA-256/224; it's a truncated SHA-256, but with a different internal state.)
- foobiekr 7y agoTrue, that’s a good point.
- mehrdadn 7y agoDamn, I knew this and I'd forgotten it. Thanks for pointing it out.
- gcb0 7y agothat just goes to show how bad the name is. It doesn't trick you until before you learn, but it keeps on giving!