# What is an easy method of proving that a cryptographic oracle attack is possible?

Lets say an application is using CBC mode without authentication. The application is generating cipher text. This cipher text can be manipulated by the attacker and then transmitted back to the application.

Without looking at the code, what is an easy method for the attacker to prove that a Padding Oracle or Decryption Oracle is present? Is there a method more elegant than brute force manipulation of the cipher text?

-
Are asking how the attacker can prove this, or how someone knowing more than the attacker can prove this? – Paŭlo Ebermann Dec 3 '12 at 18:21
@Paŭlo Ebermann♦ good question. The attacker, no more no less. – Rook Dec 3 '12 at 18:40

We have a Padding Oracle if there is a different response from the server gives us an indication of the correctness of the pad (say if this needs proving). We can establish this by playing a game where we send badly padded cipher-text and random strings to the server, finally submitting some at random and seeing if we can get a non-negligible Advantage is guessing which one we sent.

The problem is that this might be the "brute force" way. It's fairly easy to do if there is obvious data-leakage, but you have to check through a lot of side-channel attacks to rule out data-leakage to an efficient adversary. I sense you want a clever fast way to prove there is no data-leakage, which doesn't sound possible to me.

-
I want the best method that that can be applied in a scientific way. If this is the best, then so be it. – Rook Dec 18 '12 at 17:06
I don't think you can do any better than checking timings with a large enough sample size to discern signal from noise (assuming nothing obvious, like error codes). Which obviously is going to be a statistical test and not an absolute one. – Stephen Touset Dec 19 '12 at 22:25

Prove? Why does the attacker need to "prove" it? For example, the attacker can check whether there is an oracle by looking at the code and seeing whether such an attack is possible. Or, the attacker can guess that such an attack might be possible and then try the attack. If the attack succeeds, the attacker knows the system is vulnerable. There might be other ways too.

Or, to put it another way: an easy way to prove that such an attack is possible is to actually implement the attack and demonstrate that it works. Boom, done. Problem solved.

Proving that an attack is possible is usually a lot easier than finding the attack in the first place. Both of those are, in turn, a lot easier than proving that oracle-based attacks are impossible.

There's something funny about your question that I'm not following. I'm not getting why an attacker would care about a mathematical proof of the existence of such an attack. The proof of the pudding is in the eating. If an attack successfully breaks the system, seems like that's all that matters; who cares whether we have a mathematical proof?

I can see why a system defender would want a proof of the non-existence of such an attack, but that's a different question. Is that what you were asking for?

-
As a penetration tester my job is to prove that software is insecure. – Rook Dec 20 '12 at 0:19
OK, I'd refer penetration testers to my second paragraph: "an easy way to prove that such an attack is possible is to actually implement the attack and demonstrate that it works". Of course, evaluating a cryptographic system to determine whether any attack is possible (and if so, to find the attack) remains challenging and non-trivial and not something that can be automated; for that, my best advice is "hire a cryptographer". – D.W. Dec 20 '12 at 21:59
we are the cryptographers. I think that Nathan Cooper's approach is better. Try manipulating the cipher text and look at the response. See if you can get the server to respond with a Noise Block for CBC-R or simply proving malleability by attacking the padding. – Rook Dec 20 '12 at 22:21
@Rook, I'm puzzled. I'd a cryptographer to already be familiar with padding oracle vulnerabilities and wouldn't need to ask. Are you looking for resources to learn about how padding oracle attacks work? If so, try Attack of the week: XML Encryption and Attack of the week: Datagram TLS and How (not) to use symmetric encryption. – D.W. Dec 20 '12 at 23:05
@Rook, Nathan Cooper's suggestion is a fine starting point, but beware. It will find some padding oracle attacks, but not all. If his method does not reveal the existence of a padding oracle attack, that does not mean you are safe; there could still be a different form of padding oracle attack. It is better to examine the source code and the mode of operation they are using and analyze whether it follows good cryptographic engineering principles. That requires cryptographic knowledge, not just a point-and-shoot test. – D.W. Dec 20 '12 at 23:06