SHA-3 Standard [pdf]
nvlpubs.nist.gov
nvlpubs.nist.gov
Did NIST make any changes to the algorithm since? From what I can tell it looks like they only made clarifications.
To celebrate, here's a hacked-up keccak-512 implementation in Rust: https://github.com/pshc/keccak (I have yet to check whether it's actually SHA-3.)
Glad to see it sets c = 2d at least.
Here are responses to draft comments: https://www.federalregister.gov/articles/2015/08/05/2015-191...
For that matter, I haven't looked at the algorithm. Is it readily implementable in hardware?
Aww. Is there any news on a standard (NIST, or just informal RFC) on an authenticated encryption mode for KECCAK? I remember seeing a presentation of KECCAK at passwords[1] -- and I thought that part looked the most fun ;-)
My current favorite conservative hash choice is SHA512/256, which is the SHA-2 that generates a 512-bit output but truncates it to 256. It gives you the same length extension protection that is the most important feature of SHA-3, and is available in most libraries already.
I have never recommended to anyone that they switch from SHA-2 to SHA-3. I'm actually in "wait and see" mode about SHA-3; there are compelling other hashes available if you want to be ultra-modern about which hash you use.
Wikipedia indicates that there has been at least some progress as far as cryptanalysis goes, but even with that being said, there's always that lingering 'but what if' about anything NSA-related.
No cryptographer I know takes these particular "what-if's" seriously. They appear to come exclusively from non-cryptographers reacting to anything that NIST touched.
See http://bench.cr.yp.to/results-hash.html for a comparison of hash-function speeds.
To extend on that, shortly after SHA-1 fell, there was the very real threat that the SHA-2 family would follow suit (they are conceptionally similar). This worry brought NIST to hold the SHA-3 competition. Fortunately, the SHA-1 attacks did not turn out to be transferrable, so far, and consequently trust in SHA-2 has substantially increased since. Still, NIST (rightly) followed through with the initial idea of the contest and chose a hash function that was as different from SHA-2 as possible (Keccak).
Thus, we have now two very high quality hash functions to our disposal. If you need a really conservative choice, hash the message m as SHA512(m)||SHA3-512(m) (the concatenation of the individual hashes). This construction is collision resistant if at least one of them remains collision resistant. (Pseudo randomness relies on the security of both hashes, though, and hashing the whole message twice comes at a hefty performance hit. Especially since SHA3-512 is veeery slow – blame it on the clueless tech media attacking NIST for tweaking Keccak, ignoring even the authors who supported NIST's decision.)
Although keep in mind that you'll leak information about the input if either hash leaks information about the input.
For example, the hash function `badhash(blocks) = crc(blocks) ++ goodhash(blocks)` is collision resistant... but you wouldn't want to use `badhash(pad(secret) ++ nonce)` as a precommitment scheme. All of the extra entropy in the nonce, which otherwise might have protected against brute force attacks on low-entropy secrets, is being given to the attacker via the crc.
Actually, it isn't, for the usual definition of collision resistance compares the work factor to find a collision against 2^(hash_length/2). Extending a hash with crc32 lengthens the hash, but increases the bar for considering the hash collision-resistant. Concatenating the outputs of two collision-resistant hash functions doesn't even (generally) result in a collision-resistant construction under the normal definition of collision resistance.
EDIT: See my nearby post in this same thread for a longer explanation.
Please don't throw around well-defined terms. This isn't true.
What you mean is that "the work factor for finding a collision in the concatenated pair is at least the max of finding a collision in either half of the concatenation." That's a true statement.
On the other hand, collision resistance is a comparison between 2^(hash_length/2) and the work factor required to find a collision. Concatenating the two outputs would only remain collision resistant if it caused an exponential increase in the work factor to find a collision.
Since the SHA-512 output is the whole hash state, once you've found a SHA-512 collision, you can keep appending to the two collided documents and they'll stay collided, so you can use this as a starting point for your SHA3-512 collision. So, even assuming no weaknesses, the work factor to find collisions in your 1024-bit concatenated construction is 2^256 + 2^256, not 2^512, and thus not collision resistant.
Note that some hash functions output only half of their state vector as the final hash. If you built your construction out of two such hash functions, and no weaknesses were found in either, then your proposed construction would be collision resistant. However, as proposed, it's not collision resistant, even if both underlying hash functions are collision resistant.
Actually, as long as the hash functions are iterative, the whole construction can never be significantly stronger than the best hash function, see [1].
> What you mean is that "the work factor for finding a collision in the concatenated pair is at least the max of finding a collision in either half of the concatenation." That's a true statement.
What I meant was "as long as it is infeasible in practice to find a collision in either of them, it is infeasible to find a collision in the concatenation". Comparing the security of hash functions to random oracles with the same output length only makes sense if the construction of the hash function supposedly affords this security.
Conversely, I find it absurd to call the hash function that outputs the first 64 bits of SHA-1 collision resistant, because it requires at least 2^32 steps to find a collision. It fits with the oracle definition, but gives you no information about its real world security.
If you want to make precise statements, you can add the work factor to your statement, e.g. "The first 512 output bits of SHAKE-256 afford preimage resistance up to a work factor of up to 2^256".
[1] Antoine Joux. Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions. In Advances in Cryptology - CRYPTO 2004, volume 3152 of Lecture Notes in Computer Science, pages 306–316. Springer Berlin Heidelberg, 2004. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.128...
Or you can ignore both sha256 and sha512/256 and use something else like sha-3 or blake2b. Blake2b obviously has less attention on it so more likely to harbor a weakness, but it's fast in software. And sha-3 will get cpu extensions eventually, and it'll hopefully be a better thought out inplementation than just support for the 256-bit variant.
I'm still quite a fan of it and was sad that it lost. Both are excellent algorithms however.
Granted faster is better for non-cryptographic purposes like data indexes, but even there I'd consider performance secondary to the hash size, etc
For general purpose hashing, you want to check if the fingerprint of these ten gigabytes of data is the same as the fingerprint of these other ten gigabytes, as quickly as possible. Or whether a file that you downloaded is the same as this other file. Or whether the data that you transferred has been tampered with or corrupted. Speed is important enough that this was one of the criteria in the hash algorithm selection process.
The key feature of a general purpose hashing algorithm is resistance to preimage attacks. In other words, "If I want hash 0x123456, what should the input be?" needs to be a difficult question to answer.
Speed is key when you are getting a fingerprint of a large amount of data. Don't use a general purpose hash directly for hashing passwords: It's better than plain text, but it's inferior by a long shot to special purpose password hashes.
"The SHA-3 family consists of four cryptographic hash functions, called SHA3-224, SHA3-256, SHA3-384, and SHA3-512, and two extendable-output functions (XOFs), called SHAKE128 and SHAKE256."
If BLAKE isn't intended for cryptography then it's not a direct competitor to SHA-3.
Password checking is an edge case. Special purpose password hashing functions with tunable difficulty should be used for those. Do not use general purpose hash functions: They are better than plain text, but they are designed to be fast, and this makes it easier to brute force them.
There is definitely a trade off between the two (performance on servers vs rate of passwords an attacker can crack). But generally the advice is to go for the slowest you can afford. Hence why KDF's have an iteration parameter so passwords can be hardened as harder gets faster.
Trying to make one that does both leads to something that sucks at both.
That's not true either. Hashes are recommended to be used as input to KDFs.
"Modern password-based key derivation functions, such as PBKDF2 (specified in RFC 2898), use a cryptographic hash, such as SHA-2"
Source: https://en.wikipedia.org/wiki/Key_derivation_function#Key_st...
> Trying to make one that does both leads to something that sucks at both.
eh? Nobody is advocating that what-so-ever. Not me, not anybody.
I think you're now arguing with me for the sake of arguing with me. :-/
While KDFs do use hash functions internally, the hash function is an implementation detail.
At the time of the RFC publication it was already obvious its security was way behind bcrypt that was used in OpenBSD since 2.1 (June 1997), which did its best to be ASIC hostile, which isn't the case for PBKDF2.
In retrospect, NIST choosing PBKDF2 over bcrypt in NIST SP800-132 could be seen as part of the effort to weaken standards for NSA profit.
https://www.schneier.com/blog/archives/2012/10/keccak_is_sha...
https://www.imperialviolet.org/2012/10/21/nist.html
tl;dr: Keccak is not a good partner for PBKDF2. It has good hardware performance but comparatively poor software performance. This benefits attackers with FPGAs or better.
Best practice would be to use a KDF with a hash salt, but in a lot of cases, SHA2 + salt + pepper is sufficient.
hint: they're used for more than that.
you are woefully out of your depth here.
I very much doubt that since I've been able to provide back up sources to evidence my points. However if I am wrong then please do educate me instead of posting uninformative troll comments like the above.
If you didn't know that BLAKE was one of the entries in the SHA3 competition (one of the finalists in fact), I think you are out of your depth.
Furthermore, the way you conduct yourself in these posts isn't exactly helpful. You're condescending and terse. Your comments contain the bare minimum information (or in the case of this latest exchange, no useful information what-so-ever) and it feels very much like you're more interested in winning ego points than you are in educating someone who could clearly benefit from your greater wisdom. Which is sad because without that exchange of knowledge, these kinds of threads will keep happening.
edit: that said, I did appreciate your comment about hardware vs software: https://news.ycombinator.com/item?id=10012537 so thank you for that post :)
The "digging deeper" was more down to responding to other people who had misunderstood my original comment. And lets be honest, there has been a lot of that as well.
edit: oh jeez, someone's been on the rampage with the ▾ clicking. I think it's time I get HN a break because the moderation on here has really been bugging me in recent months. I know it's a tired cliche, but I'm sure this community used to be less hostile. </soliloque>
Stream ciphers should be fast.
Message authentication should be fast.
Hash functions can be used in any of the above, therefore it should be fast. Key derivation functions generally work by taking a secure hash (that can be done fast), and then taking an operation that transforms the output of the hash function to another output that requires a lot of time and/or memory. And then possibly takes the hash of this as well to obscure the internal workings. The "slowness" is part of the KDF, and not part of the hash function. The reason it's tuneable is because it doesn't matter how fast the hash is, you can just run more iterations.
Not even close. The attempts/sec you can run against SHA-2 vs. the attempts/sec you can run against bcrypt or scrypt are an order of magnitude apart.
You should not use anything less than a proven KDF (scrypt, bcrypt, PBKDF2-HMAC-SHA2 with a lot of rounds) for password storage.
Many of your posts conflate "cryptographic" with "password hashing", which is certainly not the case. Note that PBKDF2-HMAC-SHA2 does not (at all) mean that SHA-2 is useful for password hashing. As someone else pointed out, that's just an implementation detail.
Although we do want hashing to be slow when it's password hashing, that doesn't mean we want our general-purpose hash primitives themselves to be slow.
I thought using hashing to save passwords is misusing cryptographic hashes for something they were not intended to do? (Assuming they will keep the input secret as opposed to preventing finding colliding duplicate inputs?)
The point of hashing passwords is it's a one-way cither. ie can't be unencrypted - can only be brute forced or rainbow table attacked (the latter is where salts and peppers come into the equation).
I didn't make that assumption. I exampled one use of cryptographic hashes as being for password hashing. An example is not the same as saying two things are the same.
I've possibly expressed myself rather poorly, but I think quite a few people on here have made some incorrect assumptions about the point I was raising.
Your comment (none of them, really) was not at all reasonable, assuming as it did that cryptographic hash is synonymous with password hash.
There is no use case where you want your super-fast hash to be 50% slower.
With a hash this fast you need to get thousands or more times slower to have any benefits in those specialized use cases.
It's sort of a bathtub curve.
SHA3 and BLAKE are cryptographic hash functions, but they are fast collision resistant hash functions, NOT key stretching functions. They're primitives used in the construction of other cryptographic tools. Some cases where you might use a fast collision-resistant hash:
* Timing-attack-resistant string comparison: if you're comparing API keys, you should hash them both first to prevent an attacker from guessing the keys a character at a time.
* HMAC (look it up).
* One can implement key stretching functions by applying fast collision-resistant hashes multiple times.
* Signing (one can hash a message and sign the hash, which provides as much security as signing the message itself).
* Fingerprinting (a fast hash of a public key can be used as shorthand to verify public key ownership without having to read off the entire key).
* Addressing (Bitcoin uses a fast hash of a public key as an address).
Maybe my "wealth of other content online" comment pissed a few people off - but equally I was pissed off that my original comment was downvoted so heavily with a few comments that weren't entirely accurate in response (I've often said the negative rep on HN gets over used and often causes more arguments - but that's another topic). Anyhow, I've removed my offending comment now and glad to see that the quality of responses have improved :)
Even assuming we're optimizing our selection for a KDF, blake2 is probably still the better choice. An attacker is likely to be using a hardware implementation. Your server is using software. An algorithm that's comparatively efficient in software reduces the disparity in capabilities.
For example, suppose I give you the hash of a random 128 bit network packet payload, and you have hardware to evaluate the hash function I used a quintillion times per second. How long will it takes you to find that packet? Well, there's 2^256 possibilities and you go at a rate of 10^18 per second, so... 2^128/10^18s ~= 10 trillion years.
Key derivation functions (i.e. password hashes) are a specialized version of hash functions for private low-entropy inputs. They need to be slow to prevent quickly enumerating and evaluation all likely inputs. Paying that time cost would be unnecessary, wasteful, and bloated for inputs that are public or high-entropy.
For example, Git would suffer enormously if it used a key derivation function instead of a standard hash function. Useful operations like rebase and squash would go from taking milliseconds to taking minutes or hours.
BLAKE uses the same basic construction as MD5 and SHA1, neither of which is a responsible choice for a collision-resistant hash function any more. While attacks producing collisions have not been presented, this construction means it's susceptible to some other attacks. There are well-understood ways to avoid these attacks, but a naive usage of BLAKE2 in a production system will likely leave you open to length extension attacks in particular.
Keccak, on the other hand, uses the novel sponge construction, which injects content into the hash (absorb phase) and then iterates a threshing function (squeeze phase). This construction specifically addresses security concerns which BLAKE2 simply doesn't.
To be clear: I do think the BLAKE developers made a good contribution to the security community: particularly, using ChaCha makes their algorithm very fast, and I suspect that the next generation of fast collision-resistant hash functions will use ChaCha in the sponge construction. There are situations where BLAKE is a better choice than SHA3. But its use requires a great deal of knowledge and care to be secure, and for the average person implementing a secure system, SHA3 is a much more responsible choice.
Security should not be taken lightly. Bad security can expose people's private information and get people jailed, doxxed, and sometimes even killed. Glibly claiming BLAKE is better without any discussion of the security properties of the algorithms is completely irresponsible.
As far as security goes, Keccak and BLAKE are mostly in equal standing both in security margin (number of rounds attacked vs total number of rounds) and cryptanalytic attention received.
I did make a mistake understanding the algorithm. You're mostly right: no length extension attack has yet been found. However, HAIFA is far more similar to MD than the sponge construction, and this is widely cited as a reason for Keccak's selection.
> As far as security goes, Keccak and BLAKE are mostly in equal standing both in security margin (number of rounds attacked vs total number of rounds) and cryptanalytic attention received.
Then why was Keccak selected? It's clear that at least some analysts think Keccak has significant advantages over BLAKE.
And ultimately my point still stands: a comparison of cryptographic hashes should start with a discussion of their security properties. Glibly stating "it's faster therefore it's better!" is highly dangerous.
It is in the compression function (resp. permutation) that Keccak differs the most from BLAKE. BLAKE is ARX-based---like SHA-2---while Keccak only uses bitwise operations. Since SHA-2 is not being deprecated by NIST, they figured that having a 'different' SHA-3 would hedge their bets against an attack against ARX primitives that could potentially break both SHA-2 and {BLAKE, Skein}. This is stated in [1, §3.4]. This has nothing to do with the MD structure.
Sure, when discussing these things security does come first. But all of these functions have been thoroughly vetted already, so the differentiators are elsewhere: sponges are flexible, BLAKE is faster in software, etc.
[1] http://nvlpubs.nist.gov/nistpubs/ir/2012/NIST.IR.7896.pdf
Can you also please explain some of these other attacks you're talking about it sharing with MD5 and SHA1? The commonality between MD5, SHA1, and SHA2 is the Merkle Damgard structure. BLAKE2 isn't an MD hash. Are these MD attacks that you're asserting apply to BLAKE2?
I'd like to know where the certitude you're projecting is coming from.
No, you're right: I misunderstood the algorithm; an extension attack has not yet been found. My core point still stands though: choosing a cryptographic anything should start with a consideration of the security properties of the algorithm, and only then should we talk about speed.
See http://ae7.st/p/5px. I'm using the reference code at https://github.com/BLAKE2/BLAKE2 for blake2, and https://jxself.org/git/?p=skeinsum.git for skein.