A Few Thoughts on Cryptographic Engineering

Surviving a bad RNG

2012-03-09T12:33:00.000-08:00

A couple of weeks ago I wrote a long post about random number generation, which I find to be one of the most fascinating subjects in cryptography -- mostly because of how terrible things get when people screw it up.

And oh boy, do people screw it up. Back in 2008 it was Debian, with their 'custom' OpenSSL implementation that could only produce 32,768 possible TLS keys (do you really need more?) In 2012 it's 25,000 factorable TLS public keys, all of which appear to have been generated by embedded devices with crappy RNGs.

When this happens, people get nervous. They start to wonder: am I at risk? And if so, what can I do to protect myself?

Answering this question is easy. Answering it in detail is hard. The easy answer is that if you really believe there's a problem with your RNG, stop reading and go fix it!

The detailed answer is that (assuming you've done your best for the RNG), there are many areas where you're vulnerable if it breaks down, and some are harder to deal with than others.

In the rest of this post I'm going to talk about this and maybe give a few examples. I want to make clear that the motivation for this post is intellectual curiosity only. Please do not re-engineer OpenSSL around any of the 'advice' I give herein (I'm looking at you, Dan Kaminsky), and if you do follow any of my advice, please understand the following:

When it all goes terribly wrong, I'll quietly take down this post and deny all knowledge. You're on your own.

First, some background.

RNGs and PRGs

Before we get started, it's important to understand what we mean by a 'bad RNG'. The vast majority of cryptographic systems actually have two components for random number generation. The first ('RNG') collects entropy from various sources, such as hardware or unpredictable system events. The second (PRG) is a pseudo-random generator that seeds off of the gathered entropy. This is typically based on a hash function or a block cipher.

Although things can go wrong at any point in this chain, the most common failures are entropy-related. And these can easily be 'masked' by the PRG. In fact, with a good PRG, your seed entropy can be something ridiculous like "0x000000000000000000000001", and yet the PRG outputs will pass most randomness tests.

This configuration is a blessing and a curse. The curse is that it can hide problems. Since most people only see the output of their PRG (rather than the seed material), it's easy to believe that your RNG is doing a great job, when it's actually quite sick.* (Along these lines, FIPS 140 mandates self-tests on PRG output, which makes me wonder what NIST is smoking. But I wonder that a lot.)

The blessing of a PRG is that it will typically give you nice, statistically-uniform output even when you use highly non-uniform seed entropy. This rules out attacks (like this one) which rely on the presence of obvious biases in your nonces/keys/IVs. More to the point, it turns failure into an all-or-nothing deal. Either:

Your attacker will exactly guess the seed you used, in which case she can obtain every single output of the PRG (until the next reseed), or
She won't guess your seed, and you're mostly in the clear.

Obviously (1) is quite possible and (2) is debatable, but my point is that there's very little middle ground. On a well-designed modern system, you'll typically get beautiful, uniform-looking (P)RNG output. You just might get it over and over again, or your buddies might get it too.

Key generation

When it comes to generating keys with a bad (P)RNG, the only winning move is not to play. This is fundamental to key generation, meaning that it doesn't really depend on which algorithm you're using. If an attacker can predict your 'randomness', they can generate the same key themselves. Game over.

If you think this is a problem for your implementation, then either (a) generate your keys on a reliable device, or (b) get yourself a better RNG. If neither option is available (for some reason), then for god's sake, collect some entropy from the user. Ask them to tap a ditty on a button, or (if a keyboard is available), get a strong, unpredictable passphrase and hash it through PBKDF2. This might not save you, but it probably won't hurt.

What's fascinating is that some cryptosystems are more vulnerable to bad, or shared randomness than others. The recent batch of factorable RSA keys, for example, appears to result from poor entropy on embedded devices. But it wasn't due to someone guessing the entropy that was used. Rather, the mere fact that two different devices shared entropy makes both of their keys factorable.

According to Nadia Heninger, this is an artifact of the way that RSA keys are typically generated. Every RSA public modulus is the product of two primes. Some devices generate one prime, then reseed their RNG before generating the second. The result is that one, not both, primes are shared. Unfortunately, this is a worst case: anyone in possession of these moduli can factor them both by computing the GCD.

Ironically, in this case it's at least arguable that you're safer if two devices generate the same modulus, rather than simply sharing one prime. Lenstra proposes one solution, which is to calculate q deterministically based on p. Alternatively, you can just make sure your implementation doesn't reseed, which is probably much simpler.

Neither of these solutions will really help you, by the way. You're still whistling past the graveyard. But you might get to whistle a bit longer.

Digital signatures and MACs

There's a general misconception that digital signatures must in some way be randomized. This probably stems from the popularity of probabilistic signing algorithms like DSA/ECDSA and RSA-PSS. While it's true that these algorithms have a random component, that's more an accident of history than a statement on signature schemes in general.

I'm going to quicky run through a few of the most popular MAC and signature schemes. In this discussion, I'm going to assume that all keys have been generated properly (see the previous section). The focus is on the randomness needed for signing.

MACs. The good news is that virtually every practical MAC in use today is deterministic. This includes HMAC, CMAC, etc. There do exist probabilistic MACs, but fortunately nobody uses them. So while your bad RNG might be a problem for some things, it shouldn't have any impact on your symmetric-key authentication.

Signatures. The situation with signatures is a bit more complicated. I can't cover all signatures, but I can at least talk about the most popular ones. For reasons that nobody's ever really explained to me, these are (in no particular order): ECDSA, DSA, RSA-PKCS#1v1.5 and RSA-PSS. Of these four signatures, you'll notice that three are (potentially) randomized.

The major exception is PKCS#1v1.5 signature padding, which has no random fields at all. While this means you can give your RNG a rest, it doesn't mean that v1.5 padding is good. It's probably much more accurate to say that the 'heuristically-secure' v1.5 padding scheme is equally bad whether you have a working RNG or not.

Much better is RSA-PSS, which actually has a reduction to the hardness of the RSA problem. So far so good, but wait a second: doesn't the P in PSS stand for Probabilistic? And indeed, a close look at the PSS description (below) reveals the presence of random salt in every signature.

Fortunately, this is no big thing, since the salt is optional. PSS remains (provably) secure even if you repeat your salt, or just hardcode it to zero.

The PSS signing algorithm. MGF is constructed from a hash function.

Having dispensed with RSA, we can get down to serious business: DSA and ECDSA. I have no proof, but my guess is that these two algorithms are far more common than RSA-PSS. Hence it should be no surprise that they're the worst offenders by far.

The problem in a nutshell is that every (EC)DSA signature includes a random nonce value, which must never be repeated. If you ever forget this warning -- i.e., create two signatures (on different messages) using the same nonce -- then anyone can recover your secret key. The math behind this isn't even that complicated; you could safely outsource it to a bright eighth-grader. (Or even a dumb one, if that's all you've got.)

Usually when DSA/ECDSA go wrong, it's because someone simply forgot to use a random nonce in the first place. This appears to be what Sony did with the Playstation 3. Obviously, this is stupid and you shouldn't do it. But no matter how careful your implementation, you're still vulnerable to a bad RNG. If it starts spitting out repeated values, you need to throw away your key and generate a new one.

There are basically two ways to protect yourself:

Best: don't to use (EC)DSA in the first place. It's a stupid algorithm with no reasonable security proof, and as a special bonus it goes completely pear-shaped in the presence of a bad RNG. Unfortunately, it's also a standard, used in TLS and elsewhere, so you're stuck with it.
Second best: Derive your nonces deterministically from the message and some secret data. If done correctly (big if!), this reduces the possibility that two messages will be signed using the same nonce. In the extreme case, this approach can completely eliminate the need for randomness in (EC)DSA signatures.

There are two published proposals that take this approach. The best is Dan Bernstein's (somewhat complex) EdDSA proposal, which looks like a great replacement for ECDSA. Unfortunately it's a replacement, not a patch, since EdDSA uses different elliptic curves and is therefore not cross-compatible with existing ECDSA implementations.

Alternatively, Thomas Pornin has a proposal up that simply modifies (EC)DSA into a deterministic scheme by using HMAC to derive the nonces. The best part about Thomas's proposal is that it doesn't break compatibility with existing (EC)DSA implementations. While Thomas's work looks reasonable, his proposal is just a draft (and an expired one to boot). Proceed at your own risk.

Encryption

There are various consequences to using a bad RNG for encryption, most of which depend on the scheme you're using. Once again we'll assume that the keys themselves are properly-generated. What's at stake is the encryption itself.

Symmetric encryption. The good news is that symmetric encryption can be done securely with no randomness at all, provided that you have a strong encryption key and the ability to keep state between messages.

The easiest example is CTR mode encryption. Since CTR mode IVs needn't be unpredictable, you can set your initial IV to zero, then simply make sure that you always hang onto the last counter value between messages. Provided that you never ever re-use a counter value with a given key (even across system restarts) you'll be fine.**

Please don't try this with CBC mode, since that actually does require an unpredictable IV at the head of each chain. You can probably hack around this requirement in some dangerous way, but nothing good will come of it.

Public-key encryption. Unfortunately, public-key encryption is much more difficult to get right without a good RNG, mostly because the attacker has your public key.

Here's the fundamental problem: if an attacker knows the randomness you used to produce a ciphertext, then (in the worst case) she can simply encrypt 'guess' messages until she obtains the same ciphertext as you. At that point she knows what you encrypted.

Obviously this attack only works if the attacker can guess the message you encrypted. Hence it's possible that high-entropy messages (symmetric keys, for example) might remain secure even without good randomness. But there's no guarantee of this. Elgamal, for example, can fail catastrophically when you encrypt two messages with the same randomness.****

Although I'm not going to endorse any specific public-key encryption scheme, it seems likely that some schemes will hold up better than others. For example, while predictably-randomized RSA-OAEP and RSA-OAEP+ will both be vulnerable to guessing attacks, there's some (intuitive) reason to believe that they'll remain secure for high-entropy messages like keys. I can't prove this, but it seems like a better bet than using Elgamal (clearly broken) or older padding schemes like RSA-PKCS#1v1.5.

If my intuition isn't satisfying to you, quite a lot of research is still being done in this area. See for example, recent works on deterministic public-key encryption, or hedged public-key encryption. Note that all of this work makes on the assumption that you're encrypting high-entropy messages.

In Summary

If you take nothing else from this post, I hope it's this: using a broken RNG is just a bad idea. If you think there's any chance your generator will stop working, then for god's sake, fix it! Don't waste your time doing any of the stuff I mention above.

That said, there legitimately are cases where your RNG can go wrong, and sometimes it makes sense to be aware of those cases, and the consequences for your system. Model it. Think about it. Then spend your time on better things.

Notes:

* The classic example is Debian's 2008 OpenSSL release, which used a 15-bit process ID as the only seed for its PRG. This didn't lead to any obvious problems during testing, since the 32,768 possible RNG streams all looked pretty random. It was only after the public release that people started that many devices were sharing keys.

** If you're going to do this, you should also be sure to use a MAC on your ciphertext, including the initial counter value for each message.

*** A great example is unpadded, textbook RSA. If m is random, then it's quite difficult to recover m given m^e mod N. If, however, you have a few good guesses for m and you know the public key (N, e), you can easily try each of your guesses and compare the results.

**** Given two Elgamal ciphertexts on the same key and randomness (g^r, y^r*M1), (g^r, y^r*M2) you can easily compute M1/M2. A similar thing happens with hash Elgamal. This may or may not be useful to you, depending on how much you know about the content of the various messages.

A brief update

2012-03-01T07:03:00.002-08:00

(misconmike/CC)

My early-week post on the MITM certificate mess seems to have struck a nerve with readers. (Or perhaps I just picked the right time to complain!) Since folks seem interested in this subject, I wanted to follow up with a few quick updates:

The EFF has released a new version of HTTPS Everywhere, which includes a nifty 'Decentralized SSL Observatory' feature. This scans for unusual certificates (e.g., MITM certs, certs with weak keys) and reports them back to EFF for logging. A very nice step towards a better 'net.
StalkR reminds me that Chrome 18 includes support for Public-key Pinning. This is an HTTP extension that allows a site operator to 'pin' their site to one (or more) pre-specified public keys for a given period of time. A pinned browser will reject any alternative keys that show up -- even if they're embedded in a valid certificate.
A couple of readers point out that popular sites (e.g., Google and Facebook) change their certificates quite frequently -- possibly due to the use of load balancers -- which poses a problem for "carry a list of legitimate certs with you" solutions. I recognize this. The best I can say is that we're all better off if bogus certs are easy to detect. Hopefully site operators will find a compromise that makes this easy for us.

Appearances to the contrary, this blog is not going to become a forum for complaining about CAs. I'll be back in a few days with more wonky crypto posts, including some ideas for dealing with bad randomness, some thoughts on patented modes of operation, and an update on the progress that researchers are making with Fully-Homomorphic Encryption.

The Internet is broken: could we please fix it?

2012-02-27T20:43:00.000-08:00

Ok, this is a little embarrassing, and I hate having to admit it publicly. But I can't hold it in any longer: I think I'm becoming an Internet activist.

This is upsetting to me, since active is the last thing I ever thought I'd be. I have friends who live to make trouble for big corporations on the Internet, and while I admire their chutzpah (and results!), they've always made me a little embarrassed. Even when I agree with their cause, I still have an urge to follow along, cleaning up the mess and apologizing on behalf of all the 'reasonable' folks on the Internet.

But every man has a breaking point, and the proximate cause of mine is Trustwave. Or rather, the news that Trustwave -- an important CA and pillar of the Internet -- took it upon themselves to sell a subordinate root cert to some (still unknown) client, for the purposes of ~~undermining the trust assumptions that make the Internet secure~~ eavesdropping on TLS connections.

This kind of behavior is absolutely, unquestionably out of bounds for a trusted CA, and certainly deserves a response -- a stronger one than it's gotten. But the really frightening news is twofold:

There's reason to believe that other (possibly bigger) CAs are engaged in the same practice.
To the best of my knowledge, only one browser vendor has taken a public stand on this issue, and that vendor isn't gaining market share.

The good news is that the MITM revelation is exactly the sort of kick we've needed to improve the CA system. And even better, some very bright people are already thinking about it. The rest of this post will review the problem and talk about some of the potential solutions.

Certificates 101

For those of you who know the TLS protocol (and how certificates work), the following explanation is completely gratuitous. Feel free to skip it. If you don't know -- or don't understand the problem -- I'm going to take a minute to give some quick background.

TLS (formerly SSL) is probably the best-known security protocol on the Internet. Most people are familiar with TLS for its use in https -- secure web -- but it's also used to protect email in transit, software updates, and a whole mess of other stuff you don't even think about.

TLS protects your traffic by encrypting it with a strong symmetric key algorithm like AES or RC4. Unfortunately, this type of cryptography only works when the communicating parties share a key. Since you probably don't share keys with most of the web servers on the Internet, TLS provides you with a wonderful means to do so: a public-key key agreement protocol.

I could spend a lot of time talking about this, but for our purposes, all you need to understand is this: when I visit https://gmail.com, Google's server will send me a public key. If this key really belongs to Google, then everything is great: we can both derive a secure communication key, even if our attacker Mallory is eavesdropping on the whole conversation.

If, on the other hand, Mallory can intercept and modify our communications, the game is very different. In this case, she can overwrite Gmail's key with her own public key. The result: I end up sharing a symmetric key with her! The worst part is that I probably won't know this has happened: clever Mallory can make her own connection to Gmail and silently pass my traffic through -- while reading every word. This scenario is called a Man in the Middle (MITM) Attack.

MITM attack. Alice is your grandmother, Bob is BankofAmerica.com, and Mallory establishes connections with both. (Wikipedia/CC license)

MITM attacks are older than the hills. Fortunately TLS has built-in protections to thwart them. Instead of transmitting a naked public key, the Gmail server wraps its key in a certificate; this is a simple file that embeds both the key and some identifying information, like "gmail.com". The certificate is digitally signed by someone very trustworthy: one of a few dozen Certificate Authorities (CA) that your browser knows and trusts. These include companies like Verisign, and (yes) Trustwave.

TLS clients (e.g., web browsers) carry the verification keys for a huge number of CAs. When a certificate comes in, they can verify its signature to ensure that it's legit. This approach works very well, under one very important assumption: namely, Mallory won't be able to get a signed certificate on a domain she doesn't own.

What's wrong with the CA model?

The real problem with the CA model is that every root CA has the power to sign any domain, which completely unravels the security of TLS. So far the industry has policed itself using the Macaroni Grill model: If a CA screws up too badly, they face being removed from the 'trusted' list of major TLS clients. In principle this should keep people in line, since it's the nuclear option for a CA -- essentially shutting down their business.

Unfortunately while this sounds good it's tricky to implement in practice. That's because:

It assumes that browser vendors are willing to go nuclear on their colleagues at the CAs.
It assumes that browser vendors can go nuclear on a major CA, knowing that the blowback might very well hurt their product. (Imagine that your browser unilaterally stopped accepting Verisign certs. What would you do?)
It assumes that someone will catch misbehaving CAs in the first place.

What's fascinating about the Trustwave brouhaha is that it's finally giving us some visibility into how well these assumptions play out in the real world.

So what happened with Trustwave?

In late January of this year, Trustwave made a cryptic update to their CA policy. When people started asking about it, they responded with a carefully-worded post on the company blog. When you cut through the business-speak, here's what it says:

We sold the right to generate certificates -- on any domain name, regardless of whether it belongs to one of our clients or not -- and packed this magical capability into a box. We rented this box to a corporate client for the express purpose of running Man-in-the-Middle attacks to eavesdrop on their employees' TLS-secured connections. At no point did we stop to consider how damaging this kind of practice was, nor did we worry unduly about its potential impact on our business -- since quite frankly, we didn't believe it would have any.

I don't know which part is worse. That a company whose entire business is based on trust -- on the idea that people will believe them when they say a certificate is legit -- would think they could get away with selling a tool to make fraudulent certificates. Or that they're probably right.

But this isn't the worst of it. There's reason to believe that Trustwave isn't alone in this practice. In fact, if we're to believe the rumors, Trustwave is only noteworthy in that they stopped. Other CAs may still be up to their ears.

And so this finally brings us to the important part of this post: what's being done, and what can we do to make sure that it never happens again?

Option 1: Rely on the browser vendors

What's particularly disturbing about the Trustwave fiasco is the response it's gotten from the various browser manufacturers.

So far exactly one organization has taken a strong stand against this practice. The Mozilla foundation (makers of Firefox) recently sent a strongly-worded letter to all of their root CAs -- demanding that they disclose whether such MITM certificates exist, and that they shut them down forthwith. With about 20% browser share (depending on who's counting), Mozilla has the means to enforce this. Assuming the vendors are honest, and assuming Mozilla carries through on its promise. And assuming that Mozilla browser-share doesn't fall any further.

That's the good news. Less cheerful is the deafening silence from Apple, Microsoft and Google. These vendors control most of the remaining browser market, and to the best of my knowledge they've said nothing at all about the practice. Publicly, anyway. It's possible that they're working the issue privately; if so, more power to them. But in the absence of some evidence, I find it hard to take this on faith.

Option 2: Sunshine is the best disinfectant

The Trustwave fiasco exposes two basic problems with the CA model: (1) any CA can claim ownership of any domain, and (2) there's no easy way to know which domains a CA has put its stamp on.

This last is very much by CA preference: CAs don't want to reveal their doings, on the theory that it would harm their business. I can see where they're coming from (especially if their business includes selling MITM certs!) Unfortunately, allowing CAs to operate without oversight is one of those quaint practices (like clicking on links sent by strangers) that made sense in a more innocent time, but no longer has much of a place in our world.

Merkle tree (Wikipedia/CC)

Ben Laurie and Adam Langley feel the same way, and they've developed a plan to do something about it. The basic idea is this:

Every new certificate should be published in a public audit log. This log will be open to the world, which means that everyone can scan for illegal entries (i.e., their own domain appearing in somebody else's certificate.)
Anytime a web server hands out a certificate, it must prove that the certificate is contained in the list.

The beautiful thing is that this proof can be conducted relatively efficiently using a Merkle hash tree. The resulting proofs are quite short (log(N) hashes, where N is the total number of certificates). Browsers will need to obtain the current tree root, which requires either (a) periodic scanning of the tree, or some degree of trust in an authority, who will periodically distribute signed root nodes.

Along the same lines, the EFF has a similar proposal called the Sovereign Keys Project. SKP also proposes a public log, but places stronger requirements on what it takes to get into the log. It's quite likely that in the long run these projects will merge, or give birth to something even better.

Option 3: Eternal vigilance

The problem with SKP and the Laurie/Langley proposal is that both require changes to the CA infrastructure. Someone will need to construct these audit logs; servers will have to start shipping hash proofs. Both can be incrementally deployed, but will only be effective once deployment reaches a certain level.

Another option is to dispense with this machinery altogether, and deal with rogue CAs today by subjecting them to contant, unwavering surveillance. This is the approach taken by CMU's Perspectives plugin and by Moxie Marlinspike's Convergence.

The core idea behind both of these systems is to use 'network perspectives' to determine whether the certificate you're receiving is the same certificate that everyone else is. This helps to avoid MITMs, since presumably the attacker can only be in the 'middle' of so many network paths. To accomplish this, both systems deploy servers called Notaries -- run on a volunteer basis -- which you can call up whenever you receive an unknown certificate. They'll compare your version of the cert to what they see from the same server, and help you ring the alarm if there's a mismatch.

A limitation of this approach is privacy; these Notary servers obviously learn quite a bit about the sites you visit. Convergence extends the Perspectives plugin to address some of these issues, but fundamentally there's no free lunch here. If you're querying some external party, you're leaking information.

One solution to this problem is to dispense with online notary queries altogether, and just ask people to carry a list of legitimate certificates with them. If we assume that there are 4 million active certificates in the world, we could easily fit them into a < 40MB Bloom filter. This would allow us to determine whether a cert is 'on the list' without making an online query. Of course, this requires someone to compile and maintain such a list. Fortunately there are folks already doing this, including the EFF's SSL Observatory project.

Option 4: The hypothetical

The existence of these proposals is definitely heartening. It means that people are taking this seriously, and there's an active technical discussion on how to make things better.

Since we're in this mode, let me mention a few other things that could make a big difference in detecting exploits. For one thing, it would be awfully nice if web servers had a way to see things through their clients' eyes. One obvious way to do this is through script: use Javascript to view the current server certificate, and report the details back to the server.

Of course this isn't perfect -- a clever MITM could strip the Javascript or tamper with it. Still, obfuscation is a heck of a lot easier then de-obfuscation, and it's unlikely that a single attacker is going to win an arms race against a variety of sites.

Unfortunately, this idea has to be relegated to the 'could be, should be' dustbin, mostly because Javascript doesn't have access to the current certificate info. I don't really see the reason for this, and I sure hope that it changes in the future.

Option 5: The long arm of the law

I suppose the last option -- perhaps the least popular -- is just to treat CAs the same way that you'd treat any important, trustworthy organization in the real world. That means: you cheat, you pay the penalty. Just as we shouldn't tolerate Bank of America knowingly opening a credit line in the name of a non-customer, we shouldn't tolerate a CA doing the same.

Option 6: Vigilante justice

Ok, I'm only kidding about this one, cowboy. You can shut down that LOIC download right now.

In summary

I don't know that there's a magical vaccine that will make the the CA system secure, but I've come to believe that the current approach is not working. It's not just examples like Trustwave, which (some might argue) is a relatively limited type of abuse. It's that the Trustwave revelation comes in addition to a steady drumbeat of news about stolen keys, illegitimately-obtained certificates, and various other abuses.

While dealing with these problems might not be easy, what's shocking is how easy it would be to at least detect and expose the abuses at the core of it -- if various people agreed that this was a worthy goal. I do hope that people start taking this stuff seriously, mostly because being a radical is hard, hard work. I'm just not cut out for it.

Random number generation: An illustrated primer

2012-02-21T13:42:00.000-08:00

Last week we learned (from two different sources!) that certain RSA implementations don't properly seed their random number generators before generating keys. One practical upshot is that a non-trivial fraction of RSA moduli share a prime factor. Given two such moduli, you can easily factor both.

This key generation kerfuffle is just the tip of the iceberg: a lot of bad things can happen when you use a weak, or improperly-seeded RNG. To name a few:

Re-using randomness with (EC)DSA can lead to key recovery.
Re-using randomness with Elgamal can lead to plaintext recovery and other ugliness.
Using predictable IVs in CBC or CTR mode encryption can lead to plaintext recovery.
When protocols use predictable nonces they may become vulnerable to e.g., replay attacks.

In the rest of this post I'm going to talk about the various ways that random number generators work, the difference between RNGs and PRGs, and some of the funny problems with both. Since the post has gotten horrifically long, I've decided to present it in a (fun!) question/answer style that makes it easy to read in any order you want. Please feel free to skip around.

What's the difference between Randomness, Pseudo-Randomness and Entropy?

Before we get started, we have to define a few of our terms. The fact is, there are many, many definitions of randomness. Since for our purposes we're basically interested in random bit generators, I'm going to give a workaday definition: with a truly random bit generator, nobody (regardless of what information or computing power they have) can predict the next output bit with probability greater than 1/2.

If we lived in an orderly universe, it would be hard to build generators that meet this standard. Fortunately, the universe we live in seems to be anything but orderly. Physicists tell us that at the quantum level certain events have measurable probabilities, but otherwise cannot be predicted in advance.

A hardware RNG.

The most expensive hardware RNGs take advantage of this, measuring such phenomena as radioactive decay or shot noise. Most consumer-grade RNGs don't have radioactive particles lying around, so they instead measure macroscopic, but chaotic phenomena -- typically highly-amplified electrical noise.

These devices are great if you've got 'em; unfortunately not everyone does. For the rest of us, the solution is to collect unpredictable values from the computer we're working on. While this gunk may not be truly random, we hope that it has sufficient entropy -- essentially a measure of unpredictability -- that our attacker won't know the difference.

If you're using a standard PC, your system is probably filling its entropy pool right now: from unpredictable values such as drive seek or inter-keystroke timings. Taken individually none of these events provide enough entropy to do much; but by 'stirring' many such measurements together you can obtain enough to do useful cryptography.

Random vs. Pseudorandom. The big problem with RNGs is that they're usually pretty inefficient. Hardware RNGs can only collect so many bits per second, and the standard OS entropy measurement techniques are even slower. For this reason, many security systems don't actually use this entropy directly. Instead, they use it to seed a fast cryptographically-secure pseudo-random generator, sometimes called a CSPRNG or (to cryptographers) just a PRG.

PRGs don't generate random numbers at all. Rather, they're algorithms that take in a short random string ('seed'), and stretch it into a long sequence of random-looking bits. Since PRGs are deterministic and computational in nature, they obviously don't satisfy our definition of randomness (a sufficiently powerful attacker can simply brute-force her way through the seed-space.) But if our attackers are normal (i.e., computationally limited) it's possible to build unpredictable PRGs from fairly standard assumptions.*

Combining RNGs and PRGs. As I said, most systems combine an RNG with a PRG, using the former to generate a seed for the latter. Some standards actually mandate this combination -- not just because it's faster, but because the additional layer of PRG is believed to offer some resilience in the event that the RNG contains a hardware flaw.

You can argue about whether this is a good idea, but the upshot is as follows: if you want to understand where 'random' numbers come from, you really need to understand both technologies and how they interoperate on your machine.

Where does my entropy come from?

Unless you're running a server and have a fancy Hardware Security Module installed, chances are that your system is collecting entropy from the world around it. Most OSes do this at the kernel level, using a variety of entropy sources which are then 'stirred' together. These include:

Drive seek timings. Modern hard drives (of the spinning variety) are a wonderful source of chaotic events. In 1994 Davis, Ihaka and Fenstermacher argued that drive seek times are affected by air turbulence within the drive's enclosure, which makes them an excellent candidate for cryptographic entropy sampling. It's not clear how this technique holds up against solid-state drives; probably not well.
Mouse and keyboard interaction. People are unpredictable. Fortunately for us, that's a good thing. Many RNGs collect entropy by measuring the time between a user's keystrokes or mouse movements, then gathering a couple of low-order bits and adding them to the pool.
Network events. Although network events (packet timings, for example) seem pretty unpredictable, most systems won't use this data unless you explicitly tell them to. That's because the network is generally assumed to be under the adversary's control (he may be the one sending you those 'unpredictable' packets!) You disable these protections at your own risk.
Uninitialized memory. Ever forget to initialize a variable? Then you know that RAM is full of junk. While this stuff may not be random, certain systems use it on the theory that it probably can't hurt. Occasionally it can -- though not necessarily in the way you'd think. The classic example is this Debian OpenSSL bug, which (via a comedy of errors) meant that the PRG had only 32,768 possible seed values.
Goofy stuff. Some systems will try to collect entropy by conducting unpredictable calculations. One example is to start many threads counting towards infinity, then stop one with a hardware interrupt. I've done this once before and evaluated the output. I assure you that YMMV. Significantly.
Trusted Platform Module. Many desktop machines these days include a TPM chip on the motherboard. The good news about this is that every TPM contains an internal hardware RNG, which your OS can access if it has the right drivers. It ain't fast, and the design hasn't been publicly audited. Still, folding some of this into your entropy pool is probably a good idea.
New processor RNGs. To save us all this trouble, the next generation of Intel processors will contain a built-in hardware RNG/PRG, which goes by the codename 'Bull Mountain'. Perhaps this will be the solution to all of our problems. (h/t David Johnston in comments.)

The upshot of all of this is that on a typical machine there's usually enough 'unpredictable' stuff going on to seed a decent entropy pool. The real problems come up in systems that aren't typical.

What about VMs and embedded devices?

Life inside an embedded device.

The problem with classical entropy gathering is that it assumes that unpredictable things will actually happen on the system. Unfortunately, VMs and embedded devices defy this expectation, mostly by being very, very boring.

Imagine the following scenario: you have a VM instance running on a server. It has no access to keyboard or mouse input, and only mediated access to hardware, which it shares with eight other VM instances.

Worse yet, your VM may be a clone. Perhaps you just burped up fifty instances of that particular image from a 'frozen' state. Each of these VMs may have loads of entropy in its pool, but it's all the same entropy, across every clone sibling. Whether this is a problem depends on what the VM does next. If it has enough time to replenish its entropy pool, the state of the VMs will gradually diverge. But if it decides to generate a key: not good at all.

Embedded devices present their own class of problems. Unfortunately (like every other problem in the embedded arena) there's no general solution. Some people obtain entropy from user keypad timings -- if there is a user and a keypad. Some use the low-order bits of the ADC output. Still others forgo this entirely and ship their devices with an externally-generated PRG seed, usually stored in NVRAM.

I don't claim that any of these are good answers, but they're better than the alternative -- which is to pretend that you have entropy when you don't.

How do pseudo-random number generators work?

You've read the books. You've seen the movies. But when it comes down to it you still don't understand the inner workings of the typical pseudo-random number generator. I can't possibly make up for this in a single blog post, but hopefully I can hit a few of the high points.

Block cipher-based PRGs. One common approach to PRG construction uses a block cipher to generate unpredictable bits. This seems like a reasonable choice, since modern block ciphers are judged for their quality as pseudo-random permutations, and because most crypto libraries already have one lying around somewhere.

ANSI X9.31 PRNG implemented with AES (source). At each iteration, the PRNG takes in a predictable 'date-time vector' (DTi) and updated state value (Si). It outputs a block of random bits Ri. The generator is seeded with a cipher key (k) and an initial state S0.

One inexplicably popular design comes from ANSI X9.31. This PRG is blessed by both ANSI and FIPS, and gets used in a lot of commercial products (OpenSSL also uses it in FIPS mode). It takes in two seeds, k and S0 and does pretty much what you'd expect, on two conditions: you seed both values, and you never, ever reveal k.

Unfortunately, if k does leak out things can get ugly. With knowledge of k your attacker can calculate every previous and future PRG output from one single block of output!** This is totally gratuitous, and makes you wonder why this particular design was ever chosen -- much less promoted.

Before you dismiss this as a theoretical concern: people routinely make stupid mistakes with X9.31. For example, an early draft of the AACS standard proposed to share one k across many different devices! Moreover keys do get stolen, and when this happens to your RNG you risk compromising every previous transaction on the system -- even supposedly 'forward-secure' ones like ephemeral ECDH key exchanges. You can mitigate this by reseeding k periodically.

Hash-based PRGs. Many PRGs do something similar, but using hash functions instead of ciphers. There are some good arguments for this: hash functions are very fast, plus they're hard to invert -- which can help to prevent rewinding attacks on PRG state. Since there are zillions of hash-based PRGs I'll restrict this discussion to a few of the most common ones:

FIPS 186-2 (Appendix 3) defines a SHA-based generator that seems to be all the rage, despite the fact that it was nominally defined only for DSA signing. Windows uses this as its default PRG.
Linux uses a hash-based PRG based on two variants of SHA.
The non-FIPS OpenSSL PRG also uses a hash-based design. Like everything else in OpenSSL, it's clearly documented and follows standard, well-articulated design principles.

Left: the Linux PRG (circa 2006). Right: the non-FIPS OpenSSL PRG.

Number-theoretic PRGs. The problem with basing a PRG on, say, a hash function is it makes you dependent on the security of that primitive. If a the hash turns out to be vulnerable, then your PRG could be as well.*** (Admittedly, if this happens to a standard hash function, the security of your PRG may be the least of your concerns.)

One alternative is to use a PRG that relies on well-studied mathematical assumptions for its security. Usually, you pay a heavy cost for this hypothetical benefit -- these generators can be 2-3 orders of magnitude slower than their hash-based cousins. Still, if you're down for this you have various choices. An oldie (but goodie) is Blum-Blum-Shub, which is provably secure under the factoring assumption.

If you like standards, NIST also has a proposal called Dual-EC-DRBG. Dual-EC is particularly fascinating, for the following three reasons. First, it's built into Windows, which probably makes it the most widely deployed number-theoretic PRG in existence. Second, it's slightly biased, due to a 'mistake' in the way that NIST converted EC points into bits.**** Also, it might contain a backdoor.

This last was pointed out by Shumow and Ferguson at the Crypto 2007 rump session. They noticed that the standard parameters given with Dual-EC could easily hide a trapdoor. Anyone who knew this value would be able to calculate all future outputs of the PRG after seeing only a 32-byte chunk of its output! Although there's probably no conspiracy here, NSA's complicity in designing the thing doesn't make anyone feel better about it.

Shrinking generator.

The rest. There are many dedicated PRG constructions that don't fit into the categories above. These include stream ciphers like RC4, not to mention a host of crazy LFSR-based things. All I can say is: if you're going to use something nonstandard, please make sure you have a good reason.

How much entropy do I need?

The general recommendation is that you need to seed your PRG with at least as much entropy as the security level of your algorithms. If you're generating 1024-bit RSA keys, the naive theory tells you that you need at least 80 bits of entropy, since this is the level of security provided by RSA at that key size.

In practice you need more, possibly as much as twice the security level, depending on your PRG. The problem is that many PRNGs have an upper bound on the seed size, which means they can't practically achieve levels higher than, say, 256 bits. This is important to recognize, but it's probably not of any immediate practical consequence.

I don't care about any of this, just tell me how to get good random numbers on my Linux/Windows/BSD system!

The good news for you is that modern operating systems and (non-embedded) hardware provide most of what you need, meaning that you're free to remain blissfully ignorant.

On most Unix systems you can get decent random numbers by reading from /dev/random and /dev/urandom devices. The former draws entropy from a variety of system sources and hashes it together, while the latter is essentially a PRG that seeds itself from the system's entropy pool. Windows can provide you with essentially the same thing via the CryptoAPI (CAPI)'s CryptGenRandom call.

Care must be taken in each of these cases, particularly as your application is now dependent on something you don't control. Many cryptographic libraries (e.g., OpenSSL) will run their own internal PRG, which they seed from sources like the above.

I've designed my own PRG. Is this a good idea?

Maybe. But to be completely honest, it probably isn't.

If I seed my PRG properly, is it safe to use RSA again?

Yes. Despite the title of the recent Lenstra et al. paper, there's nothing wrong with RSA. What seems to have happened is that some embedded systems didn't properly seed their (P)RNGs before generating keys.

I'm sure there's more to it than that, but at a high level: if you make sure to properly seed your PRG, the probability that you'll repeat a prime is negligibly small. In other words, don't sweat it.

Notes:

* The security definition for a PRG is simple: no (computationally limited) adversary should be able to distinguish the output of a PRG from a sequence of 'true' random numbers, except with a negligible probability. An equivalent definition is the 'next bit test', which holds that no adversary can predict the next bit output by a PRG with probability substantially different from 1/2.

** Decrypting Ri gives you (Si XOR Ii), and decrypting DTi gives you Ii. You can now calculate Si by XORing the results. If you know DT{i-1} you can now compute R{i-1} and start the process over again. This was first noted by Kelsey, Schneier, Wagner and Hall in the context of an early version (X9.17). It works even if you only have a rough guess for the timestamp values -- a pretty reasonable assumption, since some implementations specify a counter for the DT values.

*** It's also important to be clear what security properties you're relying on with a hash-based PRG. Most of the high-profile attacks on hash functions (e.g., MD5) focus on finding collisions; they're not attacks on the pseudo-random nature of the outputs. In practice, this means you usually get lots of warning before a hash function becomes unsuitable for use in a PRG. Or maybe you won't! Fun stuff.

**** Dual-EC is another fun example of NIST developing provably-secure looking protocols, but not actually including a security proof. This is particularly bizarre, because the only conceivable reason to use something as slow as Dual-EC is to gain this level of provable security. The generator is divided into two parts: the first generates pseudo-random EC points (this part is provable under the DDH assumption). The other part turns these points into bits. It's the latter part that has the biasing flaw. Amusingly, the potential 'backdoor' wouldn't be possible if the designers had built this part differently.

RSA keys: no insight whatsoever

2012-02-15T08:40:00.000-08:00

I have a deadline coming up so (substantial) posting will be light this week.

For those of you who don't read the New York Times, the big story of the week is this paper by Lenstra, Hughes, Augier, Bos, Kleinjung and Wachterlet:

Ron was wrong, Whit is right

We performed a sanity check of public keys collected on the web. Our main goal was to test the validity of the assumption that different random choices are made each time keys are generated. We found that the vast majority of public keys work as intended. A more disconcerting finding is that two out of every one thousand RSA moduli that we collected offer no security. Our conclusion is that the validity of the assumption is questionable and that generating keys in the real world for ``multiple-secrets'' cryptosystems such as RSA is significantly riskier than for ``single-secret'' ones such as ElGamal or (EC)DSA which are based on Diffie-Hellman.

Lots of people have written insightfully on this topic. See Dan Kaminsky's post here, for example, or Thomas Ptacek's excellent multi-part Twitter musing. (Update: much better, see Nadia Heninger's explanation at the end of this post.)

There must be something wrong with me, because I find it almost impossible to draw any deep insight at all from this work. Don't get me wrong: the paper itself is a fantastic piece of research; it sets a new standard for data analysis on public keys and certs. I hope we see more like it.

But what's the takeaway? That two-key systems are insecure? That intelligence agencies have known this for years? Maybe. Whatever. The takeaway to me is that one (or more) RSA keygen implementations had a crappy RNG, or didn't properly seed its PRG.

That's really good to know about, but it isn't the big news that the paper's title would imply. It doesn't have any implications for the use of RSA or any other cryptosystem. I'd sure like to solve the mystery of which implementations we need to look out for, and how to make sure this doesn't happen again, but that's literally the only thing I take away from this -- so far.

I don't mean to sound like a curmudgeon. Really, I want to believe. Please help me!

Update: Mystery solved! Nadia Heninger has a post at Freedom to Tinker explaining that most of these keys were generated by embedded devices, and that -- through a parallel research effort -- they actually know which devices. Once again extremely nice work. Even nicer than Lenstra et al., since it's actually useful. (I can only imagine how Nadia and her team have been feeling the past two days, seeing 'their' result all over the New York Times. That's responsible disclosure for you.)

SSL MITM Update

2012-02-14T08:05:00.000-08:00

The other day I snarked about Trustwave's decision to sell subordinate root ('skeleton') certificates to their corporate clients, for the explicit purpose of ~~destabilizing the web's Public Key Infrastructure~~ 'legitimately'* intercepting TLS connections. This practice (new to me) is ostensibly only permitted in limited, controlled settings (usually to spy on a company's employees).

Trustwave argues that the key was always safe inside of a Hardware Security Module and besides, they're not doing it any more. (Kind of like saying that you handed out the master key to every door on earth but it's ok 'cause you chained it to a hubcap.)

Unfortunately, the really bad news is that Trustwave may not be the only major CA implicated in this practice. And at least one browser vendor is planning to do something about it:

Dear Certification Authority,
This note requests a set of immediate actions on your behalf, as a
participant in the Mozilla root program.

Please reply by {date 2 weeks out} to confirm completion of the
following actions or state when these actions will be completed.

1) Subordinate CAs chaining to CAs in Mozilla’s root program may not be
used for MITM purposes, regardless of whether it is in a closed and
controlled environment or not. Please review all of your subordinate CAs
to make sure that they may not be used for MITM purposes. Any existing
subordinate CAs that may be used for that purpose must be revoked and
any corresponding HSMs destroyed by {date TBD}. For each subordinate CA
that is revoked, send me:
a) The certificate that signed the subCA. If it is a root certificate in
NSS, then the root certificate's subject and SHA1 fingerprint.
b) The Serial Number of the revoked certificate.
c) The CRL that contains the serial number of the revoked certificate.

As a CA in Mozilla’s root program you are ultimately responsible for
certificates issued by you and your subordinate CAs. After {date TBD} if
it is found that a subordinate CA is being used for MITM, we will remove
the corresponding root certificate. Based on Mozilla’s assessment, we
may also remove any of your other root certificates, and root
certificates from other organizations that cross-sign your certificates.

2) Please add a statement to your CP/CPS committing that you will not
issue a subordinate certificate that may be used for MITM or traffic
management of domain names or IPs that the party does not legitimately
own or control. Send me the URL to the updated document(s) and the
impacted sections or page numbers.

...

Participation in Mozilla's root program is at our sole discretion, and
we will take whatever steps are necessary to keep our users safe.
Nevertheless, we believe that the best approach to safeguard that
security is to work with CAs as partners, to foster open and frank
communication, and to be diligent in looking for ways to improve. Thank
you for your participation in this pursuit.

Regards,
Kathleen Wilson
Module Owner of Mozilla's CA Certificates Module

Now I'm no bomb-thrower, but if it were up to me, {Date TBD} would be yesterday and there would be no re-entry for the CAs caught doing this kind of thing. Still, I'm glad that Mozilla is doing this, and we're all lucky that they have the independence and browser share to force this kind of change.

But not everything is sunshine and rainbows:

We have to trust that the CAs in question will respond honestly to Mozilla's inquiry and will voluntarily exit a (presumably) lucrative business. This relies very much on the honor system, and it's hard to presume much honor in a CA that would sell such a product in the first place.
Mozilla only represents 25% of the browser share, and that seems to be falling. That's probably enough to make the difference -- today -- but it'd be nice to hear something similar from Microsoft or Google.
We still lack a good client-side mechanism for detecting and reporting unusual (that is: correctly signed, but inconsistent) certificates. Given the news from Trustwave, such a mechanism seems more useful than ever.

We cannot possibly have faith in the security of the Internet when CAs are willing to engage in this kind of practice -- even if they do it under the most 'carefully-controlled' conditions.

* Whatever that means.

Trustwave announces name change: henceforth will simply be 'Wave'

2012-02-09T13:57:00.000-08:00

This story has making the rounds for about a week and I'm still shocked by it. Here's the postage stamp version: at some point in the past few years, certificate authority Trustwave basically handed out their root signing capability to a third party company. But don't worry, it's all better now.

As with any such story, there are bits we know and bits we have to speculate about. Speculation is more fun, so let's start there:

Once upon a time there was a company -- let's call them ACME Inc -- who really didn't trust its employees. For ACME the solution was vigilance. Constant, invasive vigilance. ACME's IT department was given the task of intercepting every packet sent to and from the corporate network, which seemed straightforward; until someone pointed out that they could intercept all the packets they wanted, but they couldn't necessarily read them. Especially not the ones encrypted with SSL/TLS.

Now this isn't a killer. ACME had a few options: they could (a) block SSL/TLS at their network gateway, forcing everyone to use cleartext connections. They could (b) force their employees to use some awkward SSL proxy. If they were feeling ambitious, they could even (c) run a man-in-the-middle on every SSL connection initiated from within their corporate network. The last option would result in some awkward certificate errors, however -- which would be unpleasant for web users, and downright nasty for embedded devices or headless boxes.

But really, each of these solution is just a different version of flypaper. Why catch flies with flypaper, when you can totally screw with the trust model of the Internet?

And this is where we get to the facts. A few years back ACME -- or some company like ACME -- approached Trustwave with this problem. Trustwave seemed like a good group to ask, since they're one of the select few companies that make SSL certificates, i.e., they're one of the 'authorities' whose root certs are built into all of the major browsers and OSes.

Somehow the two companies cooked up the following plan. Trustwave would generate a new 'subordinate root' certificate with full signing authority. Anyone who possessed the signing key for this cert would essentially be Trustwave -- meaning that they could vouch for any website they wanted. Of course, such a key would be enormously valuable (and dangerous). No responsible CA would allow such a thing to leave their facilities.

But apparently Trustwave's motto is 'think different'. So they cheerfully packed the signing key into a Hardware Security Module and sent it over to ACME. From that point on, ACME possessed the ability to transparently impersonate any SSL website on the Internet.

And impersonate they did; whenever some client initiated an SSL connection from within ACME's corporate network, an ACME server would intercept the connection, sign a fresh certificate on the requested domain, then deliver that cert back to the client. To the client, it appeared that the connection went through perfectly. But of course the client was now talking to ACME's server, not to the company whose name was on the certificate. ACME would in turn connect on to the target SSL server, thus completing the connection.

Technically this tampering wasn't totally invisible; a clever user might notice that every certificate was now signed by Trustwave -- and comparison with certificates received outside of ACME's network would clearly reveal something funny going on. But since the vast majority of web users don't check this kind of thing, the interception was basically transparent.

Now I hope I don't need to tell you why this is a bad idea. Let's just take it a a given that this is a bad idea. Even Trustwave now realizes it's a bad idea, and have 'proactively' revoked the cert to make sure the evil thing doesn't fall into the wrong hands. From their blog post about it:

Trustwave has decided to be open about this decision as well as stating that we will no longer enable systems of this type and are effectively ending this short journey into this type of offering.

I guess we can at least be thankful that Trustwave has decided to be open about this decision, despite the fact that they weren't open about it while it was happening. Let's all hope this is really the last journey Trustwave plans to take into this type of offering, where by 'offering' I mean -- disastrous, short-sighted mistake.

Satellite phone encryption is terrible. Anyone surprised?

2012-02-05T12:25:00.000-08:00

I adhere to a 'one post, one topic' rule on this blog, which means that this weekend I actually have to choose which bad-crypto news I'm going to blog about.

It's a tough call, but the most interesting story comes via Erik Tews, who recently attended a talk on satellite phone security at Ruhr Universität Bochum. It seems that researchers Benedikt Driessen, Ralf Hund, Carsten Willems, Christof Paar, and Thorsten Holz have reverse-engineered and cryptanalyzed the proprietary ciphers used in the GMR-1 and GMR-2 satellite telephone standards.* If you've never heard of these standards, what you need to know is that they power the networks of satphone providers Thuraya and Inmarsat.

The verdict? Encrypting with these ciphers is better than using no encryption. But not necessarily by much.

I guess this shouldn't come as a big shock -- link privacy in mobile telephony has always been kind of a mess. And the GMR ciphers come from the same folks (ETSI) who brought us the A5-series GSM ciphers. If you pay attention to this sort of thing, you probably know that those ciphers have also had some problems. In fact, today it's possible to download rainbow tables that permit (efficient) decryption of A5/1-encrypted GSM phone calls.

A5/1 is actually the strong member of the GSM family. For export purposes there's A5/2 -- a weakened version with a much shorter key. You don't hear about people downloading huge A5/2 rainbow tables, mostly because you don't need them. A5/2 is vulnerable to ciphertext-only attacks that run in a few minutes on a standard PC.

A5/2 GSM cipher. Image: Barkan, Biham, Keller.

ETSI seems to have had A5/2 in mind when developing the GMR-1 and GMR-2 ciphers. Both are custom designs, use short keys, and depend heavily on obscurity of design to make up for any shortcomings (the ciphers are only given to manufacturers who sign an NDA). This secrecy hardly inspires confidence, and worse yet, it doesn't even do a good job of keeping things secret. The R.U.B. researchers didn't have to break into Thuraya's hardware lab; they simply reversed the ciphers from handset firmware updates.**

GMR-1 uses an LFSR-based cipher quite similar to A5/2 (pictured above), which means that it's vulnerable to a similar class of attacks. Since the underlying plaintext has correctness checks built into it, it's possible to recover the key using only ciphertext and about 30 minutes on a standard PC. The GMR-2 cipher is a bit more sophisticated (and weirder to boot), but it also appears to have weaknesses.

So why is this a big deal? The obvious answer is that satellite telephone security matters. In many underdeveloped rural areas it's the primary means of communicating with the outside world. Satphone coverage is also important in war zones, where signal privacy is of more than academic interest.

Moreover, eavesdropping on satellite communications is (in principle) easier than eavesdropping on cellular signals. That's because satellite 'spot beams' cover relatively broad geographic territories (Thuraya's are 600km on average). So you don't just have to worry about eavesdropping by your neighbor, you have to worry about eavesdropping by neighboring countries.

The really sad thing is that, unlike cellular networks -- which are fundamentally vulnerable to government eavesdropping at the infrastructure level -- satellite networks like Thuraya/Inmarsat don't need local infrastructure. That means their systems really could have provided privacy for individuals persecuted by oppressive regimes. You can argue about whether the manufacturers even had the option to use strong ciphers; it's quite possible they didn't. Still, I suspect this will be cold comfort to those who suffer as a direct result of ETSI's design choices.

Those who are really in the know (news organizations, for example) claim to use additional security measures beyond the built-in link encryption found in GMR-1 and GMR-2. Presumably these days the best way to do that is to run your own voice protocol via the packet data extensions. This practice ought to become more common going forward; now that the GMR-1 code is public, it looks like the barriers to eavesdropping are going to go down quite a bit.

The slides above come from this presentation.

Notes:

* Update 2/16/2012: I had some initial confusion about the authorship on this work, but the research paper clears it all up: see here.

** And by 'simply', I mean 'with great expertise and difficulty' -- don't read this as trivializing the effort involved. Obtaining the ciphers meant disassembling code written in a proprietary DSP instruction set, and then searching for a cipher without knowing exactly what it looks like. All in all a pretty significant accomplishment. The point here is that it could have been a lot harder. If you're going to keep a cipher secret, you shouldn't release it as software in the first place.

Multiple encryption

2012-02-02T10:07:00.000-08:00

Not everything combines well.

While browsing some community websites, I noticed a few people talking about the security of double (or more generally, multiple) encryption. Multiple encryption addresses the following problem: you have two (or more) encryption schemes, and you're worried that one of them might get compromised. Surely if you encrypt with both at the same time you'll buy yourself an added safety margin.

Let me preface this by saying that multiple encryption addresses a problem that mostly doesn't exist. Modern ciphers rarely get broken -- at least, not in the Swordfish sense. You're far more likely to get hit by malware or an implementation bug than you are to suffer from a catastrophic attack on AES.*

That said, you really are likely to get hit by malware or an implementation bug. And that's at least one argument for multiple encryption -- if you're willing to encrypt on separate, heterogenous devices.** There's also the future to think about. We feel good about AES today, but how will we feel in 2040?

I note that these are problems for the extremely paranoid -- governments, mostly -- not for the typical developer. The majority of us should work on getting single encryption right. But this kind of thing isn't ridiculous -- the NESSIE standards even recommend it. Moreover, my experience is that when people start asking questions about the security of X, it means that they're already doing X, and have been for some time.

So for all that, it's worth answering some of these questions. And roughly speaking, the questions are:

Am I better off encrypting with two or more encryption schemes (or keys?)
Could I be worse off?
If I have to do it, how should I do it securely?

Given how little sleep I've gotten recently I don't promise to answer these fully, or in any particular order. But I do hope I can provide a little bit of insight around the edges.

Preliminaries

There are many ways to double encrypt, but for most people 'double encryption' means this:

SuperDuperEncrypt(KA, KB, M) = EncryptA(KA, EncryptB(KB, M))

This construction is called a cascade. Sometimes EncryptA and EncryptB are different algorithms, but that's not really critical. What does matter for our purposes is that the keys KA and KB are independently-generated.*** (To make life easier, we'll also assume that the algorithms are published.)

A lot has been written about cascade encryption, some good and some bad. The answer to the question largely depends on whether the algorithms are simply block ciphers, or if they're true encryption algorithms (e.g., a mode of operation using a block cipher). It also depends on what security definition you're trying to achieve.

The good

Let's consider the positive results first. If either EncryptA or EncryptB is 'semantically secure', i.e., indistinguishable under chosen-plaintext attack, then so is the cascade of the two. This may seem wonky, but it's actually very handy -- since many common cryptosystems are specifically analyzed under (at least) this level of security. For example, in the symmetric setting, both CBC and CTR modes of operation can both be shown to achieve this security level, provided that they're implemented with a secure block cipher.

So how do we know the combined construction is secure? A formal proof can be found in this 2002 paper by Herzberg, but the intuition is pretty simple. If there's an attack algorithm that 'breaks' the combined construction, then we can use that algorithm to attack either of the two underlying algorithms by simply picking our own key for the other algorithm and simulating the double encryption on its ciphertexts.

This means that an attack on the combination is an attack on the underlying schemes. So if one is secure, you're in good shape.

The not-so-good

Interestingly, Herzberg also shows that the above result does not apply for all definitions of security, particularly strong definitions such as adaptive-chosen ciphertext security. In the symmetric world, we usually achieve this level of security using authenticated encryption.

To give a concrete (symmetric encryption) example, imagine that the inner layer of encryption (EncryptB) is authenticated, as is the case in GCM-mode. Authenticated encryption provides both confidentiality (attackers can't read your message) and authenticity (attackers can't tamper with your message -- or change the ciphertext in any way.)

Now imagine that the outer scheme (EncryptA) doesn't provide this guarantee. For a simple example, consider CBC-mode encryption with padding at the end. CBC-mode is well known for its malleability; attackers can flip bits in a ciphertext, which causes predictable changes to the underlying plaintext.

The combined scheme still provides some authenticity protections -- if the attacker's tampering affects the inner (GCM) ciphertext, then his changes should be detected (and rejected) upon combined decryption. But if his modifications only change the CBC-mode padding, then the combined ciphertext could be accepted as valid. Hence the combined scheme is 'benignly' malleable, making it technically weaker than the inner layer of encryption.

Do you care about this? Maybe, maybe not. Some protocols really do require a completely non-malleable ciphertext -- for example, to prevent replay attacks -- but in most applications these attacks aren't world-shattering. If you do care, you can find some alternative constructions here.

The ugly

Of course, so far all I've discussed is whether the combined encryption scheme is at least as secure as either underlying algorithm. But some people want more than 'at least as'. More importantly, I've been talking about entire encryption algorithms (e.g., modes of operation), not raw ciphers.

So let's address the first question. Is a combined encryption scheme significantly more secure than either algorithm on its own? Unfortunately the answer is: not necessarily. There are at least a couple of counterexamples here:

The encryption scheme is a group. Imagine that EncryptA and EncryptB are the same algorithm, with the following special property: when you encrypt sequentially with KA and KB you obtain a ciphertext that can be decrypted with some third key KC.**** In this case, the resulting ciphertext ought to be at least as vulnerable as a single-encrypted ciphertext. Hence double-encrypting gives you no additional security at all. Fortunately modern block ciphers don't (seem) to have this property -- in fact, cryptographers explicitly design against it, as it can make the cipher weaker. But some number-theoretic schemes do, hence it's worth looking out for.
Meet-in-the-Middle Attacks. MiTM attacks are the most common 'real-world' counterexample that come up in discussions of cascade encryption (really, cascade encipherment). This attack was first discovered by Diffie and Hellman, and is a member of a class we call time-space tradeoff attacks. It's useful in constructions that use a deterministic algorithm like a block cipher. For example:

DOUBLE_DES(KA, KB, M) = DES_ENCRYPT(KA, DES_ENCRYPT(KB, M))

On the face of it, you'd assume that this construction would be substantially stronger than a single layer of DES. If a brute-force attack on DES requires 2^56 operations (DES has a 56-bit key), you'd hope that attacking a construction with two DES keys would require on the order of 2^112 operations. But actually this hope is a false one -- if the attacker has lots of storage.
The attack works like this. First, obtain the encryption C of some known plaintext M under the two unknown secret keys KA and KB. Next, construct a huge table comprising the encipherment of M under every possible DES key. In our DES example there are 2^56 keys, this would take a corresponding amount of effort, and the resulting table will be astonishingly huge. But leave that aside for the moment.

Finally, try decrypting C with every possible DES key. For each result, check to see if it's in the table you just made. If you find a match, you've now got two keys: KA' and KB' that satisfy the encryption equation above.*****

If you ignore storage costs (ridiculously impractical, but which may also be traded for time), this attack will run you (2^56)*2 = 2^57 cipher operations. That's much less than the 2^112 we were hoping for. If you're willing to treat it as a chosen plaintext attack you can even re-use the table for many separate attacks.
Plaintext distribution issues. Maurer showed one more interesting result, which is that in a cascade of ciphers, the entire construction is guaranteed to be as secure as the first cipher, but not necessarily any stronger. This is because the first cipher may introduce certain patterns into its output that can assist the attacker in breaking the second layer of encipherment. Maurer even provides a (very contrived) counterexample in which this happens.

I presume that this is the source of the following folklore construction, which is referenced in Applied Cryptography and other sources around the Internet:

UberSuperEncrypt(KA, KB, M) = EncryptA(KA, R⊕M) || EncryptB(KB, R))

Where || indicates concatenation, and R is a random string of the same length of the message. Since in this case both R and R⊕M both have a random distribution, this tends to eliminate the issue that Maurer notes. At the cost of doubling the ciphertext size!

Now the good news is that multiple encipherment (done properly) can probably make things more secure. This is precisely what constructions like DESX and 3DES try to achieve (using a single cipher). If you make certain strong assumptions about the strength of the cipher, it is possible to show that these constructions are harder to attack than the underlying cipher itself (see this analysis of DESX and this one of 3DES).

I warn you that these analyses use an unrealistic model for the security of the cipher, and they don't treat multiple distinct ciphers., Still, they're a useful guide -- assuming that your attacker does not have any special attack against (at least one) of the underlying schemes. Your mileage may vary, and I would generally advise against assembling this sort of thing yourself unless you really know what you're doing.

In summary

I'm afraid this post will end with a whimper rather than a bang. It's entirely possible to combine encryption schemes in secure ways (many of which are not cascade constructions), but the amount of extra security you'll get is subject to some debate.

In fact, this entire idea has been studied for a quite a while under the heading of (robust) combiners. These deal with combining cryptosystems (encryption, as well as hashing, signing, protocols, etc.) in a secure way, such that the combination remains secure even if some of the underlying schemes are broken.

If you're interested, that's the place to start. But in general my advice is that this is not something that most people should spend a lot of time doing, outside of (perhaps) the government and the academic world. If you want to do this, you should familiarize yourself with some of the academic papers already mentioned. Otherwise, think hard about why you're doing it, and what it's going to buy you.

Notes:

* And yes, I know about MD5 and the recent biclique attacks one AES. That still doesn't change my opinion.

** Note that this is mostly something the government likes to think about, namely: how to use consumer off-the-shelf products together so as to achieve the same security as trusted, government-certified hardware. I'm dubious about this strategy based on my suspicion that all consumer products will soon be manufactured by Foxconn. Nonetheless I wish them luck.

*** This key independence is a big deal. If the keys are related (worst case: KA equals KB) then all guarantees are off. For example, consider a stream cipher like CTR mode, where encryption and decryption are the same algorithm. If you use the same algorithm and key, you'd completely cancel out the encryption, i.e.: CTR_ENC(K, IV, CTR_ENC(K, IV, M) = M.

**** Classical substitution ciphers (including the Vigenere cipher and Vernam One-Time Pad) have this structure.

***** The resulting KA' and KB' aren't necessarily the right keys, however, due to false positives: keys that (for a single message M) satisfy DES(KA', DES(KB', M)) = DES(KA, DES(KB, M)). You can quickly eliminate the bad keys by obtaining the encryption of a second message M' and testing it against each of your candidate matches. The chance that a given false positive will work on two messages is usually quite low.

Bad movie cryptography, 'Swordfish' edition

2012-01-30T14:56:00.000-08:00

Hackers are paler than the general public. Also, they use gel.

I was just working on an honest-to-god technical post when I thought: here's an idea, let's illustrate this point with a reference to the classic bad-security movie 'Swordfish'. What a terrible mistake.

In searching for a link I turned up what purports to be Skip Woods' original shooting script. And now I'm not going to get any work done until I get this off my chest: holy &#^$*&# crap the cryptography in that movie is way worse than I thought it was.

I know, I know, it's a ten year old movie and it's all been said before. So many times that it's not even shooting fish in a barrel anymore, it's more like shooting frozen fish in a barrel.

There isn't much crypto in the movie. But what there is, whew... If you consider a modified Pritchard scale where the X axis is 'refers to a technology that could actually exist' and the Y axis is 'doesn't make me want to stab myself', Skip Woods has veered substantially into negative territory.

I know most people will say something like 'Duh' or 'It's swordfish!' or 'What do you expect from a movie where a guy breaks a password while John Travolta holds a gun to his head and Halle Berry fiddles around in his lap.' And yes, I realize that this happens. But that stuff actually doesn't trouble me so much.

What does bother me is that the DoD system he breaks into uses 128-bit RSA encryption. Does anyone really think that the NSA would validate that? And then there's this exchange (emphasis mine):

                            GABRIEL
                  Here's the deal. I need a worm,
                  Stanley. A hydra, actually. A
                  multi-headed worm to break an
                  encryption and then sniff out
                  latent digital footprints
                  throughout an encrypted network.

                                STANLEY
                  What kind of cypher?

                                GABRIEL
                  Vernam encryption.

                                STANLEY
                  A Vernam's impossible. Its key
                  code is destroyed upon
                  implementation. Not to mention
                  being a true 128 bit encryption.

                                GABRIEL
                  Actually, we're talking 512 bit.

Ok, I don't know about the stuff at the beginning -- but the rest is serious. We're not going after a mere Vernam One-Time Pad, which would just be impossible to break. Instead we're going after the Big Kahuna, the true 128-bit unbreakable Vernam One-Time Pad. No, wait, that's too easy. To do this right, we're gonna have to break the full 512-bit unbreakable Vernam One-Time Pad, which is at least 2^384 times as unbreakable as the regular unbreakable kind. Get Halle back in here!

What kills me is that if you squint a little some of this technical jargon kind of makes sense. This can only mean one thing: Skip Woods brought in a technical advisor. But having done so, he obviously took the advice he was given and let it fly prettily out the windows of his Mercedes on the way home. Then he wrote what he wanted to write. Who needs an unbreakable cipher when we can have an unbreakable cipher with a frickin' 128 512 bit key!

I thought this post would be cathartic, but the truth is I just feel dirty now. Where will this end? Will I find myself criticizing Mercury Rising and Star Trek? The thing is, I like movies, even bad ones. I don't ask for realism. I just have limits.

And Swordfish is a bridge too far. If you're a Hollywood type and you need someone to vet your scripts, I'll do it. Cheap. I won't leave you all hung up in painful details -- if your plot requirements have the main character breaking cryptography in his head, I'll find a way to make it work. But it won't be a One-Time Pad and it sure as hell won't be 128-bit RSA. It will be *ahem* realistic.

Tor and the Great Firewall of China

2012-01-26T08:01:00.000-08:00

(credit)

Here's a fascinating post by Tim Wilde over at the Tor Project blog, discussing China's growing sophistication in blocking Tor connections:

In October 2011, ticket #4185 was filed in the Tor bug tracker by a user in China who found that their connections to US-based Tor bridge relays were being regularly cut off after a very short period of time. At the time we performed some basic experimentation and discovered that Chinese IPs (presumably at the behest of the Great Firewall of China, or GFW) would reach out to the US-based bridge and connect to it shortly after the Tor user in China connected, and, if successful, shortly thereafter the connection would be blocked by the GFW.

... we discovered two types of probing. First, "garbage binary" probes, containing nothing more than arbitrary (but sometimes repeated in later probes) binary data, were experienced by the non-China side of any connection that originated from China to TCP port 443 (HTTPS) in which an SSL negotiation was performed. ... The purpose of these probes is unknown ...

The second type of probe, on the other hand, is aimed quite directly at Tor. When a Tor client within China connected to a US-based bridge relay, we consistently found that at the next round 15 minute interval (HH:00, HH:15, HH:30, HH:45), the bridge relay would receive a probe from hosts within China that not only established a TCP connection, but performed an SSL negotiation, an SSL renegotiation, and then spoke the Tor protocol sufficiently to build a one-hop circuit and send a BEGIN_DIR cell. No matter what TCP port the bridge was listening on, once a Tor client from China connected, within 3 minutes of the next 15 minute interval we saw a series of probes including at least one connection speaking the Tor protocol.

Obviously this is disturbing. And unlike previous, passive efforts to block Tor, these active attacks are tough to defend against. After all, Tor was designed to be a public service. If the general public can download a Tor client and connect to a bridge, so can the Chinese government. This means that protocol-level workarounds (obfuscators, for example) will only work until China cares enough to stop them.

The situation isn't hopeless: proposed workarounds include password protecting Tor bridges, which might solve the problem to an extent -- though it seems to me that this is just kicking the problem down the road a bit. As with the bridge security model, it embeds the assumption that Chinese users can find bridges/passwords, but their government can't. More to the point, any password protocol is going to have to work hard to look 'innocent' (i.e., not Tor-like) to someone who doesn't know the password. There are a lot of ways this could go wrong.

On the research side there are ideas like Telex which would eliminate the need for bridges by embedding anti-censorship into the network. Chinese Tor clients would make TLS connections to arbitrary US websites; the connections would be monitored by special Telex routers along the way; any TLS connection with a special steganographic marking would get transparently re-routed to the nearest Tor node. Unfortunately, while the crypto in Telex is great, actually deploying it would be a nightmare -- and would almost certainly require government cooperation. Even if Western governments were game, the Chinese government could respond by banning overseas TLS connections altogether.

One last note: I love a good mystery, so does anyone care to speculate about those "garbage probes"? What are they -- a test? Automated fuzzing? Most likely they're an attempt to provoke a response from some other TLS server that the Chinese government cares about, but if it's not Tor then what is it?

Tim's full investigation can be found here.

Update 1/26: Emily Stark points me to the Flash Proxies project out of Stanford. This would put Tor proxies in individual client machines, thus massively increasing the number of bridges available and eliminating the outgoing client->bridge connection. They even have an implementation, though I warn you: running untrusted traffic through your Flash plugin is not for the faint of heart!

In memoriam: Tim Hartnell

2012-01-22T11:10:00.000-08:00

Last week the students and I went looking for our long-lost GnuRadio USRP in a dusty hardware security lab down the hall. This particular USRP hasn't been seen in about five years (I suspect it may have been deported with the lab's previous occupant) so the whole thing was kind of a long shot.

Sometimes best part of a treasure hunt is what you find along the way. The students didn't find the USRP, but they did uncover a fog machine and laser that someone had tucked under a workbench. This kept them happy 'til we got a whiff of the "fog" it was making. I scored something even better: a mint copy of Tim Hartnell's 1985 masterpiece, the Giant Book of Computer Games.

If you're just a few years younger than me, you might think Games is a book about games. But of course, it literally is games: dozens of all-caps BASIC listings, printed in a font that was probably old when Wargames was new. Each game sits there on the page, pregnant with potential, waiting for a bored 9-year old to tap it into his C64 or Apple ][ and hit "RUN". It could be long wait.

Flipping through Games brings back memories. The Chess AI was a bastard, routinely cheating even if you implemented it properly. And you never implemented anything properly, at least not on the first pass. This was part of the fun. Between typos and the fact that Hartnell apparently coded to his own BASIC standard, the first play usually went like this:

WELCOME TO SNARK HUNT
ENTER 1 FOR SNARK, 2 FOR HUNTER
> 2
YOU CHOSE SNARK
?SYNTAX ERROR AT LINE 3980
READY

You learned debugging fast. When that didn't work, your last, desperate move was simply to delete the offending lines -- 'til the program either (a) worked, or (b) got so crazy that you deleted it and loaded Bruce Lee off a cassette. Sometimes you hit the sweet spot between the two: my "Chess" AI would grab control of my pieces Agent Smith-style and send them hurtling towards my undefended King. I never saw this as a bug, though; I just thought it had style.

When I started writing this post I intended to make a broader point about how my experience with Games mirrors the way that modern implementers feel when faced with a mysterious, unjustified cryptographic standard. I think there is a point to be made here, and I'll make it. Another day.

But when I googled to see what Hartnell is up to, I was saddened to learn that he died all the way back in 1991, only a few years after Games was published. He was only a few years older than I am today. So on reflection, I think I'll just let this post stand as it is, and I'll go spend some time with my kid.

Tim, wherever you are, please accept this belated tribute. Your book meant a lot to me.

EAX', Knight Rider, and an admission of defeat

2012-01-15T19:20:00.000-08:00

A few weeks back I found myself on the wrong side of Daniel Bernstein over something I'd tweeted the week before. This was pretty surprising, since my original tweet hadn't seemed all that controversial.

What I'd said was that cryptographic standards aren't always perfect, but non-standard crypto is almost always worse. Daniel politely pointed out that I was nuts -- plenty of bad stuff appears in standards, and conversely, plenty of good stuff isn't standardized. (As you can see, the conversation got a little weirder after that.)

Today I'm here to say that I've found religion. Not only do I see where Daniel's coming from, I'm here to surrender, throw down my hat and concede defeat. Daniel: you win. I still think standards are preferable in theory, but only if they're promulgated by reasonable standards bodies. And we seem to have a shortage of those.

My new convictions are apropos of an innocuous-looking ePrint just posted by Kazuhiko Minematsu, Hiraku Morita and Tetsu Iwata. These researchers have found serious flaws in an authenticated block cipher mode of operation called EAX' (henceforth: EAXprime). EAXprime was recently adopted as the encryption mode for ANSI's Smart Grid standard, and (until today) was practically a shoo-in to become a standalone NIST-certified mode of operation.

Ok, so standards get broken. Why I am I making such a big deal about this one? The simple reason is that EAXprime isn't just another standard. It's a slightly-modified version of EAX mode, which was proposed by Bellare, Rogaway and Wagner. And the important thing to know about EAX (non-prime) is that it comes with a formal proof of security.

It's hard to explain how wonderful this is. The existence of such a proof means that (within limits) a vulnerability in EAX mode would indicate a problem with the underlying cipher (e.g., AES) itself. Since we're pretty confident in the security of our standard block ciphers, we can extend that confidence to EAX. And the best part: this wonderful guarantee costs us almost nothing -- EAX is a very efficient mode of operation.

But not efficient enough for ANSI, which decided to standardize on a variant called EAXprime. EAXprime is faster: it uses 3-5 fewer block cipher calls to encrypt each message, and (in the case of AES) about 40 bytes less RAM to store scheduled keys. (This is presumably important when your target is a tiny little embedded chip in a smart meter.)

Unfortunately, there's a cost to that extra speed: EAXprime is no longer covered by the original EAX security proof. Which brings us towards the moral of the story, and to the Minematsu, Morita and Iwata paper.

Did you ever see that old episode of Knight Rider where the bad guys figure out how to neutralize KITT's bulletproof coating? Reading this paper is kind of like watching the middle part of that episode. Everything pretty much looks the same but holy crap WTF the bullets aren't bouncing off anymore.

The MMI attacks allow an adversary to create ciphertexts (aka forgeries) that seem valid even though they weren't created by the actual encryptor. They're very powerful in that sense, but they're limited in others (they only work against very short messages). Still, at the end of the day, they're attacks. Attacks that couldn't possibly exist if the standards designers had placed a high value on EAX's security proof, and had tried to maintain that security in their optimized standard.

And this is why I'm admitting defeat on this whole standards thing. How can I advocate for crypto standards when standards bodies will casually throw away something as wonderful as a security proof? At least when KITT lost his bulletproof coating it was because of something the bad guys did to him. Can you imagine the good guys doing that to him on purpose?

Useful cryptography resources

2012-01-12T08:13:00.000-08:00

Over the past few weeks I've been scouring the Internet for a good list of crypto and security resources to link to from this blog. The ideal list would include technical blogs, of course, but also textbooks, courses and other helpful websites.

There are a few good resource lists out on the web. Some are even pretty good, but none of them meet all of my criteria. Per XKCD, I decided that the solution here is to obviate them all and create an even better list of my own. You can see my first draft here (it's also linked from the sidebar at right, under 'Useful crypto resources'). This is very much a work in progress, and I hope that you'll all help me to flesh it out.

Attack of the week: Datagram TLS

2012-01-09T17:11:00.000-08:00

Nadhem Alfardan and Kenny Paterson have a paper set to appear in NDSS 2012 entitled 'Plaintext-Recovery Attacks Against Datagram TLS'.* This is obviously music to my ears. Plaintext recovery! Datagram TLS! Padding oracles. Oh my.

There's just one problem: ~~the paper doesn't seem to be online yet~~ (Update 1/10: It is now. See my update further below.) Infoworld has a few vague details, and it looks like the vulnerability fixes are coming fast and furious. So let's put on our thinking caps and try to puzzle this one out.

What is Datagram TLS?

If you're reading this blog, I assume you know TLS is the go-to protocol for encrypting data over the Internet. Most people associate TLS with reliable transport mechanisms such as TCP. But TCP isn't the only game in town.

Audio/video streaming, gaming, and VoIP apps often use unreliable datagram transports like UDP. These applications don't care if packets arrive out of order, or if they don't arrive at all. The biggest priority is quickly handling the packets that do arrive.

Since these applications need security too, TLS tries to handle them via an extension called Datagram TLS (DTLS). DTLS addresses the two big limitations that make TLS hard to use on an unreliable datagram transport:

TLS handshake messages need to arrive whole and in the right order. This is easy when you're using TCP, but doesn't work so well with unreliable datagram transport. Moreover, these messages are bigger than the typical 1500 byte Ethernet frame, which means fragmentation (at best), and packet loss (at worst).
Ordinarily TLS decryption assumes that you've received all the previous data. But datagrams arrive when they want to -- that means you need the ability to decrypt a packet even if you haven't received its predecessor.

There are various ways to deal with these problems; DTLS mounts a frontal assault. The handshake is made reliable by implementing a custom ack/re-transmit framework. A protocol-level fragmentation mechanism is added to break large handshake messages up over multiple datagrams. And most importantly: the approach to encrypting records is slightly modified.

So what's the problem?

To avoid radical changes, DTLS inherits most of the features of TLS. That includes its wonky (and obsolete) MAC-then-Encrypt approach to protecting data records. Encryption involves three steps:

Append a MAC to the plaintext to prevent tampering.
Pad the resulting message to a multiple of the cipher block size (16 bytes for AES). This is done by appending X bytes of padding, where each byte must contain the value X.
Encrypt the whole mess using CBC mode.

Cryptographers have long known that this kind of encryption can admit padding oracle attacks. This happens when a decryptor does something obvious (throw an error, for example) when it encounters invalid padding, i.e., padding that doesn't meet the specification above.

CBC Mode encryption, courtesy Wikipedia.

This wouldn't matter very much, except that CBC mode is malleable. This means an attacker can flip bits in an intercepted ciphertext, which will cause the same bits to be flipped when the ciphertext is ultimately decrypted. Padding oracle attacks work by carefully tweaking a ciphertext in specific ways before sending it to an honest decryptor. If the the decryptor returns a padding error, then the adversary knows something about the underlying plaintext. Given enough time the attacker can use these errors to completely decrypt the message.

I could spend a lot of time describing padding oracle attacks, but it's mostly beside the point.** Standard TLS implementations know about this attack and deal with it in a pretty effective way. Whenever the decryptor encounters bad padding, it just pretends that it hasn't. Instead, it goes ahead with the rest of the decryption procedure (i.e., checking the MAC) even if it knows that the message is already borked.

This is extra work, but it's extra work with a purpose. If a decryptor doesn't perform the extra steps, then messages with bad padding will get rejected considerably faster than other messages. A clever attacker can detect this condition by carefully timing the responses. Performing the unnecessary steps (mostly) neutralizes that threat.

Ok, so you say these attacks are already mitigated. Why are we still talking about this?

Before I go on, I offer one caveat: what I know about this attack comes from speculation, code diffs and some funny shapes I saw in the clouds this afternoon. I think what I'm saying is legit, but I won't swear to it until I read Alfardan and Paterson's paper.

But taking my best guess, there are two problems here. One is related to the DTLS spec, and the second is just an implementation problem. Either one alone probably wouldn't be an issue; the two together spell big trouble.

The first issue is in the way that the DTLS spec deals with invalid records. Since standard TLS works over a reliable connection, the application should never receive invalid or out-of-order data except when packets are being deliberately tampered with. So when standard TLS encounters a bad record MAC (or padding) it takes things very seriously -- in fact, it's required to drop the connection.

This necessitates a new handshake, a new key, and generally makes it hard for attackers to run an honest padding oracle attack, since these attacks typically require hundreds or thousands of decryption attempts on a single key.***

DTLS, on the other hand, runs over an unreliable datagram transport, which may not correct for accidental packet errors. Dropping the connection for every corrupted packet just isn't an option. Thus, the standard is relaxed. An invalid MAC (or padding) will cause a single record to be thrown away, but the connection itself goes on.

This still wouldn't matter much if it wasn't for the second problem, which is specific to the implementation of DTLS in libraries like OpenSSL and GnuTLS.

You see, padding oracle vulnerabilities in standard TLS are understood and mitigated. In OpenSSL, for example, the main decryption code has been carefully vetted. It does not return specific padding errors, and to avoid timing attacks it performs the same (unnecessary) operations whether or not the padding checks out.

In a perfect world DTLS decryption would do all the same things. But DTLS encryption is subtly different from standard TLS encryption, which means it's implemented in separate code. Code that isn't used frequently, and doesn't receive the same level of scrutiny as the main TLS code. Thus -- two nearly identical implementations, subject to the same attacks, with one secure and one not. (Update 1/11: There's a decent explanation for this, see my update below.)

And if you're the kind of person who needs this all tied up with a bow, I would point you to this small chunk of the diff just released for the latest OpenSSL fix. It comes from the DTLS-specific file d1_pkt.c:

+ /* To minimize information leaked via timing, we will always

+ * perform all computations before discarding the message.

+ */

+ decryption_failed_or_bad_record_mac = 1;

I guess that confirms the OpenSSL vulnerability. Presumably with these fixes in place, the MAC-then-Encrypt usage in DTLS will now go back to being, well, just theoretically insecure. But not actively so.

Update 1/11/2012: Kenny Paterson has kindly sent me a link to the paper, which wasn't available when I wrote the original post. And it turns out that while the vulnerability is along the lines above, the attack is much more interesting.

An important aspect that I'd missed is that DTLS does not return error messages when it encounters invalid padding -- it just silently drops the packet. This helps to explain the lack of countermeasures in the DTLS code, since the lack of responses would seem to be a padding oracle attack killer.

Alfardan and Paterson show that this isn't the case. They're able to get the same information by timing the arrival of 'heartbeat' messages (or any predictable responses sent by an upper-level protocol). Since DTLS decryption gums up the works, it can slightly delay the arrival of these packets. By measuring this 'gumming' they can determine whether padding errors have ocurred. Even better, they can amplify this gumming by sending 'trains' of valid or invalid packets.

All in all, a very clever attack. So clever, in fact, that it makes me despair that we'll ever have truly secure systems. I guess I'll have to be satisfied with one less insecure one.

Notes:

* N.J.A. Alfardan and K.G. Paterson, Plaintext-Recovery Attacks Against Datagram TLS, To appear in NDSS 2012.

** See here for one explanation. See also a post from this blog describing a padding oracle attack on XML encryption.

*** There is one very challenging padding oracle attack on standard TLS (also mitigated by current implementations). This deals with the problem of session drops/renegotiation by attacking data that remains constant across sessions -- things like passwords or cookies.

A very casual introduction to Fully Homomorphic Encryption

2012-01-02T11:16:00.000-08:00

Craig Gentry on board the mothership. (credit)

A couple of weeks ago I polled readers for the subjects that they were interested in. You gave me some excellent responses, and I promise they're all in the hopper.

By far the most popular request was for some background on the recent results in computing on encrypted data, or 'Fully-Homomorphic Encryption'. Even though the current techniques are still in the research phase -- way outside the domain of the 'practical' crypto I usually talk about -- this topic is so neat that it deserves a few words.

Before I get started, I want to make a few important stipulations. First, I'm hardly the world's leading expert on the subject. Moreover, plenty of real experts have already published highly accessible introductory pieces. If you're interested, you should check out Craig Gentry's fantastic intro paper, or even his (surprisingly readable) PhD thesis. Alternatively, you can go directly to some of the recent papers on FHE.

My last warning is that this subject is kind of involved. I'm going to do my best to keep this explanation relatively non-technical (see the papers above if you want the gory details), but it could still get fairly long.

In this first post I'm going to cover some of the background behind FHE, and explain why it's such a neat problem.

Why encryption is not like a safe

(credit)

People love to use analogies to talk about encryption. Sometimes these are helpful, sometimes they're just limiting. Consider this one:

Encrypting a document is like placing it inside of a locked safe.

The locked safe is a great teaching example because cryptography and physical safes (usually) serve the same purpose: they ensure the confidentiality of sensitive data. In practice, they also share many of the same drawbacks.

If you've ever worked in an environment where safe-storage is required (e.g., a bank or intelligence agency) you probably know what I'm talking about. Once you lock a document into a safe, your document is locked inside of a damn safe.

Consequently, people tend to remove useful documents from safe storage at the first chance they get. This exposes them to all the usual threats, and explains why so few cases of document theft involve safecracking. Typically the same principle holds for encryption. People decrypt their data so they can use it.

But analogies are never perfect. Encrypting a document isn't the same as putting it into a physical lockbox. And this is a good thing! Because in fact, there is a kind of encryption that allows us to bypass some of these limitations. We refer to this as homomorphic encryption, and its defining characteristic is this: you can perform useful operations on encrypted values without decrypting them first.

This may seem like an exotic property. Trust me, it's not. In fact, cryptographers have put a lot of effort into removing the homomorphic properties from common public-key schemes like Elgamal and RSA. Without those protections, both schemes are homomorphic with respect to (modular) multiplication. This means you can multiply together any two Elgamal ciphertexts, and upon decryption you'll find that the (single) resulting ciphertext now embeds the product of the two original plaintexts. Neat!

Homomorphic encryption has some immediate practical applications. Consider the Paillier scheme that's used in several electronic voting protocols. Paillier is homomorphic with respect to addition. Now imagine: each voter encrypts their their ballot as a number (0 or 1) and publishes it to the world. Anyone can now tally up the results into a final ciphertext, which makes it hard for a corrupt election judge to throw away legitimate votes. Decrypting the final ciphertext reveals only the total.*

A few bits of history

Homomorphic encryption is hardly a new discovery, and cryptographers have long been aware of its promise. Way back in 1978 (about five seconds after the publication of RSA), Rivest, Adleman and Dertouzos proposed homomorphic encryption schemes that supported interesting functions on encrypted data. Regrettably, those first attempts kind of sucked.** Thus, the agenda for researchers was twofold: (1) come up with secure encryption schemes that could handle useful homomorphisms, and (2) figure out how to do interesting things with them.

To be interesting, a homomorphic encryption scheme should at very least permit the evaluation of useful mathematical functions, e.g., polynomials. But no computer scientist in history has ever been satisfied with mere polynomials. The holy grail was something much neater: a scheme that could handle arbitrary computations -- embodied as real computer programs! -- on securely encrypted inputs.

This idea -- sometimes called 'cryptocomputing', or 'computing on encrypted data' -- has a way of capturing the imagination. There's something fascinating about a computer that works on data it can't see. More practically, a technology like this would eliminate a very real weakness in many security systems -- the need to decrypt before processing data. It could even spawn a whole business based on outsourcing your computations to outside parties. (Something you obviously wouldn't do without strong cryptographic protections.)

Anyway, it was a beautiful dream. There was just one problem: it didn't work.

To explain why, let's go back to some of the encryption schemes I mentioned above. Throughout the '80s and '90s researchers came up with these, and many more interesting schemes. Quite a few supported some kind of homomorphism, usually multiplication or addition. However, none seemed capable of handling even both operations simultaneously -- at least not without serious limitations.

For researchers this was frustrating. Coming up with such a 'doubly homomorphic' scheme was an obvious first step towards the higher purpose. Even better, they quickly realized, this 'first step' was also the last step they'd need to achieve arbitrary computation.

How's that? Well, imagine that you have a doubly homomorphic encryption scheme that encrypts bits, meaning that every plaintext is either 0 or 1. Given ciphertexts encrypting bits A and B, we could use this scheme to compute the simple function 1+A*B. Keeping in mind that all arithmetic is binary (i.e., modulo 2), such a function would produce the following truth table:

A B : 1+A*B

0 0 1

0 1 1

1 0 1

1 1 0

Why the excitement? Well, this table describes a NAND gate. And any computer engineer can tell you that NAND is a big deal: once you've got it, you can derive all of the other useful boolean logic gates: AND, OR, NOT, XOR and XNOR.*** And that means you can implement circuits.

To a theoretical computer scientist this is a Big Deal. Given an encryption scheme like this, we could encrypt our input one bit at a time, then send the encrypted values to a third party for processing. This party would run an arbitrary program just by rendering it into a huge circuit -- a series of connected boolean logic gates -- and evaluating the result one gate at a time. At the end of the process we'd get back a bunch of ciphertexts containing the (bit) results.

In theory, the existence of an appropriate encryption scheme would give us everything we need to, for example, play Halo on encrypted inputs. This would obviously be a poor gaming experience. But it would be possible. If only we had such an encryption scheme.

A brief note

At this point I'd like to take a quick break to address the more practical kind of reader, who (I suspect) is recoiling in horror. I know what you're thinking: I came here for computing, and this is what you're giving me? Break the input into single bits and process them one gate at a time?

Well, yes. That's exactly how it's going to work -- at least, if we want general computation. And I stipulate that in many ways it's going to suck. Consider, for example, a loop like this one:

while (encrypted_value < 100) { perform_some_operation_on(&encrypted_value); }

Just try converting that into a circuit. I mean, it's not impossible to unroll loops (if you know the maximum number of iterations), but the resulting circuit is not likely to be practical. Moreover, this isn't purely an issue with the use of circuits, but rather with the use of encrypted data. No matter what computational model you employ, you're always going to have difficulty with things like control flow changes that depend on input data that the executing party can't see.

This makes it tough to implement the efficient programs that we're accustomed to running on typical random access machines. Simply writing a bit to encrypted 'RAM' might require you to recalculate every bit in memory, at least, if the write location is dependent on the input data.

And no, I'm not going to reassure you that it gets better from here. Actually it's going to get a lot worse once cryptography comes into the picture. That's because each of these 'bits' is actually going to become a ciphertext -- potentially hundreds or thousands of bits in length. Not to mention that evaluating those logic gates is going to require some pretty serious computing.

I'm pointing this out not to dismiss the research -- which we'll get to, and is pretty amazing -- but rather, to point out that it is research. We aren't going to be outsourcing general programs with this anytime soon -- and in fact, we may never do so. What we might do is find ways to implement specialized subroutines with very high sensitivity requirements: e.g., stock trading models, proprietary bioinformatics processes, etc. By combining these with other less-general techniques, we could accomplish something pretty useful.

In Summary

I've written just about all I can fit in a reasonable blog post, and I realize that I've barely covered any of the actual research.

What I did accomplish was to lay out some of the background behind the recent developments in fully-homomorphic encryption. In the next post we'll talk about the search for an appropriate encryption scheme, some of the failures, and Gentry's eventual success.

Notes:

* Obviously there's more to this. See, for example, this paper for some of the complexity.

** This might sound insulting, but it's not. As I've said before, 'suck' is a purely technical term for schemes that aren't semantically secure, i.e., indistinguishable under chosen plaintext attack.

*** Two notes here: First, you can obviously derive these gates more directly. For example, AND is (A*B). Second, while I've used the example of a scheme that encrypts only bits (meaning that addition and multiplication are always mod 2), the encryption scheme doesn't have to be limited this way. For example, consider a scheme that encrypts arbitrary integers (say, a finite ring). As long as you know that the inputs (A, B) are both in {0, 1}, you can implement the NAND gate as 1-(A*B). This is a more common description and you'll see it in most papers on the subject.

OpenSSL and NSS are FIPS 140 certified. Is the Internet safe now?

2012-01-01T22:10:00.000-08:00

People like standards. The more important something is, the greater the likelihood that someone, somewhere has drawn up a standard for how it should be done. Although this can get out of hand (viz: the EU standard for cucumbers), I do think that standards can serve a useful purpose. This is particularly true when you're talking about something as complicated (and easy to screw up) as encrypting data on the Internet.

Given all this, you'd expect that I'd be excited, nay thrilled, that two of the major crypto libraries in use today -- OpenSSL and Mozilla's NSS -- offer a FIPS-approved mode. Our children can sleep safely at night! And yet, having spent part of the weekend poring over nightmarish NSS code, I feel obliged to offer the following opinion: FIPS compliance, while certainly not a bad thing, doesn't really have anything to do with the security of a cryptographic library. Certainly not a library like OpenSSL or NSS.

For those who have no clue what FIPS is, let me start from the beginning.

If there's one organization that really likes standards, it's the US Federal government. For IT alone the US has an entire fleet of standards known collectively as FIPS -- the Federal Information Processing Standards. These deal with lots of boring stuff like the standard codes to be used when referencing US states. More interestingly, FIPS also includes the standards for designing cryptographic modules. These are laid out in a series of documents headlined by FIPS 140-2 (obligatory warning: do not drive or operate heavy machinery while reading FIPS publications).

FIPS 140-2 outlines a set of requirements that must be adhered to by any US-government certified cryptographic module. This applies to products purchased by Federal agencies, and implicitly to outside systems that exchange sensitive-but-unclassified data with Federal computers (think: banks). To give these standards some teeth, the US NIST and Canada's CSEC jointly run something called the Cryptographic Module Validation Program (CMVP). Only serious cryptographic modules survive CMVP, at least in theory. So NSS and OpenSSL's validation is a Big Deal.

Like I said, that's the theory.

To understand why I'm not so excited about FIPS, you have to understand the what, who and why. Specifically, what the heck a 'cryptographic module' is, who does the validation, and why we're validating these modules in the first place.

What is a cryptographic module?

A 1970s-era hardware voice encryption
module.

To understand the FIPS viewpoint on this, you need to hark back to the early 90s when the FIPS 140-1 standard was first being hashed out. You also need to pretend that you worked for the US DoD in the previous decades. At this point you should have a very clear picture of a cryptographic module in your head. It looks something like the picture on the right.

Ok, so that's a Dutch voice encryption module, and it dates from 1973. The point I'm trying to make is that a cryptographic module is a piece of hardware. It's contained within some kind of metal enclosure. Plaintext data comes in on a physical port, encrypted data comes out of another. Keys are entered by punching them into the front, or alternatively, by inserting some kind of key storage token.

In fact, to achieve "FIPS 140 Level 2" (or higher) certification, you still need hardware. But what does FIPS 140-2 tell us about evaluating pure software cryptographic modules? How do we map these hardware rules onto something like OpenSSL?

Mostly by doing a lot of creative re-interpretation. Module boundaries have to become machine boundaries. Logical boundaries have to be defined around the software itself. The flow of data across these boundaries has to be relentlessly mapped into a hardware metaphor, even if using that metaphor doesn't provide any tangible security benefit.

(To give a concrete example: FIPS key management at higher levels requires entering only encrypted keys. Neat. But if the module is a piece of software, what's the point? You might find yourself encrypting keys on one machine, so that they can be decrypted in another process on the same machine. This is silly. But if that's how NIST will interpret the standard, then that's what we'll do.)

In fairness, a new iteration of the standard -- FIPS 140-3 -- is supposed to make validation of software modules a whole lot clearer. Unfortunately the finalization date is currently listed as TBD. Moreover, when it comes to government standards, sometimes you're better off with the devil you know.

Who does the validation?

Here's another thing about CMVP to keep in mind. It's not a free service offered by the US government to those modules it finds really important.

Yes, final approval of modules is performed by a team at NIST. However, this is only the tip of the iceberg. In order to reach NIST, you need to first retain a private testing laboratory, who will actually do most of the validation. NIST mostly evaluates the results of this process. You have a choice of labs, and yes, they compete on price. I've had the good fortune of working with excellent testing labs, but that doesn't mean that my results are typical.

Why (and what) are we validating?

Finally, we get to the most important question: why are you evaluating the module. Actually, this is more of a what question -- what does the evaluation look for, what kind of bugs is it going to turn up, and how much assurance do you really have at the end of the process.

And this is the depressing part. FIPS is not about detailed software evaluation. It's not code review, at least not the kind of rigorous code review that will find the inevitable (and devastating) software vulnerabilities that your development team missed. It's certainly not going to detect subtle cryptographic attacks that stem from bad use of padding or the presence of useful timing channels. And it's definitely not going to detect clever backdoors.

What it is going to tell you is whether you have a solid checklist describing how the system should be used. It'll tell whether you're using some sort of authentication to launch the module. It'll ensure that you're using only FIPS-approved algorithms, and only in a way that's specified by NIST. Finally, validation will tell you whether you're implementing those algorithms correctly -- or more accurately, whether your outputs match a set of test vectors provided by your testing lab, which is mostly, but not entirely the same thing.

These are all good things, and they probably serve to lop off the low-hanging fruit -- the genuinely dumb bugs that lead to obvious compromise. (As a side benefit, FIPS prohibits the use of RC4.) Moreover, the process of getting through CMVP is so time-consuming that it probably increases the likelihood that your engineers will find bugs in the code along the way. This is a good thing, but it's hardly a first order effect.

So what does this have to do with NSS and OpenSSL?

Good question. What are the problems in these libraries, and how is FIPS supposed to solve them?

The big problem that I see with both NSS and OpenSSL is not that they use bad algorithms, or that they have bad security policies. Rather, it's that their code is uncommented and hard to read, which occasionally hides serious (but extremely subtle) vulnerabilities. Moreover, even when the implementation is faithful, they each support legacy standards that contain a lot of questionable nonsense (e.g., obsolete padding schemes) which needs to be hacked around. The above issues would be academic, except that to a surprising extent these two libraries are responsible for securing the Internet.

Even more problematic is that between OpenSSL and NSS we have two separate and competing libraries, in a world with enough interested brains and eyeballs to review at most one. Optimistically.

This is how NSS managed to stay vulnerable to the BEAST attack until this year, despite the fact that OpenSSL had 'empty fragment' mitigations in place since 2002. Similarly, it's how OpenSSL managed all of this. It's why OpenSSL code often looks like this, and why NSS is no better.

Unfortunately the problems that FIPS evaluation solves are mostly orthogonal to these.

Now, to be fair, nobody in either the OpenSSL project or Mozilla is claiming that FIPS compliance makes these libraries magically secure. I'm sure they not only know better, but they curse FIPS privately behind closed doors because it requires a whole lot of extra code in exchange for a dubious security benefit. Moreover, both libraries are developed by smart people and have done fairly well considering what they're up against.

Still, there's a huge need for a real security standard for cryptographic modules, one that takes into account all of the things we know can go wrong. At very least we could mandate a coding standard with requirements for commenting, indentation, sensible error handling, and variable names that aren't plain crazy. (Even if a single review doesn't find the bugs, mandating a coding standard could increase the probability that others do.)

The whole point of this post is to remind readers that FIPS 140-2 is not that standard. Encrypt with caution.

2011 Redux

2011-12-28T21:37:00.000-08:00

(credit)

I started this blog just a few months ago, and it's been something of a learning experience. Someday maybe I'll talk about that, but not in this post. What I'm here to talk about is regret -- regret that there are so many things I missed the opportunity to blog about in 2011.

Since I'm finally done traveling and the alternative is to actually be productive, I thought this might be a good opportunity to make up for some of that lost blogging ground. Hence this post: my attempt to sum up what's happened in practical cryptography in 2011.

Before anyone objects, I'm going to clarify the ground rules. This list is naturally incomplete, and moreover, I'm going to take 'practical' seriously. That rules out reduced-round attacks (on anything); improvements in Fully-Homomorphic Encryption (getting faster!); and any paper with 'composable' in the title. I will cover implementation and usability issues. But I don't really plan to take any of my own rules that seriously. If you think I missed something important -- and I will -- please feel free to follow up in comments.

Phishers don't mess with the
imaginary SecurID key storage facility.

SecurID not so secure after all. RSA's SecurID has become practically synonymous with two-factor authentication. And it's not a bad system. Back in 2010 if you'd asked me about the most likely avenue for a compromise, I would have guessed (a) theft of secrets from a local SecurID server, or (b) some kind of bug in the authentication software.

What I wouldn't have guessed was (c) compromise of RSA's master seed data. Obviously that wasn't going to happen -- given the sensitivity of this information, RSA naturally took good care of it. Remember the underground research facility in Resident Evil? My vision of the RSA master seed storage facility was kind of like that, only without the friendly computer or Milla Jovovich.

In retrospect this seems a bit naive, but really: SecurID was everywhere. Even military contractors used it. If local banks had learned to store their secrets in hardware security modules, then certainly RSA would take modest precautions with something as important as their master seed database.

What 2011 taught us is that just because you think something will be done a certain way, it won't necessarily be so. Perhaps 2012 will be different.
Still more attacks on AES. I promised to keep this to the practical, and the latest attacks against AES certainly aren't. The best of them still only shave a couple of bits off of the security of an AES key (although the new attacks don't depend on related keys).

Still, AES is such an important cipher that any reduction in its security margin is going to have some kind of practical impact. The question now is what lies down the road: (a) an improved AES beefed up with additional rounds, (b) a new standards competition, (c) apathy, or (d) something even weirder. Maybe 2012 will put us on a path to finding that answer.
D-Wave actually builds a quantum computer. With two caveats: it's not really a computer, and it may or may not be quantum.

In case you've never heard of D-Wave, they're a private company that purports to sell the first working adiabatic quantum computer, complete with "128 pair-wise coupled superconducting flux qubits". If you're not sure what to make of this, you're not the only one. Thanks to D-Wave's NDA-heavy business model, there's been some doubt in learned quarters as to whether the D-Wave device actually performs useful quantum computation at all.

But D-Wave has an active and respectable research department. Just this past May they published an article in Nature demonstrating apparent quantum tunneling amongst eight qubits. This is a far cry from the 128 qubits claimed in their commercial products, it doesn't demonstrate entanglement, and of course, it doesn't result in computation. Still it's not nothing. So does this mean practical implementations of Shor's algorithm are just around corner? Probably not.
TLS falls to the BEAST. This fall Thai Duong and Juliano Rizzo raised the pulse of the security industry by demonstrating the most exciting practical attack against SSL/TLS in years. This attack is dear to my heart because it's one of the first attacks I wrote about on this blog.

BEAST is based on a five year-old academic attack on a twelve year old standard. Now there's a bit more to the attack that Rizzo/Duong implemented, but still --- how in the world does such a thing stay in the wild so long? A colleague describes Rizzo/Duong's research strategy as 'working their way through the Eurocrypt archives, actually exploiting the theoretical vulnerabilities that academics couldn't be bothered to follow through on'. If this sounds dismissive, it wasn't -- he only wished that he'd done it first.

Lesson: there's a hell of a gap between academic crypto and 'the real world'. We're only safe as long as you believe in attackers who are sophisticated enough to spear-phish SecurID, but not bright enough to read a crypto paper. Time will tell if that belief is a good one.
Nothing much happens with hash functions. Well, that's a bit unfair. Things did happen, and there are some papers to show for it. The SHA3 finalists, announced late last year, continued to percolate through the system. (Go BLAKE!) Still, 2011 was a huge disappointment for those of us you who thought that it would be the year of SHA1 collisions. I guess there's always 2012.
Unsigned code running on iOS. Many cryptographers would exclude this from a list of 'crypto' happenings. Still, a theme of this blog is that your crypto doesn't matter if your implementation undermines it.

This is exactly what Charlie Miller demonstrated when he showed how to execute malicious application code on an iPhone. Even though iOS devices are only supposed to run signed code, it turns out that a few bad checks created a tiny section of memory in which these requirements were irrelevant. To thank him, Apple created a tiny section of their developer program in which Charlie Miller is irrelevant.
Certificate Authorities still a giant mess. Some will say I'm exaggerating -- there were only a few major hacks this year, notably Dutch CA DigiNotar, and a smaller CA called Gemnet. But don't forget, Microsoft also revoked Digicert Malaysia -- not because they were hacked, but for using 512-bit RSA keys to sign certificates (!!) And this is only a partial list of the problems we know about. All in all, it was not a good year to be a CA.
Secure police radios not all that secure. APCO Project 25 is a digital radio standard used by law enforcement. Naturally it supports encryption -- a valuable tool when you're discussing a confidential source or razzing those Occupy protestors. And the P25 encryption itself isn't half bad (it's unauthenticated AES). Rather, the problem with P25 is that simply getting encryption turned on is a daunting prospect -- to the point where it often doesn't happen.

To illustrate the problem, a team from UPenn spent two years snarfing up confidential traffic. The agents generating most of this traffic either thought it was encrypted, or would have encrypted it if only they could've figured out how to set the keys. Still more evidence that usability is every bit as important as crypto, implementation, or any other issue that we come across in our field.
XML Encryption nearly as awful as XML itself. This fall brought news of a clever attack on the unauthenticated W3C XML Encryption standard. The attack, by researchers Tibor Jager and Juraj Somorovsky, used various features of XML encoding to implement what I would call a 'padding oracle attack-plus-plus' -- which completely decrypts protected XML on Axis2 and JBoss systems.

The W3C response: "We are so sorry for promulgating this terrible standard and recommend that you never, ever listen to anything we say regarding security every again." No, of course I'm just kidding. Actually, they're adding AES-GCM as an option. Should take care of everything.
Quantum key distribution still a work in progress. Quantum Key Distribution (QKD), sometimes known as 'quantum crypto' is a promising technique for distributing keys over geographic distances without the need to rely on complicated stuff like hard mathematical problems. Instead, you just need to run direct fiber-optic cables to the person you want to communicate with (much easier). On the bright side, the security of QKD is supposedly based on fundamental quantum-physical properties.

In general, the caveat in any QKD design is that security only holds if the physical device works as expected. This year researchers from Singapore and Norway showed that this is a big assumption: by exploiting certain limitations of existing detector equipment, they were able to extract an entire secret key without anyone being the wiser. None of these attacks are fundamental 'breaks' of QKD, and indeed they've already been mitigated. But it goes to show how you should never trust a system just because someone tells you it's 'theoretically unbreakable'.

And that's 2011. I'm sure I'm missing tons of important stuff -- and that's what comments are for. Please enjoy the rest of your holidays and be safe in the new year.

What's TLS Snap Start?

2011-12-23T23:19:00.000-08:00

Google is promoting a new TLS extension which is designed to speed up the negotiation of TLS handshakes. The extension is called called Snap Start, and it's already been deployed in Chrome (and presumably throughout Google's back end.)

So what is Snap Start, why is it different/better than simply resuming a TLS session, and most importantly: how snappy is it?

Background: The TLS Handshake

To understand Snap Start we need to quickly review the TLS handshake. Snap Start only supports the classic (non-ephemeral) handshake protocol, so that's what we'll be talking about here. Leaving out a lot of detail, that handshake can be reduced to the following four messages:

C -> S: Client sends a random nonce CR.
C <- S: Server responds with its public key (certificate) and another nonce SR.
C -> S: Client generates a pre-master secret PMS, encrypts it with the server's public key and sends the ciphertext to the server.
C <- S: The client and server both derive a 'master secret' by hashing* together (CR, SR, PMS). The server and client also MAC all previous handshake messages to make sure nothing's been tampered with. Finally the server notifies the client that it's ready to communicate.

I'm ignoring many, many important details here. These include ciphersuite negotiation, parameter data, and -- most importantly -- client authentication, which we'll come back to later. But these four messages are what we need to think about right now.

So why Snap Start?

It only takes a glance at the above protocol to identify the problem with the classic handshake: it's frickin' slow. Every new TLS connection requires two latency-inducing round-trips. This can be a drag when you're trying to deploy TLS everywhere.

Now technically you don't need to run the whole handshake each time you connect. Once you've established a TLS session you can resume it anytime you want -- provided that both client and server retain the master secret.** Session resumption reduces communication overhead, but it isn't the answer to everything. Most people will balk at the idea of hanging onto secret keys across machine reboots, or even browser restarts. Moreover, it's not clear that a busy server can afford to securely cache the millions of keys it establishes every day.

What's needed is a speedy handshake protocol that doesn't rely on caching secret information. And that's where Snap Start comes in.

The intuition behind Snap Start is simple: if TLS requires too many communication rounds, then why not ditch some. In this case, the target for ditching is the server's message in step (2). Of course, once you've done that you may as well roll steps (1) and (3) into one mutant mega-step. This cuts the number of handshake messages in half.

There are two wrinkles with this approach -- one obvious and one subtle. The obvious one is that step (2) delivers the server's certificate. Without this certificate, the client can't complete the rest of the protocol. Fortunately server certificates don't change that often, so the client can simply cache one after the first time it completes the full handshake.***

Replays

The subtle issue has to do with the reason those nonces are there in the first place. From a security perspective, they're designed to prevent replay attacks. Basically, this is a situation where an attacker retransmits captured data from one TLS session back to a server in the hopes that the server will accept it as fresh. Even if the data is stale, there are various scenarios in which replaying it could be useful.

Normally replays are prevented because the server picks a distinct (random) nonce SR in step (2), which has implications throughout the rest of the handshake. But since we no longer have a step (2), a different approach is required. Snap Start's solution is simple: let the client propose the nonce SR, and just have the server make sure that value hasn't been used before.

Obviously this requires the server to keep a list of previously-used SR values (called a 'strike list'), which -- assuming a busy server -- could get out of control pretty fast.

The final Snap Start optimization is to tie proposed SR values with time periods. If the client suggests an SR that's too old, reject it. This means that the server only has to keep a relatively short strike list relating to the last few minutes or hours. There are other optimizations to deal with cases where multiple servers share the same certificate, but it's not all that interesting.

So here's the final protocol:

The client generates a random nonce CR and a proposed nonce SR. It also generates a pre-master secret PMS, encrypts it with the server's public key and sends the ciphertext and nonces to the server.
The server checks that SR hasn't been used before/recently. Both the client and server both derive a 'master secret' by hashing* together (CR, SR, PMS). The server notifies the client that it's ready to communicate.

The best part is that if anything goes wrong, the server can always force the client to engage in a normal TLS handshake.

Now for the terrible flaw in Snap Start

No, I'm just kidding. There doesn't seem to be anything wrong with Snap Start. With caveats. It requires some vaguely synchronized clocks. Moreover, it's quite possible that a strike list could get wiped out in a server crash, which would open the server up to limited replays (a careful implementation could probably avoid this). Also, servers that share a single certificate could wind up vulnerable to cross-replays if their administrator forgets to configure them correctly.

One last thing I didn't mention is that Snap Start tries to use as much of the existing TLS machinery as possible. So even though the original step (2) ('Server Hello' message) no longer exists, it's 'virtually' recreated for the purposes of computing the TLS Finished hash check, which hashes over all preceding handshake messages. Ditto for client authentication signatures. Some new Snap-specific fields are also left out of these hashes.

As a consequence, I suppose there's a hypothetical worry that an attack on Snap Start (due to a bad server implementation, for example) could be leveraged into an attack that works even when the client requests a normal TLS handshake. The basic idea would be to set up a man-in-the-middle that converts the client's standard TLS handshake request into a Snap Start request, and feeds convincing lies back to the client. I'm fairly certain that the hash checks and extra Snap Start messages will prevent this attack, but I'm not 100% sure from reading the spec.

Beyond that, all of this extra logic opens the door for implementation errors and added complexity. I haven't looked at any server-side implementations, but I would definitely like to. Nonetheless, for the moment Snap Start seems like a darned good idea. I hope it means a lot more TLS in 2012.

Notes:

* Technically this is a denoted as a PRF, but it's typically implemented using hash functions.

** At session resumption the master secret is 'updated' by combining it with new client and server randomness.

*** Certificate revocation is still an issue, so Snap Start also requires caching of 'stapled' OCSP messages. These are valid for a week.

A brief note on end-of-year giving

2011-12-23T12:58:00.000-08:00

I wanted to take a quick break from the technical to bug you about something important.

The end of the year is coming up and no doubt there are some folks thinking about last minute charitable donations. There are many, many worthy causes you can support. All things being equal, I'd give to my local food bank first, given how much need there is, and how far these institutions can stretch a charitable dollar ($1 at a food bank buys the equivalent of $20 at a retail supermarket).

But if you have something left over I'd strongly recommend that you give to the Electronic Frontier Foundation. In case you haven't noticed, there's a lot of crazy stuff going on with technology and the law these days. I recently poked fun at how small the EFF's budget is, but I meant it with love (and with reason!). They're fighting a tough uphill battle with minimal resources.

I have a personal reason for supporting the EFF. Back when I was a grad student, some colleagues and I reverse-engineered a commercial device as part of a research project. This is something that security researchers do from time to time, and it's something we should be able to do. Our goal was expose flaws in industrial security systems, and hopefully to spur the adoption of better technology. (Note: better technology is now out there, and no, I'm not taking credit. But scrutiny is generally a good thing.)

Anyway, we knew that there were legal obstacles related to this work, we just didn't realize how significant they'd be. When we first disclosed our findings, there were some... unpleasant phone calls at high levels. The University's legal counsel politely informed us that in the event of a lawsuit -- even a frivolous one -- we'd be bearing the expense on our own. This is not a pleasant prospect for a newly-married grad student who's just signed mortgage papers.

It's possible that without the EFF we'd have called the whole thing off right then. But the EFF did support us. They took our case (for free!), and worked miracles.

While our story has a happy ending, white hat security research in the US is still a minefield. Sadly this state of affairs doesn't seem to be improving. The EFF is just about the only group I know of that stands up for security researchers. Even if you're not a researcher, you probably benefit indirectly from their work.

So please take a minute to donate. It's tax deductible and some employers will match. If you donate at least $65 and become a member, they'll even send you an awesome T-shirt (I have one from 1999 that's still going strong -- it's ugly as sin but damn, the build quality is high.) Again, I'm not saying this should be the only donation you make this year, but it certainly would be a good one.

A question for you

2011-12-21T12:35:00.000-08:00

This post is addressed to you, my patient and wonderful audience.

I realize that my interests may not be entirely representative of yours. So what would you like to read about? I don't guarantee that I'll write on any of your suggestions, but I do promise to at least think about the topics you propose.

Feel free to make your suggestions in comments or Twitter. If you don't, be warned: you'll be as much to blame for that future post on Leakage Resilient Cryptography as I will.

What's the deal with RC4?

2011-12-15T08:11:00.000-08:00

(credit)

Jacob Appelbaum tweets:

Does anyone have a good reading list on practically attacking RC4?

I don't intend to give an exact answer to Jacob's question here, but his tweet caught my eye for a reason. You see, just the other week I advised implementers to avoid RC4 -- both because it's easy to misuse, and because it's has some real and theoretical flaws. But that doesn't mean any particular RC4 implementation is broken.

Instead, you should take my advice as the crypto equivalent of "don't run with scissors", "don't run near the pool", or "don't run near the pool while carrying scissors". I don't know anyone who's actually lost an eye because they ignored these warnings, but I still yell this stuff at my kids. It's common sense.

Still, this leaves us with a question: how bad is RC4, really?

RC4, the stream cipher for the rest of us

First, the basics. RC4 was invented in 1987 by Ron Rivest. It spent its first seven years as an RSA trade secret before it was eventually leaked to a public mailing list in 1994. The rest, as they say, is history.

You could argue that RC4's rise was inevitable. By the time of its leak, it was already in widespread commercial use. Unlike DES it was fast in software.* More importantly, the scheme itself is dirt simple. You can fit the code for RC4 onto a cocktail napkin, with plenty of room left over for the cocktail. And of course, having become public, the 'alleged' RC4 was free.

One phase of the RC4 PRG. K is the
output byte. Image: Wikipedia.

The scheme consists of two parts: a key scheduling algorithm (KSA), and a pseudo-random generator (PRG). To encrypt a message, you run the key through the key scheduler, which produces a scrambled array called the state vector. You then feed the state vector into the PRG, which continuously permutes it while outputting a series of bytes. You then XOR those 'keystream' bytes with your plaintext.

RC4 is probably most famous for its (mis)use in 802.11 WEP. It's still used in WPA-TKIP (unsurprising, since TKIP is just a bandaid patch for WEP). But its use goes way beyond that. For one thing, it's a common ciphersuite for TLS, and as of a year or two ago it was even preferred by browsers like Chrome. Up until recently, Microsoft used it everywhere. Skype uses it to obfuscate (though not to encrypt) its communication protocol. It shows up in malware and a zillion crappy DRM packages.

To make a long story short, you'll usually find RC4 anywhere the hardware was too weak, or the developers too lazy to use a better cipher.

The plain stupid

There are a few basic things you need to avoid when using any PRG-based cipher. These aren't specific to RC4, but for some reason they seem to crop up at a higher rate in RC4 implementations than with other ciphers.

The big honking obvious one is that you can't re-use the same RC4 keystream to encrypt two different messages. I hope I don't need to go into the consequences, but they're bad. Don't do it.

You'd think this is so obvious that nobody could get it wrong, but that's exactly what Microsoft famously did back in 2005, encrypting different versions of a Word document with the same key. If you must use the same key for different messages, the solution is to combine the key with an Initialization Vector or 'nonce'. Unfortunately this can be problematic as well.

Another big issue is ciphertext malleability. If you flip a bit in an RC4 ciphertext, you'll see the same bit flipped in the decrypted plaintext. This is awesome at parties. More to the point, it can lead to practical padding-oracle type attacks that totally compromise the security of your encryption.**

The solution to the latter problem is simply to MAC your ciphertexts. Unfortunately, people don't use RC4 because they know what a MAC is -- they use RC4 because you can download the code from Wikipedia. So, again, while this can happen with many ciphers, it tends to happen with RC4 a lot more than it should.

Key Scheduling

Leaving aside the stupid, the real problem with RC4 is the Key Scheduling Algorithm (KSA), which kind of sucks.

Picture a brand new box of playing cards. Starting with the unshuffled deck, work systematically from top to bottom, swapping each card's position with another card in the deck. The position you're swapping to is determined by a few simple computations involving the original card's face value and the cryptographic key. Now do this with a stack of about five ordered decks and you've got the RC4 KSA.

While this shuffle seems thorough, the devil is in those simple computations. Ultimately their simplicity means the shuffle isn't unpredictable enough. This leads to predictable patterns that show up in the first PRG output bytes. For example, Mantin and Shamir noted that the second output byte takes on the value '0' with about twice the probability it should. By itself that may not seem terribly useful, but for one thing: it's enough to practically determine whether an unknown algorithm is RC4, given about 128 keystreams on different (random) keys.

From what I can tell, the first person to notice problems with KSA was Andrew Roos, who posted a paper to sci.crypt about a year after the leak. Aside from the fact that it was published on Usenet, Roos's result is notable for two reasons. First, he correctly identified use of concatenated IVs as a likely source of weakness in WEP implementations -- years before anyone else did. Second, Roos gave recommendations that -- had they been followed -- could have prevented a lot of subsequent heartache. (Lesson: don't publish scientific results in newsgroups.)

FMS

Roos's paper set the table for the most famous attack on RC4, and the one that people still associate with RC4, even though it's rarely used in its original form. This is, of course, the Fluhrer, Mantin and Shamir, or 'FMS' attack, which appeared in 2001.

Just like Roos, FMS looked at the KSA and found it wanting -- specifically, they discovered that for certain weak keys, the first byte output by the PRG tends to be correlated to bytes of the key. These weak keys can be obtained by prepending a few chosen bytes (say, 3 of them) to an unknown, fixed, secret key. Given keystreams resulting from 60 such chosen keys, you can derive one byte of the secret portion of the key. A 16-byte key can therefore be computed from about 960 such keystreams.

On the face of it this sounds pretty unlikely -- after all, how are you going to get an encryptor to prepend chosen bytes to their secret key. Fortunately the attack works fine even if the adversary just knows that the appropriate bytes were used. This works perfectly for implementations that prepend (or append) a known Initialization Vector to the WEP key. Simply by observing a few million IVs, an attacker can eventually collect enough keystreams to meet the FMS requirements.

All of this would have be a historical footnote if it hadn't been for protocols like WEP, which (among its many problems) used a three-byte prepended IV. FMS was quickly demonstrated to work on WEP, then packaged into a neat tool and distributed.

Klein, Dropping and Hashing

There are two common approaches to dealing with the FMS attack:

Drop the first N bytes of the RC4 keystream, for values of N ranging from 256 to 3,072.
Don't concatenate the IV to the key, hash the two together instead.

The first option is sometimes referred to as RC4-drop[N], and the actual value of N has been subject to some debate. In 2006, Klein presented a super-charged variant of the FMS attack that reduced the necessary number of IVs from millions down to about 25,000. More importantly, he showed that FMS-type attacks are still (borderline) viable even if you drop the first 256 bytes of the keystream. So 768 seems like a bare minimum to me, and some people will argue for much larger values.

The second approach was adopted for WPA-TKIP, which was proposed as a band-aid replacement for WEP. TKIP was designed to support legacy WEP-capable devices that had internal RC4 hardware, but weren't powerful enough to handle AES. It made a bunch of positive changes to WEP (including adding a larger IV to prevent keystream reuse), but the most notable change was a new custom hash function that creates a per-packet key from an IV and secret key.

As a hash function, the TKIP hash kind of stinks. For one thing, it can be inverted given only about 10 per-packet keys and about 2^32 computation (these days, a few minutes on a TI calculator). However, this isn't as big of a deal as it sounds: pre-image resistance isn't precisely a goal of the TKIP hash, since those per-packet keys themselves should themselves be hard to obtain. Nonetheless, I wouldn't recommend that you mess around with it. If you must use RC4, try a proper hash function. Or better yet, don't use RC4 at all.

Distinguishers

Last but not least: RC4 is just a PRG, and a PRG is secure if its output is indistinguishable from a stream of truly random bits -- to a 'reasonable' adversary who doesn't know the key.*** Hence a great deal of RC4 research focuses on the quality of the cipher's PRG.

So is RC4 a good pseudo-random generator? Meh. Given a mere 1.5GB of keystream data, Fluhrer and McGrew presented an algorithm that distinguishes RC4 from random. I already mentioned Mantin and Shamir who cranked this down to about 256 bytes (over various unknown, unrelated keys) by looking at the second output byte. Finally, Mantin noticed the presence of repeating patterns in RC4, which aren't simply dependent on the first few bytes of output, and can be used to distinguish RC4 given about 64MB of keystream.

There are, of course, other distinguishing attacks. But does it matter?

Well, sort of. Indistinguishability is a critical characteristic of an XOR-based stream cipher. If we have it, then the security argument for RC4 encryption is very simple: to an adversary who can't distinguish the PRG, RC4 encryption is indistinguishable from using a one-time pad.

Unfortunately the converse isn't true. Just because RC4 output is distinguishable from random doesn't mean that there's a practical attack on the cipher. These results are important mostly because they illustrate the fundamental wonkiness of RC4, wonkiness that doesn't go away just because you drop the first 3,072 bytes. But they don't exactly give us a practical opening into the cipher itself. Yet.

Ok, none of this was very helpful. I just want to know: can I use RC4?

Great question.

The upshot is that RC4, if used as recommended (with hashed IVs and/or dropped output and MACs), is perfectly sufficient for securely encrypting messages. Today. The problem is, we never know what the future will bring.

My advice? Don't run with scissors. You can lose an eye that way.

Notes:

* My totally unscientific results, from running 'openssl speed' on a lightly loaded Macbook Pro: 3DES-EDE: 21 bytes/μsec. DES: 54 bytes/μsec. AES-128: 118 bytes/μsec. RC4: 248 bytes/μsec.

** You might argue that RC4 implementations shouldn't use padding in the first place, since (unlike CBC mode encryption with a block cipher) messages don't need to be padded to a multiple of a block size. This is true -- however, I would note that 'padding oracle'-style attacks needn't rely specifically on padding. Padding is just one type of encoding that can leak useful information if used incorrectly. For a great example, see Jager and Somorovsky's recent result that uses UTF8 coding checks to defeat XML encryption.

*** By reasonable, of course, we mean 'computationally limited'. This rules out attacks that require an unrealistically long time, quantum computing, or ESP.

Programming note

2011-12-13T16:37:00.000-08:00

I realize that posts have been a bit light on this blog over the past couple of weeks. I've been a bit preoccupied recently, but this will soon change. I'm also aware that I have a few outstanding unfinished threads, and I certainly haven't forgotten them. If you have no idea what I'm talking about, that's great! See:

Stay tuned. There will be content.

Paul Kocher

2011-12-11T22:44:00.001-08:00

On the one hand, I have enormous respect for Paul Kocher.

On the other hand, writing:
/* Paul Kocher thinks this is ok */
does not necessarily make it ok.

Just sayin'.

Liveblogging WWII: December 12, 1941

2011-12-11T21:50:00.001-08:00

In mid-December 1941, Driscoll finally sent the British some information on her special method, with only cursory answers to the few questions Denniston had posed four months before. Driscoll again declared her faith in her approach, but GCCS concluded that it "apparently failed." For one thing, it could not, as she had claimed, overcome the problem of turnover -- that is, the tumbling of the Enigma's wheels before enough letters had been enciphered to identify the wheel being used. And as Turing pointed out to her in a letter in October 1941, her method would take seventy-two thousand hours -- more than eight years -- to find a solution. Given Driscoll's obstinacy, Bletchley park began to have second thoughts about providing more technical information.

As luck would have it, an apparent mix-up in the mail delivery between OP20G and Bletchley Park soon brought the simmering distrust and jealousies between the two agencies flaring the the surface. Dennison's early October dispatch -- a bag of materials containing detailed answers to all but one of Driscoll's questions -- never reached OP20G, the Navy claimed. It didn't take long for Safford, who feared the British were breaking their promises, to push Leigh Noyes into firing off a series of complaints to the British. Through November and December 1941, angry memos and accusations flew across the Atlantic. Noyes didn't mince his words: Britain had broken its promise to OP20G; American had no use for the Bombe; and if GCCS cooperated, Driscoll could have her method working on real problems. ...

Noyes, who was unaware of the complexities of the mail mix-up, continued to fire off angry memos to the British, some of them clearly threatening. The U.S. Navy, he said, had never agreed to confine itself to Enigma research. It had always intended to be "operational" -- that is, intercepting and decoding messages on its own. He told Hastings that all the Navy wanted from the British was the information on the Enigma and the codebooks and Enigma machine that Safford and Driscoll had requested.

Then, belying later histories of GCCS and OP20G relations, Noyes apologized to the British, twice. On December 10 and again on the twelfth, he declared that British explanations and actions since his outbursts had satisfied him and "everyone" at OP20G. The missing package, of course, was found. On December 13, Bletchley received a cryptic yet pointed message from someone in the U.S. Navy Department: "Luke Chapter 15, v 9: And she found it. She calleth together her friends and neighbors saying: Rejoice with me for I have found the piece which we lost".

-- Jim DeBrosse, Colin Burke: The secret in Building 26