20.4 Padding oracle attacks on TLS handshake

The term oracle originally comes from complexity theory, where it is used to compare the complexity of two computational problems P₁,P₂.

Suppose we can solve P₁ efficiently (i.e., in polynomial time), if there is a polynomial-time algorithm A to solve P₂. In this situation, we say that P₁ polytime reduces to P₂, or

Informally, we can say that P₂ is at least as hard as P₁ ([117]). Now, the (hypothetical) algorithm A that can efficiently solve P₂ is called an oracle for P₂.

As an example, let P₁ be the RSA-problem and P₂ be the integer factorization problem. Recall from Chapter 7, Public-Key Cryptography, that the RSA problem means we have to find the plaintext m, given the ciphertext

and the public key (e,n), while the integer factorization problems is to find the prime factors of a given integer.

Now it is easy to see that if we had an oracle that provides us with the prime factors of n in polynomial time, we could also solve the...