On the Impending Crypto Monoculture
metzdowd.com
metzdowd.com
* Theoretical rigor
* Competitive performance ("new speed record for X" being a theme of his research)
* Misuse-resistant constructions and interfaces
He was doing this stuff before it was cool (he's as far as I can tell the only cryptographer to have written something like qmail) and the rest of the industry is struggling to catch up.
The list of Bernsteinisms is slightly less scary in context:
* Curve25519 and EdDSA are sort of related work, and the alternative in non-DJB cryptography would be "NIST P-curve and ECDSA over that P-curve". The consensus seems to be that Edwards curves are superior for a bunch of practical reasons, and Bernstein pioneered them, so: no surprise.
* Poly1305 and ChaCha20 are virtually never used independently; they can been seen as DJB's most current AEAD construction. There are plenty of competing AEADs; in fact, there's a competition (CAESAR) underway that DJB is involved in.
So really, that's not that much scarier than the fact that AES and SHA-3 share an author.
Had he not done that, it might be more useful. When it expires, maybe we'll see it put to good use.
"6. No Discrimination Against Fields of Endeavor" https://en.wikipedia.org/wiki/The_Open_Source_Definition
and
"The freedom to run the program as you wish, for any purpose (freedom 0)." https://en.wikipedia.org/wiki/The_Free_Software_Definition
http://web.cs.ucdavis.edu/~rogaway/ocb/license1.pdf
So while it's true that free and open source software would not be able to impose a no-military-use restriction, Rogaway in this case is exempting free and open source projects from that restriction.
So you can release free and open source software which might be used for military purposes, OR you can release closed sourced software, but it can't be used for military purposes. The effect is that if your software will be used for military purposes you have to release it as free and open source software.
In this case it's not a dual license where you're bound by the terms of both licenses, it's a situation where you choose one of the licenses based on which set of terms you can comply with. Multi-option licenses like this are frequently used for proprietary software to enforce tiered pricing (such as nonprofit/personal/corporate licenses all applying to the same software but different licensees).
This is my interpretation, but I'm not a lawyer. I wouldn't stake my business on my interpretation without consulting a lawyer and neither should you.
I'm not quite sure what you're referring to, but I don't think any interpretation is quite right.
* "No existing FOSS license limits military applications of its covered software." That's true, but Rogaway's license doesn't even limit military applications of covered software either.
* "If a FOSS license limited military applications of its covered software, it wouldn't qualify as a FOSS license." Also true, but Rogaway's license doesn't do that.
* "Some FOSS licenses try to make it hard to grant a patent to some of their users but not to all." Also true, but Rogaway's license probably doesn't do that (depending on how we interpret the part about "Software Implementation"), and not all licenses have this property.
* "If a patent grant is specific to a particular program, FOSS projects can't accept or rely on it as a matter of policy." Maybe true for some projects, but this concern comes up more regularly for copyright licensing rather than patent licensing, and not part of the definition of FOSS licensing, and Rogaway's license only refers to the licensing style rather than the identity of the program.
* "If a patent grant is specific to FOSS, then FOSS projects can't accept it as a matter of policy." I don't think this is true at all; I think many FOSS projects have been quite happy to rely on such licenses in the past and I think there are a number of precedents for them. (That doesn't mean that the developers or projects necessarily think that software should be patentable or that they should require a license in the first place.)
I agree with the observation that Rogaway's licensing terms have discouraged standards adoption of the technology, but I don't see how they would forbid individual free and open source projects from adopting it.
I think people may have been confused by the presence of alternative patent licenses; recall that license #1 requires only FOSS (not non-military), while license #2 requires only non-military (not FOSS). If license #1 would be sufficient for FOSS projects to benefit from in the absence of license #2, it should still be sufficient in the presence of license #2. (Edit: geofft also points out that the terms of the licenses have changed over time and that #1 used to be GPL-specific -- but I think my observations still apply in the case of GPL-covered projects.)
That's true, and if you were making a one off library like NaCl OCB might be a good choice. But the restrictions means it couldn't be adopted into any standard for interoperable software. Though ISTR that recently there was another license grant that allows it to be incorporated into TLS.
In addition because it was never adopted into any standard interoperable software it didn't get as much scrutiny as it might have otherwise, and so even for a one off you might be skeptical.
The long and short of it is that if OCB hadn't been patented at the time it was invented it probably would have "won" and been widely used. GCM was invented several years later, has some worse performance characteristics, and AFAICT considerably harder to implement well in software. Instead it is something that is taught but rarely used in practice. Whether Rogaway prefers this world to the counterfactual one, only he knows.
http://web.cs.ucdavis.edu/~rogaway/ocb/license.htm
Part of the history here is that OCB used to have a patent grant for all GPL software, again regardless of military use, and then in 2012 authorized Mosh to use it under GPL + two exceptions.
https://github.com/mobile-shell/mosh/blob/master/ocb-license...
(In the general case, yes, such a restriction on use makes it non-free / non-open-source, which makes it annoying for people who want to use the software through an intermediary like Debian.)
Ron Garret replies:
Saying "How on earth did it come to this?” strongly implies
that you think that the trend towards DJB’s crypto suite a
problem, but you don’t offer much in terms of proposals for
how to solve it, or even what a solution would look like.
You seem to agree that a solution would *not* look like the
status quo. So what exactly are you advocating here?
I submit that the impending monoculture in crypto is not
necessarily a problem, any more than the monoculture in
physics (what? No alternatives to GR and QM?) or climate
science is necessarily a problem. It’s possible that crypto
has a Right Answer, and that Dan Bernstein has discovered/
invented it. If you believe that simplicity and minimalism
ought to be part of the quality metric then there may be very
few local maxima in the design space, and DJB may simply have
found one of them.
rgHowever, is there a legitimate concern that we're collectively hoping DJB hasn't messed anything up? I'm no expert in the area, but are there ways to prove that his work is correct?
> ...multiple approaches and techniques and tools are always a good thing.
Only at a very high level. If you switched out "cryptography" with "privacy protection" then you'd be right.
[1]SafeCurves: https://safecurves.cr.yp.to/
tptacek's answer to that question is pretty reasonable: https://news.ycombinator.com/item?id=11357587
Basically this monoculture is a consequence that crypto is very subtle and it is often better to have 1 algorithm than everybody uses implements and studies and tries to break rather than 10 that nobody really studies.
You just state the status quo, but make it sound like a good thing, but the impliciy reason is, that there aren't enough capable people, at least not interested ones.
Peter Gutmann definitely has the credibility to make this critique. But saying that DJB having won is more a vote against other crypto than a vote for Dan is like saying that Git having won is more a vote against other SCMs than a vote for Linus.
Well sure, you could say that. But that would rather understate Linus' substantial contribution to thinking about version control differently and better.
Similarly DJB has won because he led the way in thinking about the crypto problem correctly. Peter basically acknowledges the underlying facts here, but seems to not want to give Dan his due.
That paradigm of version control existed previously. (Monticello in Smalltalk, for example.) However, Linus had the programming chops and name recognition to start it off down the road to what it is today.
(Most of what is annoying and difficult about git makes much more sense when you realise it was literally invented for Linus to handle his email, and anyone else having use for it is a serendipitious happenstance.)
However, I worry many (developers) will get the wrong message from this post: that they shouldn't use the new standards from DJB (even if they are clearly superior in every way), because that would "help create the monoculture".
Also look at how this post ends:
> So the (pending) Bernstein monoculture isn't necessarily a vote for Dan, it's more a vote against everything else.
So it's not a vote for Berstein that he got so much so right? If it's not a vote for DJB's work, then maybe he can point out what's wrong with it (other than everyone wanting to adopt it).
The post could've very well ended like this, and it would've been better for it:
> The impending monoculture (based around DJB's crypto) is showing us that we need simpler, more boring crypto everywhere, but it needs to come from other authors as well.
Something like that. He is after all arguing against non-boring crypto throughout the post, no? So that should've been his conclusion?
Maybe even add a little bit of "DJB has showed us the way - now it's time for others to pick up the torch and take it from here." But I imagine he wouldn't have gone that far.
In fact, I think it's comments like these that set people like Guttman off. If you pay enough attention to the people who select but don't design ciphers --- ie, non-cryptographer engineers --- you're starting to hear more and more of a drumbeat of "do whatever DJB says"; if you push those people to explain those decisions, you don't usually get good answers.
Sure. I like to call that condition "secure by default". Said engineers most often don't have a lot of knowledge and experience with cryptography, so they opt for the best option available. In a lot of cases, it's DJB's work. In other cases, it's someone who followed his example (e.g. the BLAKE(2) team).
Also, this might have had something to do with this shift towards the current situation:
https://gist.github.com/tqbf/be58d2d39690c3b366ad
> Use, in order of preference: (1) The Nacl/libsodium default
> If you can just use Nacl, use Nacl. You don't even have to care what Nacl does.
The primary innovation of both git and Mercurial was performance. Git is a highly optimized content-addressable database with version control built on top.
More than git? I shudder at the thought.
In Arch, a changeset is represented as a directory tree full of bookkeeping files, patches, new files and removed files. The best contribution technique is to create a changeset directory and then tar it up for delivery:
$ tla changes -o ,,new-robot-comment
$ tar czvf my-changes.tar.gz ,,new-robot-comment/
Is anyone who's used Mercurial able to comment on the UI differences?
The famous two weeks time off to write git was many years later, when tridge finally forced his hand to do it. I don't think it's quite right to say git was a vote against anything else (except maybe against C++, which would bring some maintenance problems in the kernel community).
If you are using 10 ciphers or 10 hash functions or 10 signature schemes, then you need 10 different breakthroughs before it all falls down.
There is really no reason to not do this unless performance is important, and a lot of times performance does not really matter.
NOTE: obviously you need to this properly and use a different key for each cipher, concatenate hashes, concatenate signatures and so on. Also, you should start encrypting with the best implemented ciphers, so that plaintext is not leaked if the worst ciphers happen to have timing/cache vulnerabilities.
sha1(md5(things))
We can both study the relative security of sha1() and md5() separately, but also know that using both means that an attacker must defeat both methods. This isn't security by obscurity so much as security insurance. If either sha1() or md5() is compromised, the data is still protected by the other.
Similarly, if we use ten different encryption methods on top of each other... we know a few things:
- If we're studying all of those methods for flaws, the initial challenge of beating it is defeating all ten methods. - If a method is found to be compromised, our data is still protected by nine other methods. - At the very least, we've made brute forcing this a pain in the rear, because nine of those ten layers' output is probably really hard to tell are correct.
If you have a crypto 'stack' of ten methods, and you find one is now easy to compromise, you can napkin math realize you've lost one layer of protection, so when a zero day happens on one method, you don't have to panic and assume all of your data is compromised.
But your goal remains to ensure as many of those individual layers work against 'guns and explosives'.
hash1(hash2(...)) is not as secure as the stronger of the hash functions, it may only be as secure as the weaker of the hash functions. Your example is sha1(md5(...)). Well, md5 is no longer considered collision-resistant, which means that sha1(md5(...)) also isn't collision-resistant. If you're able to obtain two different inputs that are mapped to the same hash by md5, computing the sha1 of that hash is still going to lead to the same value, i.e. a collision overall.
So your assumption that an attacker must defeat both is clearly wrong and dangerous. In the case of hash functions, I believe it would be safe two concatenate the hashes (instead of composing the functions), but now you have a bigger hash size in addition to a slower running time.
Let's say you have an entirely broken hash function for which hash(A) = A.
Clearly if you cocatenate hash(A) + sha256(A), you still end up with something is broken. I think if you concatenate the hash function, you may well end up with something which is strictly worse than using either hash function (as breaking one will break both).
Also, if you have the result of both hash functions, then you may have provided data which warps the probability chart, as you now have much more information on the output state of the data, which isn't combined in a clearly useful way.
Their might be a way to combine two hashes in a way which does preserve the properties of a hash function, but I think it would be significantly tricky that you would have essentially created a new hash function using other hash functions as building blocks.
(That might be good grounds for generating a hash function resistant to attack - combine multiple different styles of hashing, but it doesn't seem to be common when hash functions are designed which suggest to me there are fundamental problems. (e.g. most hash functions repeat the same functional blocks, rather than having a large selection of different blocks).)
Now it could depend on your treat model. You want to hash passwords (A is secret)? If yes, then this is broken. You want an integrity check / tamper resistance on A, but A is public (see git)? Then this could be fine. Correct me if I'm wrong.
Consider what would happen if the "md5" function was found to always return the number 3 for "things" greater than 999 - the "sha1" function would be no help. The entire chain is only as strong as the weakest link. It doesn't matter how you mix the inputs, any biased input weakens the system.
For example, sha1(md5) has several flaws that jump out to crypto people. For example, a flaw in the inner function will not be protected by the outer sha1 function. In fact, the outer function will be rendered useless by an error or weakness in the inner md5 function. If I can create an md5 collision (which I just may be able to do...) then the outer sha1 is worthless.
On the other hand, if there is an error in the outer sha1, the inner md5's value as a construct is reduced - since its usefulness is wholly subject to the output of the sha1.
In addition, your construct f(g(data)), for many f.g implementations, clearly has a meet in the middle attack.
What you are creating with your stack of ten layers is a stack that _you_ cannot break, not a secure crypto stack.
There are very few situations where performance is not important in cryptography, and those situations do not, generally speaking, have sufficiently unusual security requirements that it would make sense to use a completely different set of crypto primitives for them.
source?
More importantly: Guttman's argument isn't that it's unsafe that we have this "monoculture" (how would that work? DJB turns evil and reveals the secret trapdoor in Curve25519?) --- it's that it's sad that things ended up this way.
I can imagine a hypothetical world where DJB creates three crypto building-blocks, gets hailed as the next coming of Alan Turing, and then we don't do nearly the fact-checking we should when he creates a fourth, and it ends up having a horrible flaw.
That seems to be half of what this article is warning against: a blind optimistic trust that anything that DJB creates in the future will be perfect. It's not that he's an infallible god of cryptography; it's that everyone else is making obvious mistakes, and he at least has eyes.
If DJB releases a crypto algorithm with huge glaringly unexplained constants, you'd better believe people will ask questions. I don't think it's possible to both use "nothing up your sleeve numbers"[1] and to backdoor an algorithm. You'd likely need the computing power needed to brute force the EC in the first place in order to do it.
[1] https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number
* During the recent CFRG curve selection debacle, Microsoft pushed for a noncompatible variant to Curve25519 (now called "PinkBikeShed") on the basis of it having minimal parameters.
* One of DJB's more notorious research papers, BADA55, is about the extent to which reliance on "easily explained math constants" is not actually safe.
Also: the problem with Dual_EC is that it's a public key RNG. It's a construction that has no reason to exist. The reason you don't have to worry about DJB's (or Rogaway's or Shay Gueron's or whatever) documents having the Dual_EC problem is that none of them are going to propose a public key RNG.
Do you think it's possible for constants (selected in the way the constants for ed25519 were selected) to be backdoored ala BADA55? It seems the vulnerabilities come from using hashing algorithms on some small constant, not from the constant itself being something simply constructed.
Also, it looks like DJB did alight on PinkBikeShed originally[1] but rejected it for technical reasons. (Reasons I can't evaluate myself). Is my understanding correct that the PinkBikeShed curve has more minimal parameters than ed25519, but that it doesn't satisfy all of the security criteria that ed25519 does?
[1] https://www.ietf.org/mail-archive/web/cfrg/current/msg05745....
https://www.ietf.org/mail-archive/web/cfrg/current/msg05619....
He also ends with "I didn't bother writing down a comprehensive critique of PinkBikeShed, and didn't imagine that anyone would ever try to revive that curve."
I agree with Bernstein but I won't pretend it's a totally cut and dried argument.
What won the argument wasn't so much the merits of Bernstein's case, but that Microsoft was in effect arguing for something that would break compatibility with the 25519 installed base.
If you want a good laugh (and some discussion of BADA55), you might enjoy this[1] talk where DJB praises his "new job" at Verizon.
[1] https://projectbullrun.org/surveillance/2015/video-2015.html...
My formula varied but amounted to this: at least three passes; 1-3 of strongest ciphers (eg AES finalists); optionally 1 old one (eg IDEA, Blowfish) for obfuscation; randomized choice of ciphers, keys, IV's, and counter values; counter mode or random good ones; those sent during key exchange. Each thing in isolation had necessary pre-conditions and configuration for secure operation. In combination, they should be as strong as weakest link plus difficulty of breaking obfuscations.
Seemed to work in practice. Many years later, I see a very watered-down version called TripleSec here with similar claims. Also, Marcus Ottela implemented a subset of my scheme in Tinfoil Chat. Past that, the advice has been "use OpenSSL" or something followed by "patch OpenSSL before the latest flaw in one component affects you."
They know better, though, as easy compromises are OK when it's something everyone was doing. Maybe they're disguising CYA legal strategy as good crypto recommendations. (shrugs)
Meanwhile, there's a steady stream of problems in regular ciphers, modes, and protocols that justify mitigating any one in a design. So, yeah, my polyciphers are a hedge. They also exploit combinatorial explosion by randomizing extra, large numbers. Used to by resources required to simulate the combos of algorithms themselves but FPGA's made that obsolete. :(
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.36....
I don't like this argument at all. Nobody is doing it so that means it is "bad"? As the grand parent said, there is no reason to not do cascading if you don't care about speed performances.
I've reviewed this sort of activist code (Minds.com, Tutanota, etc.) and found it to be dangerous.
Bad idea, using 10 128-bit hash functions instead of a single 1280-bit hash function. Instead of a single post hash view of the hidden data - you've given an attacker 10 different perspectives. Instead of studying and securing one function - you now have to secure 10 functions and study their interaction in 10 dimensions... If 1 in 10 of your functions is broken, the damage isn't limited to a 10% reduction in keyspace.
> ...start encrypting with the best implemented ciphers...
If that is known up front then the whole exercise is pointless. You can't know that because you can't see into the future.
Encrypting the data before hashing with a secret key solves this issue if applicable.
> You can't know that because you can't see into the future.
The "best cipher" is the single one you would have used if you had not decided to use a cipher cascade.
The idea is to make sure that your cascade is never worse than that single cipher.
So, compared to many sectors of computer science, much more patience and willingness to toil for years before creating anything of use is required.
Attack the rolls of others and roll your own demo and ask for attacks.
Same for crypto - you need a crypto phd for a fully secure novel crypto implementation, not a cs student.
And it's hard. I've been in this industry over 20 years, and been involved in a bunch of high-ish profile stuff, but I know that I don't have the knowledge to touch this stuff.
But in fairness it's a combination of understanding maths and understand some low level CPU stuff. If you are into that, just start learning it. Practice it. Someone has to follow on all this work. It could be you. But if it isn't, there's a ton of interesting stuff out there that isn't crypto. (Although I'd prefer everyone understood the basics of crypto, but that won't happen in my lifetime).
"A major feature of these changes includes the dropping of traditional encryption algorithms and mechanisms like RSA, DH, ECDH/ECDSA, SHA-2, and AES, for a completely different set of mechanisms, including Curve25519 (designed by Dan Bernstein et al), EdDSA (Bernstein and colleagues), Poly1305 (Bernstein again) and ChaCha20 (by, you guessed it, Bernstein)."
Curve25519 is an implementation of a cryptographic group. (EC)DH is an agorithm that you can run over such a group. In fact, when you do key exchange the recommended way in libsodium, you're doing DH key exchange over Curve25519. (ECDH is simply "DH performed over an elliptic curve".)
Isn't EdDSA just ECDSA (which is again an algorithm) performed over a group that happens to be a curve in Edwards form?
Put another way, the basic maths of DH key exchange is that you have a vector space of "points" (vectors), you can add one point to another to get a new point and you can multiply a point with an integer to get another point.
DH key exchange starts with an agreed-on point P. Person A picks a secret x and sends x * P to B. Person B picks a secret y and sends y * P to B. Now A has x and y * P so can compute x * (y * P) = (xy) * P while B computes y * (x * P) = (xy) * P.
If the vector space is a certain kind of subgroup of Z ^ * _ p then this is called DH. If the vector space is an elliptic curve group we call it ECDH. Presumably if the elliptic curve is in Edwards form we should call it EdDH. But the DH algorithm is by and large the same idea in each case - you could happily define an interface for the vector space and then implement the key exchange part once over this interface, which would let you link the same KEX code against different implementations for ECDH, EdDH etc.
The same applies as far as I know for DSA/ECDSA/EdDSA.
https://www.ietf.org/mail-archive/web/cfrg/current/msg06826....
https://www.ietf.org/mail-archive/web/cfrg/current/msg06805....
the truth is that we are all brainwashed for pair-programming and working in an agile pressure-cooker without code ownership. But if you look at the quality of the work and code one single strong software architect can deliver precisely because they didn't have to compromise with other stakeholders it is clear why the result may be better.
I'm not saying that this is always true. But I have seen it times and times again where a single individual built a whole platform that simply worked mainly because he had the freedom to do so uninterrupted.
Also, there is now a cipher suite with AES in OCB mode. And the licensing terms as stated in the ITEF IPR disclosures makes the mode easier to use. There are also a draft for Argon2 as KDF (an algorithm not by DJB).
I was more worried when everything seemed to end up being based on AES. Not because its a bad algorithm, but beacuse we didn't have a fallback. That is actually why the ChaCha-Poly1306 suite came about. RC4 was no longer a usable fallback for AES.
There is only one option: AES128. It was quite surprising to me, though I'm very far from a crypto expert.
AES256 is also possible if you get the extra strength Java crypto libs.
And there is no reason to believe AES256 is stronger than AES128. There have been attacks against the former which are not applicable to the latter, and the key length is enough.
GCM-SIV is good, but it doesn't address all the problems of GCM. You still need hardware support to get a safe, efficient GCM-SIV.
GCM-SIV is also way more complicated than Chacha20+Poly1305.
Why do you need hardware support for GCM-SIV?
https://en.wikipedia.org/wiki/Daniel_J._Bernstein#Bernstein_...
He created all of this boring crypto that everyone wants to use now ahead of most. He even launched a site around the sole idea of post-quantum cryptography 8 years ago, because he thought it's that important and we needed to start worrying about it then, if not earlier.
Most cryptographers started paying attention to PQ crypto only after the NSA said we should worry about it, last year (because obviously we should all wait until the NSA bestows its knowledge and guidance upon us before doing anything). But even then it's more of a mild worry, as I'm not seeing the crypto community act too panicked about it, despite the fact that we probably have only about 5 years to figure out some fast and resilient algorithms and protocols, another 5 years to test them, and another 5 to deploy them worldwide.
Because in about 15 years quantum computers will probably be strong enough to break conventional encryption. I think Google expects to have a 100-qubit universal QC around 2018, and from there it should scale up easily (possibly at a rate of 2-4x every 2 years, if it's similar to D-WAVE's progress).
https://www.technologyreview.com/s/544421/googles-quantum-dr...
According to this, a 4,000 qubit computer will be able to break RSA 2048-bits:
https://security.stackexchange.com/questions/87345/how-many-...
If we get a 100-qubit in 2018 and then double-up the qubits every 2 years, then we'll have a 6400 qubits quantum computer in 2032. Maybe it will happen sooner, maybe it will happen 10 years later than predicted (although many seem to be predicting a large enough to be useful universal quantum computer within 10 years), but either way we don't have much time left to figure this out.
So I guess my point is - don't give DJB the opportunity to create yet another "monoculture" by allowing him to stand alone in paving the road for PQ crypto. Because if he does, and 15 years from now we end up adopting his PQ crypto, too, then you can't come complaining again about using "too much DJB crypto".