The padding oracle attack (Bleichenbacher)

The last great family of attacks targets neither the maths nor the keys, but the implementation: what the server lets leak when it responds.

What is an oracle?

An oracle is a service that, without meaning to, answers a question it should not. Here, the question is: "does this decryption have a valid padding?" If a server that receives a ciphertext responds differently depending on whether the PKCS#1 v1.5 padding obtained after decryption is correct or not, it becomes a padding oracle.

The leak can be crude (an explicit error message "bad padding") or subtle (a slightly different response time, a connection cut off earlier). Whatever the channel: a single leaked bit — valid / invalid — is enough.

The Bleichenbacher attack (1998)

Bleichenbacher showed how to turn this oracle into a decryption machine. The attacker does not know d, but exploits the malleability of RSA (lesson from chapter 1):

Boucle (des milliers, voire des millions de fois) :
  1. choisir un multiplicateur s
  2. calculer  c' = c × s^e mod n       (nouveau chiffré "bricolé")
  3. envoyer c' au serveur
  4. lire la réponse de l'oracle :
        remplissage VALIDE   -> l'info restreint l'intervalle où vit m
        remplissage INVALIDE -> on essaie un autre s
Fin : l'intervalle se resserre jusqu'à un seul m -> message déchiffré

Each "valid" response teaches the attacker that the multiplied message falls within a certain range. By repeating, they bracket m more and more finely, until recovering it exactly — without ever possessing the private key.

The oracle diagram

   Attaquant                         Serveur (oracle)
      |                                    |
      |----  c' = c × s^e mod n  --------->| déchiffre avec d
      |                                    | teste le remplissage PKCS#1
      |<---  "valide" / "invalide"  -------| (ou : temps de réponse)
      |                                    |
      | resserre l'intervalle de m         |
      |  ... recommence des milliers de fois...
      v
   message m retrouvé

ROBOT: the return, twenty years later

In 2017, the ROBOT attack (Return Of Bleichenbacher's Oracle Threat) showed that many major HTTPS servers remained vulnerable: the 1998 flaw had never really been closed everywhere. It is fixed by revealing nothing: the same response and the same time whether the padding is valid or not, and migration to OAEP rather than PKCS#1 v1.5.

The general lesson

A mathematically solid encryption can be broken by what its implementation lets slip: distinct error messages, computation time, power consumption. These are side-channel attacks. A good implementation is constant-time and stingy with information.

In summary

If a server reveals — through an error or a timing — that the PKCS#1 v1.5 padding of a decryption is valid, it becomes an oracle. The Bleichenbacher attack (1998), revived by ROBOT (2017), then decrypts by querying the oracle thousands of times, without the private key. Golden rule: let nothing leak, respond in constant time, prefer OAEP.