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.

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 }

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.

This series concludes in Part 5.

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.

This is part 3 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

I began this series in the hope of writing a true layperson’s introduction to the Random Oracle Model. At the outset I figured I probably knock this thing out in a couple of not-too-technical posts. Yet, here I am at post three, and there’s still a big chunk of technical left to go.

Please bear with me. We’re going to get back to some solid, practical crypto with the next post in the series.

A quick recap

In the last two posts we’ve covered a bit of ground. We talked about cryptographic hash functions and their properties, and discussed why the cryptographer’s ‘ideal’ hash function would be a random function. We noted that random functions would never work in real life (too big to store, too slow to compute), so we came to a strange resolution: we would pretend that our hashes were random functions, just for the purposes of our security analysis. Then of course we would use real hash functions like SHA.

Of course, even this required us to tamper with the fabric of the universe, since we want to restrict our ‘adversaries’ to running in a reasonable amount of time, and they can’t do that if they’re busy evaluating random functions. So we created a new model of computation (aka ‘thought experiment’) called the Random Oracle Model. In this model all hashing is computed by a magical third party called an oracle.

If you know a little about the random oracle model, say from reading the previous posts, you could be forgiven for thinking that it isn’t all that bad. Basically we’re assuming that hash functions are super-duper “random”. Maybe a little more so than a real function can be, but big deal.

But unfortunately it’s much more than that.

The world’s shortest lesson on provable security

To explain what I mean, we first need to understand a little about provable security, and particularly, a type of proof called a reduction proof.

When we say that an encryption scheme is “provably secure”, we usually mean that it’s secure under some assumption. For most practical schemes the assumption is mathematical in nature. For example, we might found an encryption scheme on the assumption that it’s hard to factor large composite numbers, or to find the shortest vector in a lattice. In this case ‘hard’ doesn’t mean ‘I can’t figure out how to do it’. It means: there exists no (efficient) algorithm that can do it.¹

Now, I mentioned that these are assumptions. We don’t absolutely know that these problems are hard. However, we like to think that if some bright people have looked at the problem for a while, and nobody has made any progress towards solving it, that means it’s probably not easy. In some cases the problem may even fall into a useful class of problems, i.e., it may be NP-Hard.

Even if you’re not willing to blindly trust in these assumptions, security proofs are still useful. Analyzing a new cryptosystem can soak up huge amounts of time and energy. If we can at least ‘reduce’ each new scheme to one of a small number of mathematical problems, we can pour our brainpower into attacking just those problems, knowing that our work will apply to every scheme that uses them.

All of this brings me to my main point, namely, how do these proofs work. Getting specific, the general flow of such a proof is as follows:

1. Assume that problem X is hard.¹
2. Show that if there exists an (efficient) algorithm that “breaks” our cryptographic scheme, then there exists an (efficient) algorithm that solves problem X.
3. Snottily point out that (2) means if the scheme can be broken, then problem X can’t be hard.

Clearly point (3) cannot be true if point (1) is. Following the logic, this allows us to conclude that if Problem X is hard, then there can’t be an algorithm that breaks our encryption scheme.

Of course I haven’t explained how to actually accomplish step (2), which is pretty important. It’s also the beautiful part. You see, in most reductions, step (2) consists of actually writing an efficient algorithm that solves problem X.

You probably think I’m crazy. I just claimed that problem X can’t be efficiently solved, now I’m telling you that we write an algorithm for solving it. But the genius of it is that our solver algorithm won’t quite work. It’s missing an important subroutine.

That subroutine is identical — at the API level — to an algorithm that ‘breaks’ our encryption scheme.

Let me be more clear about this. We cannot, for example, have a step in our ‘solver’ algorithm where we decompile the breaker algorithm, or peek inside its internal memory registers, and then assume that they’ll contain a partial result we need.

This is because our reduction only works if it works with every possible algorithm that breaks the scheme. Since we can’t guess a priori how such an algorithm might work internally, we can’t depend on its internal workings. The breaker algorithm could hypothetically be horrifically obfuscated, to the point where we couldn’t understand it even if we held the code in our hands.

Thus in a traditional black box reduction, we can count on the breaker algorithm having a standard “API” (which we’ll define at some point). This typically takes in public keys and/or ciphertexts (or signatures, etc.) It outputs some useful information that constitutes our definition of ‘breaking’. And though it doesn’t always need to succeed, we expect that it does so with reasonable probability. But everything that happens inside the algorithm must be hidden from us.

Dirty laundry

You wouldn’t think this has anything to do with provable security.

Let’s pause for a moment to consider some related problems in the area of celebrity journalism.

Imagine you’re a muckraking celebrity reporter who’s been assigned to get a scoop on Brad Pitt and Angelina Jolie’s latest adopted baby. The Pitt/Jolies are extremely private, and won’t even acknowledge that they’re adopting. You’re a clever reporter, and more importantly, you have no morals.

You know that if you could just get a peek at the family laundry, you’d have your whole story. Sex, size, weight, favorite color. Even diet (Angelina insists on eco-safe cloth diapers). In a perfect world you could drive over to Pitt/Jolie’s laundry company, slip someone $500, and lo — your whole story would be there in the clothes. If you were really devious, you could start your own celebrity laundry service and trick them into sending it right to you.

But this is all wishful thinking. Pitt and Jolie don’t send out their laundry — they have it done at home.  In truth, you’re not sure that they even do laundry. You heard a rumor that Angelina has her clothes ritually burned after each use.

In case you don’t see the relevance, this is an analogy to reduction proofs. To you, the ‘breaker’ algorithm is a black box. You can see inputs go in, and see what comes out, but you can’t see what it’s doing in between. If your reduction depends on peeking at its dirty laundry, you’d better come up with a better reduction. It does its own laundry.

Back to the Random Oracle Model

The Random Oracle Model is different. In my previous post I explained that it’s just like the real world, with one exception: nobody can compute hashes by themselves. Every party — including the adversary (synonymous with ‘breaker’ algorithm) — must hash by sending messages to a special outside party. This party computes the hashes using a random function, and sends them back to the caller.

To make this abundantly clear, in the Random Oracle Model, everyone sends out their laundry.

The Random Oracle Model. The oracle computes hashes for all parties, including the adversary.

Speaking more formally, in the Random Oracle Model, an adversary (aka our ‘breaker’ algorithm) is no longer quite a black box. In one very important way we have visibility into it. It must call outside of itself if it ever wants to hash something.

If we’re building a reduction, that means we can take advantage of the ‘extra’ info that leaks from these calls, just as our gossip reporter could take advantage of celebrities’ laundry. We know that the algorithm has to make these hash calls, so there must exist a ‘port’ in the API for it to make them. Once we make this stipulation, our reduction can tap into this port and intercept the adversary’s hash calls to see which messages it’s asking for, and possibly even tamper with the results it gets back.

In an extreme case, our reduction can even run its own fake ‘oracle’ (aka laundry service), as long as we always hand back convincing responses.

And while this may not seem a big deal, it really is. Just as Brangelina’s dirty laundry could reveal major details about the stars’ private life, the choice of which messages a ‘breaker’ algorithm chooses to hash can reveal major details about what it’s thinking internally. By tampering with those responses we can also fundamentally change its operation. These details can be the difference between a reduction proof that works, and one that doesn’t.

Taking Stock

At this point, I think it’s worth taking a breath and asking what we’ve gotten ourselves into here. When we started with this nonsense, all we wanted was a better hash function. One that looked slightly more ‘random’ than any real function we could construct.

Along the way we realized that random functions were totally impractical. Even to pretend we could use them, we had to tamper with our computational model and “pull the random function” outside of the parties. After all, they run in polynomial time and couldn’t possibly evaluate such a function.

Each of these steps seemed perfectly reasonable, and yet somewhere we jumped the shark. We took the most sacrosanct principle of reductionist security and violated it. Instead of “our argument works with any adversary”, we now say “our argument works only with adversaries who kindly tell us whatever and whenever they need to hash”.

Real adversaries don’t work like this. If someone comes up with an algorithm that breaks an implementation of RSA-OAEP that uses a real hash function (say SHA256), that algorithm won’t need to tell us what it’s hashing. It will just do it internally. And if its code is obfuscated, we won’t be even able to connect it to our reduction, if our reduction depends on knowing (or tampering with) the hash calls.

An Example: RSA Signing

At this point I’ve run out of ways to talk about the Random Oracle Model without actually invoking a real scheme. So let’s bring this back to something concrete.

The RSA scheme is probably the most famous cryptosystem of the modern age. Many people mistakenly believe that RSA is based on the hardness of factoring large integers. In fact, that’s not quite accurate. RSA is actually based on a slightly different, but related assumption not-creatively named the “RSA assumption“.

This assumption holds that the following problem is fundamentally hard, at least when the numbers get sufficiently large.¹ Given three values (N, e, M), where:

1. N is the product of two prime numbers (p, q) that you don’t know.
2. 2 < e < N and gcd(e, (p-1)(q-1)) = 1.
3. 0 <= M < N.

The problem is to find a value “S” such that S^e mod N = M.  ²

It’s conjectured that this problem is hard¹ if you only have the values given above. However, if you know (p, q) or an additional ‘secret key’ derived from those values, it’s quite easy to solve.

The RSA signature scheme depends on this. In a textbook RSA signature, you “sign” a message by first encoding it as an integer m, such that 0 <= m < N.  Then, using your secret key you compute a ‘signature’ “s”, such that s^e mod N = m. (See here for the exact algorithm.)

The intuitive argument for RSA signatures rests on three legs:

1. Since only you know the secret key, it’s easy for you to “sign” messages of your choice.
2. Anybody else can verify your signatures given (m, s) and the “public key” (N, e).
3. Intuitively, nobody else can sign messages on your behalf (this is known as ‘forging’), because doing so without the secret key would be equivalent to solving the RSA problem.

This is, of course, total nonsense.

If you look carefully, what the RSA assumption actually implies is that it’s hard to come up with a “signature”(S) on a particular message (M). If the adversary has freedom to choose the message himself, then it’s easy for him to come up with a whole bunch of ‘signed messages’. This makes textbook RSA signatures pretty useless.³

More importantly, to prove that RSA signatures are secure under the RSA assumption, we can’t just have the adversary spitting out any old message/signature pair. To make a reduction work, we must use the adversary to solve a specific RSA problem instance (N, e, M). That means whatever the adversary outputs, we must be able to use that value in order to compute an “S” that satisfies S^e mod N = M.

And now here, finally is where the hash functions come through for us.

Adding a Hash

I’ve mentioned previously that most signature schemes don’t literally sign a raw message. Rather, they sign the hash of a message. This is convenient, since messages can be large and hashes are usually small. But in the Random Oracle Model it has a special significance.

Let’s say that we have a hash function H() with the odd property that it outputs an integer between 0 and N-1. This is called a “full domain hash”. This is a little unusual for a hash function, but I promise that such things can be built out of more “traditional” hash functions like SHA.

Instead of signing the message directly, we could have our signer first hash the message (which can now be an arbitrary string), and sign the resulting hash. More formally, a signature “s” must now satisfy:

s^e mod N = H(message)

Can we prove that this scheme is secure under the RSA assumption?

A proof sketch

Imagine that A is some algorithm that breaks the signature scheme, meaning that it takes in a public key (N, e), and eventually outputs an “existential forgery”, i.e., any pair (message, s’) that satisfies the verification equation above.

Our goal is to design a solving algorithm for that can take in an arbitrary RSA problem instance (N, e, M) and somehow force A to help us solve it. Our goal is to eventually spit out a value S where S^e mod N = M.

First, our solver will send A a “public key” consisting of (N, e). Since we’re in the Random Oracle Model, A will eventually have to hash something. Whenever A asks to hash a message, we’ll intercept its attempt to call the oracle, pick a random value 0 <= r < N and answer its query as follows:

H(message) = M * r^e mod N

I will claim that since “r” is random, then our “hash” result is also randomly-distributed, and thus “looks right” to A. So he won’t twig to what we’re doing. Most importantly, we’ve managed to tie every single hash value back to the one value “M” that we took from the RSA problem instance. Of course, we’ll also store each value “r” so we can retrieve it later.

We assumed that eventually A will output a valid “forged” message/signature pair of the form (message, s’), where this pair satisfies s’^e mod N = H(message). If this is the case, then all we have to do is look up the “r” value used to compute H(message) and output:

S = s’ / r mod N         (or more accurately, s’ * inverse(r) mod N)

This is the answer to our RSA problem instance, since S^e mod N = M. ⁴, ⁵

Why does this work? Well, let’s simplify the equation “s’^e mod N = H(message)” a bit:

s’^e mod N                            = H(message)
s’^e mod N                            = M * r^e mod N         (this is the hash we computed)
s’                                            = M^{1/e} * r mod N  (raising both sides to the inverse of e)
        s’                                            = S * r mod N              (because S = M^{1/e}.)

A full version of this proof can be found here. None of it works in the real world, of course. The minute you sub in a real hash function, this whole proof is bunk.

A few notes and a conclusion

This has been a long post; even my footnotes are getting out of control. I do hope I was able to make my main point, which is that the Random Oracle Model is both deeply unnatural, and deeply useful to cryptographers writing security proofs.

This is a dangerous combination, since it allows us to take shortcuts and make assumptions, that simply can’t be supported in the real world we live in. And yet, it’s so powerful that we can find it hard to stop.

More to the point, even when cryptographers stop relying on this crutch (and it’s started to happen), we have a hard time convincing end users to get rid of schemes that have been proven in the ROM. Heck, we have a hard time convincing our friends in the systems security community. They think we’re nuts.

And it’s hard to blame them. Even when we have proper replacements, they’re usually funny looking, almost always more “costly”, and sometimes rest on bizarre new mathematical assumptions that people don’t trust. Plus, it’s not like the random oracle schemes are broken.

In my next post I’m going to talk about all this, pull back from the crypto a bit, and focus on this dispute. I’ll also talk a bit about the state of the art in ROM/non-ROM schemes.

And oh yes, I’ll explain why cryptographers have started to get religion on this point.  Hint: someone proved something. Something very bad for the ROM.

Click here for the next post in this series.

Notes:

1. More formally, saying that a problem is “hard” means that that all probabilistic polynomial time Turing machines solve it with at most negligible probability.

2. For a quick explanation of modular arithmetic, see here.

3. For example, he can pick an arbitrary number as “S”, then — using only the public key — work backwards to compute “M” as M = S^e mod N. This pair (M, S) is a valid message/signature pair. Similarly, he can mangle legitimate message/signature pairs in various ways, to get new ones.

4. In practice, there’s no division mod N. Instead, we compute the inverse of “r” mod N, then multiply by that number.

5. In a real proof, we would also consider the possibility that the adversary can ask for and obtain signatures on chosen messages. Our reduction would have to answer these requests. This can be done, but it adds a bit of complexity. See the full proof for some details on this process.

This is part 2 of a series on the Random Oracle Model.  See “Part 1: An introduction” for the previous post.

In a previous post I promised to explain what the Random Oracle Model is, and — more importantly — why you should care about it.  I think I made a good start, but I realize that I haven’t actually answered either of these questions.

Instead what I did is talk a lot about hash functions. I described what an ideal hash function would look like: namely, a random function.  Then I spent most of the post explaining why random functions were totally impractical (recap: too big to store, too slow to compute).

At the end of it all, I left us with the following conclusions: random functions would certainly make great hash functions, but unfortunately we can’t use them in real life. Still, if we can’t get a security proof any other way, it might just be useful to pretend that a hash function can behave like a random function. Of course, when we actually deploy the scheme we’ll have to use a real hash function like SHA or RIPEMD — definitely not random functions — and it’s not clear what our proof would mean in that case.

Still, this isn’t totally useless. If we can accomplish such a security proof, we can at least rule out the “obvious” attacks (based on the kind of glitches that real scheme designers tend to make). Any specific attack on the scheme would essentially have to have something to do with the properties of the hash function. This is still a good heuristic.

As you can see, this has gotten somewhat technical, and it’s going to get a bit more technical through to the end of the post. If you’ve gotten enough background to get the gist of the thing, feel free to skip on to the next post in this series, in which I’ll talk about where this model is used (hint all modern RSA signing and encryption!), and what it means for cryptography in practice.

Brass tacks

A security proof typically considers the interaction of two or more parties, one of whom we refer to as the adversary. In a typical proof, most of the players are “honest”, meaning they’ll operate according to a defined cryptographic protocol. The adversary, on the other hand, can do anything she wants. Her goal is to break the scheme.

Usually we spell out a very specific game that the parties will play.  For an encryption scheme, the rules of this game allow the adversary to do things that she might be able to do in a “real world” environment. For example: she might be able to obtain the encryption of chosen plaintexts and/or the decryption of chosen ciphertexts. In most cases she’ll intercept a legitimate ciphertext transmitted by an honest encryptor. Typically her goal is to learn (something about) the underlying plaintext.

It’s standard to assume that the parties will all know the scheme or protocol, including how to compute the hash function if one is used. This is a common-sense assumption, sometimes referred to as Kerckhoffs’s Principle.  Moreover, we generally assume that the adversary is limited in some way — she doesn’t have unlimited computational power or time, which means she can’t just brute force the decryption key.

Security proof in the random oracle model.  All parties (Encryptor, Decryptor and Adversary) can call out to the Random Oracle, which computes the hash function for them and provides consistent responses to all parties.

A Random Oracle security proof is just like this, but we make one further tweak. Even though everyone is allowed to compute the hash function, they can’t do it by themselves. Hashing is done by a new magical party called the “oracle”. If any party needs to hash something, they ship the message (over an imaginary secure channel) to the oracle, who computes the hash and sends it back to them.

Why the oracle? Well, since the oracle is “outside” of the parties, they no longer need to carry around a description of the hash function, and they don’t need to do the work of computing it.  This is good because — as I mentioned in the previous post — the full description of a random function is ridiculously large, and consequently takes an insane of amount of time to compute. By sticking it into the oracle, we can handwave away that ugliness.

We’ll place two restrictions on the random oracle. First, it must implement a genuine random function (sampled at the beginning of the game), with the same input/output profile as a realistic hash function we might use (e.g., 256-bit output strings if we’re eventually going to implement with SHA256).

Secondly, the responses given by the oracle must be consistent.  In other words, just as hashing “Peter Piper” through SHA1 will always produce 1c6244929dc8216f5c1024eebefb5cb73c378431,* regardless of who does it, sending a given string through the random oracle will produce the same result, regardless of which party asks for it.

Lazy Afternoon

1. At the beginning of the game the oracle’s table is empty.
2. Whenever some party asks the oracle to hash a message, the oracle first checks to see if that input value is already stored in the table.
3. If not, it generates a random output string, stores the input message and the new output string in its table, and returns the output string to the caller.
4. If the oracle does find the input value in the table, it returns output value that’s already stored there.

Back to Delphia

1. Pick a random secret key (say 128 bits long) and share it with both the sender and receiver.

    Set IV to 1.

2. Cut a plaintext message into equal-length blocks M1, …, MN,

    where every block is exactly as long as the output of the hash function.

3. Using || to indicate concatenation and ⊕ for exclusive-OR, encrypt the message as follows:

      C1 = H(key || IV)       ⊕ M1

      C2 = H(key || IV+1)   ⊕ M2

      …

      CN = H(key || IV+N) ⊕ MN

4. Output (IV, C1, C2, ..., CN) as the ciphertext.

5. Make sure to set IV = (IV+N+1) before we encrypt the next message.

A proof sketch!

Some honest party — the encryptor — is going to encrypt a message.  The adversary will intercept the ciphertext.  The adversary “wins” if he can learn any information about the underlying plaintext besides its length.

Recall that we’re in the magical Random Oracle Model. This is just like the real world, except whenever any party computes the hash function H(), s/he’s actually issuing a call out to the oracle, who will do all the work of hashing using a random function. Everyone can call the oracle, even the adversary.

Following the scheme description above, the encryptor first chooses a random key (step 1). He divides his plaintext up into blocks (step 2). For each block i = 1 to N, he queries the oracle to obtain H(key || i).  Finally, he XORs the received hashes with the blocks of the plaintext (step 3), and sends the ciphertext (C1, …, CN) out such that the adversary intercepts it (step 4).

1. Internally, the oracle starts with an empty table.
2. Each time the oracle receives a new query of the form “key || i” from the encryptor, it produces a new, perfectly random string for the output value. It stores both input and output in its table, and sends the output back to the encryptor.
3. The encryptor forms the ciphertext blocks (C1, …, CN) by XORing each message block with one of these random strings.
4. The encryptor never asks for the same input string twice, because the IV is always incremented.And finally, we make the most important observation:
5. XORing a message with a secret, perfectly random string is a very effective way to encrypt it. In fact, it’s a One Time Pad. As long as the adversary does not know the random string, the resulting ciphertext is itself randomly-distributed, and thus reveals no information about the underlying message (other than its length).

The Final Analysis

Part (b) is a little harder.  Is there any way the Adversary could learn the oracle’s output for H(key || i) for even one value of i from 1 to N? The oracle does not make its table public, and the adversary can’t “listen in” on the hash calls that the encryptor made.

Thinking about this a little harder, you’ll realize that there’s exactly one way that the adversary could learn one of those strings: she can query the oracle too. Specifically, all she has to do is query the oracle on “key || i” for any 1 <= i <= N and she’ll get back one of the strings that the encryptor used to encrypt the ciphertext. If the adversary learns one of these strings, she can easily recover (at least part of) the plaintext, and our argument doesn’t work anymore.

There’s one obvious problem with this, at least from the adversary’s point of view: she doesn’t know the key.

So in order to query on “key || i”, the adversary would have to guess the key.  Every time she submits a guess “guess || i” to the oracle she’ll either be wrong — in which case she gets back a useless random string. Or she’ll be right, in which case our scheme won’t be secure anymore.

But fortunately for us, the key is random, and quite big (128 bits). This tells us something about the adversary’s probability of success.

Specifically: if she makes exactly one guess, her probability of guessing the right key is quite small: one in the number of possible keys.  For our specific example, her success probability would be 1/(2^128), which is astronomically small. Or course, she could try guessing more than once; if makes, say q guesses, her success probability rises to q/(2^128).

The basic assumption we started with is that the adversary is somehow limited in her computational power. This means she can only perform a reasonable number of hashes. In a formal security proof this is where we might invoke polynomial vs. exponential time. But rather than do that, let’s just plug in some concrete numbers.

Let’s assume that the adversary only has time to compute 2^40 (1.1 trillion) hashes. Assuming we used a 128-bit key, then her probability of guessing the key is at most (2^40)/(2^128) = 1/(2^88).  This is still a pretty tiny number.

Think a real-world adversary might be able to compute more than 2^40 hashes? No problem.  Plug in your own numbers — the calculation stays the same. And if you think the scheme isn’t secure enough, you can always try making the key longer.

In Summary

Depending on your point of view, this may have seemed a bit technical. Or maybe not. In any case, it definitely went a bit past the “layperson’s introduction” I promised in the previous post. Moreover, it wasn’t technical enough, in that it didn’t capture all of the ways that cryptographers can “cheat” when using the random oracle model.***

I’m going to do my best to up for that in the next post, where we’ll talk a bit about some real schemes with proofs in the random oracle model, and — more importantly — why cryptographers are willing to put up with this kind of thing.

See the next post: Part 3, in which the true nature of the Random Oracle Model is revealed.

Notes:

* I got this result from an online SHA1 calculator of untrusted veracity.  YMMV.

** Of course, in a real proof we’d be more formal, and we’d also consider the possibility that an adversary might at least be able to obtain the encryption of some chosen plaintexts.  This would be captured in the security game we use.

This is the first in a series of posts on the Random Oracle Model.  This might get a little wonky for some people’s tastes, so if you’re not interested in provable security, no problem.  I’ll be back with more on software and physical security once I get this out of my system.

It happens that I’m scheduled to teach a class today onprovable security, and something called the “Random Oracle Model”.  While getting my thoughts together, it occurred to me that a) this subject might be of interest to people who aren’t my grad students, and b) there doesn’t seem to be a good “layperson’s” introduction to it.For the most part I like to talk about how cryptography gets implemented.  But implementation doesn’t matter a lick if you’re starting with insecure primitives.

So at the risk of alienating my tiny readership, I’m going to take a break from our regularly scheduled “how cryptographic systems go bad” programming to talk about this wonkish subject — which, as we’ll see in a bit, is itself just another flavor of how crypto goes wrong.

Hash Functions for Dummies

Before we talk about Random Oracles, we first need to discuss hash functions.  These are functions that take a (potentially) long input, and ‘hash’ it down into a fixed-size value that we refer to as a Message Digest.

We use hash functions a lot in cryptography.  They get the most press for turning up in digital signature schemes, but they also make an appearance in many encryption schemes.  In fact, throughout the field, it’s pretty hard to throw a stone without hitting one.

For the most part, a cryptographic hash function has to satisfy at least some of the following properties.  First of all, we expect it to be “one way”, meaning that it’s hard to ‘invert’ the function, i.e., to find the original message given only a Message Digest.

Secondly, a hash function should be “collision resistant”.  In other words, it should be hard to find two different messages (M, M’) such that Hash(M) == Hash(M’).  This property is very important for digital signatures, since we typically don’t sign the message directly, we sign a hash of the message.  If an adversary can find two messages that hash to the same value, then a signature on (the hash of) one message is also a signature on the other.  In practice this can lead to bad consequences.

Sometimes we demand even more from our hash functions.  The tricky part is knowing how much more we can ask.  To illustrate, let me give an example.

Encryption in Delphia

Imagine that you live in Delphia, a nation that bans all encryption algorithms.  Despite this, you have secrets to keep.  You notice that your government has not banned hash functions.  This gives you an idea: perhaps you can ‘hack’ an encryption scheme out of a hash function.

This isn’t crazy.  The outputs of many hash algorithms look pretty random.  Maybe you could use a hash function to build a stream cipher.  Basically, you’ll use a hash function to hash a secret key (along with some kind of counter value); this will result in a stream of ‘random looking’ bits which you can then XOR with your plaintext.

The question is: would a “one-way” and “collision-resistant” hash function be sufficient to ensure that this scheme is secure?  I’ll give you a blunt hint: no.  Technically neither of these properties implies that the output of a hash function be ‘random looking’.  You can conceive of hash functions that meet those guarantees, and yet produce outputs that would be useless for building a stream cipher (they might, say, contain long strings of predictable values).  If you use these to build your cipher, you’ll be terribly disappointed.

Spherical horses

When cryptographers first started pondering problems like the above, their question was what they wanted from an “ideal” hash function.  To a mathematician, the answer turned out to be obvious.  They wanted it to behave like a random function.  That term has a very specific mathematical definition; for the purposes of this discussion we’ll use an equivalent one that’s easier to talk about.

Imagine that we wanted to implement an ideal hash function.  Instead of designing a small algorithm that uses confusion and diffusion (as we do with most real hash functions), we might instead create a big hard-coded table.  The table would have the input messages in one column, and the corresponding outputs on the other.

The important thing about this table is that every single output value is an independent, random string.

       Input (binary)                  Output                      
       0                               Totally random bitstring 1
       1                               Totally random bitstring 2
       00                              Totally random bitstring 3
       01                              Totally random bitstring 4
       10                              Totally random bitstring 5
       11                              Totally random bitstring 6
       and so on...

Obviously the full table for a useful hash function would be pretty big.  How big? Well, SHA1 accepts messages up to 2^64 bytes in length.  So the answer is: too big to fit in this blog.  In fact, there would be more entries in the full table than there are atoms in the universe.

Even if we had room to store such a table, the process of hashing — looking up an input and finding the output — would be awfully time consuming.  If we stored our hash table on the tape of a Turing machine (the quintissential computer), just moving the tape head to the right place would take (on average) a number of time steps that’s exponential in the size of the input.

From time to time when I mention all of this in my intro course, some ambitious student tries to come up with a clever way to shrink the table down into something that we can carry around.  But here’s the problem: the set of output strings are perfectly random. Finding a way to represent them in a compact hash would be equivalent to compressing random data.  Unfortunately, information theory tells us that this is a big no-no.

Doubling down

Let’s take stock for a moment.  So far I hope that I’ve convinced you of at least two things. First, cryptographers would really like their hash functions to behave like random functions.

Second, “real” hash functions can’t be random functions, because that would be totally unworkable and impractical.  If you look at practical hash functions like SHA1, SHA512 and RIPEMD160 — all of which have nice, short implementations consisting of a few KB of code — it should be obvious that these are not random functions, no matter how ‘random’ the outputs look.

Cambridge, Massachusetts, 10:35am

So if we can’t use random functions in practice, what about an alternative approach? Perhaps we could model our hash functions as random functions, just for the purposes of the security proof.  Then in real life we’d substitute in SHA or RIPEMD or some practical hash function.  It’s not totally clear that the security proof would still mean anything, but at least we’d be doing something.

I’ll describe a scene as Hollywood would present it: an unrealistically well-lit office at MIT. A noted cryptographer, played by Steve Buscemi, has just proposed to model hash functions as random functions.  His colleague, played by Kate Winslet, sets him straight.

“Can’t do it,” she explains, shaking her head sadly, “it’s not just inconvenient that it takes exponential time to evaluate a random function.  If we allowed this sort of hashing in our security proof, we would have to let the parties — including the Adversary — run for an exponential number of time steps.  But we can’t do that.  Our entire security proof is based on the idea that the parties can only perform limited computations, specifically those that can be conducted in polynomial-time.  If let the parties peform arbitrary exponential-time computations, then adversary could do anything: he could even brute-force the key.”

(Hollywood would probably punch up this dialog a bit.)

The breakthrough comes from a passing janitor (Matt Damon, reprising his role from Good Will Hunting): “What if you just create an imaginary world where everyone is limited to polynomial time computations, but there’s a special exception for hashing.  Hashing, and hashing alone, doesn’t take any time at all.  When you try to hash something, the clock stops.”

Towards a paradigm