Cryptographic libraries and applications do not provide adequate defense against a side-channel timing attack against RSA private keys. Such an attack has been shown to be practical using currently available hardware on systems and networks with sufficiently low variance in latency.
David Brumley and Dan Boneh, researchers at Stanford University, have written a paper that demonstrates a practical attack that can be used to extract private keys from vulnerable RSA applications. Using statistical techniques and carefully measuring the amount of time required to complete an RSA operation, an attacker can recover one of the factors (q) of the RSA key. The timing differences examined in the paper are based on whether an extra Mongtomery reduction is performed (section 2.3) and whether Karatsuba (recursive) or "normal" multiplication is used (section 2.4). With the public key and the factor q, the attacker can compute the private key. As noted in the VMM/attestation example in section 4 of the paper, applications that perform RSA encryption (signing) operations may also be vulnerable if the attacker can control the data to be signed.
Similar types of timing attacks are discussed in CERT Advisory CA-1998-07, a paper by Daniel Bleichenbacher et al., and a paper by Paul Kocher.
A remote attacker could derive private RSA keys. It is important to note that the attacks described in this paper appear to be practical under certain conditions. In the case of remote attacks against SSL/TLS-enabled web servers, variance in network latency must be sufficiently low (less than 1ms), and the attacker must account for other variables such as the load on the server. A server may be more vulnerable during a period of low activity. In the case of local interprocess attacks against a web server or a VM, all the necessary conditions exist.
Monitor RSA applications
Apple Computer Inc.
Foundry Networks Inc.
Guardian Digital Inc.
Red Hat Inc.
SSH Communications Security
The SCO Group
Trustix Secure Linux
VanDyke Software Inc.
Global Technology Associates
Internet Initiative Japan (IIJ)
Netscape Communications Corporation
Cisco Systems Inc.
Internet Software Consortium
Intersoft International Inc.
Massachusetts Institute of Technology (MIT)
MetaSolv Software Inc.
Multi-Tech Systems Inc.
National Center for Supercomputing Applications (NCSA)
National Institute of Standards and Technology (NIST)
Redback Networks Inc.
Secure Computing Corporation
Sun Microsystems Inc.
Wind River Systems Inc.
This vulnerability is documented in a research paper written by David Brumley and Dan Boneh of Stanford University.
This document was written by Art Manion.
|Date First Published:||2003-03-25|
|Date Last Updated:||2004-08-25 17:59 UTC|