Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

I came across the term "cryptographic oracle" and despite a bit of googling I was unable to come across a clear, concise definition. What is a cryptographic oracle and what does it do? Can anyone give an example?

share|improve this question
1  
This question on crypto.se might help: crypto.stackexchange.com/questions/879/… –  mikeazo Jan 12 '12 at 14:35

3 Answers 3

up vote 27 down vote accepted

An oracle is an individual who knows the personal cell phone number of a god. This enables him (or her) to obtain some information which is usually considered as out of reach of mere mortals, such as glimpses of the future. In cryptography, that's the same, except that no deity is involved: an oracle is any system which can give some extra information on a system, which otherwise would not be available.

For instance, consider asymmetric encryption with RSA. The standard I link to states how a piece of data should be encrypted with a public key. In particular, the encryption begins with a padding operation, in which the piece of data is first expanded by adding a header, so that the padded data length matches the RSA public key length. The header should begin with the two bytes 0x00 0x02, followed by at least eight random non-zero bytes, and then another 0x00. Once the data has been padded, it is time to apply the mathematical operation which is at the core of the RSA operation (modular exponentiation). Details of the padding are important for security.

The encryption result is an integer modulo the RSA modulus, a big integer which is part of the public key. For a 1024-bit RSA key, the modulus n is an integer value greater than 21023, but smaller than 21024. A properly encrypted data chunk, with RSA, yields an integer value between 1 and n-1. However, the padding implies some structure, as shown above. The decrypting party MUST find, upon decryption, a properly formed PKCS#1 header, beginning with the 0x00 0x02 bytes, followed by at least eight non-zero bytes, and there must be a 0x00 which marks the end of the header. Therefore, not all integers between 1 and n-1 are valid RSA-encrypted message (less than 1 every 65000 such integers would yield a proper padding upon decryption).

Knowing whether a given integer modulo n would yield, upon decryption, a valid padding structure, is supposed to be infeasible for whoever does not know the private key. The private key owner (the deity) obtains that information, and much more: if the decryption works, the private key owner actually gets the message, which is the point of decryption. Assume that there is an entity, somewhere, who can tell you whether a given integer modulo n is a validly encrypted piece of data with RSA; that entity would not give you the full decryption result, it would just tell you whether decryption would work or not. That's a one-bit information, a reduced glimpse of what the deity would obtain. The entity is your oracle: it returns parts of the information what is normally available only to the private key owner.

It turns out that, given access to such an oracle, it is possible to rebuild the private key, by sending specially crafted integers modulo n (it takes a million or so of such values, and quite a bit of mathematics, but it can be done). It also turns out that most SSL/TLS implementation of that time (that was in 1999) were involuntarily acting as oracles: if you sent, as a client, an invalidly RSA-encrypted ClientKeyExchange message, the server was responding with a specific error message ("duh, your ClientKeyExchange message stinks"), whereas if decryption worked, the server was keeping on with the protocol, using whatever value it decrypted (usually unknown to the client if the client sent a random value, so the protocol failed later on, but the client could see the difference between a valid and an invalid padding). Therefore, with such an implementation, an attacker could (after a million or so of failed connections) rebuild the server private key, which is usually considered to be a bad thing.

That's what oracles are: a mathematical description of a data leak, to be used in security proofs. In the case of RSA, this demonstrates that knowing whether a value has a proper padding or not is somehow equivalent to learning the private key (if you know the private key you can attempt the decryption and see the padding for yourself; the Bleichenbacher attack shows that it also works the other way round).

share|improve this answer
    
Great explanation as always. I'd be really interested to know what your character-per-rep ratio is. –  Iszi Jan 12 '12 at 16:23
1  
@Iszi data.stackexchange.com/it%20security/query/14517/… says 52. Yours is 66, Tom Leek's 73. –  Gilles Jan 12 '12 at 17:46

An oracle is something which can immediately (O(1)) give you the answer to some problem, usually an infeasible or impossible problem. For example, a "Halting-problem Oracle" could tell you immediately whether a certain program on a certain input halts or not, even though the halting problem is uncomputable to us mere mortals. However, we can sometimes prove some useful properties by pretending certain oracles exist.

In cryptographic papers, for instance, oracles are most often used to show that, even if our attackers had access to some seemingly-impossibile oracle, they still wouldn't have any (significant) advantage to breaking our security. For example, one important property of encryption algorithms (called resistance to known plaintext attacks) is that if an attacker is given a message encrypted with your key m' and they want to know the original message m (or figure out your key), then giving them another message n and its encryption with your key n' should not help them do so in any way whatsoever.

Taking this to the extreme (chosen plaintext attack): give an attacker an oracle who can encrypt or decrypt any message with your key except for m and m'. Even under these extreme conditions, we'd want to show for our encryption that the attacker with the oracle will have no advantage in finding m (or your key) than the attacker without the oracle. This would mean our encryption is safe from chosen-plaintext attacks.


[Edit]
Here is another practical example. In the question Could a program ever tell if another program plays chess, we show that no such program exists by first assuming that there is a chess-detection oracle, then showing its existence leads to a logical impossibility.

share|improve this answer

Cryptographic oracles are a black box input/output method.

It will respond to any input with a pseudo-random response but will always give the same output for a specific input.

They're generally used for hash functions where randomness is important for higher security.

Obviously there are still going to be security issues as it is just a mathematical function that is returning seemingly pseudo-random numbers, but they are obviously stronger than some of their less random counterparts.

Here's a solid paper about them and their design - http://cseweb.ucsd.edu/users/mihir/papers/ro.pdf

share|improve this answer
2  
You're describing a random oracle, which is a related concept (or rather, a particular case of oracle). –  Gilles Jan 12 '12 at 17:50
    
Ah ok, thanks for clarifying that one for me. –  doyler Jan 12 '12 at 18:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.