BLAKE2: “Harder, Better, Faster, Stronger” Than MD5
leastauthority.com
leastauthority.com
No competent new design in 2014 would use SHA1 either.
In the world we live in now, there are two "mainstream" options for hash functions: SHA2 (ie, SHA2/256, SHA2/512, &c) and SHA3. SHA3 is actually not at all mainstream (very few applications use it), but (a) that will change over time and (b) nobody will really bat an eyelid if you choose to use it.
What Zooko is advocating for is a third mainstream option: BLAKE2. BLAKE2 is derived from a well-regarded SHA3 finalist; the preponderance of evidence suggests that BLAKE2 is safe, and arguably a more conservative choice than SHA3 (a/k/a Keccak, pronounced "Ketchup"), because SHA3's novel sponge function design hasn't been banged on the way SHA2's design, which BLAKE sort of shares, has.
The reality is that for most software designers, this isn't an important issue; most software isn't constrained by the speed of its hashing algorithms (the common bottleneck in crypto code is the bignum work public key algorithms have to do --- if you're worried about bottlenecked on hashing, you probably have a much bigger problem with I/O).
As always, thanks for playing "HN asks tptacek about security."
[^1]: This is a genuine question. I do not have any reason to doubt zooko et al's judgement. I guess another way of saying this is "For someone smarter than me is it easy to know when this is a good/bad idea?"
Strange segway: I was browsing Plos and saw this article about egg washing and shell characteristics. After reading the title for some reason I remembered reading a somewhat lengthy comment you wrote about the safety of eggs and different egg washing regimes in the us and the uk. I did not check too see if my recollection was accurate but in case it is and the comment was indicative of your interest in the subject you might get a kick out of:
Effect of Egg Washing and Correlation between Eggshell Characteristics and Egg Penetration by Various Salmonella Typhimurium Strains. PLoS ONE 9(3): e90987. doi:10.1371/journal.pone.0090987
http://www.plosone.org/article/info%3Adoi%2F10.1371%2Fjourna...
I also hope to see more non-standard crypto and protocols, where "the market" leads the way, and standards groups try to keep up in order to appear legitimate.
This is super-dangerous, unless the amorphous "market" is also paying for cryptanalysts to bang on the crypto primitives as a public service to all competitors in the market.
After all, RSA adopting Dual EC DRBG was a business decision, and one which the market didn't reverse despite Dual EC DRBG being publically known to have a probable backdoor since 2007.
If you think Joan Daemen is an NSA plant, you've got bigger problems than hash functions.
The IETF writes RFCs which developers are expected to follow, and (mostly) do. This is a standardization of sorts, but it's beside the point I was making.
I'm not talking about Joan Daemen wrt BULLRUN. I'm referring to secure protocols that offer RC4 but not Salsa20, TLS without a single constant time cipher, 112-bit security, secure protocols that aren't even encrypted, null ciphers, Dragonfly, cipher suites so complex that they're expected to be implemented wrongly, secure protocols made so complex they won't be used at all, crypto advisory groups run by NSA employees, etc.
It's worth mentioning here that the "encrypted by default" Internet that was the dream of the 1990s was a government project, and TLS more or less thwarted it.
Different ciphers can be more or less straightforward to implement without timing leaks, but "constant time" is a property of an implementation, not of a cipher.
Dragonfly is exceedingly lame, but it's also completely inside-baseball. Even if Dragonfly had been "standardized" by the TLS WG, nobody ever would have used it, because nobody ever used SRP either, and SRP was better.
The ciphersuites in TLS aren't complicated. They're very simple. The problem with TLS ciphersuites isn't that they're complicated but that they're wrong. Which is unsurprising, because they were designed before anything like Bellare and Namprempre; in fact, they were designed in an era where many practitioners believed that message authentication was unnecessary for cryptosystems at all.
I'm not sure which complex secure protocols you're referring to. TLS and SSH are so widely used it seems fair to call them universal.
As for the CFRG chair, well, I won't repeat myself:
https://news.ycombinator.com/item?id=6942145
In the end, though, the real issue I have with your comment is that the IETF has nothing at all to do with BLAKE2's standards- friendliness. The IETF will soon standardize ChaCha20-Poly1305 for TLS, for instance, despite the fact that no NIST standard will ever do the same.
but databases, filesystems, checksums for packages, git(to be fair, they're all some sort of storage systems)
by the definition you said above we would still be using md5 in everything.
Since SHA-3 is now based on a totally different architecture, any weakness in SHA-2 has no effect for SHA-3. At the same time, if someone does find an attack against SHA-3, SHA-2 is still secure.
If you care about performance, stick to the standard.
Another commenter also rightly pointed out that SHA3 implementations will be more scrutinized, and therefore more secure. Exploitable security issues lie rarely in the algorithm.
Long story short: stick to the standard.
ahem... http://en.wikipedia.org/wiki/Dual_EC_DRBG
when you can no longer trust the organizations setting the standards (NIST, CFRG) this argument looses water.
If the algorithm had been left unstandardized and was simply "Foo Corp's Custom Wonderful Bit Generator™" the public may never have known of the vulnerability, while the NSA would still have the resources to have discovered the flaw on their own and use TAO to recover the priv key.
Also, wouldn't we rather trust software implementations than hardware implementations post-Snowden revelations? Isn't that the same logic behind PRNGs now?
For an ideal secure hash function with 256-bit output it takes ~ 2^128 operations to find a collision, while most other attacks, like finding preimages, takes ~ 2^256.
The sponge construction Keccak uses allows you to reduce the difficulty of finding preimages in return for increased speed, by adjusting the capacity of the sponge.
The idea was to have a fixed "level of security" for each hash, based on the collision resistance, and tune the other parameters based on that. So a 256-bit output would require 2^128 operation for either a collision or a preimage attack.
The NIST is currently modifying SHA3 to make it faster, with some controversy.
You are right in the sense we will have to wait for the definitive standard to get out before we see some heavily optimized implementations.
If you want immediate performance, use SHA2. If you want more "future proof" security, use SHA3 (and one could say that SHA2 is still very good in terms of security).
Stick to the standard, unless you know a lot about crypto.
https://github.com/sekitaka/node-blake2
I hasn't been touched in a year, but it looks fairly good. I may try it out soon to see how it performs myself.
"The ideal cryptographic hash function has four main properties:
(a) it is easy to compute the hash value for any given message
(b) it is infeasible to generate a message that has a given hash
(c) it is infeasible to modify a message without changing the hash
(d) it is infeasible to find two different messages with the same hash."
MD5 fails (b), (c), and (d).
One additional problem is due to the length extension attack: http://en.wikipedia.org/wiki/Length_extension_attack
For MD5 and SHA-1, given any hash, it's possible to reconstruct the internal state of the hash function. (They're named "hash function," but "hash state machine" is probably a better way to think about it.) For example,
MD5("The quick brown fox jumps over the lazy dog").hexdigest() => 9e107d9d372bb6826bd81d3542a419d6
Given 9e107d9d372bb6826bd81d3542a419d6, you can reconstruct the internal state of MD5, allowing you to continue hashing data. For example, you could add " while the cow goes moo:"
MD5("The quick brown fox jumps over the lazy dog while the cow goes moo").hexdigest() => ab7e4a96438e33094a7df3d41fa89c47
MD5_FromHash("9e107d9d372bb6826bd81d3542a419d6").append(" while the cow goes moo").hexdigest() => ab7e4a96438e33094a7df3d41fa89c47
Ideally, you'd like to be able to reveal the hash publicly without revealing any details about the internal state of the hash algorithm. (It's my understanding that SHA-3 accomplishes this goal automatically.) Another way to accomplish that goal is to use HMAC-MD5 or HMAC-SHA1. At that point you can prove that you hashed something by prepending a secret key to the data. For example,
HMAC_MD5("My 256-bit random secret key", "My message to be hashed").hexdigest()
This would yield a hash value that you can reveal publicly, and which no attacker can append any data to. For any given data D, you can verify that you generated the hash value by computing
HMAC_MD5("My 256-bit random secret key", D).hexdigest()
and comparing it to the other hexdigest. If they're equal, then either some attacker has stolen your private key or you generated the hash.
But if you tried this with plain old MD5, then an attacker can easily append data and trick you into thinking you generated it.
This is actually all the time I have right now, so someone else please feel free to step in and fill in missing details, such as how to find two different messages which hash to the same MD5 value.
No, for hashes, you definitely want speed; that's not the problem with MD5. For applications where speed is not appropriate, such as password hashing, you want an iterated hash of some kind. (Disclaimer: as with most crypto, you want one of the existing implementations, not something custom.)
The cyptographic security issues with MD5 concern breaks to the hash algorithm that make it possible to find hash collisions more easily than the number of bits in the hash would imply. A 128-bit hash should require 2128 hashing operations to find a collision against an existing fixed value. (Finding two independently chosen values with the same hash is far easier, due to the birthday problem: https://en.wikipedia.org/wiki/Birthday_problem ) MD5 has algorithmic weaknesses that make it far easier to find collisions, to the point where a current system can find some types of collisions in seconds.
This means that both data authenticated by MD5 hashes (say, software package signatures) and access mediated by hashes (say: passwords, if you're incredibly stupid), can be trivially hacked.
Where can I buy commodity hardware with 2^128 bytes of RAM?
I've taken the opportunity to look up how rainbow tables are used, and in practice, what are constructed are rainbows of likely hits, as well as exploitation of crytographic weaknesses in the MD5 algorithm. So, no, it's not the total address space, but, say, for keywords in multiple languages or known revealed passwords (of which the most common give you tremendous amounts of access -- the top 10 and 100 passwords will access many systems, and lists of millions are now available, for which rainbow tables are easily constructed). And the collision problem also remains.
As for assembling large amounts of storage: with distributed systems, whether on bare metal, cloud systems, or botnets, it's possible to aggregate terrebytes of memory (not merely on-disk storage) for quite modest budgets within reach of a company or moderate-high-net-worth evil genious, let alone a state actor. For commodity x86 servers, high-end memory now looks to be ~320 - 512 GB, though terrabyte range wouldn't surprise me (I think SGI are still pushing the envelope in this area in their Rackable incarnation).
Fast cryptographic hashes are more like 100 megabytes a second per core or slower. You can use cryptographic hashes in performance sensitive scenarios like git to get a unique fixed size handle on some bytes, but CRC32c is faster if all you want to detect is random changes.
I wouldn't expect a filesystem to need collision resistant cryptographic hashes.
There is hardware support for SHA-1 and SHA-2 now, but is recent and I haven't seen an implementation or benchmark. I doubt it's as fast as the hardware CRC32c implementation.
BLAKE2's authors do say they designed a fast algorithm envisioned for storage, so that's why I think it fits btrfs.
Thanks, that's very information. I checked out the link and it is very cool how blake2 can be tuned for different roles. I hadn't though of how newer filesystems are doing deduplication, my head is stuck in the ext4 era.
I still think performance matters. Even at 800 megabytes a second you are talking about committing two entire cores to checksums on 10-gig E if you need to move data around. An entire core if you are talking about sequentially scanning an SSD. I suppose this will stop mattering as we get more cores.
If a filesystem is using CRC32 for something, it doesn't need the properties of a cryptographic hash or they are doing it wrong. I can see how you can argue against CRC for reliability.
I am not sure whether you actually risk a corrupt block every 1 in 2^32 blocks. Most blocks won't be corrupt so the CRC only has to detect a much smaller number of errors. Assuming every block had an error needing detection you will miss an error every 16 terabytes (assuming other things as well). Assuming 1% of blocks are corrupt you would miss an error every 1.6 petabytes? Maybe I am thinking about this wrong, and I recall other factors like block size effecting CRC's reliability.
I'm also not sure what sort of risks and attacks cloud storage providers have to deal with, but AWS S3 for instance computes MD5 hashes for each object. If they or any other storage providers need guarantees about collision and preimage resistance, crc32c, or even xxhash, won't suffice (and MD5 may not, either, but the fact that they haven't run screaming from it yet suggests that they don't use it in a way where its known weaknesses matter).
Sounds like MD5 on viagra.