At 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.
> 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.
And 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).
Cloud computing makes this true for everybody else too now, at least within a practical range. Now I can easily afford a multi-million dollar distributed compute facility... for a few hours, rented from Amazon.
I'd be surprised if the NSA has a clear purpose for bulk colliding SHA-1. It's a pretty niche thing to want to do even compared to say, "cracking" DES. For MD5 we know such government agencies made some collisions to exploit various technologies that didn't stop trusting MD5 in a timely fashion, but it wasn't something they did a lot just one collision here or there as necessary. e.g. https://en.wikipedia.org/wiki/Flame_(malware)
This isn't actually true in practice though. Most of the cloud providers have quota's on accounts and actually won't let you provision that many resources without getting the quota's increased, which you are unlikely to be able to do unless you're actually regularly spending that much money.
I do think it's amazing that we can now script out a million dollar data center, build up, tear down for just an hour of use (and just a fraction of the cost). And that's available to ordinary people (with a little budget obviously). Compare what we had 20 years ago. Mind blown.
In theory [0], this problem is fully parallelizable, so you would be correct. Each mutation and hash calculation is fully independent so it can scale forever. On a national lab sized cluster, you could probably generate a collision in minutes.
[0] Have not read the paper thoroughly enough to determine if this is true for this technique
Not 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?
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.
The PHC string format 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.
I 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.
Not 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.
What'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].
SHA-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.
If 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.
The 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.
I proposed no method. I simply made the statement that typical cryptographic hash functions are optimal (and better than the alternatives) for high entropy passwords. I said nothing regarding low-entropy passwords.
Please justify why hashing a high entropy password should have a high cost. I can't see any benefit arising from this. If anything you lose entropy if you use something like pbkdf due to cycles.
Because it slows down anyone looking to crack/reverse the passwords? The only thing protecting your high entropy password is the cost of the hash. If you could run infinite attempts in 2 seconds then even your high entropy password would fail.
Anyways, most people don't use high entropy passwords, so there's little point in arguing against this IMHO.
"for a while" suggests that this was ever a recommended choice, which is not the case. As others have pointed out, for password hashing you want a specialized algorithm, not a general purpose cryptographic hash function. This is true regardless of whether the hash function is "compromised;" it just wasn't designed for that application in the first place.
Algorithms designed for password hashing are intentionally both compute and memory intensive, to make guessing slower, whereas general cryptographic hash functions are by contrast intended to be fast, as most applications will want that. The idea is that password hashing algorithms should be fast enough to keep up with a human and no faster; if you already know he password the performance is not a hindrance but if you have to guess it makes doing so impractical.
That's a fair point, I didn't want to come off like it was ever a great choice. I definitely would argue that people are more aware now than they used to be, so thanks for clarifying that.
What are some of the modern hashing alternative for uniqueness? Mainly for speed, bit distribution, and collision risk while having small hash size. Not for cryptographic purpose.
Depends on what you want to do. For hash tables and macs there is siphash. There is also Chaskey (although this is optimised for embedded systems I think).
I 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?
> 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.
No. 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.
1: 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.
The real question is why you would want to. You have a lot of other options! For example, on 576 byte messages on a core i7, eBASH reports the following performance characteristics:
- Blake2b (~20% faster)
- SHA-384/192 and SHA-512/256 (~50% slower)
- SHA-256 (~100% slower)
- SHA3-224 and SHA3-256 (~150% slower)
So if speed is absolutely important to you, like you are hashing millions of messages a minute and you have profiled and the speed of the hash function is absolutely the most important thing, then link the Blake2 or more recently Blake3 libraries and get the extra speed AND you don't have to deal with all of the security vulnerabilities.
Or, if speed is modestly important to you but you need to use primitives that are available on every single computer you will ever encounter, use SHA-512 and then truncate it to 32 bytes. Or if you really need that 160-bit level truncate to 20 bytes. (Truncation is usually a good thing with hash functions, defending against something called length-extension attacks.)
Or if you want to be substantially safer than all of these options and you are not doing a lot of hashing, use SHA-3. Also the performance of the others (that are not BLAKE) is generally somewhat artificially enhanced by dedicated processor instructions which will almost surely also happen for BLAKE (as it is based on the ChaCha cipher which is reasonably well used) and SHA-3 (as it is the new US government standard). I can't off the top of my head speak to the CoffeeLake Core i7 architecture without digging up some research about what instructions it implements, but its SHA-1 is 25% faster than its MD5 which suggests some dedicated SHA-1 instructions, at least.
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.
63 comments
[ 0.18 ms ] story [ 106 ms ] threadAs 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.
I'd be surprised if the NSA has a clear purpose for bulk colliding SHA-1. It's a pretty niche thing to want to do even compared to say, "cracking" DES. For MD5 we know such government agencies made some collisions to exploit various technologies that didn't stop trusting MD5 in a timely fashion, but it wasn't something they did a lot just one collision here or there as necessary. e.g. https://en.wikipedia.org/wiki/Flame_(malware)
[0] Have not read the paper thoroughly enough to determine if this is true for this technique
The test fails on my OpenWRT 19.07.03 router's Dropbear installation.
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.
[1] https://multiformats.io/multihash/#the-multihash-format
Edit: someone already detected this: https://github.com/multiformats/website/pull/62
It's been done before. ;)
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
[2] https://en.wikipedia.org/wiki/Preimage_attack
[3] http://www.phreedom.org/research/rogue-ca/
SHA256, SHA512 and Blake* algorithms are suitable for secure checksums and HMACs, but not password hashing
> argon2
It uses BLAKE2 internally
> I also see no benefit to that approach
- less primitives
- faster
- less memory usage
- no concern regarding cycles
Anyways, most people don't use high entropy passwords, so there's little point in arguing against this IMHO.
Good luck brute-forcing through 2^256 passwords. The speed of the hash function should not matter.
If you still want a slow hash function though then just use more rounds.
> The only thing protecting your high entropy password is the cost of the hash
No, not really. It is the fact that the password is high entropy, combined with the preimage resistance of the hash.
> If you could run infinite attempts in 2 seconds then even your high entropy password would fail.
So would your pkdf.
Algorithms designed for password hashing are intentionally both compute and memory intensive, to make guessing slower, whereas general cryptographic hash functions are by contrast intended to be fast, as most applications will want that. The idea is that password hashing algorithms should be fast enough to keep up with a human and no faster; if you already know he password the performance is not a hindrance but if you have to guess it makes doing so impractical.
But none of the SHA family of hashes have ever been recommended for passwords, not because they are weak, but because they are too fast.
For other purposes, the logical successor to SHA-256/512 is SHA-3:
https://en.wikipedia.org/wiki/SHA-3
But this is far from the only choice. Hashing algorithms are trendy right now, and there's plenty to choose from.
xxhash (https://github.com/Cyan4973/xxHash) with 32/64 bit output. The latest version, xxh3, supports up to 128 bit output.
meow hash (https://github.com/cmuratori/meow_hash)
The recently released Blake3 which is designed to be cryptographically secure is very fast also (https://github.com/BLAKE3-team/BLAKE3)
https://github.com/git/git/commit/28dc98e343ca4eb370a29ceec4...
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.
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.
2, and my real objection:
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.- Blake2b (~20% faster)
- SHA-384/192 and SHA-512/256 (~50% slower)
- SHA-256 (~100% slower)
- SHA3-224 and SHA3-256 (~150% slower)
So if speed is absolutely important to you, like you are hashing millions of messages a minute and you have profiled and the speed of the hash function is absolutely the most important thing, then link the Blake2 or more recently Blake3 libraries and get the extra speed AND you don't have to deal with all of the security vulnerabilities.
Or, if speed is modestly important to you but you need to use primitives that are available on every single computer you will ever encounter, use SHA-512 and then truncate it to 32 bytes. Or if you really need that 160-bit level truncate to 20 bytes. (Truncation is usually a good thing with hash functions, defending against something called length-extension attacks.)
Or if you want to be substantially safer than all of these options and you are not doing a lot of hashing, use SHA-3. Also the performance of the others (that are not BLAKE) is generally somewhat artificially enhanced by dedicated processor instructions which will almost surely also happen for BLAKE (as it is based on the ChaCha cipher which is reasonably well used) and SHA-3 (as it is the new US government standard). I can't off the top of my head speak to the CoffeeLake Core i7 architecture without digging up some research about what instructions it implements, but its SHA-1 is 25% faster than its MD5 which suggests some dedicated SHA-1 instructions, at least.
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&qu...
[1] https://alf.nu/SHA1