Making sure crypto remains insecure [pdf]
cr.yp.to
cr.yp.to
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...
There's already a Node-Sodium package... https://github.com/paixaop/node-sodium
Why can't browsers support it natively? (e.g. through NSS)
Looks like there's already a bug in Mozilla's tracker.
NSS and OpenSSL are difficult codebases to work with, which may also explain why it's so hard to find people to work on them.
The political problem is that unless there's an authority whose blessing can be appealed to to justify inclusion, how do you decline curves from Microsoft Research and so-called NUMS curves? (Of course, it's not like the CFRG is a politically spoyless authority...)
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.
Edit: based on http://cr.yp.to/talks/2013.05.31/slides-dan+tanja-20130531-4...
It's unlikely that any credible new protocol is going to adopt a NIST curve. They exist only for legacy support now. BULLRUN killed them.
Fortunately, in this case I think hysteria actually served a good purpose. I do not think highly of crypto standards, and these ones in particular were dragging the industry down.
Is my poor understanding terribly wrong?
The NIST curves suck. But if your choice is between the NIST P- curves and PKCS1v15 RSA, it's not hard to see what the better of the two options is.
Visibility isn't a matter of "can the public see it?" I also mean "is it in a place the public is likely to look?"
Sorry if there was a miscommunication ;)
Which is fine, given that even today Sha1's preimage resistance is not practically broken.
Let's try to be clear: The NSA (naming names, among them Jerry Solinas) worked directly with the Certicom engineers to choose the properties of the SECG curves (some of which became the NIST/X9.82/Suite B curves, there's a lot of parallel working/overlap). They helped to perform the computational search to find the seeds, which were manipulated so that the results had certain properties (some of which were concealed and then were misrepresented as "provably random"). That is not a scenario: that is actually what happened.
Given that, and how incredibly opaque the process was, why am I not screaming in horror running away from secp256r1 et al? Because the information I've found (except for the SIGINT Enabling Project's budget) all points to that manipulation and deception taking place to obscure properties of the curves which allowed patents for efficient implementation of the curves - patents the NSA had in return agreed to licence.
Also, they use it themselves, in their most critical systems (they are particularly careful about randomness and side-channels). Is that just a cover? (Are they really willing to sacrifice the IA mission for the SIGINT?) I have no evidence that it is. It probably isn't. It could be. (They also use Dual-EC_DRBG themselves, likely on the basis that since only they have the private key, "nobody but us" can break it - shame it's got a bias anyway!)
On balance, I think the NIST curves are probably OK to use for now. If secp256r1 was somehow "backdoored", I have absolutely no idea how, and on balance, I do not think that it is. I think it's more likely any negative manipulation was to deliberately standardise something that's fragile not because it's weak but because it's easy and naïve to make it weak: hard to do in constant-time, convince some people to use insecure blinding techniques, etc. (And yes, I agree RSA w/PKCSv1.5 is definitely not better - one may wonder if it's another example.)
So I'm not running away from P256. But I'd like to walk away from it and switch to something more rigid, safer and a bit faster soon - and hopefully we get that out of the CFRG process (to the grandparent comment: Curve25519 is one of the top contenders).
The slides are a bit of out context without the talk, by the way!
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.)
(ducking)
Compared to AES: Implementation and use is dead simple and short (less room for bugs). The algorithm is easy to grasp. Naive implementations are resistant to timing and power analysis. Built in support for Tweaking, so you don't need to mess around with weird modes of operation. Large key size, and no mis-match between key and block size. Efficient (~6 cpb). It was designed by a large group of well known and respected cryptographers.
The simplicity of Threefish is the most important, in my opinion. Applications of AES in the wild have been broken numerous times because of improper use of AES and its modes of operation. Threefish is less likely to suffer those issues, since Tweaking is built in. So, as of today, I think that benefit outweighs the possible risk of Threefish being found weak (and keep in mind that Threefish is specifically designed to resist analysis by using a large number of rounds. Breaks in reduced Threefish are expected, and are not likely to be breaks in full Threefish).
Additionally, if people (e.g. Google) are willing to use ChaCha20, I don't see why they wouldn't be willing to use Threefish. They're built on the same principles, as far as I can tell, and both have just as much backing (in terms of peer review and who designed them). Again, the only arguments I've heard in favor of AES involve fear of the unknown.
What I can't see is why someone would militate for Threefish over Salsa20, or one of the eSTREAM portfolio ciphers, or at least say "wait and see" on CAESAR. What process happened that landed on Threefish for you?
Incidentally: native support for tweakability is a good thing, but it doesn't mean you don't need support for "weird modes of operation". A tweakable cipher core is a primitive that you use with other tweakable block cipher modes.
I'm a little confused by your claim that Threefish got as much review as Salsa20; Salsa20 is an eSTREAM winner, implying that a pretty big team of some of the best cryptographers in the world tried hard to break it as a cipher, and Threefish is just an artifact of a SHA-3 contestant that wasn't selected.
Finally, 6 cpb isn't great, is it?
I can't see why someone would advocate Threefish over ChaCha20 either. They serve different functions (one is a block cipher; the other a stream cipher). In my case, I needed a block cipher, hence my choice of Threefish.
I brought up Threefish not in conflict with the top parent's suggestion of using ChaCha20, but rather to suggest its place alongside ChaCha20, Poly1305, Curve25519, etc. in a modern crypto toolbox. In other words, I was saying "If someone is building an application that requires a block cipher, they should take a strong look at Threefish over AES; contrary to popular wisdom."
> A tweakable cipher core is a primitive that you use with other tweakable block cipher modes.
Indeed, but, for example, disk encryption requires less and simpler code using Threefish versus AES in XTS mode. Not to mention the caveats to XTS mode.
> I'm a little confused by your claim that Threefish got as much review as Salsa20
Off-hand, you're probably right that Salsa has more review than Threefish. But Threefish has more designers. And, Skein was one of the top SHA3 choices. Not that that conducts strength directly to Threefish, but it's a good sign. I mostly defer to Dmitry and Jon's comments here (http://crypto.stackexchange.com/questions/11725/has-threefis...).
> Finally, 6 cpb isn't great, is it?
Quick searching shows Salsa20 as ~3cpb, AES as 20-30cpb, and AES-NI as 3.5cpb. So 6 is great in my book, with Salsa20's 3 being amazing.
AES-128-CTR with AES-NI is ~0.8-1.2cpb on Haswell/Ivy Bridge/Bulldozer
Chacha20 is ~1.1cpb on AVX2, ~2.2cpb on AVX/XOP, ~2.8 on SSSE-3, and ~3.3cpb on SSE2.
ChaCha20 also performs much better on 32 bit systems, especially those without SIMD.
RC4 was the first cipher I ever successfully worked with (in my defense, I was a teenager). I had a devilishly hard time debugging block crypto code, but once you had a working RC4 library, you could round-trip data through it trivially. I remember seeing RC4 get embedded in a lot of code for that same reason: if you had RC4, you were "done", but if you had a 3DES core, you'd still need to be crypto-literate enough to rig up some half-assed block cipher mode; even ECB requires some adaptation to encrypt arbitrary streams, which is what everyone wants to do.
There was a pretty significant amount of interest in reversing the RC4 algorithm (hence "arcfour"), and I think this is part of the reason. People wanted something that worked like a stream cipher, and didn't have better alternatives (unless they were themselves cryptographers).
Someone more acquainted with the literature might correct me, but my sense is: we didn't "move away" from stream ciphers, so much as we didn't have them at all, and gradually developed some. You see the same thing now with CAESAR and native AEAD ciphers.
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).
Their constant time approach is "assume use of hardware AES instructions, otherwise enjoy a speed hit if you want to be safe".
There are many competing requirements when designing a primitive. Groestl's choices were not necessarily wrong, even when treating side-channel attacks as a "big issue". I don't like Groestl, but I get what they were trying to achieve; Keccak did it much better, though.
[1] http://www.groestl.info/groestl-implementation-guide.pdf
I will admit they are less at fault than the CAESAR candidates who insist on re-using AES.
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 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.
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...
So it's more "why wasn't hwrng treated as the other sources later" than why he wrote what he wrote here.
(http://blog.cr.yp.to/20140205-entropy.html: "imagine RDRAND microcode that's looking at the randomness pool that it's about to be hashed into")
I'm not sure I agree with Bernstein here.
Randomness from these sources are
added to an "entropy pool", which is mixed using a CRC-like function.
**This is not cryptographically strong**, but it is adequate assuming
the randomness is not chosen maliciously
> the one actually implemented afterwards: feeding hwrng to the pool just like the all other sources.
And now you're saying it's not fed "just like all the other sources".
This is contradictory.
In my older post I claim that I've read the random.c source cca 1-2 years ago. Note: the source, the C code, not the comments. My older sentence was: "Here he suggests an even better implementation than the one actually implemented afterwards: feeding hwrng to the pool just like the all other sources. The last time I've checked (a year or a two ago) the hwrng was there but had the special treatment, not passing the same path as the other sources."
I think it's clear: "The last time I've checked (a year or a two ago) the hwrng (..) had the special treatment, not passing the same path as the other sources."
Then in the later post my words are: "they still don't mix hwrng directly to the pool." I wrote it as I've actually checked the current git master of the random.c.
I don't see anything contradictory.
I also have more understanding for the idea behind the current implementation. Now it looks to me like they try to handle the hwrng as something that can be actively malicious, not just having a known seed (while just having the known seed, to my understanding, shouldn't be a problem to mix together with with other inputs). I personally think that the assumption of active maliciousness is to much, because the same company produces the whole CPU, and if you assume that, then you shouldn't use the CPU at all: they can be actively malicious all the time, not just with one instruction.
And, by the way, mixing through the same path but without increasing the "entropy counter" were maybe possible, but maybe it was cleaner this way.
At the end of the day, there are just things that are easy to get wrong, it's not all a big conspiracy.
* 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.
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.
Sodium (which I like and recommend) can't make the same claim. It gets what trustworthiness it has from the fact that it's a slavish fork of Nacl that merely aims to make it compatible with more runtimes.
Ok, interesting. Do you happen to have an example at hand? I don't see where there is room left for much sophistication in the implementation (regarding misuse-resistance), between the well defined algorithms and the strict API that Sodium shares with NaCl. For example lets look at crypto_box (public-key authenticated encryption):
On the crypto side it uses Curve25519 (alias X25519). Its paper has a pretty clear definition how to use the public key bytes as an x-coordinate. Because of the Montgomery multiplication an implementation does not have to calculate the y-coordinate, this eliminates one potential error source. Because of (1) its twist security and because (2) any input in a small subgroup results in a zero element output (neutral element or the (0,0) point), an implementation does not have to check the public key for its validity (another error source eliminated). All these are benefits any implementation will have.
On the interface side crypto_box is as locked down as a nonce based design can be. You enter: (•) Any 32 byte public key value (X25519 makes sure no harm can be done with malicious values), (•) your 32 bytes private key (not malleable by the attacker), (•) the nonce (during decryption any input is ok, because a wrong input will just generate an authentication error; during encryption there is the danger of nonce reuse, which is also present in NaCl) and (•) the plaintext / crypttext (again, because of the mandatory authentication any malicious ciphertext input will be rejected by the library).
So I don't see how a faithful implementation of the interface and algorithm specifications can get much wrong regarding misuse-resistance. Regarding it being secure because it was designed from the ground up to be secure at an implementation level, that is something I expect from any cryptography library. After all, is there any more basic requirement than that? (Well, you could argue being interoperable with other implementations is the most fundamental requirement, but I won't accept such low expectations when I'm asking for a competent developer.)
> It gets what trustworthiness it has from the fact that it's a slavish fork of Nacl that merely aims to make it compatible with more runtimes.
I fully agree that its inheritance from NaCl is Sodiums strongest selling point and its the argument I should have been using instead. I only had it dimly in the back of my heat at that time, though, and wasn't sure enough about it to claim it as a fact. Being less lazy to look it up would have saved me this follow up post ;) (Though I am genuinely interested in my question above.)
I'm just saying: I wouldn't trust libressl if Vincent Rijmen wrote it. :)
I like libsodium. It demonstrates that usable packaging is important, something that DJB seems to either ignore or not understand. But I only endorse libsodium as long as you stick to the NaCl API and not the stuff it's been slowly piling on, which may or may not be OK. What it certainly does is make choosing which function to use a lot harder: do I use crypto_secretbox or crypto_aead? crypto_hash, crypto_generichash, or crypto_shorthash? crypto_auth or crypto_generichash?
You can be reasonably sure that his code is bug free, but they went the extra step of proving the absence of certain types of bugs using static analysis tools. One of the project's deliverables mentioned they used Frama-C to prove the absence of integer overflows, for example. (I will update this comment when I find the specific report.)
Other projects take the traditional approach of trusting that the code looks right until someone proves otherwise.
Edit: The report was probably one of these, which I can't access anymore:
http://www.cace-project.eu/downloads/deliverables-y1/CACE_D5... http://www.cace-project.eu/downloads/deliverables-y1/CACE_M5... http://www.cace-project.eu/downloads/deliverables-y3/31_CACE...
- The core library's memory safety was verified using VCC; - A Frama-C plugin was used to verify (a limited form of) side-channel resistance.
Correctness verification seems to have been done by reimplementing NaCl in CAO, a language made during CACE for this purpose. It is not a 1:1 match to C, from what I can tell, so this does not imply correctness of the C code.
However, none of this is verifiable at all. The NaCl code has no VCC or Frama-C annotations, or associated CAO; there is absolutely no mention of this in the NaCl page. So we are forced to take the authors of that report at their word, if we want to believe them at all.
[1] https://www.cspforum.eu/documents-reports/description/cace
Nevertheless, one thing that is “left” from the verification effort is hidden options -experimental-mem-deps and -experimental-path-deps for Frama-C. These are on the automatic side of Frama-C analyses: they require a value analysis to pass on the target code, but they do not require it to be precise. And it is fun to see input length and error conditions pop up as things the execution time depend on (and in the case of a typical AES implementation, the input buffer itself):
http://blog.frama-c.com/index.php?post/2011/12/31/Do-not-use...
All I'm saying is, in general, crypto is hard, and an easy theory doesn't change how hard it is to get an implementation exactly right.
GnuPG hasn't been audited? Huh.
In this particular case, there is the issue that the AES implementation in OpenSSL has been shown in the past to be vulnerable to timing side-channel attacks over the network (again, by Dan Bernstein) and as far as I know has not been through the complete overhaul necessary to fix that problem.
I wouldn't be at all surprised if someone found exploitable side-channel attacks in third-party implementations of Salsa20 or ChaCha in the next few years.
I'm a big fan of DJB, but the sad fact of the matter is that his stuff is, at the moment, only usable by people who already know what they are doing.
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.
It's pretty hard to make a credible argument that Bernstein and Schwabe and Lange did a poor job with Nacl, since the next best alternative is Keyczar, which might not even be maintained anymore. What's the other credible high-level crypto library?
This is Bernstein's entire stick. Which is fine, but if you can't use it on ARM and therefor on mobile, you've killed a large area where adoption of new crypto could actually happen. Arguably, a slower constant time cross platform library would have been a better idea if he actually wanted to see it used widely. This is what Sodium claims to be ....but well who knows if that's secure.
And I don't think I agree with you that this is Bernstein merely saying here's why you need what I've done. It's an explanation of why it didn't happen that basically argues that people' are being so stupid about crypto that they might as well be NSA shills. As a narrative it ignores a lot of reasons this stuff didn't happen and a lot of lessons that should be applied in getting it right this time.
It's also worth remembering that Bernstein has this reputation you're alluding to among Unix nerds. In cryptography, he has no such stigma; he's a world-class cryptographer and I can't find any indication of interpersonal DJB drama in that field at all. I'm almost inclined to attribute the problem to the Unix nerds.
Schwabe has even written AVR versions of many of the NaCl operations, so maybe you can do your crypto not only on mobile but on an 8-bit microcontroller.
It's "anciently conservative" (not based on fancy new ciphers, you can like it or not), by a competent cryptographer, and battle-tested.
What I'd like to see is a way for others to support his efforts.
How can I, for example, currently working as a software developer working at a reasonably 'high' level (currently I'm mainly a consumer of libraries and frameworks) push for better quality in the crypto that I depend on, knowing that DJB has at least partial answers to some of the problems?
In Linux we already have this with /dev/random, right?
http://sockpuppet.org/blog/2014/02/25/safely-generate-random...
I'm pretty sure they are exactly the same on many of the BSDs.
* OpenBSD: /dev/random + /dev/urandom are the same and use ChaCha20.
* FreeBSD: They are the same (via symlink) and use RC4. Soon will use ChaCha20.
* NetBSD: Unsure. Last I checked, /dev/random was broken/non-functional like on Linux, and /dev/urandom was slow, like on Linux.
* Dragonfly BSD: Somewhat unsure, but ChaCha output can be xor'd with another stream to produce the returned random numbers.
* Bitrig: when it is released, it will use ChaCha20 like OpenBSD.
Related: libbsd currently uses RC4 in its arc4random functions but has publicly stated a future switch to ChaCha20.
TLDR - they are broken. He does not even care to explain why it's broken, because everybody knows it.
That's why most libraries use /dev/random to seed their own RNG, he says that's wrong and that /dev/urandom (which does not block) is scary.
Usually libraries (openssl,JCE) RNG seeds from /dev/random - this is the internal state of the RNGb; internal state is transformed into next iteration by applying SHA-1 and at each turn some initial bits of internal state are returned as random numbers.
of course the library RNG comes from the requirement for a lot of randomness in most protocols, (and for predictable performance, also servers also may need to do a lot of random numbers) of course the article has many points.
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.
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
No wonder our patent reform is so broken... literally the government is using it to it's advantage. Screw the cloak and daggers shit when we can just hire some lawyers to bury people and everyone acts like it's common place... wow. WOW WOW WOW.
Ty for this.
But it could be. Any smart attacker with a budget could work like that…
Another problem is that every time we've talked about posting solutions, people have asked us to hold off.
Finally, a quick jab: thousands and thousands of people completed several sets of these challenges --- more than a thousand got through the CBC padding oracle, which (in our challenge) is cryptographically more complicated than the TLS POODLE attack. None of them had solutions. You don't need them either. :)
https://www.coursera.org/course/cryptoWhile coursera focuses on theory, it is a bit more practical. I'd say they complement each other nicely.
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. */
No matter what upper bound you set you'll still end up with it going over at some point - and as soon as you go over the upper limit you're leaking timing information again.
This also ups RAM requirements, drastically in some cases.
And it isn't even necessarily secure against timing attacks! Because the thread scheduling by the OS changes depending on how much work is being done, and so it could take less or more time to retrieve the saved response depending on how long another request takes to process.
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.
Also, my comment directly addressed the notion of a lowest- common- denominator sleep.
I think maybe you meant to respond to a different comment?
You say that adding sleeps only helps if you know what the side channel is. That's true; for example, adding sleeps won't help at all against power analysis, acoustic analysis, or cache timing attacks. But that's also true of other side-channel countermeasures. For example, using constant-time operations (as Bernstein suggests and you endorse) probably won't help against attacks using those other side channels either. Most side-channel countermeasures are only effective against the side channels they're intended to protect, or not even those.
But pdkl95 was specifically talking about over-the-network timing side-channel attacks on a protocol. Adding sleeps will defend against that, even if you don't know which part of your code has variable timing. For example, Futoransky–Saura–Waissbain 2007 published "ND2DB", a feasible over-the-network timing side-channel attack on database indices. Sleeping so that the time in between network transactions does not depend on any of the data being transmitted will defend against ND2DB as well as any timing attack against your cryptosystems, while reimplementing your cryptosystems to use only constant-time operations will not defend against Futoransky's attack.
TheLoneWolfling pointed out correctly that you can only do this imperfectly in the presence of concurrency and caches, because the network response may take longer to send if, for example, your data has been swapped to disk in the interim. That is true, but I think that you can still reduce the information leakage by two to five orders of magnitude with this approach. For example, if you choose 1100ms as the time interval between receiving the request and sending the response, and 0.1% of the time your response is delayed until 1108ms because of paging in a single disk page, you are leaking about 0.01 bits to the attacker per transaction. If your timing varied over about a 50ms range and the attacker can measure latency to within 50μs, you would have been leaking about 10 bits to the attacker per transaction.
Second, you say that you have to make sure that your noise function itself is not a target of attack, which I take to mean that you must ensure that it doesn't leak information either; for example, the predictable cycling of the low-order bits of old "rand()" implementations could tell an attacker whether the process they connected to had handled transactions from other clients in between transactions to the attacker.
While this is true, I agree with you that it is not a big problem. Here's why. As I said, randomness does not help in this case, so you can simply pick a constant time interval, or one that only depends on data the attacker can already observe, such as the response size; or you can use any CSPRNG to generate a time to add to the constant time interval.
I didn't say anything about this before, but I also agree that it's (usually) a non-problem to make a transaction's average-case time the same as its worst-case time, but I don't agree that doing so "defeats the purpose of high-speed cryptography", because high-speed cryptography generally reduces the worst-case time to an acceptable time.
Is that better? Please correct me if I've said something incorrect above.
My point, as you've acknowledged, is simple. I think, for a bunch of reasons which are more and less easy to mitigate depending, it's a good rule of thumb to just avoid key-dependent side channels altogether. If you know what you're doing, you can shrink the risks. I'm dubious about whether they can be eliminated.
But even if one is the kind of person who can argue eloquently and accurately about those risks on a mailing list (nb: not alluding to you here), one is unlikely in my experience to be the kind of person who can actually implement countermeasures to these problems reliably. I've reviewed lots of expertly developed cryptosystems and found exploitable problems. My experience suggests that even good implementors do not tend to design systems from the vantage point of attackers, which squares with my experience of every other kind of software security as well.
A caveat to all of this is that it's easy for me to opine about what I think good conservative rules of thumb are because my technical depth doesn't extend to safely implementing variably-timed crypto operations. A subject matter expert might be able to refute a lot of what I think.
Because this is a fluffy comment, a quick shotgun blast of technical responses, none of which beg for rebuttals (but feel free):
* I can think of cases where randomized delays on one code path failed to eliminate timing leaks on other code paths that turned out to be relevant to attackers.
* I'm skeptical about exploitation of microscopic timing leaks; I don't even worry about memcmp timing, really. Other people are less skeptical, and there's a line of research pursuing statistical filtering and heuristics to bring those timing channels into reach. Also, there are some secrets that are attackable essentially indefinitely.
* My thoughts about worst-case timing are probably poisoned by client reactions to the idea of slowing down crypto operations at all.
So when any standards body recommends a particular cryptographic approach, we should ask why, and then why again.
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?)
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.
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.
More generally, try to scare implementors away entirely. "Never roll your own crypto." Leave it to the experts -- i.e., NSA.
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.