International Association
for Cryptologic Research

We show how to exploit the encrypted key import functions of a

variety of different cryptographic devices to reveal the imported

key. The attacks are padding oracle attacks, where error messages

resulting from incorrectly padded plaintexts are used as a side

channel. In the asymmetric encryption case, we modify and improve

Bleichenbacher\'s attack on RSA PKCS#1v1.5 padding, giving new

cryptanalysis that allows us to carry out the `million message

attack\' in a mean of 49 000 and median of 14 500 oracle calls in the

case of cracking an unknown valid ciphertext under a 1024 bit key

(the original algorithm takes a mean of 215 000 and a median of 163

000 in the same case). We show how implementation details of certain

devices admit an attack that requires only 9 400 operations on

average (3 800 median). For the symmetric case, we adapt Vaudenay\'s

CBC attack, which is already highly efficient. We demonstrate the

vulnerabilities on a number of commercially available cryptographic

devices, including security tokens, smartcards

and the Estonian electronic ID card. The attacks are

efficient enough to be practical: we give timing details for all

the devices found to be vulnerable, showing how our optimisations make a qualitative difference to the practicality of the attack.

We give mathematical analysis of the effectiveness of the attacks,

extensive empirical results, and a discussion of countermeasures and manufacturer reaction.