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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bardou, R., Focardi, R., Kawamoto, Y., Simionato, L., Steel, G., Joe-Kai-Tsay: The million message attack in 15 000 messages, or efficient padding oracle attacks on cryptographic hardware. Cryptology ePrint Archive (to appear, 2012), http://eprint.iacr.org/
Black, J., Urtubia, H.: Side-channel attacks on symmetric encryption schemes: The case for authenticated encryption. In: Boneh, D. (ed.) USENIX Security Symposium, pp. 327–338. USENIX (2002)
Bleichenbacher, D.: Chosen Ciphertext Attacks against Protocols Based on the RSA Encryption Standard PKCS #1. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 1–12. Springer, Heidelberg (1998)
Bond, M., French, G.: Hidden semantics: why? how? and what to do? Presentation at Fourth Analysis of Security APIs Workshop, ASA-4 (July 2010)
Bortolozzo, M., Centenaro, M., Focardi, R., Steel, G.: Attacking and fixing PKCS#11 security tokens. In: Proceedings of the 17th ACM Conference on Computer and Communications Security (CCS 2010), Chicago, Illinois, USA. ACM Press (October 2010)
Clulow, J.: On the Security of PKCS #11. In: Walter, C.D., Koç, Ç.K., Paar, C. (eds.) CHES 2003. LNCS, vol. 2779, pp. 411–425. Springer, Heidelberg (2003)
Degabriele, J.P., Paterson, K.G.: On the (in)security of ipsec in mac-then-encrypt configurations. In: Al-Shaer, E., Keromytis, A.D., Shmatikov, V. (eds.) ACM Conference on Computer and Communications Security, pp. 493–504. ACM (2010)
Delaune, S., Kremer, S., Steel, G.: Formal analysis of PKCS#11. In: Proceedings of the 21st IEEE Computer Security Foundations Symposium (CSF 2008), Pittsburgh, PA, USA, pp. 331–344. IEEE Computer Society Press (June 2008)
Dworkin, M.: Recommendation for block cipher modes of operation: Modes and techniques. NIST Special Publication 800-38A (December 2001)
Estonian Certification Center. The estonian ID card and digital signature concept, principles and solutions (March 2003), http://www.id.ee/public/The_Estonian_ID_Card_and_Digital_Signature_Concept.pdf
Estonian Informatics Center. Estonian ID-software, https://installer.id.ee/?lang=eng
Housley, R.: Cryptographic Message Syntax (CMS). RFC 5652 (Standard) (September 2009)
ID Süsteemide AS. EstEID specification v2.01, http://www.id.ee/public/EstEID_Spetsifikatsioon_v2.01.pdf
Jager, T., Somorovsky, J.: How to break XML encryption. In: Proceedings of the 18th ACM Conference on Computer and Communications Security (CCS), pp. 413–422 (2011)
Manger, J.: A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 v2.0. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 230–238. Springer, Heidelberg (2001)
Martens, T.: eID interoperability for PEGS, national profile estonia, European Commission’s IDABC programme (November 2007), http://ec.europa.eu/idabc/en/document/6485/5938
Mitchell, C.J.: Error Oracle Attacks on CBC Mode: Is There a Future for CBC Mode Encryption? In: Zhou, J., López, J., Deng, R.H., Bao, F. (eds.) ISC 2005. LNCS, vol. 3650, pp. 244–258. Springer, Heidelberg (2005)
National Institute of Standards and Technology. NIST special publication 800-57, recommendation for key management (March 2007), http://csrc.nist.gov/publications/PubsSPs.html
Paterson, K.G., Watson, G.J.: Immunising CBC Mode Against Padding Oracle Attacks: A Formal Security Treatment. In: Ostrovsky, R., De Prisco, R., Visconti, I. (eds.) SCN 2008. LNCS, vol. 5229, pp. 340–357. Springer, Heidelberg (2008)
Paterson, K.G., Yau, A.: Padding Oracle Attacks on the ISO CBC Mode Encryption Standard. In: Okamoto, T. (ed.) CT-RSA 2004. LNCS, vol. 2964, pp. 305–323. Springer, Heidelberg (2004)
Minutes from the April, 2003 PKCS workshop (2003), ftp://ftp.rsa.com/pub/pkcs/03workshop/minutes.txt
Rizzo, J., Duong, T.: Practical padding oracle attacks. In: Proceedings of the 4th USENIX Conference on Offensive Technologies, WOOT 2010, pp. 1–8. USENIX Association, Berkeley (2010)
Rogaway, P.: Evaluation of some blockcipher modes of operation (February 2011), http://www.cs.ucdavis.edu/~rogaway; Evaluation carried out for the Cryptography Research and Evaluation Committees (CRYPTREC) for the Government of Japan
RSA Security Inc., v2.1. PKCS #1: RSA Cryptography Standard (June 2002)
RSA Security Inc., v2.20. PKCS #11: Cryptographic Token Interface Standard (June 2004)
Klíma, V., Pokorný, O., Rosa, T.: Attacking RSA-Based Sessions in SSL/TLS. In: Walter, C.D., Koç, Ç.K., Paar, C. (eds.) CHES 2003. LNCS, vol. 2779, pp. 426–440. Springer, Heidelberg (2003)
Vaudenay, S.: Security Flaws Induced by CBC Padding - Applications to SSL, IPSEC, WTLS... In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 534–545. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 International Association for Cryptologic Research 2012
About this paper
Cite this paper
Bardou, R., Focardi, R., Kawamoto, Y., Simionato, L., Steel, G., Tsay, JK. (2012). Efficient Padding Oracle Attacks on Cryptographic Hardware. In: Safavi-Naini, R., Canetti, R. (eds) Advances in Cryptology – CRYPTO 2012. CRYPTO 2012. Lecture Notes in Computer Science, vol 7417. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32009-5_36
Download citation
DOI: https://doi.org/10.1007/978-3-642-32009-5_36
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32008-8
Online ISBN: 978-3-642-32009-5
eBook Packages: Computer ScienceComputer Science (R0)