A Timing-Resistant Elliptic Curve Backdoor in RSA
We present a fast algorithm for finding pairs of backdoor RSA primes (p,q) given a security parameter. Such pairs posses an asymmetric backdoor that gives the designer the exclusive ability to factor n = pq, even when the key generation algorithm is publi
- PDF / 481,817 Bytes
- 15 Pages / 430 x 660 pts Page_size
- 90 Downloads / 156 Views
Cryptovirology Labs [email protected] 2 Columbia University [email protected]
Abstract. We present a fast algorithm for finding pairs of backdoor RSA primes (p, q) given a security parameter. Such pairs posses an asymmetric backdoor that gives the designer the exclusive ability to factor n = pq, even when the key generation algorithm is public. Our algorithm uses a pair of twisted curves over GF(2257 ) and we present the first incremental search method to generate such primes. The search causes the 12 log(n)+O(log(log(n))) least significant bits of n to be modified during key generation after p is selected and before q is determined. However, we show that this is tolerable by using point compression and ECDH. We also present the first rigorous experimental benchmarks of an RSA asymmetric backdoor and show that our OpenSSL-based implementation outperforms OpenSSL RSA key generation. Our application is highly efficient key recovery. Of independent interest, we motivate the need to find large binary twists. We present the twist we generated and how we found it. Keywords: Twisted elliptic curves, RSA, subliminal channel, kleptography.
1
Introduction
The problem of devising a backdoor within RSA [27] public keys is a well-studied area. It is an important topic since RSA key generation machinery is often implemented in hardware or binary executables. Therefore, the extent to which such implementations can/should be trusted is not always clear and considerable effort may be needed to access the design of the machinery that has been deployed. Without expending such effort, a backdoor may go unnoticed for years. This threat provides a motivation for the study of backdoors. The approaches to designing backdoors can be divided into two categories: symmetric backdoors and asymmetric backdoors. A symmetric backdoor is suitable when one may assume that the key generation device is a tamper-proof black-box. However, a reverse-engineer that breaches the black-box learns the secrets and is able to use the backdoor in like implementations. On the other hand, an asymmetric backdoor only assumes that the key generator is implemented in a tamper-resistant black-box. The reverse-engineer that breaches the Dingyi Pei et al. (Eds.): Inscrypt 2007, LNCS 4990, pp. 427–441, 2008. c Springer-Verlag Berlin Heidelberg 2008
428
A.L. Young and M. Yung
black-box will learn that a backdoor is present but will be unable to use it. The asymmetric backdoor constructions to date have all utilized asymmetric cryptography to construct the asymmetric backdoor (public key of the designer). Anderson presented a symmetric backdoor [3] and it was subsequently cryptanalyzed by Kaliski [17]. The notion of an asymmetric backdoor was presented in [32] (see also [33]) where the backdoor was in turn an RSA public key. The construction is called a secretly embedded trapdoor with universal protection (SETUP) and the trapdoor is the public key of the malicious designer. A problem in the design is that the secretly embedded trapdoor has a security parameter tha
Data Loading...
