TU Darmstadt / ULB / TUbiblio

A Vulnerability in RSA Implementations due to Instruction Cache Analysis and Its Demonstration on OpenSSL

Aciicmez, Onur and Schindler, Werner
Malkin, T. (ed.) (2008):
A Vulnerability in RSA Implementations due to Instruction Cache Analysis and Its Demonstration on OpenSSL.
In: Topics in Cryptology, CT-RSA, Springer, Berlin, In: LNCS, [Conference or Workshop Item]

Abstract

MicroArchitectural Analysis (MA) techniques, more specifically Simple Branch Prediction Analysis (SBPA) and Instruction Cache Analysis, have the potential of disclosing the entire execution ow of a software-implemented cryptosystem ([5, 2]). In this paper we will show that one can completely break RSA in the original unpatched OpenSSL version (v.0.9.8e) even if the most secure configuration is in place, including all countermeasures against side-channel and MicroArchitectural analysis (in particular, base blinding). We also discuss (known) countermeasures that prevent this attack. In a first step we apply an instruction cache attack to reveal which Montgomery operations require extra reductions. To exploit this information we model the timing behavior of the modular exponentiation algorithm by a stochastic process. Its analysis provides the optimal guessing strategy, which reveals the secret key ( mod p1) and finally the factorization of the RSA modulus n = p1p2. For the instruction cache attack we applied a spy process that was embedded in the target process (OpenSSL), which clearly facilitates the experimental part. This simplifiation yet does not nullify our results since in cache attacks empirical results from embedded spy processes and (suitably implemented) stand-alone spy processes are very close to each other [16] and, moreover, our guessing strategy is fault-tolerant. Interestingly, the second step of our attack is related to that of a particular combined power and timing attack on smart cards [23] (see also [27, 22]). Before we published our result [1] we informed the OpenSSL development team who included a patch into the stable branch of v.0.9.7e ([31, 32]) and CERT which informed software vendors ([33{35]). In particular, this countermeasure is included in the current version 0.9.8f. We have only analyzed OpenSSL, thus we currently do not know the strength of other cryptographic libraries.

Item Type: Conference or Workshop Item
Erschienen: 2008
Editors: Malkin, T.
Creators: Aciicmez, Onur and Schindler, Werner
Title: A Vulnerability in RSA Implementations due to Instruction Cache Analysis and Its Demonstration on OpenSSL
Language: German
Abstract:

MicroArchitectural Analysis (MA) techniques, more specifically Simple Branch Prediction Analysis (SBPA) and Instruction Cache Analysis, have the potential of disclosing the entire execution ow of a software-implemented cryptosystem ([5, 2]). In this paper we will show that one can completely break RSA in the original unpatched OpenSSL version (v.0.9.8e) even if the most secure configuration is in place, including all countermeasures against side-channel and MicroArchitectural analysis (in particular, base blinding). We also discuss (known) countermeasures that prevent this attack. In a first step we apply an instruction cache attack to reveal which Montgomery operations require extra reductions. To exploit this information we model the timing behavior of the modular exponentiation algorithm by a stochastic process. Its analysis provides the optimal guessing strategy, which reveals the secret key ( mod p1) and finally the factorization of the RSA modulus n = p1p2. For the instruction cache attack we applied a spy process that was embedded in the target process (OpenSSL), which clearly facilitates the experimental part. This simplifiation yet does not nullify our results since in cache attacks empirical results from embedded spy processes and (suitably implemented) stand-alone spy processes are very close to each other [16] and, moreover, our guessing strategy is fault-tolerant. Interestingly, the second step of our attack is related to that of a particular combined power and timing attack on smart cards [23] (see also [27, 22]). Before we published our result [1] we informed the OpenSSL development team who included a patch into the stable branch of v.0.9.7e ([31, 32]) and CERT which informed software vendors ([33{35]). In particular, this countermeasure is included in the current version 0.9.8f. We have only analyzed OpenSSL, thus we currently do not know the strength of other cryptographic libraries.

Title of Book: Topics in Cryptology, CT-RSA
Series Name: LNCS
Number: 4964
Publisher: Springer
Uncontrolled Keywords: Secure Things;RSA, Montgomery Multiplication, Instruction-Cache Attack, MicroArchitectural Analysis, Side Channel Analysis, Stochastic Process
Divisions: LOEWE > LOEWE-Zentren > CASED – Center for Advanced Security Research Darmstadt
LOEWE > LOEWE-Zentren
LOEWE
Event Location: Berlin
Date Deposited: 30 Dec 2016 20:23
Identification Number: TUD-CS-2008-11475
Export:
Suche nach Titel in: TUfind oder in Google

Optionen (nur für Redakteure)

View Item View Item