Vulnerability Note VU#997481

Cryptographic libraries and applications do not adequately defend against timing attacks

Original Release date: 25 Mar 2003 | Last revised: 25 Aug 2004

Overview

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.

Description

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.

The Brumley and Boneh paper documents a set of experiments using currently available hardware to attack three different OpenSSL-based RSA decryption applications: a simple RSA decryption oracle, Apache/mod_ssl, and Stunnel. Under optimal conditions, a 1024-bit RSA private key was extracted in approximately two hours using ~350,000 guesses. In the context of an SSL/TLS handshake, the guesses take the form of the premaster secret (client key exchange message), and the guesses may appear to a web server as completed TCP connections and failed attempts to set up SSL/TLS sessions. The experiments were conducted both interprocess on a single machine and on a high-speed, closed network that does not accurately reflect the network conditions found on the Internet. The attack could, however, be feasible on a network with a low variance in latency such as a LAN, corporate/campus network, or Internet2/Abilene. The attack could also work against an SSL/TLS enabled web server to which the attacker has local access, such as a shared server in a co-location facility. The paper also notes that interprocess attacks against Virtual Machines (VM) running on the same physical computer could yield RSA secrets held by a trusted VM, such as a TCPA/Palladium system.

The experiments focus on RSA software implementations, OpenSSL in particular. The paper states that "most crypto acceleration cards also implement defenses against the timing attack. Consequently, network servers using these accelerator cards are not vulnerable." Any applications that perform RSA private key operations may be vulnerable: SSL/TLS-enabled network services, IPsec, Secure Shell (SSH1, ssh-agent), TCPA/Palladium, and smart cards are some examples of such applications. For specific vendor information, see the Systems Affected section below.

The paper recommends a defense called "RSA blinding" that introduces an additional random component to the RSA calculation and makes timing information unusable to attackers. It appears that many cryptographic libraries and applications either do not implement RSA blinding or do not make use of it when it is available. RSA blinding does incur a slight performance penalty. Although the OpenSSL library used in the experiments does implement RSA blinding, it is not enabled by default. Many applications that use OpenSSL, including Apache mod_ssl, do not use RSA blinding, and are therefore vulnerable to this attack.

Impact

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.

Solution


Upgrade or Patch

    Upgrade or apply a patch as specified by your vendor. The preferred defense against this attack is to use RSA blinding, however other methods such as quantizing may also be effective. RSA blinding incurs a slight performance penalty. If an application links to a library to perform RSA operations, it is necessary for the underlying cryptographic library to support RSA blinding and for the application to make use of it.

Monitor RSA applications

    Monitor RSA applications for signs of attack. In the case of an attack against SSL/TLS web servers, logs may show a relatively high number of network connections and failed attempts to establish SSL/TLS sessions.

Systems Affected (Learn More)

VendorStatusDate NotifiedDate Updated
Apple Computer Inc.Affected11 Mar 200325 Mar 2003
ConectivaAffected11 Mar 200314 Apr 2003
CovalentAffected11 Mar 200304 Apr 2003
cryptlibAffected11 Feb 200304 Apr 2003
Crypto++Affected25 Feb 200325 Mar 2003
DebianAffected11 Mar 200323 Apr 2003
eSoftAffected11 Mar 200323 Apr 2003
F5 NetworksAffected11 Mar 200325 Mar 2003
Foundry Networks Inc.Affected11 Mar 200322 Apr 2003
FreeBSDAffected11 Mar 200325 Mar 2003
FreSSHAffected11 Mar 200325 Mar 2003
Gentoo LinuxAffected-05 Apr 2003
GNU LibgcryptAffected11 Feb 200324 Mar 2003
GNU TLSAffected15 Apr 200323 Apr 2003
Guardian Digital Inc. Affected11 Mar 200305 Apr 2003
If you are a vendor and your product is affected, let us know.View More »

CVSS Metrics (Learn More)

Group Score Vector
Base N/A N/A
Temporal N/A N/A
Environmental N/A N/A

References

Credit

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.

Other Information

  • CVE IDs: CAN-2003-0147
  • Date Public: 14 Mar 2003
  • Date First Published: 25 Mar 2003
  • Date Last Updated: 25 Aug 2004
  • Severity Metric: 9.42
  • Document Revision: 66

Feedback

If you have feedback, comments, or additional information about this vulnerability, please send us email.