Dual EC DRBG |
Extended RandomThe basic Dual EC attack requires the attacker to see at least a block of 30 Dual EC output bytes (and to know the back door for the Dual EC parameters). This raises the question of whether an attacker eavesdropping upon a TLS connection (e.g., an HTTPS connection) can actually see so many Dual EC output bytes. Green reported to Lange in December 2013 that he and Checkoway had discovered a proposed TLS extension named "Extended Random". This extension increases the amount of PRNG output visible to an attacker, which facilitates using the back door in Dual EC. They also noticed that the RSA BSAFE documentation indicates support for this TLS extension although they say that they have no evidence that Extended Random has ever actually been enabled. This page explains the amount of randomness visible in a typical TLS connection, and explains the impact of Extended Random. This page also reports a security analysis from Bernstein and Lange disputing the published motivation for Extended Random. TLS randomness and Dual EC exploitationTLS random values are typically 224 bits. The server obtains 224 bits from its RNG and sends those as a public "server random value" to the client. If the RNG is implemented using Dual EC and generates these bits with a fresh call then the server random value reveals the top 224 bits of the x-coordinate of sQ. Similarly there is a public "client random value" from the client's RNG. The server also sends a 256 bit "session ID" which often includes random data but not necessarily for the full length and not necessarily fresh randomness. The analysis of basic attack costs for NIST P-256 assumed that the full 240 bits of φ(x(sQ)) were available to the attacker, requiring only 16 missing bits to be guessed. However, in the TLS use case, typically 16 more bits are missing, pushing the attack costs from about 215 to about 231. A single 231 computation is not a problem, but if the same attack is carried out many times, say 2t times, then the attack costs are increased from 215+t to 231+t. This is a serious issue when t is large. Extended Random eliminates this issue. Furthermore, if Dual EC is used with P-384 or P-521 instead of P-256 then there is a critical gap between the standard 224 bits in TLS and the 368 or 504 bits in a Dual EC output block. In this case Extended Random makes the difference between a feasible attack and an infeasible attack. Extended Random also simplifies attacks against Dual EC, because it includes more than one block of output (a few extra bits for P-521 and many extra bits for P-384 or P-256). The attacker easily and efficiently confirms guesses for internal Dual EC states by comparing the potential next output to the next bits of the extended randomness. For P-521 this reduces the candidate list of inner states to a small number, and for P-384 and P-256 it always pinpoints the correct inner state. Origin of Extended RandomExtended Random was proposed in an Internet-Draft by Eric Rescorla (RTFM, Inc.) and Margaret Salter (NSA) in April 2008. The latest version, draft 02, is from 2 March 2009:
Section 6 of the document acknowledges a funding source: "This work was supported by the US Department of Defense." The official reason for the proposalThe Internet-Draft states the following rationale for extended randomness: The United States Department of Defense has requested a TLS mode which allows the use of longer public randomness values for use with high security level cipher suites like those specified in Suite B [I-D.rescorla-tls-suiteb]. The rationale for this as stated by DoD is that the public randomness for each side should be at least twice as long as the security level for cryptographic parity, which makes the 224 bits of randomness provided by the current TLS random values insufficient. "Cryptographic parity" is not a common phrase among cryptographers. It is not defined in the document, and its intended meaning is highly unclear. Furthermore, there is no known attack strategy that comes even close to exploiting the 224 bits of randomness used in TLS. The document contains no further explanation to support its allegation of these 224 bits being insufficient. TLS encrypts data using a "master secret" computed from the server's 224-bit random value, the client's 224-bit random value, and a "pre-master secret". The pre-master secret is the foundation of TLS security: in ECC cipher suites it is obtained from a DH key exchange between client and server, and in RSA cipher suites it is chosen by the client and encrypted to the RSA key of the server. The pre-master key is already at least twice as large as the security level. Even if the client constantly reuses the same pre-master secret and random value, the server has negligible chance of ever repeating its 224-bit random value with a properly functioning RNG: a server generating an incredible 1000000000000000000 random 224-bit values has chance below 0.0000000000000000000000000000001 of seeing the same value twice. ConclusionThe draft-rescorla-tls-extended-random-02.txt document was funded by the United States Department of Defense, requested by the United States Department of Defense, and coauthored by an NSA employee. It facilitates attacks on TLS implementations that use Dual EC. We have not found any way in which it increases security. We have heard the following two explanations:
Authors of this "Extended Random" page (alphabetical order)
Last modified: 2014.03.31 |