Title:
The "Million Message Attack" in 15,000 Messages -- Efficient Padding Oracle Attacks on Estonian Electronic ID Card, Security Tokens and Smart Cards

Presenters: Yusuke Kawamoto and Joe K. Tsay

Time: September 13, 16:15

Location: Liivi 2-405

Abstract:
We present an efficient attack against widely available cryptographic

devices, including the Estonian electronic ID card, security tokens and smart cards, that employ RSA key pairs. With this attack an adversary could perform cryptographic operations (i.e., decryption or signing with those devices) without knowing the corresponding RSA private key. The attack is a padding oracle attack, where a cryptographic device (behaving as a so-called `padding oracle') leaks partial information about plaintexts: The oracle never reveals the plaintexts themselves to the adversary, but returns error messages when it fails to decrypt bit strings that are given by the adversary.

We modify and improve a previously known attack on RSA encryption standard PKCS#1 v1.5, which was considered to be impractical and called the `million message attack'. Our improved attack could allow an adversary to perform RSA decryption of an unknown valid ciphertext under a 1024 bit key in a mean of
50,000 and median of 15,000 oracle calls. We show how implementation details of certain devices admit an attack that requires only 9,400 oracle calls on average (3,800 median). In the case of the Estonian eID card with 1024 bit RSA keys, we estimate that an adversary could decrypt an arbitrary valid ciphertext in 11 hours and 30 minutes or produce a (non-legally binding) digital signature on an arbitrary message in around 48 hours (without knowing neither the RSA private key nor its PIN).

This is joint work with Romain Bardou, Riccardo Focardi, Lorenzo Simionato and Graham Steel.