Wonk post: Circular security

Apologies in advance for a super-wonky post, but I’m in kind of a wonky mood this week. It happens that I’m putting together a talk on the subject of circular security, and I figured this blog might be a good place to get my thoughts together.

If you’ve never heard of circular security, don’t feel bad — you’re in good company. In a nutshell, circular security describes the way that an encryption scheme behaves when you ask it to encrypt its own key. In theory, that behavior can be pretty unpredictable.

The key word in the previous sentence is ‘theory’. Circular security is a very interesting research area, but if your primary reason for reading this blog is to learn about practical things, this post may not be for you. (Though please come back next week, when I hope to be writing about electronic cash!)

Assuming you’re still reading, the first order of business is to talk about what circular security (or insecurity) is in the first place. To do that, we need to define what it means for an encryption scheme to be ‘secure’. And that means a discussion of semantic security.

Semantic Security

Semantic security is one of the earliest and most important security definitions in our field. It’s generally considered to be the minimum bar for any modern ‘secure’ encryption scheme. In English, the informal definition of semantic security is something like this:

An attacker who sees the encryption of a message — drawn from a known, or even chosen message space — gains approximately the same amount of information as they would have obtained if they didn’t see the encryption in the first place. (The one exception being the length of the message.)

This is a nice, intuitive definition since it captures what we really want from encryption.

You see, in an ideal world, we wouldn’t need encryption at all. We would send all of our data via some sort of magical, buried cable that our adversary couldn’t tap. Unfortunately, in the real world we don’t have magical cables: we send our data via the public WiFi at our neighborhood Starbucks.

Semantic security tells us not to worry. As long as we encrypt with a semantically-secure scheme, the adversary who intercepts our encrypted data won’t learn much more than the guy who didn’t intercept it at all — at worst, he’ll learn only the amount of data we sent. Voila, security achieved.

(Now, just for completeness: semantic security is not the strongest definition we use for security, since it does not envision active attacks, where the adversary can obtain the decryption of chosen ciphertexts. But that’s a point for another time.)

Unfortunately, before we can do anything with semantic security, we need to turn the English-language intuition above into something formal and mathematical. This is surprisingly complicated, since it requires us to formalize the notion of ‘an attacker gains approximately the same amount of information‘. In the early definitions this was done by making grand statements about predicate functions. This approach is faithful and accurate. It’s also kind of hard to do anything with.

Fortunately there’s a much simpler, yet equivalent way to define semantic security. This definition is called ‘indistinguishability under chosen plaintext attack‘, or IND-CPA for short. IND-CPA is described by the following game which is ‘played’ between an adversary and some honest party that we’ll call the challenger:

  1. The challenger generates a public/private keypair, and gives the public key to the adversary.
  2. The adversary eventually picks two equal-length messages (M0, M1) from the set of allowed plaintexts, and sends them to the challenger.
  3. The challenger flips a coin, then returns the encryption of one of the messages under the public key.
  4. The attacker tries to guess which message was encrypted. He ‘wins’ if he guesses correctly.

(This game can also be applied to symmetric encryption. Since there’s no public key in a symmetric scheme, the challenger makes up the lost functionality by providing an encryption oracle: i.e., it encrypts messages for the adversary as she asks for them.)

A quick glance at the game should convince you that even a moron adversary can win this game. In fact, if the adversary simply guesses randomly he’ll be right exactly half the time. Hence the real question is: how much better can he do?

And that leads us to our (basically) formal definition:

A scheme is IND-CPA secure if no adversary can win the above game with probability (significantly) greater than 1/2.

The term ‘significantly’ in this case hides a lot of detail — typically it means that ‘non-negligibly‘. In many schemes we also require the adversary to run in limited time (i.e., be a probabilistic polynomial-time Turing machine). But details, details…

Encrypting your own key

One of the weirder aspects of the IND-CPA definition above is that it doesn’t handle a very basic (and surprisingly common!) use case: namely, cases where you encrypt your own secret key.

Believe it or not, this actually happens. If you use a disk encryption system like Bitlocker, you maybe already be encrypting your own keys, without even noticing it. Moreover, newer schemes like Gentry’s Fully Homomorphic Encryption depend fundamentally on this kind of “circular” encryption.

It seems surprising that IND-CPA can give us such a strong notion of security — where the attacker learns nothing about a plaintext — and yet can’t handle this very simple case. After all, isn’t your secret key just another message? What makes it special?

The technical answer to this question hangs on the fact that the IND-CPA game above only works  with messages chosen by the adversary. Specifically, the adversary is asked to attack the encryption of either M0 or M1, which he chooses in step (2). Since presumably — if the scheme is secure — the adversary doesn’t know the scheme’s secret key, he won’t be able to submit (M0,M1) such that either message contains the scheme’s secret key. (Unless he makes a lucky guess, but this should happen with at most negligible probability.)

What this means is that an encryption scheme could do something terribly insecure when asked to encrypt its own secret key. For example, it could burp out the secret key without encrypting it at all! And yet it would still satisfy the IND-CPA definition. Yikes! And once you raise the possibility that such a scheme could exist, cryptographers will immediately wants to actually build it.

(This may seem a little perverse: after all, aren’t there enough broken schemes in the world without deliberately building more? But when you think about it, this kind of ‘counterexample’ is extremely valuable to us. If we know that such oddball, insecure schemes can exist, that motivates to watch out for them in the real constructions that we use. And it tells us a little about the strength of our definitions.)

It turns out that there’s a ‘folklore’ approach that turns any IND-CPA secure public-key encryption scheme into one that’s still IND-CPA secure, but is also totally insecure if it ever should encrypt its own secret key.

The basic approach is to modify the original scheme by changing the encryption algorithm as follows:

  1. On input a public key and a message to be encrypted, it tests to see if the message is equal to the scheme’s secret key.*
  2. If not, it encrypts the message using the original scheme’s encryption algorithm (which, as we noted previously, is IND-CPA secure).
  3. If the message is equal to the secret key, it just outputs the secret key in cleartext.
It’s pretty easy to see that this scheme is as secure as the original scheme for messages that aren’t the secret key. It’s also easy to see that it’s totally insecure when you do encrypt the actual secret key. (Though I’ve glossed over a small technical challenge in step 2, see footnote*).

Circles and cycles

Just as cryptographers were congratulating each other for answering the previous question — showing that there are schemes that fail catastrophically when they encrypt their own secret key — some smartass decided to up the stakes.

The question (s)he asked was: what if two people encrypt each other’s secret keys?

Let’s be clear what I’m saying here. Imagine that Alice decides to entrust Bob with her secret key, so she wraps it up under his public key (say, sending him a PGP encrypted email). And imagine that Bob decides to do exactly the same with his key, encrypting it under Alice’s public key. We now have the following ‘key cycle’:

CA = Encrypt(pkA, skB),               CB = Encrypt(pkB, skA)

To be clear, IND-CPA by itself tells us that it’s perfectly secure for Alice to encrypt her own key under Bob’s key (or vice versa). There’s no problem there. However, the minute Bob also encrypts Alice’s secret key, a cycle is formed — and semantic security doesn’t tell us anything about whether this is secure.

So this is worrisome in theory, but are there actual schemes where such cycles can cause problem?

Up until 2010, the answer was: no. It turns out to be much harder to find a counterexample for this case, since the approach described in the previous section doesn’t work. You can’t just hack a little bit of code into the encryption algorithm; the ciphertexts are encrypted independently. At the time they’re encrypted, the ciphertexts are perfectly secure. They only become insecure when they come into close proximity with one another.

(If a weird analogy helps, think of those encrypted keys like two hunks of Plutonium, each inside of its own briefcase. As long as they’re apart, everything’s fine. But get them close enough to one another, they interact with one another and basically ruin your whole day.)

It gets worse

A breakthrough occurred at Eurocrypt 2010, where Acar, Belenkiy, Bellare and Cash showed that indeed, there is a scheme that’s perfectly IND-CPA secure in normal usage, but fails when Alice and Bob encrypt their keys in a cycle like the one described above.

The Acar et al. scheme is based on certain type of elliptic-curve setting known as bilinear SXDH, and what they show is that when Alice and Bob create a key cycle like the one above, an adversary can recognize it as such.

To be clear, what this means is that the ciphertexts (Encrypt(pkA, skB), Encrypt(pkB, skA)) jointly leak a little bit of information — simply the fact that they encrypt each other’s secret keys! This may not seem like much, but it’s far more than they should ever reveal.

The Acar et al. result is interesting to me, because along with my colleague Susan Hohenberger, I was thinking about the same problem around the same time. We independently came up with a similar finding just a few months after Acar et al. submitted theirs — crappy luck, but it happens. On the bright side, we discovered something slightly worse.

Specifically, we were able to construct a scheme that’s totally secure in normal usage, but becomes catastrophically insecure the minute Alice and Bob encrypt each others’ secret keys. This means in practice that if two parties innocently encrypt a key cycle, then both of their secret keys become public. This means every message that either party has ever encrypted (or will encrypt) becomes readable. Not good!**

The worst part is that both the Acar et al. scheme and our scheme are (almost) normal-looking constructions. They could be real schemes that someone came up with and deployed in the real world! And if they did, and if someone encrypted their secret keys in a cycle, things would be very bad for everyone.

So what do we do about this?

The solution to this problem is to develop schemes that can handle (by design) the case where someone encrypts a secret key, or a function of a secret key. This concept is known as Key-Dependent Message (KDM) security, and it’s been the subject of some research.

Unfortunately, building provably KDM-secure schemes is not an easy task, at least, not without resorting to artificial constructs like random oracles. While this may change in the future, for the moment we have a ways to go before we can build truly efficient schemes that don’t (potentially) have problems like the above.

And this is what makes cryptography so interesting. No matter what we say about our schemes being  ‘provably secure’, the truth is: there’s always something we haven’t thought of. Just when you thought you’d finally solved all the major security problems (ha!), another one will always pop up to surprise you.

Notes:

* The obvious objection is that a public key encryption algorithm takes in only a public key and a message. It doesn’t take in the scheme’s secret key. So: how can it check whether the given message is the encryption of the secret key? There’s a general solution to this, but I’ll leave it as an exercise for the reader.

** David Cash, Susan Hohenberger and I have summarized these results, along with several related to symmetric encryption, and will be presenting them at PKC 2012. If you’re interested, a full version of our paper should appear here shortly.

Poker is hard, especially for cryptographers

I have this friend who’s an obsessive poker fan, to the point where it’s actually a little scary. The worst part is that as a computer scientist, he approaches the game with a numeracy that would make an Apollo 11 technician blush. He refuses to touch a hand until he’s computed the precise odds, which wouldn’t be so bad if he didn’t tell me about it — all while gibbering mysterious 19th-century words like ‘flop’ and ‘river’ and ‘hole card’.

When this happens I try to smile and nod like I have some idea what he’s talking about. But trust me, I don’t. My card-playing experience runs to a few tense games of ‘Go Fish!’ and a drunken weekend in Vegas playing Blackjack.

Still, there’s one aspect of card playing that I am fascinated by: mental poker. This is a blanket term for a protocol that allows mutually-distrustful people to deal and play cards without a dealer, or, indeed, any trusted party at all.

Like all crypto/privacy protocols, mental poker interests me because it’s so counterintuitive. You get a bunch of people together, none of whom trust each other — some of whom may be actively trying to cheat the others — and at the end of the day everyone gets a fair deal, or at worst, enough warning to get out clean.

I also love the concept because it’s so obviously disruptive. In case you hadn’t heard, US law enforcement doesn’t have warm, cuddly feelings towards online poker. This past spring, the FBI took down three of the biggest sites, and there’s no reason to think they’re done. I may not be a poker player myself, but decentralized mental poker appeals to me, mostly because it would be a lot harder to shut down — especially if it was tied to a peer-to-peer currency such as Bitcoin. (On the other hand, you’d be playing for Bitcoin. So there’s that.)

In the rest of this post I’m going to talk a little bit about where mental poker came from and how it works. I don’t plan to give too many equations, but it will get a little (or a lot) wonky, and will certainly depart a bit from the pro-implementer, pro-engineering spirit of this blog. (If you want to pass, I certainly won’t hold it against you.)

Secret history

Like every other problem in our field, ‘Mental poker’ was first proposed by Shamir, Rivest and Adleman (note to self: invent new research field, get dibs on all the interesting problems.) Their motivation was — well, let’s just let them tell it:

Once there were two “mental chess” experts who had become tired of their favorite pastime. Let’s play “mental poker” for some variety suggested one. “Sure” said the other. “Just let me deal!”

In that first paper, Shamir et al. managed the fascinating trick of both proving that mental poker is impossible, and then giving a protocol to do it securely. (Don’t get discouraged by this — it happens.)

While the Shamir et al. paper may have been the first to address mental poker, it definitely wasn’t the last. Indeed, it’s an open secret that most of the ‘fundamental’ advances in cryptography — semantically-secure encryption, zero-knowledge proofs, etc. — were actually just happy accidents: things that dropped out while MIT cryptographers were fiendishly seeking better ways to play Five Card Stud with their colleagues at Weizmann.

Whether you believe this or not, the fact is that mental poker is really challenging, and did motivate a lot of new work. To explain this, let’s go over the basics of the problem.

Face up or Face Down?

For a mental poker scheme to be useful, it has to achieve three basic goals:

  1. The shuffle must be random.
  2. The deck must be correct — no trick aces!
  3. Some cards must be dealt face down.

Let’s focus on the last point for a moment. If you’ve ever toyed with the idea of writing a card game, you probably know how to represent face-up cards: just let each be an integer from 0 through 51. Obviously we’ll need a table to map those values into something that humans can work with, but fundamentally this is no sweat.

Face-down cards, on the other hand, are more complicated. We need a publicly-visible data structure that can do what a physical card does: it must commit the holder to a particular face value. At the same time, it must hide that value from everyone else.

The simple and elegant solution (in case you didn’t see it coming) is to encrypt the face-down cards using a semantically-secure encryption scheme such as Elgamal.

(A quick note: ‘semantic security’ is a fundamental security definition that’s considered the minimum bar for every modern encryption scheme. In english, it means that you can’t learn any useful information from a ciphertext. It goes without saying that the definition was proposed in a paper about mental poker.)

While encryption solves some of our problems, it doesn’t quite solve them all. In fact, it gives us a big new one. If we’re going to encrypt the cards, who the heck is going to hold the decryption key?

And this is where modern public-key cryptography really shines. A basic trick is that every player can generate a ‘share’ of the decryption key such that the sum of all those shares is the decryption key for the entire scheme (they can also use these shares to generate the public key). This allows the players to cooperatively decrypt any ciphertext, such that no individual player ever gets the entire decryption key.

And now we have almost enough to describe a ‘simple’ mental poker protocol.

Generate the deck. First, one player generates an ordered ‘deck’ of cards — the integers (0, 1, 2, 3, …, 51) — and encrypts each one using known randomness. Since this player might be a cheater, she publishes all of her work so the group can repeat and verify it. If all goes well, the group should be confident that the deck is well-formed, i.e., there are no missing cards or duplicates.

Shuffle. The players now pass the deck around the ‘table’, giving each individual a chance to shuffle it thoroughly. This is harder than it sounds; it’s not enough to simply permute the order of the encrypted cards, since the ciphertexts themselves are recognizable (think of each card as having a different back-face). The good news is that schemes like Elgamal allow you to re-randomize a ciphertext — change its outward appearance without changing the underlying plaintext.

Unfortunately, re-randomizing ciphertexts leads to yet another serious limitation: if the output of the shuffle can’t be linked to the input, then a malicious player could simply replace the cards instead of shuffling them. The last player to shuffle would essentially be deciding the order (and even the types of cards in) the deck!

Fortunately, in their quest for better ways to play poker, cryptographers have solved this this problem as well. The answer is something called a publicly-verifiable shuffle (used in Mix networks, which completely by accident were later shown to have applications in e-Voting and anonymous communication). In these systems, the shuffler can actually prove that the shuffled deck contains the same cards, without giving away the shuffle.

Dealing. If everything’s gone well, and if at least one player is honest, the players should now have a beautifully shuffled deck of encrypted cards. It remains only to deal them. To do this, the players cooperatively decrypt the cards using their key shares. If the card is face-up, they go ‘all the way’ and simply reveal the plaintext to the whole group. If it’s face-down, they collaborate most of the way, but let the recipient handle the last component of the decryption process.

Ok, maybe this wasn’t so simple. And there’s still a lot I’m leaving out — including the whole Mix mechanism and a bunch of zero-knowledge proofs you’d need to prevent cheating in the decryption process. Still, figuring that stuff out isn’t the problem.

The problem is that the protocol above is expensive.

A single shuffle alone can result in megabytes of data, which every party has to verify. So much for playing mental poker over the phone (or, to use a modern analogy, Twitter). Clearly a better approach is needed.

Golle to the rescue?

The problem with the ‘classic’ approach is that it requires the players to generate and shuffle an entire deck of cards every time they play. But this is pointless work, since many games don’t actually use the entire deck. A better approach would generate random cards on the fly, then check for ‘collisions’: cards that have already been dealt to the players.

This is what Philippe Golle proposed back in 2005, in a paper submitted to the ITCC e-Gaming track (What is this? It sounds awesome.) I know about this paper because a student recently implemented it in Charm; hence I can attest to the fact that it’s practical. Actually, it cooks.

Golle’s idea was to use the additively-homomorphic property of schemes such as Elgamal,* to allow the parties to draw random cards. In a nutshell, each of the k players selects a random value in the range 0 to 51, then encrypts her value and publishes it to the other players. The group can now add the ciphertexts together, which gives them the encryption of (r_1 + r_2 + … + r_k).

By working together the group can decrypt the summed ciphertext, which reveals a plaintext in the range 0 to (k*51). By reducing this modulo 52 they obtain a random card number.

The big obstacle to this approach is that you can get repeated cards, i.e., collisions. The clever part of Golle’s protocol is the way that he checks that a given card hasn’t been dealt to a player already, which allows him to ‘throw back’ any colliding cards.

I won’t spend much time on how this works, except to point out that Golle’s paper may have a small bug (though one that’s easily fixed). To make a long story short, when a collision occurs in the first round of dealing — i.e., a card is dealt that already exists in a player’s hand — Golle will actually ‘throw back’ both the new card, and the card that was already in the player’s hand.

Why am I complaining about this? Well, imagine that a real poker dealer did this. That is, he paused, asked to look at your hand, took away the King of Hearts and put it back in the deck (with a brief apology for his mistake). It strikes me that this would not be viewed as kosher. I’ll leave it to a real poker player to tell me what the implications are, but I’m trusting they’re not good.

All the rest

This has been a long post, and while I hope it’s given some of the flavor of the problem, obviously there’s still tons I haven’t said.

For example, how do you check for winning conditions? How do you handle players who ‘drop out’ when the cards don’t go their way? And finally, how would you tie the result of the game to a Bitcoin ‘pot’? (Bitcoin script seems like a great candidate for this, but unfortunately it’s not well supported on the actual Bitcoin network.)

And of course, none of this addresses the real problem with online poker, which mere cryptography does not solve — namely, how to keep your opponents from sharing their hands via a backchannel.

Still, this is a fun area that I’d love to see pursued with a bit more vigor. Yes, from time to time someone promises to do it, but those promises never quite materialize. So if you’re a poker fan and you find this stuff interesting, please do drop me a line.

Notes:

* For the super-wonky, Elgamal is actually multiplicatively homomorphic, but that’s ok. What’s being encrypted is g^r, for some generator g. The product of (g^r1 * g^r2 = g^{r1+r2}) which can be decrypted by testing the result against a table of pre-computed values. (This only works for small values).

Random number generation: An illustrated primer

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.
random
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.

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:

  1. 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.
  2. Linux uses a hash-based PRG based on two variants of SHA.
  3. 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
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.

Multiple encryption

 

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:

  1. Am I better off encrypting with two or more encryption schemes (or keys?)
  2. Could I be worse off?
  3. 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 (EncryptAdoesn’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:

  1. 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.
  2. 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.

  3. 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.

A very casual introduction to Fully Homomorphic Encryption

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.

How (not) to use symmetric encryption

This is supposed to be a blog about cryptographic engineering. brass_key_corkscrew12That means crypto, but it also means software engineering, protocol design, HCI and hardware engineering (fair warning: my hardware experience mostly consists of solder burns).

And yet, in describing the attacks of the past few weeks, I’ve mostly been talking about basic symmetric encryption. This seems to be an area that people get wrong, no matter how straightforward it sounds.

So at the risk of boring my readership to tears — I’m going to spend the next two posts talking about the dos and don’ts of symmetric encryption, particularly symmetric encryption with block ciphers. I may also branch out a little into key derivation and management, but I know you’ll be understanding.

I realize that for some of you this may not make for scintillating reading, but here’s my thinking: we do it once now, we’ll never have to discuss it again. Right?

Excellent. In this first post I’m going to start with the don’ts.

Symmetric Encryption Don’t #1: Don’t encrypt with ECB mode

Block ciphers are designed to process discrete chunks of data. For example, AES works on 128-bit blocks. To encrypt longer messages with them, we use one of several “modes of operation“. These modes are not all created equal.

 Tux image: Larry Ewing. (I will not
thank the GIMP, no matter what
his license says.)

ECB (Electronic Codebook) mode is by far the stupidest. Essentially you’re just chopping the message up into blocks, then using the raw block cipher to encipher each block individually. There are two problems with ECB mode:

  1. It’s not randomized. This means that anytime you encrypt a given message under a key, you’ll get exactly the same ciphertext. This goes for substrings of the message as well.
  2. It treats each block of the message independently. As a result, some of the structure of the message can leak through. This includes things like padding, which will produce predictable patterns in the ciphertext.

The first point can be a problem in some circumstances. Imagine, for example, that you’re sending a relatively small number of messages (e.g., commands for a remote system). Every time you send a given command, you’re sending exactly the same ciphertext. This gets obvious pretty fast.

I would say that the second problem is the more serious one. Perhaps you’ve seen Wikipedia’s classic image of an ECB-mode encrypted TIFF file (right). But probably this seemed a little contrived to you — after all, who uses TIFF files anymore?

So allow me to give my favorite example of why ECB mode is problematic. This image comes from a software packaging system that used ECB mode to encrypt executable files. All I’ve done is open one of those encrypted files as a raw bitmap image. You’ll have to squint a little.

An executable file encrypted using ECB mode. Click to see a larger version.

This doesn’t give away the contents of the executable, but it gives a pretty good picture of where different segments are. Just look for the funny patterns and tire tracks. Just having this little bit of information might give you a nice head start on finding those segments when they’re in memory, which is potentially what you’re going to do next.

Symmetric Encryption Don’t #2: Don’t re-use your IVs

Every block cipher mode of operation except for ECB (which you shouldn’t use!) employs a special per-message nonce called an Initialization Vector, or IV. The basic purpose of an IV is to ensure that the encryption function works differently every time; it adds an element of randomness, or at least unpredictability to your ciphertexts.

Unfortunately, developers seem genuinely stumped by IVs. Maybe this isn’t their fault. Every mode of operation has slightly different rules about how to pick IVs, and a slightly different set of consequences for when you screw it up.

So let’s start with something simple. No matter what mode you use, this kind of thing is never ok:

This chunk of bad advice comes from an ancient (and hopefully obsolete) version of the AACS specification. But it’s hardly the exception. Grep for “IV” in the source repositories of just about any major software house, and I guarantee you’ll find plenty of stuff like this.

Why is this a problem? Let me count the ways:

  1. At a minimum, it eliminates any random behavior in the encryption scheme. With a fixed IV, a given message will always encrypt to the same ciphertext (if you’re using the same key). This goes for two messages that are the same up to a certain point. See my discussion of ECB mode above for why this can be a problem.
  2. If you’re using a stream cipher mode of operation like CTR or OFB, it’s a disaster. If you encrypt two different messages with the same key, and the IV is fixed, then an attacker can XOR two ciphertexts together. This will give them the XOR of the two underlying plaintexts. (Think this will be useless? I doubt it, especially if they’re clever.)

    By the way, this kind of thing also happens when people forget to change the IV when encrypting multiple versions of a file. Don’t do that either.

  3. If you’re using a chaining mode like CBC, use of a fixed IV can still lead to plaintext recovery. See, for example, this chosen plaintext attack on TLS, which only requires the adversary know which IV is being used. This type of attack is pretty tricky to implement, but it’s definitely possible.
  4. It will make you look stupid and embarrass you when a professional audits your code.

Clearly some of these issues are application-specific. Maybe you don’t think anyone will be able to leverage them. You might even be right — in this version of the application. But sooner or later, you or a future developer will bolt on new features, deploy it in the cloud, or make it into a browser applet. When they do, all of these issues will magically go from theoretically vulnerable to stupidly vulnerable.

And people will blame you.

So how do you use IVs correctly? I’ll talk about this more in my next post. But if you’re really chomping at the bit, my advice is to take a look at the FIPS specification for block cipher modes. (I must warn you, however: please don’t operate heavy machinery while reading these documents.)

Symmetric Encryption Don’t #3: Don’t encrypt your IVs

So you’ve generated your IV correctly, you’ve used it correctly, but now you’re hung up on a final question: what do I do with this darn thing?As I’ve said, IVs make people nervous. People know they’re not keys, but they’re not ciphertexts either. They wonder: is this an important value? Should I just send it over the wire as it is? Hmm, just to be safe, I’d better encrypt it. Even if I’m wrong, it can’t hurt.

As this Reddit commenter can attest, what you don’t know can hurt you.

Here’s a simple rule of thumb. IVs are not keys. They’re not secret. If you’ve chosen the IV correctly, you can send it along with your ciphertext in the clear. You should authenticate it (see below), but you should never encrypt it.

The worst thing you can do is encrypt your IVs using the same key that you’re using to encrypt messages. The absolute worst example is when you’re using CTR mode encryption, and you make the mistake of encrypting your IV using ECB mode. When you do this, anyone can XOR the first block of ciphertext with the encrypted IV, and obtain the plaintext of that block.

These problems aren’t limited to CTR. My advice: have faith in your IVs, and they’ll have faith in you.

Symmetric Encryption Don’t #4: Don’t forget to authenticate your ciphertexts

Once upon a time cryptographers looked at encryption and authentication as two unrelated operations. Encryption was for protecting the confidentiality of your data, and authentication was used to keep people from tampering with it.*

Nowadays we know that the two are much more tightly linked. You may not care about people tampering with your data, but your encryption scheme just well might. The problem is active attacks. See here and here for just a couple of examples.

To make a long story short, many of the clever attacks on symmetric encryption schemes these days require an attacker to tamper with ciphertexts, then submit them to be decrypted. Even if the decryptor leaks just a tiny bit of information (e.g., is the padding correctly formatted, is the message properly formatted), that can be enough to gradually peel away the encryption and recover the plaintext.

Obviously you don’t want this.

The very elegant solution is to authenticate your ciphertexts, and not just in any willy-nilly fashion. There are basically two approaches that won’t lead to heartburn down the road:

  1. Best: use an authenticated mode of operation, such as GCM, CCM, OCB or EAX. These modes handle encryption and authentication in one go (and they can even authenticate some optional unencrypted ‘associated’ data for you). Best yet, they use a single key.
  2. Almost as good: first encrypt your message using a secure mode of operation (say, CTR), then compute a Message Authentication Code (e.g., HMAC-SHA1) on the resulting ciphertext and its IV. Use two totally different keys to do this. And please, don’t forget to MAC the darn IV!

What you should not do is apply the MAC to the plaintext. First of all, this won’t necessarily prevent active attacks. Padding oracle attacks, for example, can still be leveraged against a scheme that authenticates the message (but not the padding). Furthermore, even if you MAC the padding, there’s still a slim possibility of timing attacks against your implementation.

Symmetric Encryption Don’t #5: Don’t CBC-encrypt in real time

Let me use this space to reiterate that there’s nothing wrong with CBC mode, provided that you use it correctly. The unfortunate thing about CBC mode is that there are many ways to use it incorrectly.

Knowing this, you shouldn’t be surprised to hear that CBC is the most popular mode of operation.

This ‘don’t’ is really a variant of point #2 above. CBC mode can be insecure when an attacker has the ability to submit chosen plaintexts to be encrypted, and if the encryption is on a live stream of data where the adversary can see the ciphertext blocks immediately after they come out (this is called ‘online’ encryption). This is because the adversary may learn the encryption of the previous plaintext block he submitted, which can allow him to craft the next plaintext block in a useful way.

If he can do this, he might be able to take some other ciphertext that he’s intercepted, maul it, and feed it through the encryptor. This kind of attack is challenging, but given the right circumstances it’s possible to decrypt the original message. This attack is called a blockwise chosen plaintext attack, and it’s essentially what the BEAST attack does.

Symmetric Encryption Don’t #6: Don’t share a single key across many devices

A wise man once said that a secret is something you tell one other person. I’m not sure he realized it, but what he was saying is this: don’t put the same symmetric key into a large number of devices (or software instances, etc.) if you want it to remain secret.

About the fastest way to lose security in a system is to spread a single key broadly and widely. It doesn’t matter if you’ve embedded that key inside of a tamper-resistant chip, buried in a block of solid concrete, and/or placed it in a locked file cabinet with a sign saying ‘beware of leopard‘.

The probability of your system being compromised goes up exponentially with each additional copy of that key. If you’re doing this in your current design, think hard about not doing it.

Symmetric Encryption Don’t #7: Don’t pluralize your keys using XOR

(credit)

This one is really a flavor of #5, but a more subtle and stupid one.

Key ‘pluralization’ refers to a process where you obtain multiple distinct keys from a single master key, or ‘seed’. Usually this is done using some strong cryptographic function, for example, a pseudo-random function.

This happens all over the place. For example: TLS does it to derive separate MAC and encryption keys from a master secret. But an extreme type of pluralization often occurs in large-scale systems that provide unique keys to a large number of users.

Think of a cellular provider distributing SIM cards, for example. A provider could generate millions of random authentication keys, distribute them to individual SIM cards, and then store the whole package in a back-end database. This works fine, but they’d have to store this database and do a lookup everytime someone contacts them to authorize a phone call.

Alternatively, they could start with one short master seed, then pluralize to derive each of the SIM keys on demand. This process would take as input the seed plus some auxiliary value (like the subscriber ID), and would output a key for that user. The advantage is that you no longer need to keep a huge database around — just the tiny initial seed.

This approach is so tempting that sometimes people forget about the ‘strong cryptographic function’ part, and they derive their keys using tools that aren’t so secure. For example, they might just XOR the master seed with the subscriber or device ID.

No, you say, nobody could be that dumb. And yet KeeLoq was. Millions of cars keys were provisioned with cryptographic keys that were generated this way. It turns out that if you can extract any one of those per-car keys, and if you know the device’s serial number, you can easily recover the master key — which means you can break into any other car.

Symmetric Encryption Don’t #8: Don’t use DES or RC4 or @#(*&@!

Ok, I said this was mostly going to be about block ciphers. DES fits that category, and I hope you know why not to use it. But RC4 also deserves a special mention just for being the world’s most popular dubious stream cipher.

RC4 shows up everywhere. It shows up in products. It shows up in malware. Basically, it shows up anywhere someone needed crypto, but was too lazy to download a copy of AES. Hell, I’ve used it myself — um, for personal reasons, not for work, mind you.

If you use RC4 correctly, it’s probably ok. For now. The problem is twofold. First of all, cryptanalysts are slowly chipping away at it — sooner or later they’re going to make some serious progress.

The second problem is that it’s not always used securely. Why not? You might as well ask why meth labs explode at a disproportionate rate. My guess is that the set of people who use caution when mixing volatile chemicals simply doesn’t overlap well with the set of people who cook methamphetamine. Ditto RC4 and proper usage.

I could waste a lot of time going on about all of this, but instead I’m just going to quote Thomas Ptacek:

if you see a bespoke crypto design, and it dates from after 2000, and it uses RC4, that’s an audit flag.

Now if Thomas says this about RC4, what do you think he’s going to say about your homebrew protocol based on the Russian GOST cipher? That’s right: nothing nice. Don’t let it happen to you.

In Summary

So this is where I leave you. I doubt this list is complete — I’ll try to update it if I think of anything else. At the very least, if we could fix these issues it would knock out a healthy chunk of the silly crypto issues I see on a day to day basis.

Oh, and a pony too.

Ok, so, I’m a little skeptical that all of these problems will go away that easily, but I’d be content with even just one or two of the points. So if you’re designing a new crypto product and could spare a minute just to glance at the above, you would certainly make my day.

Notes:

* Honestly, there was even a certain amount of confusion on this point. If you look at old protocols like  Needham-Schroeder, you’ll see that they basically treat encryption as authentication. Don’t do this. Most common modes of operation are malleable, meaning that you can mess with the ciphertext, cut and paste different ones, etc.

What is the Random Oracle Model and why should you care? (Part 4)

This is part four of a series on the Random Oracle Model.  See here for the previous posts:

Part 1: An introduction
Part 2: The ROM formalized, a scheme and a proof sketch
Part 3: How we abuse the ROM to make our security proofs work

This is the penultimate post in a series on the Random Oracle Model. I originally meant for this to be short and tidy, something that could be easily digested by a non-expert who was interested in what cryptographers were up to. More to the point, I expected to be done by now.

But the end is in sight, and I feel that there are only a few things left that I want to cover. Even better, one of these topics is of a very practical bent, which is in keeping with the theme of this blog.

Specifically: I keep talking about the random oracle model, but what impact does it have on anyone’s life? Where is this thing used?

Giving a complete answer to that question is hard — it’s kind of like coming up with a list of all the foods that have sodium benzoate in their ingredients list. So in this post I’m going to at least hit at least a couple of the high points, meaning: the schemes that are probably most relevant to our daily security lives.

RSA Signing and Encryption

RSA is probably the most famous cryptosystem in use today. I don’t know exactly why it’s so popular, but I suspect there are few reasons. First of all, RSA is flexible; it provides signature and encryption in one scheme. It’s relatively simple — you can compute simple encryptions with a calculator. It’s been around for a while and hasn’t been broken yet. And I would be remiss if I didn’t mention that there are no current patents on RSA.

This is all great, but in some sense it’s also too bad. Over the past twenty years, attacks on the factoring problem (and by implication, RSA) have been getting better at the margins. This means that RSA key sizes have had to get bigger just to keep up. Sooner or later we’re going to lose this game.*

More interesting (to me) is RSA’s status as a sort-of-provably-secure cryptosystem. There’s a general understanding that RSA encryption is provably secure under the hardness of the RSA problem. However, this really isn’t true, at least given the way that most people have traditionally used RSA. You can get a reduction to the RSA assumption, but you need to take some very specific steps. Most importantly: you need to invoke the random oracle model.

To explain all this, I need to take you back in time to the late 1990s and I need to talk about padding.

If you’ve ever looked at a real RSA implementation, you probably know that we don’t use plain-old ‘textbook’ RSA (“m^e mod N“) to encrypt or sign raw messages. There are lots of reasons for this. One is that plain-old RSA isn’t randomized, meaning that a given message will always encrypt to the same ciphertext.

Another reason is that RSA is malleable, meaning that you can mess with ciphertexts and signatures in creative ways — for example, by multiplying them by constants of your choice. When you do this, the decrypted (resp: verified) message will be altered in predictable ways. This is bad for encryption. It’s downright awful for signatures.

We deal with these problems by applying padding to the message before encrypting or signing it. Padding schemes can add randomness, apply hashing in the case of signature, and most importantly, they typically add structure that lets us know when a message has been tampered with.

Some historical background: RSA before the ROM

The first widely-used, standard padding schemes were described in RSA’s PKCS#1 standard. Nowadays we refer to these as the “PKCS #1 v1.5” standards, with the implication that the standard (now at version 2.1) has left them behind.

Back in the 90s these standards were the only game in town. Sure, there were a few pedantic cryptographers who objected to the lack of formal security justification for the standards. But these troublemakers were mainly confined to academic institutions, which meant that the real security professionals could get on with business.

And that business was to implement the PKCS padding standards everywhere. PKCS #1 v1.5 padding still turns up in products that I evaluate. Most notably at the time, it was all over a young standard known as SSL, which some people were using to encrypt credit card numbers traveling over the Internet.

Danielbleichen
Daniel Bleichenbacher
shortly after his arrest. Or
possibly just posing for a
Bell Labs publicity photo.

Now, I said that almost nobody of a practical bent had a problem with PKCS. One notable exception was a bright cryptographer from Bell Labs named Daniel Bleichenbacher.

Dr. Bleichenbacher had a real problem with the PKCS padding standards. In fact, one could say that he made it his life’s mission to destroy them. This vendetta reached its zenith in 2006, when he showed how to break common implementations of PKCS signature with a pencil and paper, shortly before driving a fireworks-laden minivan into the headquarters of RSA Data Security.

(Ok, the last part did not happen. But the rest of it did.)

Bleichenbacher took his first crack at PKCS in CRYPTO 1998. In a surprisingly readable paper, he proposed the first practical adaptive chosen ciphertext attack against “protocols using the PKCS #1” encryption standard. Since, as I’ve just mentioned, the major protocol that met this description was SSL, it was a pretty big deal.

The attack goes something like this.

Whenever somebody sends their credit card info over an SSL connection to a web server, their browser and server execute a handshake protocol to derive a secret key. In particular, at one step of the protocol, the browser encrypts a very important value called the “pre-master secret” under the server’s RSA public key, and ships the resulting ciphertext to it over net.

This encryption is important, because anyone who decrypts that ciphertext — immediately, or five years later — can ultimately recover the SSL transport key, and hence decrypt all communications between the server and browser.

What Bleichenbacher pointed out was very specific to how most web servers processed RSA messages. Specifically, every time the server receives an RSA ciphertext, it first decrypts it, and then checks that the padding is valid. For a typical RSA key, PKCS #1 padding looks like this:

0x 00 02 { at least 8 non-zero random bytes } 00 { message }
When an SSL webserver doesn’t like the padding it sees, it may kick back a specific ‘bad padding’ error. Bleichenbacher first showed that if he could intercept a legitimate RSA ciphertext “C = M^e mod N” on the wire, then he could ‘maul’ it by multiplying it by a chosen value. In other words, given some C, he would pick some “s” and compute:
C' = C * s^e mod N

This value C’ will decrypt to “M * s mod N”. Bleichenbacher showed that for some values of “s”, this mauled message might also be a valid PKCS-padded message, meaning that it would begin with “0x 00 02” etc. This wasn’t all that unlikely, mainly because just looking at a couple of bytes was a pretty crappy padding check in the first place.

It was quite common for servers to leak the result of the padding check back to the sender, by way of some specialized error code like “BAD PADDING”. Even if they didn’t do that, you could sometimes detect a failure in the padding check by measuring the time it took the server to get back to you.

Bleichenbacher’s main trick was noting that the “s” values that led to a successful padding check could also be used to learn something about the original message M. To make a long story short, he showed how to choose these values adaptively in such a way as to gradually zero in on the actual plaintext, until he had just one candidate. And that was the ballgame.

The actual attack could require a couple of million decryption queries, on average. This sounds like a lot, but it meant you could decrypt an SSL session overnight, as long as nobody was paying attention to the server logs.

Random Oracles to the Rescue

The Bleichenbacher attack was a big deal for a whole variety of reasons. First of all, it was practical. It worked on a widely-deployed system, and it could be implemented and executed even by non-experts. It completely negated the protections offered by SSL, unless you were willing to monitor your SSL webserver literally night and day.

But to cryptographers the attack had special significance. First, it demonstrated that adaptive-chosen ciphertext attacks were a real problem, not just some airy academic topic. I suspect that even the cryptographers who worked in this area were a bit surprised by this. Some probably started looking for less useful topics to work on.

More importantly, the Bleichenbacher demonstration was seen as a victory for proponents of provable security. Up until now, their concerns had mostly fallen on deaf ears. Now a lot of people were listening.

And even better, the crypto research community had something to say to them. The overwhelming consensus was to immediately switch to a new RSA padding scheme that had been proposed all the way back in 1994. This scheme was called Optimal Asymmetric Encryption Padding (OAEP), and it was only a little bit more complex than PKCS #1. Even better, and unlike PKCS #1, RSA encryption with OAEP could be provably reduced to the hardness of the RSA problem, in the random oracle model. 

The success of OAEP also led to the adoption of the PSS padding scheme, which did essentially the same thing for RSA signatures.

OAEP padding, courtesy Wikipedia.  G and H are independent hash functions with different output lengths.

Now, to hear some people tell it, this is where the story ends. And it’s a good story — bad, unproven security protocol gets broken. New, provably-secure protocol steps in and saves the day.

And for the most part the story is true. With some important caveats.

The first of these is implementation-related. Just as PKCS #1 was broken because the server gave too many detailed errors, even OAEP encryption can break if the server leaks too much info on its error conditions. And when OAEP implementations go bad, they can really go bad. James Manger showed that you can break 1024-bit RSA-OAEP in a mere 1100 queries, assuming your server leaks a little bit too much information on why a given decryption attempt went wrong.****

But even if you do everything correctly, the OAEP security proof only holds in the random oracle model. That means that whatever guarantees it supposedly offers are only valid if the hash function is ideal. That’s a good heuristic, meaning that OAEP is unlikely to be laden with obvious flaws.

But if you dig into the OAEP security proof, you’ll see that it’s using random oracles in about the strongest ways imaginable. The essential concept of OAEP is to use a pair of hash functions to construct a tiny, invertible Feistel network. The beauty is that every time you encrypt, you’re essentially sending the message (and some randomness) directly “through” the random oracle, in a way that permits all sorts of nonsense.

The reduction proof can then see what the adversary’s encrypting, which turns out to be very useful when you’re building a system that’s secure against chosen ciphertext attacks. This would never work if you implemented OAEP with a real hash function, like the ones that are actually used to implement it in real life.

So in one very real sense, we still don’t really have a practical, provably-secure way to encrypt with RSA. Moreover, there’s little reason to believe that we ever will, given a slew of impossibility results that seem to keep getting in the way.*****

All of which raises an important question. Given all the limitations of RSA, why are we so darn attached to it?

The Digital Signature Algorithm (DSA/DSS)

You might find it a bit strange that I’m mentioning DSA in a discussion about provable security. This is mainly because, unlike the Elgamal signature on which DSA is based, the DSA standard has no security proof whatsoever.******

There’s no really defensible reason for this. As best I can tell, NIST took a look at the Elgamal signature and thought it was cute, but the signatures were a little bit too long. So they took some scissors to it and produced something that looks basically the same, but doesn’t have the very nice reduction to the Discrete Logarithm assumption that Elgamal did.

This kind of behavior is par for the course, and honestly it gets me a little down on government standards bodies.

For the record, while DSA isn’t really provably-secure at all, the Elgamal scheme is. But unfortunately, the Elgamal scheme is only provably secure in the random oracle model. This means that if your hash function has the very nice property of being a perfectly random function and programmable, Elgamal signatures can be reduced to the hardness of the Discrete Logarithm problem. But otherwise you’re on your own.

Key Derivation and Beyond

There are probably a zillion cryptosystems that ought to be mentioned here, and we can’t cover them all. Still, there’s one more class of ‘things that hash functions are used for’ that probably isn’t really secure at all, unless you’re willing to make some pretty strong assumptions about the properties of your hash function.

The example I’m thinking of is the use of hashing to derive cryptographic keys. For example, many password-based encryption schemes use a hash function to combine a password and some salt to derive a key for encryption. This approach seems to work ok in most cases (assuming a high entropy password), but it doesn’t have any strong theoretical legs to stand on.

In general, if you’re trying to extract a uniform random key from from a ‘lumpy’, non-uniform source like a password, the proper tool to use is something called a randomness extractor. These can be implemented in the standard model (no random oracles), but all of the existing constructions pretty much suck. This sounds rude, but it’s actually a technical term that cryptographers use to indicate that a scheme is complicated and slow.

So in real life, nobody uses these things. Instead they just hash the password and salt together, and assume that the result will be pretty good. If they’re feeling frisky they might even hash it a bunch of times, which is the crypto equivalent of shooting a turkey with an AK-47. It’s probably just fine, although technically you can never rule out bulletproof turkeys.*******

Whenever people bother to argue formally about the security of schemes like this (which is, essentially, never), the usual argument goes like this: let’s just assume the hash function is a random oracle. In the random oracle model, of course, every hash function is a perfect extractor. Stick any high-entropy source into an ideal hash function, no matter how ‘lumpy’ or ‘weird’ the input is, and you get a fantastic key out the other end.

So even if your favorite key derivation has no formal security proof whatsoever, you can bet somebody, somewhere has made this argument, if only to help themselves sleep better at night.

In Summary

This was supposed to be a post about the random oracle model, but I feel that it took on a life of its own. That’s not a bad thing. I promised that I’d spend some time talking about practical crypto, and I’ve certainly accomplished that.

Although I could say a million things about the random oracle model, I only have one more post left in me. And in some ways, this is going to be the most important post of all.

You see, we always knew that this ride wouldn’t last forever, we just thought we had more time. Unfortunately, the end is nigh. Just like the imaginary city that Leonardo de Caprio explored during the boring part of Inception, the random oracle model is collapsing under the weight of its own contradictions.

This collapse — and what it means for cryptographers, security professionals, and everyone else — will be the subject of my final post.

Notes:

* NIST has begun to deprecate RSA in its FIPS standards. You can use it in some places, but it’s no longer a major supported algorithm.

**** Specifically, the OAEP decoding algorithm has a step in which it decodes the padded plaintext (a value between 0 and N-1) into a bitstring. This requires it to check that the decrypted RSA value is less than 2^n, where n is some number of bits that can be reliably encoded within the range. The Manger attack assumes that the decoding algorithm might leak the result of this check.

***** Although, on the signature side things are a little better. Hohenberger and Waters recently proposed a hash-and-sign RSA signature that’s secure under the RSA assumption without random oracles. This is really a very neat result. Unfortunately it’s inefficient as hell.

****** This is not to say people haven’t tried to piece a proof together. You can do it, if you’re willing to work in the random oracle model, and also assume the existence of leprechauns and unicorns and similarly unrealistic things.

******* In fact, repeated hashing is usually just as as much about making the hash process slow as it is about achieving a strong key. This can be helpful in thwarting dictionary attacks.