▲ 439 points
back
171 comments
Bernstein on a "thought experiment", analyzing how government could have deliberately weakened cryptographic standards through various means.
It's actually quite compelling, given that we know DES key size was weakened by the NSA back in the 70s, against IBM's will, and that we know Dual_EC_DRBG was backdoored also by the NSA a few years ago.
Bernstein's main point is that we need independent, peer-reviewed, cryptography that doesn't depend on government standardization. This talk is mostly a justification for his own work on ChaCha20/Poly1305 and DNSCurve, that were designed to be fast, constant-time and padding resistant. But the talk doesn't make mention of alternatives, except for Serpent that should have been a better cipher than Rijndael in the AES competition.
A good read. I would love to see broader adoption of ChaCha20 in OpenSSL and its standardization in TLS1.3. Google already supports it and it needs more attention from cryptographic before we start using it everywhere. It also seems that SHA-3 has failed to convince, and everyone is standardizing on SHA-2 instead, despite the computational cost. Maybe here too we need an alternative...
Could I give a mention to Threefish as well? It's in the same vein as ChaCha20, but it's a block cipher, based on modern ideas, is more capable than AES, and naive implementations are resistant to power/timing attacks by default. Yet, I rarely hear much talk about it. Half of the time I see it discussed, it's along the lines of "Hey, AES is looking really old, should I use Threefish in my new application/library?" to which people respond "AES is proven and still secure, so just keep using that." Personally, I find Threefish to be a beautiful algorithm; simple and effective just like ChaCha20.
Seems to me we've hit this local minima with various crypto algorithms. SHA2, AES, et. al are still considered secure, and almost no one has the guts to "risk" something new while the old stuff still works. Whereas before, we knew SHA1, DES, etc. were failing, so people were happy to jump to new algorithms as soon as they hit the market.
(Side note: I chose to use Threefish-512 in my hardware password manager project. It gets used in the disk and database encryption, so its built in tweaking is a godsend.)
Can you actually pose an argument in favor of Threefish? I have suspicions as to why Threefish, Twofish, Blowfish, &c come up in discussions like these, but rarely in discussions between actual cryptographic engineers.
I would also like to see Curve25519 (as well as others) supported in all browsers. It really bothers me that while at least websites are making an effort to default to ECDHE encryption with PFS, they have to resort to using the low-performance, insecure and probably NSA-backdoored P-256 curve, because most browsers aren't supporting anything else right now.
You could cite sources on "probably NSA-backdoored" P-256, but they'd all boil down to "you can with some effort devise a scenario in which it would have been possible for NSA to influence the curve selection". You'd be in a very similar rhetorical position to the "controlled demolition" conspiracy theorists.
We should, of course, demand rigid curves, and very few of the mainstream curves are rigid. But there's a difference between that and the assertion that P-256 is "probably backdoored"; for one thing, the latter assertion encourages people to adopt RSA, which is more fraught than ECC.
That RSA vs. ECC issue is even worse in browsers, which I think makes your sentiment even less useful. In ground-up implementations, you can get some comfort from OAEP/PSS for RSA. No such help in TLS, where RSA still uses (terribly broken) PKCS1v15.
If anyone has the time and skills to implement these curves in NSS, I'm sure that the Firefox and Chrome security teams would be more than happy to enable them!
I agree. Through PECL, PHP is soon going to have curve25519 support http://pecl.php.net/package/libsodium
There's already a Node-Sodium package... https://github.com/paixaop/node-sodium
Why can't browsers support it natively? (e.g. through NSS)
Are there actually many alternatives at this time? SHA-3, and more recently CAESAR, still received submissions based on AES. Grøstl (one of the SHA-3 submissions borrowing from AES) was a top 5 candidate. Constant time, side-channel free algorithms don't seem to be a big issue for many people yet.
I don't think this is a fair assessment. There was a lot of concern over implementation issues during SHA-3 and every finalist did have constant-time implementations, usually coming from the design team itself.
The thing with AES and its derivatives is that they make it very easy to prove resistance against cryptanalysis (differential and linear); ARX designs are very hard to analyze exaustively, and bit-oriented designs tend to be slow. Using AES-like constructions provides a middle ground of reasonable performance and provable security (for some value of security).
He's right about the low entropy of many crypto random number generators. There are so many cases of this that it can't be by accident.
2013: Android random number flaw exploited for Bitcoin theft.
http://arstechnica.com/security/2013/08/google-confirms-crit...
Backdoor in RSA?
http://arstechnica.com/security/2014/01/how-the-nsa-may-have...
Linus Torvalds insists on accepting Intel patch to use their hardware random number generator directly instead of just using it as one of multiple sources being XORed together.
http://cryptome.org/2013/07/intel-bed-nsa.htm
Then there are "features" in SSL/TLS which make little sense, such as the ability to change the cryptosystem during the connection. This includes changing it to "None". That's been exploited.
http://www.praetorian.com/blog/man-in-the-middle-tls-ssl-pro...
Regarding Android: not only could it be an accident, it almost certainly is an accident. For instance: the Android RNG flaw didn't stem from a single coherent design flaw, but rather from the meta-flaw of relying on application-layer (or in this case runtime-layer) randomness, and not nailing the order of initialization in all the components. It's easy to see why this would have happened by accident: (a) the belief that runtime-layer randomness is better, more performant, more reliable on mobile platform and (b) the lack of understanding that a single central kernel-level RNG is superior to app-layer RNGs (which is a relatively modern idea).
Regarding RSA: that's not a backdoor in RSA. That's a supposed backdoor in BSAFE, a library sold by RSA. The story pertains to BSAFE's support for the Dual-EC PKRNG. (Of the supposed backdoors propagated by the NSA, by the way, this is probably the most credible).
I'm not sure what your allusion to Torvalds was meant to indicate.
The SSL/TLS downgrade attack you linked to didn't have anything to do with the "None" ciphersuite, or re-negotiation.
I'm not sure what your allusion to Torvalds was meant to indicate.
This. Right here is where Linus Torvalds sold out:
https://lkml.org/lkml/2012/7/5/425
FreeBSD didn't:
http://arstechnica.com/security/2013/12/we-cannot-trust-inte...
By this logic NSA also is responsable for all buffer overflow attacks as well.
At the end of the day, there are just things that are easy to get wrong, it's not all a big conspiracy.
This is a fun slide deck, but if you'll forgive me for sucking some of the mystique out of it: it's just a reframing of DJB's hobby horses:
* The group that standardized AES rejected cache timing as a viable attack vector: http://cr.yp.to/antiforgery/cachetiming-20050414.pdf --- more generally, that constant-time algorithms and constructions (a feature of virtually all of Bernstein's work for the last 15+ years) aren't taken seriously in industry. Also helpful to know: there's a defensible argument that Bernstein more or less started AES cache timing research.
* Side-channel attacks weren't taken seriously by TLS, and Bernstein is affiliated with one of the research groups that found a TLS side-channel attack: http://www.isg.rhul.ac.uk/tls/Lucky13.html
* Application-layer randomness is a bad idea, and, like Nacl does, everyone should just use a single, carefully audit kernel RNG: http://blog.cr.yp.to/20140205-entropy.html
* Protocols and constructions should be designed to minimize dependence on randomness, the way DJB's EdDSA does: http://ed25519.cr.yp.to/ed25519-20110926.pdf
* Crypto performance is both not taken seriously as a research goal and an excuse for the deployment of terrible cryptography. This isn't so much a hobby horse of DJB's as it is his entire research career: http://cr.yp.to/cv/research-net-20070115.pdf
* DNSSEC, with its core design goals of "sign-only", "sign offline", and "sign from the root down" is a terrible idea. A sane design would look more like DNSCurve: http://dnscurve.org/ (helps also to know that DJB has a longstanding feud with both the design team for BIND, the flagship DNSSEC implementation, and with Namedroppers, the IETF DNS standardization list).
Unsurprisingly, considering the source, these are all really great important ideas. Bernstein is one of my heroes, and I'm certainly not trying to take him down a peg here. I just thought it might be interesting for people to know that this deck is less a revelation about cryptography than it is a survey of DJB's research over the last 15 years.
I'm surprised he didn't take more time on RC4, which he was closely involved with breaking. The story about how something as dazzlingly broken as RC4 could have gotten so entrenched in the industry is much more interesting than the story about how AES was standardized despite its performance relying so much on table lookups.
"Protocols and constructions should be designed to minimize dependence on randomness, the way DJB's EdDSA does:"
I think a lot of the reason that ECDSA/DSA are so inelegant was that they were designed to get around the patent on the (quite elegant) Schnorr signature algorithm, which EdDSA is based on. Thankfully, the patent expired in 2008, so moving to better signature algorithms that don't rely on per-message randomness is a matter of institutional inertia at this point.
Hmmm… and ElGamal's signing scheme didn't qualify? I don't think that's a reason, or even an excuse: Schnorr actually did claim his patent read on DSA. (That obviously never went anywhere, and the US Government, in a show of force via the NSA, filed their own patent on DSA.)
The NSA also really doesn't seem to have had much of a problem negotiating the licensing of patents with industry participants in the past! It is, after all, in an extraordinarily strong bargaining position: an awful lot of public money to throw around (openly, via on-the-book government contracts, and otherwise); the backing of a 'superpower' government and its negotiators; a remarkably good idea of what the position of those its bargaining with is (it is a signals intelligence agency…!); and is even able to classify patents and other nonsense like that.
DSA was sceptically received at the time, and there was widespread suspicion about its complexity and critical dependency on random k. (Even just two or three predictable leading bits of k can cause disaster!) Sizes above 1024 bit were not specified for way too long, and I would consider a 1024-bit DSA key most definitely crackable by the computing resources available to the NSA (or perhaps anyone else with a budget and a chip fab on contract after-hours!) today. (Those with DSA PGP signing keys may wish to take note and replace them, I suggest, with 4096-bit RSA keys.)
I think perhaps the only reason DSA got any popularity was because of the RSA patent, which it wasn't subject to, and the US cryptographic export restrictions which were the style at the time (remember the PGP source code "type-in listing" book publication?), which DSA avoided ostensibly because you couldn't encrypt with it but mainly because the US Government wanted you to use it. (ElGamal's encryption scheme was commonly used in tandem with it in practice, for example by some PGP versions.)
ECDSA has been accepted in a more sanguine fashion overall, although I'm not sure why that has been. Just like DSA, it definitely works correctly if it's done properly - but one tiny slip and you're toast.
Why was ECDSA better-received than DSA? Time may have helped; so is what they were seen to have done in the meantime. "Suite B-eatification" (as Kevin put it!) I think might've made people a little less sceptical of the NSA's intentions overall; also SHA (which as far as we know is not backdoored and has never been), and (via NIST) their arms-length involvement in reviewing candidates for the AES process. That introduced its "Information Assurance" mission (the one to protect classified US Government data - anyone else's data, or unclassified US Government data, is Not Their Problem). With Suite B, they wanted to be able to use more off-the-peg commercial providers for that purpose (rather than their bespoke, if a bit haute couture weird and distinctly old-looking, in-house stuff, which they referred to by contrast as "Suite A"). And people - perhaps foolishly - trusted that, despite the "equity" tension between their two missions, they would never risk compromising the same encryption systems they'd use for top secret US Government data. (It appears that trust may have been sadly misplaced… and, thanks to Snowden's bold willingness to go on-the-record about their unethical actions, they have permanently destroyed that trust now.)
We can, indeed, do better now, happily. I wonder if we will?
This talk was a fun "thinking-like-the-enemy" thought experiment, interlaced with the kinds of things djb's been generally warning about for years - I think it's up on YouTube somewhere, and like many slides makes more sense with the talk, although I sadly can't find it now (and I recall the audio quality wasn't great).
Along similar lines, someone down below has helpfully pointed out the fantastic "Operation ORCHESTRA" briefing PHK gave at FOSDEM 2014, which is equally funny and pointed. That video is on YouTube: https://youtu.be/fwcl17Q0bpk - http://phk.freebsd.dk/_downloads/FOSDEM_2014.pdf
I found this particular talk to be different that the usual DJB. It felt more like a self-reflection on why, despite being technically correct, his cryptographic solutions always fail to gain mainstream traction.
I have a lot of respect for DJB and for the way he always challenges the status-quo. This talk is an excellent summary of the current issues in the crypto industry. But he ignores the fact that we use AES, SHA and RC4 because _it's easy to use them_. And his solutions are never easy to use.
Make Nacl dead simple to use. Write clients and servers that use it. Integrate it into Firefox, Chrome, Dovecot, Nginx, Postfix, cUrl, etc... and people will slowly move away from TLS and its broken crypto.
Have you seen libsodium [1]? It's a "portable, cross-compilable, installable, packageable fork of NaCl, with a compatible API, and an extended API to improve usability even further." I've been using it in a toy project of mine and so far I'm very impressed!
TweetNaCl (http://tweetnacl.cr.yp.to/software.html) is dead easy use - just drop the .c & .h files into your code.
It's a terrible piece of self reflection in that case. His thesis is his stuff never got adopted because of the NSA? DJB is very smart, but he doesn't necessarily play well with others (as tptacek alluded to) and sometimes does some odd things.
As a random example: Nacl, which is pretty good, isn't portable. The portable version that someone made, Sodium ripped out a bunch of the platform specific stuff to make it portable, but because no one knows which parts were security critical and which weren't,there more than some doubts. These kind of things matter.
Put another way, as a piece of self reflection at least he could figure out how to make it harder for the NSA to marginalize his ideas if that's really the reason they haven't been adopted.
Hey tptacek, I'm CTO at a young zero knowledge email startup, and while I'm a proficient crypto user, I'd like to learn more about security and cryptography in general. Do you have any tips for me? Thanks!
I do! http://cryptopals.com.
Try this "Crypto I" course
https://www.coursera.org/course/cryptoOne of the points he makes is that "if it's standardized then it's broken. So if we were to take his words to the letter, we should be worried at the current work of standardizing Chacha20-Poly1305 into TLS 1.3 (https://tools.ietf.org/html/draft-agl-tls-chacha20poly1305-0...) and assume it's somehow broken ?
No.
Your comment could be read as saying that these slides are self-promotional — that is, that they are intended to puff up the importance of the topics that Bernstein has happened to publish work on. A more charitable and accurate reading is that these slides explain why he believed and still believes that those topics were important to spend time on, and why people should do things differently now. (That explains the lack of emphasis on RC4: everybody already knows RC4 is broken.)
I believe the latter, for what it's worth, not the former.
> Application-layer randomness is a bad idea, and, like Nacl does, everyone should just use a single, carefully audit kernel RNG
In Linux we already have this with /dev/random, right?
Yes, modulo "carefully audited", but the problem isn't that it's not possible; the problem is that so few applications rely on it, and that there's folklore encouraging people not to use it.
http://sockpuppet.org/blog/2014/02/25/safely-generate-random...
Re: timing attacks - can these be protected against by simply inserting into a protocol a mandatory random sleep that is strictly larger than the worst case run time of the crypto implementation? For example, if it takes up to 1s to run the crypto, would a protocol that required a usleep() of uniform_random(5s..10s)?
Such a scheme would obscure any variations in timing, right?
I ask because I have been thinking recently about the cost of "realtime", when many use-cases don't actually need it. Bittorrent exploits this idea - multicast is hard and most methods never really worked well enough to become popular. Then bittorrent comes along and gives up on the idea preserving an ordered, realtime-streamable transmission. In return, bittorrent got a lot of other features and became a very useful tool.
As these slides mention - it is easy to be blinded by a supposed need to make everything fast.
(brainstorming) Perhaps something like a modern variation on the batched store-and-forward used in the old FidoNet could be useful for non-interactive needs; instead of trying to save on long-distance fees it tries use ideas like the usleep("many seconds or more") and much larger (slower) key sizes.
/* Given the tone of those slides, I would guess that DJB just saw PHK's amazing "Operation Orchestra" talk? BULLRUN? "PSYOPS for nerds"? The lesson is important either way. */
Apart from the fact that adding noise just increases the measurement cost, the "add random sleeps" solution has two other problems, one small and one big.
The big one: it implies that you actually know what the side channel is, so you can sleep at a useful point. The virtue of relying solely on constant-time operations is that they're constant time by design. You don't have to worry about how the variable-time operations are implemented, because there aren't any.
The smaller problem is that you have to make sure that your noise function is not itself a target of attack, which can be a little tricky because your noise function must be extremely, extremely cheap to compute.
There's also the obvious "non-problem" that reducing a function to it's lowest common denominator of performance defeats the purpose of high-speed cryptography and variably-timed implementations in the first place.
Adding random sleeps does not prevent timing attacks. It just adds noise making them a bit more work to pull off.
So subtlety and obfuscation to make good ideas sound bad (serpent), and bad ideas attractive (in the interest of performance and practicality).
So when any standards body recommends a particular cryptographic approach, we should ask why, and then why again.
Currently they say performance and performance again. Sometimes they say nothing. Sometimes there is a good reason, sometimes there isn't. Sometimes they want to protect, sometimes they want to attack. That's the problem when you give one institution the job to do both.
A previous version of this slide set has been published and discussed here:
https://news.ycombinator.com/item?id=8023812
I did put up a version of those older slides in markdown format on Github here:
https://github.com/pflanze/slides-djb-20140710/blob/master/s...
(Perhaps someone feels like forking and merging in the changes?)
Very eerie. Scary to imagine that the very systems we rely on are fundamentally flawed even more so than generic "NSA back doors," but down to policy of implementation.
They keep saying China is a big enemy, so it would not be surprising if they have growing resources to start exploiting these kinds of vulnerabilities as well. Should stop backdooring stuff in the name of terrorism because the economic and political damage of enemy states with growing IT resources is far worse IMHO.
Dan, your sliders are hard to read online, because you make us read the same slide four times, just for an extra sentence on each. It's distracting. So please just put together the "full" slides when you put them online.
The supposition here is that maybe Bernstein didn't consider that raw presentation foils were harder to read online than slideshows?
Most PDF readers have a presentation/full screen mode for this (even pdf.js in Firefox does). The nice thing about them is that PDFs work nearly everywhere (if they are made that way, which in this case appears to be true).
I've put them on Kivo, which might be easier to view and so people can annotate them.
In other words, all crypto is broken?
Technically, I think it is only saying that all crytpo you know is not broken is broken.
All, before implementation.
I don't think that most of the problems stem from the NSA, most of the problems stem from the fact that security is hard, and we don't culturally have a proper appreciation of this.
We love complexity, we love adding features and wrappers and creating libraries, and when it comes to security this complicates things very quickly. You end up with massive specifications, layers of dependencies, and lots of code. And in many cases a single bug in the code can compromise the entire system.
In security, complexity is very much the enemy and we don't apply that mentality forcefully enough.
The crypto world is evolving quickly, and new vulnerabilities appear. Backdoors appear, ciphers get compromised, this or that RNG is shown to be flawed, etc. And when something that your application uses gets broken, are you going to know? If you do know, are you going to be able to swap it out for something more secure, or is that going to cause a lot of pain and dev time?
Lots of applications are going to prefer the single patch hotfix to the system redesign. And this introduces more weaknesses, because often the hotfix only addresses the single attack, and not the core vulnerability that made the attack possible. Future attacks may be harder, but they haven't been made impossible. (But... it's good enough, right? It'd be like, way harder now to create an attack... right?)
Building properly secure applications is hard, because it requires you to be minimalist, modular, and it requires you to pay attention to the latest security problems and be aware of the types of problems you can introduce when you implement something. Security is incredibly nuanced and you have to be properly aware of all the nuances. A single weakness in your entire stack can affect your whole system if you haven't carefully configured your applications.
Crypto is broken because crypto is hard, and application builders will take the easy way out, often without realizing that they're taking the easy way out. Although the NSA has been shown to be an issue, most of the problems seem to come from our own ignorance when trying to build secure applications, and there's no silver bullet.
Creating reliably secure systems is only possible when working with simple systems. Right now, the Internet is built with a ton of complexity. Operating systems are built with a ton of complexity. There are many libraries with different implementations and they all interact together in ways that are difficult to track. (IE shellshock... who would have thought that Bash would be vulnerable?). We aren't going to have real security until we melt all of this complexity away, and until we train ourselves to view complexity as an enemy, and until we culturally appreciate how difficult and nuanced security is. And that's going to take a long time and a lot of effort.
Does it seem ironic to anyone else that this was served over HTTP?
Crypto insecurity is just one of many concerns and it is missing somewhat of the point. There will always be debate over it.
There is a chilling effect that big tech companies in the US have been working on side channels for nearly any protocol that is ever developed. There needs to be research into side channel resistant crypto as well.
But what about the bigger growing trend in computing that is causing more troubles (dependency growing system wrappers)?:
Has anyone else noticed the trend for wrappers over increasingly larger and larger parts of operating systems? For example systemd (https://en.wikipedia.org/wiki/Systemd) while good for providing automation provides even more system administration power by controlling package managers.
Docker contains configuration information for the full app that is being deployed contained within that container as well. It will take quite some time to make docker more secure, and using it may contain some level of attacks.
And hypervisors as well are larger and larger in size as well. There is becoming an increasing standard for the amount of code in frameworks, platforms, operating systems and more for interoperability.
While these are good things that need to happen as fixes need to be quicker, they are also bad things in that they provide newer larger attack surfaces. Cloud computing is also becoming more and more rewarding for heavyset computation and sharing of resources. The ambiguity in choice of it all means that there will inevitably be a plethora of choices in the cloud.
The dependencies in frameworks and how we develop software has continously grown over the years as well to the point that people are using things like versioneye: https://www.versioneye.com/ to sort changes in it all.
While diversity is good and the cloud ecosystem is becoming more profitable. Why is there almost no security company focused on making the "cloud" tamper resistant? (i.e. monitoring docker containers and looking for misconfigurations etc even on github) There definitely should be a working effort in that retrospect.
It is also equally problematic that cloud software will be ambiguous in design. Cloud software that is built to be fast may use a custom in-house Just-In-Time code engine for faster database or code execution which may be harder to really address security wise.
In retrospect there are many security companies that are working towards securing the appstores, why should they not be working towards securing/integrating with cloud providers?
There should also be more opensource security anti-viruses besides just clamav. For people to be secure there should be a newer trend into opensourcing specific security modules and working towards a functioning operational level of configuration/management security as well as malware detection.
> Try to scare implementors away from constant-time software. e.g. “It will be too slow.” “It’s too hard to write.”
More generally, try to scare implementors away entirely. "Never roll your own crypto." Leave it to the experts -- i.e., NSA.
Erm, no.
There are good reasons not to roll your own and none are to do with the NSA. One is that your own is likely full of flaws that you can't see but an attacker will spot in seconds.
It's easy to write crypto you can't break yourself.