7 ms·
SHA-1 collisions now cost $45k [pdf]
- johannesgoslar 6y agoNot a crypto expert, how easy/hard it is with this (or other techniques) at the moment to generate a random file which matches a given SHA1 hash? Can have totally random bits lets say.
- dependenttypes 6y agoThis is not a preimage attack.
- gregmac 6y agoWhat's been done here is a chosen-prefix collision attack [1] where the attacker can produce two files that have the same hash. What you're asking about is a preimage attack [2] where one of the files is already created and the attacker can't influence it. The practical attack enabled here is mostly around digital signatures. An attacker could produce documents A and B that both have the same SHA-1. They can then get someone to sign document A (which really is signing the SHA-1 of document A), then use the signature with document B and make it look like they have a document B signed with a valid signature. As an example, if document A is a regular SSL certificate request, and document B is a "CA certificate", the attacker can trick a real CA into signing a rogue CA into existence, which can then sign its own certificates that will be trusted by every browser. This has already happened with MD5 in 2008 [3]. [1] https://en.wikipedia.org/wiki/Collision_attack https://en.wikipedia.org/wiki/Collision_attack [2] https://en.wikipedia.org/wiki/Preimage_attack https://en.wikipedia.org/wiki/Preimage_attack [3] http://www.phreedom.org/research/rogue-ca/ http://www.phreedom.org/research/rogue-ca/
- dependenttypes 6y agoIt should be noted that certain modern signature schemes (such as ed25519) are fine with just preimage resistance.
- throwaway2048 6y agoEven MD5 is still strong against that sort of attack
- tyingq 6y agoHTML summary of the same content, by the same authors: https://sha-mbles.github.io/ https://sha-mbles.github.io/
- haunter 6y agoNice URL
- wiz21c 6y agoIt also cost 2 months (FTA)... So the ever returning question is : how long does it take when NSA/military/government-levle funding is applied ?
- veonik 6y agoIt would scale linearly right? Double the amount of computing thrown at it, you'd half the time on average. Or am I mistaken?
- sansnomme 6y agoDepending on the algorithm, you might be able to skip from GPGPU straight to ASIC.
- DaiPlusPlus 6y agoAt this scale - I’m not convinced that $5,000 worth of ASICs would have the same performance as $5,000 worth of GeForce cards - especially after factoring in lead-time to design the ASIC. As for FPGAs - forgive my ignorance - but can they even handle that kind of load? In my head I just see them breaking-down under the sheer thermal load.
- nordsieck 6y ago> As for FPGAs - forgive my ignorance - but can they even handle that kind of load? In my head I just see them breaking-down under the sheer thermal load. They worked for Bitcoin before miners switched to ASICS; I imagine they'd be fine in this application as well.
- finnh 6y agoAnd of course double the compute for half the time = same cost (more or less). I would imagine the NSA has sunk enough into hardware to do this fairly cheaply per-pass, and very quickly (hours not weeks).
- deleted 6y ago
- xwdv 6y agoWhat could get the cost down even lower?
- notyourwork 6y agoIncreasing supply by making them more easy to compute?
- mxz3000 6y agoFaster/cheaper hardware probably
- mxz3000 6y agoCheaper/faster hardware probably
- est31 6y agoAs a reaction, Openssh will deprecate SHA-1 support in a future release: http://www.openssh.com/txt/release-8.3 http://www.openssh.com/txt/release-8.3 The test fails on my OpenWRT 19.07.03 router's Dropbear installation.
- cellularmitosis 6y agoNot knowing much about binary executable formats, what does this mean for binary executables or libraries? How easy is it to insert e.g. a remote shell or keystroke logger into an executable or library using only a prefix? Or would that require arbitrary in-place edits to a file?
- guipsp 6y agoIf you control the executable then it's easy. If you can only append then it's harder.
- rudolph9 6y agoOne of the best things to come out of protocol labs is https://multiformats.io/ https://multiformats.io/ Really simple mechanisms for things like identifying the hash algorithm and gives you a programmatic way of supporting new hash algorithms without breaking or changing anything that depends on the old.
- kardos 6y agoThe first example [1] doesn't have the hash-func-type prefix [1] https://multiformats.io/multihash/#the-multihash-format https://multiformats.io/multihash/#the-multihash-format Edit: someone already detected this: https://github.com/multiformats/website/pull/62 https://github.com/multiformats/website/pull/62
- tmcw 6y agoThe PHC string format https://github.com/P-H-C/phc-string-format/blob/master/phc-sf-spec.md https://github.com/P-H-C/phc-string-format/blob/master/phc-s... (used by stuff like Rust's LibreAuth/BoringAuth) is a less fancy but probably better-suited-to-passwords solution, because it can indicate salt values and additional parameters.
- dependenttypes 6y agoI do not think that this would work for the hashes that are used in signatures sadly. In addition I do not see the point for the digest-length parameter.
- owenmarshall 6y agoman 3 crypt | fgrep '$' It's been done before. ;)
- ww520 6y agoHow safe is SHA-256 now? Or Is SHA-512 needed in the near future?
- easterncalculus 6y agoSHA-256 is still secure for plenty of applications, but for awhile it's been regarded as a suboptimal choice for password hashing. SHA512 is probably overkill.
- eadan 6y agoNot only sub-optimal, but unsuitable. Use algorithms specifically designed for password hashing: argon2 / scrypt etc. SHA256, SHA512 and Blake* algorithms are suitable for secure checksums and HMACs, but not password hashing
- dependenttypes 6y agoI disagree, I would argue that they are optimal for passwords with sufficient entropy (which includes passwords generated by a password manager) > argon2 It uses BLAKE2 internally
- willcipriano 6y agoIf you have two solutions and the first solution requires humans behave in a certain manner (getting them to use high entropy passwords) and the second does not. The second is more secure.
- dependenttypes 6y agoI do not see how this is relevant to what I said.
- willcipriano 6y agoThe method you purpose is less secure as humans often use low entropy passwords even when you ask them not to. If you are building a system only for humans that use high entropy passwords (are you really willing to bet the farm on that just to save a couple clock cycles) or other machines it might work but I also see no benefit to that approach so you might as well just bcrypt it and call it a day anyway.
- dependenttypes 6y agoIs git fixed yet?
- est31 6y agoIf you wonder whether Git supports non-sha1 hashes yet, then it's not ready yet. But it is "fixed" in that it includes code to detect sha1 collisions: https://github.com/git/git/commit/28dc98e343ca4eb370a29ceec4c19beac9b5c01e https://github.com/git/git/commit/28dc98e343ca4eb370a29ceec4...
- dokument 6y agoI understand not wanting to use SHA-1 now for security reasons, but is it still an OK practice to use it as a general hashing function for a uuid/data checksum?
- AlexanderDhoore 6y agoAre you protecting against random accidental data corruption? Or malicious attackers?
- hinkley 6y agoEveryone is protecting against accidental data corruption, until someone figures out how to turn it into an attack. Even when you ask people "is there any universe in which this could be used as an attack?" most people will reflexively say "no, of course not." Most of us are wrong, which is why you have professional pen testers.
- a1369209993 6y ago> is it still an OK practice to use it as a general hashing function for a uuid/data checksum? No. If you don't care about collision resistance, use MD5. It's faster, it's smaller, and it makes it obvious to everyone than your software isn't supposed to rely on collision resistance.
- mD5pPxMcS6fVWKE 6y agoNo. MD5 is a cryptographic hash function. For the purposes stated one uses a non-cryptographic hash function, such as seahash. The difference is the latter is much faster but does not provide protection against an intentional collision.
- a1369209993 6y ago1: MD5 still provides preimage resistance (both first and second), which is sometimes useful. 2, and my real objection: $ md5sum /dev/null d41d8cd98f00b204e9800998ecf8427e /dev/null $ seahashsum /dev/null <stdin>:2:0: seahashsum: command not found That said, my main point was don't use SHA-1, because if you actually need a half-broken hash function for something, MD5 has all the same properties (good and bad) for cheaper.
- dang 6y agoBig discussion of the same material from 4 months ago: https://news.ycombinator.com/item?id=21979333 https://news.ycombinator.com/item?id=21979333 Please don't editorialize titles. This one broke the site guidelines badly. Cherry-picking the detail you think is most important from an article is editorializing. Threads are sensitive to initial conditions and the title is the dominant initial condition, so this is a big deal. Being the first (or luckiest) user to submit an article doesn't confer any special right to frame it for everyone else. HN readers should make up their own minds about what parts of an article are important. If you want to say what you think is important about an article, that's fine, but do so in the comments. Then your view will be on a level playing field with everyone else's: https://hn.algolia.com/?dateRange=all&page=0&prefix=false&query=by%3Adang%20%22level%20playing%20field%22&sort=byDate&type=comment https://hn.algolia.com/?dateRange=all&page=0&prefix=false&qu...
- thanksforfish 6y agoRemember, collisions can be reused[1] to create lots of pairs of files with the matching hashes. [1] https://alf.nu/SHA1 https://alf.nu/SHA1