My takeaway from this post kind of is that there are probably too many variants and derivatives of SHA-3. Then again, these days normal developers should probably use some recommended interface of mature crypto libraries anyway and shouldn't play around with cryptographic primitives directly, so maybe more choice for the library devs is good.
> some recommended interface of mature crypto libraries
Maybe for bubble code it'd be okay to just say "gimma a hash".
But most real code needs to interoperate with stuff. E.g. I need to send a SHA-256 from a JS client to a Python server. So there needs to be a consistent and portable "SHA-256" concept that everyone understands.
A cryptographic hash is not a complicated concept (even if developing one is).
I suppose you can think about whether you require collision resistance or merely second pre-image resistance, but the popular ones are all intended to be collision resistant anyway.
Yeah all these discussions are rather aimed at people who implement cryptography or have to make a well-thought hash choice at some point.
As a developer you should use something like libsodium that has a default "hash" API. Underneath, the developers made the choice of choosing Blake2, but this is transparent to the user of the library.
If you do not have access to high level libraries like that, and don't want to loose time/dig too much into the topic, following standards (SHA-3) is easy.
Yes and no. After all, these are just modes using Keccak (think, say, AES-CBC, AES-GCM all use AES), so the choice depends more on the purpose than anything else.
But indeed, the naming is confusing. Instead of SHA3-256, SHAKE256, KMAC256 and ParallelHash256, maybe they should have better named them SHA-3-hash256, SHA-3-xof256, SHA-3-mac256 and SHA-3-parallel256 (or so).
Speaking of hashing quickly, I actually just posted an article about hardware-assisted SHA calculations and their support (or lack thereof) in mainstream processors, if anyone is interested.
This was really really interesting! I'm currently trying to get SIMD to work in Go, and my problem right now is that it's hard to understand which SIMD instruction I should support (MMX, SSE, SSE2, SSE3, SSE4, AVX, AVX2, ...?) and how I should test what my architecture supports. If you have any resources on that I'd take it.
[0] is a presentation on SIMD targeted at game developers. It has a lot of valuable information about instruction set support and how to make effective use of vector instructions. [1] is a HN comment that summarizes the content.
> If you have a 64-bit build, you WILL have SSE2 instructions
Go allows you to detect a few architecture when you build (amd64, arm, arm64, 386) but not really the CPU model. So using SSE2 for anything amd64/arm64 would probably be a good solution.
Anyone who thinks that Hacker News comments are a great source of information should consider the number of top-level commenters on this thread who don't know the difference between fast collision-resistant hashes and password hashes, but who decided to post as if they knew what they were talking about.
In fairness, this is because 1) password breaches are the lowest common denominator of hash function discussions in which developers participate, and 2) developers have it beat into their heads not to use e.g. MD5 for password storage, but they don't typically receive the same lectures (with the same vehemence) for things like MACs.
I don't really think this is much of an excuse. Fast collision-resistant hashes and password hashes are very basic crypto concepts. If you don't know that difference, it would be hard to pass even the most introductory course on cryptography. If you've literally no education on crypto except what you heard someone at work say once, you shouldn't feel qualified to correct crypto articles on Hacker News.
Ignorance isn't the problem. The problem is ignorance combined with confidence.
I think crypto is a field where one needs an unfortunately low amount of confidence (relatively speaking) to come across this way, because it's complex enough that the default position is extreme ignorance. That's why I try to be a bit more charitable - I don't think people are trying to come across as authorities on the subject, they just haven't had enough exposure. It's an unknown unknown. Better crypto education would help.
I've been thinking for some time now about the state of cryptography education for non-experts, and what I've noticed over the years is we push a lot of digestible soundbites ("Don't use MD5, don't roll your own, use encrypt-then-mac", etc) without significant explanations. Sometimes there is an accessible explanation for these things that's appropriate for a message board comment, sometimes there isn't, and this advice is necessarily separated from a larger corpus of material due to the medium.
If telling developers what not to do over and over again in order to dissuade them from shooting themselves in the foot has made them more secure overall, this is a good thing. But I do think it comes at the cost of not encouraging real understanding of why not to do these things. You're right that they shouldn't take specific positions without that understanding, but I think it can be hard for them to know they don't have it due to the culture.
Since you guys appear to be familiar with crypto, can you recommend some book/article/blog that give a good intro, to the level of explaining the difference between the two concepts above? Many thanks in advance.
Why would this matter? You can get an IETF RFC drafted on pretty much everything. Dan Harkins even got Dragonfly an RFC: https://tools.ietf.org/html/rfc7664.
No, you're confusing them with password hashing functions (bcrypt, scrypt) and password-based key derivation functions (PBKDF1, PBKDF2). These _are_ cryptographic hash functions, but they are designed to iterate many many times (the exact number is customizable) in order to take a given amount of time.
"Generic" cryptographic hash functions like SHA-1/SHA-2/SHA-3 (or BLAKE, or MD5) don't iterate more times than is necessary for security, and are designed to be as fast as possible. This way, you can hash multi-gigabyte documents in a fraction of a second.
No good hash functions are usually fast. You're talking about "password hashing function", and I can understand the confusion. Maybe if people decided to rename these "pash" it would be easier.
Anyway the state of the art here is Argon2 which won the latest password hashing competition: https://password-hashing.net/
I think we're circling back, KDFs are definitely not suited for hashing passwords. For example, you wouldn't use SHA-3(password) as a password hashing function, but it makes a fine KDF.
If you're thinking of PBKDF2, it's a "password-based" KDF as its name hints. While both password-based KDFs and password hashing functions seem to have common properties, I think the term "password hash" has caught up more (specifically thanks to the password hashing competition).
For passwords, yes. You want your hash function to be as slow as possible to reduce the impact of brute force attacks.
But for all other cryptographic purposes like message integrity checking, file verification, signing, or fingerprinting speed is extremely important.
In these cases, the input to the hash is generally public, so there is no reason to even try bruteforcing. And even if you did, these inputs are much longer than passwords.
But nVidia and AMD haven't sabotaged their chips to be bad at hashing (it wouldn't surprise me if they did the opposite back before ASICs thrashed the GPU bitcoin mining scene) so I don't see how your point transfers. The Powers That Be also haven't put a damper on bitcoin mining ASICs for that matter, which can do precisely one thing: calculate lots of SHA hashes faster than any other hardware.
If there's a shadow war over SHA hardware, the deep state is failing miserably.
The thing is, from the Snowden leaks, we _know_ that the NSA relies on being the most powerful hasher to identify people and things as they do. As I said, it's only a possibility that they could be actively trying to damper _consumer_ (not ASICs) SHA hash rates.
But it's unlikely. It's just a motive for them really.
SHA-3 in XOF mode can be used (and was expected to be used) as a KDF. XOF mode is part of the NIST SHA-3 standard.
SHA-3 is incredibly versatile. This obsession with speed is unfortunate. It's a great function. If you've ever implemented SHA-3, it becomes obvious that all of these modes are simple changes in parameters to the core Keccak function--basically either changing the number of rounds or changing the output window size. And many of these degrees of freedom of Keccak are standardized as part of the NIST SHA-3 standard.
Contrast that with the BLAKE family of hash functions, which all involve substantial changes to the core routine. It didn't have to turn out that way as the original BLAKE proposal was quite versatile, but the downside of being passed over for standardization is greater susceptibility to fragmentation.
Once the core SHA-3 routine begins to see hardware support all of this handwringing and bikeshedding will be forgotten. Choosing SHA-3 today is a solid choice and should be beyond reproach, whereas not choosing SHA-3 should require a substantial and continued defense.
Also, it should be pointed out that the excessive security parameters of the standardized hashing modes will likely be considered prescient once the era of quantum computers is firmly established.
That doesn't mean you wouldn't want to be able to brute-force it (in theory). If you're dealing with a data format where you can easily write garbage to a few bytes (e.g. executables) brute forcing would let you find a useful collision.
Of course a hash function that won a NIST competition a few years ago has nothing to fear from bruteforcing via a specialized CPU instruction :P
His point was that cryptographic hash functions can be designed to be both slow or fast for different purposes. Key derivation functions and password-hashing functions like bcrypt and PBKDF2 are designed to be slow to mitigate brute-force attempts. But general-purpose hash functions like SHA-3 are not designed to be slow; in fact, you'd rather they be fast, because they're designed to be used in e.g. MACs.
In general, cryptographic hash functions are designed to be computed quickly, and key derivation functions are a special subset with greater difficulty requirements designed to be computed slowly. Your comment conflated the two, hence the parent's response.
There are already a bunch of blockchain stuff using SHA-3 apparently. If people want to drop a list of products/companies/apps that use SHA-3 (or other Keccak construction) I'd be interested!
A bit off-topic, but I am currently trying to recover ~$70000 worth of ether[1] from my presale wallet and the encryption used is indeed SHA-3.
I'm currently trying 21970881 passwords against the hash using fairly basic python code (ETA: 2-3 days), and can definitely use tips for speeding up the work, as Id likely need to try an order of magnitude or 2 more generated password in order to crack it.
You should definitively use hashcat[0]. It's the fastest hashing tool at the moment, and it supports both PBKDF2-HMAC-SHA256 and SCRYPT for Ethereum wallets since the last update.
It can test 588 passwords per second on my modest GPU. I guess that's a lot better than a basic Python script.
You should also have a look at probable wordlists[1], which contains a lot of passwords sorted by their popularity. It could significantly speedup the research, as long as your password has already leaked elsewhere.
The password definitely hasn't leaked as it is a one time password I created based on a somewhat complex scheme, but switching to hashcat (as also pointed outby flipp3r) seems to be the best next step.
It sounds like you have it under control but I typically point people to Dave @ https://walletrecoveryservices.com/ for the less tech-savvy. He's pretty good. You can look at his site for what he can and can't crack. I know he's super super busy but it never hurts to give him a shout and ask him if he has any pro-tips or open-source code somewhere. A ping from someone who has a basic understanding of encryption might be refreshing.
Here are a random assortment of links I have saved regarding recovering presales:
It makes brute forcing more difficult, and promotes decentralization of infrastructure (slowness adds up only for large-scale deployments like Google and Facebook, and we want to depend less on centralized actors, not more).
If you need to choose between strength and performance, choose strength in nearly 100% of all cases. You make the job of NSA or GRU much harder, and promote offsetting security mechanisms to the edge, where they ought to be.
1) It means default-secure will not happen. If the NSA has to spend 10x as long to attack your security, but 1/10th as much communication is encrypted, it's a win for them (since now the simple fact that something is encrypted means someone put effort into it, which is a good signal that it will be useful).
2) Brute force attacks are typically embarrassingly parallel, and can be amenable to special purpose hardware (e.g. GPUs). An attacker with an 8 GPU system spend $10k and can attack PBKDF2 much faster than a $10k server will be authenticating people.
3) If your security relies on slowness, then people will pick less-secure defaults. If you can get an equivalent level of security per cpu-cycle, then people will pick a higher security margin (this is the non-binary version of #1).
3DES is way slower than most crypto primitives used today. I haven't seen it recommended much though.
This is simply not correct. There are a few cryptographic problems where slowness is the solution, but in most cases you want your cryptographic algorithms to be fast.
Could you please counter my arguments (brute force security against immeasurably larger computing power, resilience to novel unknown crypto attacks reducing the algorithm strength) with something more substantial than "this is simply not correct"?
I could, but doing so would likely involve teaching you a good chunk of crypto 101 while you try to tell me I'm actually wrong so you can be right, which would be enjoyable for neither of us. It would be more efficient for you to just take a introductory course on cryptography from someone more qualified than me. I'm not trying to be rude here, it's just clear that you've learned about password hashing and then assumed based on that one exceptional case that slowness is how all of crypto works. It's not, and you shouldn't make claims about all of crypto if the only thing you know about crypto is that password hashing works by being slow.
Once you've reached an appropriate security margin you shouldn't pour more resources into making it even slower. You don't typically need to choose between performance and security in a general sense, because you can achieve very good performance with very good security. Slowing down your password hashing function any further than is required is overkill, and won't improve your security.
Usually, security margins are planned against brute force according to Moore's law. This is not enough. Novel cryptographic attacks do not suddenly render the entire algorithm useless (usually); rather, they dramatically reduce its strength. And novel cryptographic attacks appear all the time even in the public space -- who knows what stays behind closed doors and clearances?
If you have large enough security margin, you can escape unscathed while you upgrade your infrastructure. And if not, not.
Sure, but even assuming Moore's Law, algorithms like SHA-2 and SHA-3 are not likely to broken within our lifetimes, if ever. For the set of hashing algorithms that are quantum-safe, you literally gain nothing in practice by making them arbitrarily stronger - they're already so strong that any increase in security margin is a negligible improvement slighter than a rounding error in computational time. But these improvements can come with a performance cost. There's generally no upside and only a downside for choosing to increase the strength beyond what's required for the sake of future proofing.
I think it's crazy that we're considering "settling" for a 128-bit hash function that we won't even start to adopt until 5-10 years from now, when Google is already planning to announce its 49-qubit quantum computer by the end of this year. It's also very likely that quantum computers will scale at a "Moore's Law" of sorts rate (doubling the qubits every 2 years or so, if not even faster in the first few years). We've seen that with D-Wave already.
I feel the same about all of those "faster" (read: weaker) IoT-optimized crypto algorithms that are being proposed right now for standardization.
What we should be talking about now is quantum-resistant algorithms that are likely to be even slower than SHA-3, but would at least protect communications against quantum computers. We need them soon, because they'll have to be deployed on 80%+ of the internet by 2030 or so, and we know how slow the internet ecosystem is at adopting a new protocol.
> I think it's crazy that we're considering "settling" for a 128-bit hash function
Actually the sponge capacity in the so called 128-bit keccak functions is 256, they only call them 128-bit because they provide 128bits of preimage and collision resistance (at 256 bits of output). In a quantum setting the difficulty for preimage and collision attacks for these functions is 2^(256/3), when assuming that the output is of at least 256 bits.
> What we should be talking about now is quantum-resistant algorithms that are likely to be even slower than SHA-3
SHA3-256 has c = 512 and output of 256 bits (128 bits of preimage resistance and ~85 bits of collision resistance on a quantum setting), while SHA3-512 has c = 1024 and output of 512 bits (256 bits of preimage resistance and ~170 bits of collision resistance on a quantum setting). I would say that both of the above sha3 versions are quantum resistant.
Most modern symmetric cryptography would safe in a post-quantum world, I would say that the only thing that is left is to adopt post-quantum asymmetric algorithms more widely.
Quantum computers are pretty unlikely to follow anything like Moore's law. They are fundamentally difficult to scale up due to decoherence and compounding of errors, a property that digital circuits have never shared. It's not "just" a matter of increasing density or clock rates.
I'm not sure if SHA-3 has a design goal of being fast. My understanding is that, if your using it for encryption, for example password storage, you want it to be slow. This helps with brute force attacks, particularly if someone gets ahold of your database full of password hashes and can unleash as many calculations as they want. Because the SHA family has typically been fast, they are considered bad candidates for passwords. My quick Google foo doesn't turn up the goals of the competition, but I'm guessing being fast might be a negative.
Remember, what you are talking about is only one application of hash functions. In the world of crypto, speed becomes very important in things like MACs and signatures. There are a ton of other uses for hash functions that are not crypto-related too!
Besides, even when using a "fast" hash function for password storage, you can always just increase the number of rounds to compensate.
Highly recommend using Argon2id/Argon2d/scrypt/bcrypt/PBKDF2 (in that order of preference) for password authentication/"storage." While SHA-3 might be slower than other fast hash functions, it's not at all designed for the same purpose. Functions suitable for password authentication are not merely CPU-intensive, but also memory-intensive.
From the SHA3 Round 1 results: "NIST expects SHA-3 to
offer improved performance over the SHA-2 family of hash algorithms at a given security strength"
KDF != PB-KDF / password hashes. There is no need that a KDF needs to be slow, e.g. you want fast handshakes for protocols (e.g. TLS), not slow handshakes.
