Sliding Right into Disaster: Left-to-Right Sliding Windows Leak
It is well known that constant-time implementations of modular exponentiation cannot use sliding windows. However, software libraries such as Libgcrypt, used by GnuPG, continue to use sliding windows. It is widely believed that, even if the complete patte
- PDF / 522,635 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 19 Downloads / 218 Views
Abstract. It is well known that constant-time implementations of modular exponentiation cannot use sliding windows. However, software libraries such as Libgcrypt, used by GnuPG, continue to use sliding windows. It is widely believed that, even if the complete pattern of squarings and multiplications is observed through a side-channel attack, the number of exponent bits leaked is not sufficient to carry out a full key-recovery attack against RSA. Specifically, 4-bit sliding windows leak only 40% of the bits, and 5-bit sliding windows leak only 33% of the bits. In this paper we demonstrate a complete break of RSA-1024 as implemented in Libgcrypt. Our attack makes essential use of the fact that Libgcrypt uses the left-to-right method for computing the sliding-window expansion. We show for the first time that the direction of the encoding matters: the pattern of squarings and multiplications in left-to-right sliding windows leaks significantly more information about the exponent than right-to-left. We show how to extend the Heninger-Shacham algorithm for partial key reconstruction to make use of this information and obtain a very efficient full key recovery for RSA-1024. For RSA-2048 our attack is efficient for 13% of keys.
Keywords: Left-to-right sliding windows attack · Flush+Reload · RSA-CRT
1
·
Collision entropy
·
Cache
Introduction
Modular exponentiation in cryptosystems such as RSA is typically performed starting from the most significant bit (MSB) in a left-to-right manner. More efficient implementations use precomputed values to decrease the number of c International Association for Cryptologic Research 2017 W. Fischer and N. Homma (Eds.): CHES 2017, LNCS 10529, pp. 555–576, 2017. DOI: 10.1007/978-3-319-66787-4 27
556
Bernstein, Breitner, Genkin, Groot Bruinderink, Heninger, Lange, van Vredendaal, Yarom
multiplications. Typically these windowing methods are described in a right-toleft manner, starting the recoding of the exponent from the least significant bit (LSB), leading to the potential disadvantage that the exponent has to be parsed twice: once for the recoding and once of the exponentiation. This motivated researchers to develop left-to-right analogues of the integer recoding methods that can be integrated directly with left-to-right exponentiation methods. For example, the only method for sliding-window exponentiation in the Handbook of Applied Cryptography [16, Chap. 14.6] is the left-to-right version of the algorithm. Doche [7] writes “To enable ‘on the fly’ recoding, which is particularly interesting for hardware applications” in reference to Joye and Yen’s [14] left-to-right algorithm. Given these endorsements, it is no surprise that many implementations chose a left-to-right method of recoding the exponent. For example, Libgcrypt implements a left-to-right exponentiation with integrated recoding. Libgcrypt is part of the GnuPG code base [2], and is used in particular by GnuPG 2.x, which is a very popular implementation of the OpenPGP standard [6] for applications such as encrypted email and files. L
Data Loading...
