[ Pobierz całość w formacie PDF ]
block, and 216 for the last two bytes, giving approximately
233 candidate curve points. Of these, approximately 217 ephemeral private key,7 and, when ECDSA is being used,
a 32-byte nonce. OpenSSL s implementation of Dual EC
will agree with the last two bytes of the session ID, and we
does not cache unused random bytes at the conclusion of
determine which is correct by generating two additional
a generator call, hence each sequence of random bytes
Dual EC blocks for a P-256 ECDHE private key, then per-
begins with up to 30 bytes drawn from a single elliptic
forming a point multiplication to compare with the public
curve point. Figure 2 illustrates the generation of these
key sent in the same handshake. The total complexity is
values.
233(Cv +Cf ) + 217(5Cf ).
OpenSSL s use of additional input. While analyzing
4.3 OpenSSL
OpenSSL s implementation of SP 800-90, we discovered
an important difference between OpenSSL and the other
Description. OpenSSL is one of the most widely used
TLS libraries, due to its inclusion in many Linux/Apache 5
The bug involves a flaw in the runtime self-test mechanism that
distributions. While the standard edition of OpenSSL causes OpenSSL-FIPS to shut down the generator immediately upon ini-
tializing it. This bug is not triggered while the module is in TEST mode,
does not contain Dual EC, OpenSSL also ships a separate
which explains why unit and Known Answer Tests did not discover the
package called the OpenSSL FIPS Object Module. When
issue. See [13] for details.
this module is combined with OpenSSL, it provides a 6
Although we do not discuss attacks against the client, a recent
TLS library containing all four DRBG algorithms defined fix to the OpenSSL client implementation increases the amount of
PRNG output in the client random to 32 bytes (seehttp://bit.ly/
in NIST SP800-90A, including Dual EC. The Dual EC
1ftSQrM) which may decrease the attack complexity significantly.
algorithm is not the default PRNG in OpenSSL, but it
7
OpenSSL generates this key by drawing 32 random bytes and
can be manually enabled by changing the PRNG settings
checking whether the result (expressed as an integer) is less than the
through an API call at runtime. group order n. If not, the process is repeated.
9
s0 s3 s5 s8
Ï% •" H(adin2) Ï% •" H(adin3)
Ï% •" H(adin1)
x(Ï%"P)
x(Ï%"P)
t1 t4 t6
x(Ï%"P) x(Ï%"P) x(Ï%"P)
x(Ï%"P)
x(Ï%"P) x(Ï%"P)
s1 = t2 s2 s4 s6 = t7 s7
x(Ï%"Q) x(Ï%"Q) x(Ï%"Q) x(Ï%"Q) x(Ï%"Q)
r1 r2 r4 r6 r7
session id server random ecdhe sk
Figure 2: Dual EC usage in OpenSSL-FIPS using ECDHE with P-256.
libraries analyzed in this work. Specifically, OpenSSL we expect to see 1 or 2 candidate states that generate the
provides additional input with each call to the gener- correct first two values. In practice, we never saw more
ate function. The additional input string is constructed than 3 candidate states.
uniquely by the function FIPS_get_timevec() prior to Since the time in seconds is already transmitted as part
each query for random bytes. It comprises 16 bytes with of the server random, the first portion of adin is known.
the following structure. Thus it remains to predict the time in µseconds, process
ID and counter. Under reasonable assumptions about the
adin = (time in secs || time in µsecs || counter || pid)
operating system and the number of connections so far
handled by the server, this can range from approximately
Each of the component fields in the additional input string
220 (primarily guessing the µsecs field) to 235 with a typ-
is 4 bytes in length. On Unix-based systems the time
ical Unix range of pid values and known counter value,
fields are computed using gettimeofday(). The counter
and possibly 245 or more depending on how recently the
is a monotonically increasing global counter that is set
library was initialized. Notice that once an attacker re-
to 0 at library initialization, and increments with each
covers the adin string for a first TLS connection, it may
call to FIPS_get_timevec(). On operating systems where
be relatively easy to predict these values for later connec-
the process IDs are available, pid contains the process ID
tions.
returned from getpid().
A passive attacker can capture 32 consecutive bytes of The inclusion of additional input complicates the attack
Dual EC output by observing the session ID sent to the since recovering the Dual EC state when it is most con-
client by an OpenSSL server. Assuming the generator is venient, namely during the generation of the session ID,
instantiated with P-256, the attacker can now execute the does not immediately translate into recovering the session
initial steps of the basic attack using the first 30 bytes, keys. There are two cases to consider.
in order to recover multiple candidate states, and (using In the first case, the attacker knows nothing about the
the additional two bytes) reduce the number of candidate state of the generator except that the counter value is no
states to one, or a small number. From this point, the bigger than k d" 32 bits. The first step is to recover the
OpenSSL attack differs from the basic attack. Given each generator state (for ease of analysis, assume only one can-
candidate state s, the attacker now calculates the step-14 didate state is possible). As with BSAFE-C, this requires
update s = x(sP) and exhaustively guesses the additional approximately 215 variable base point multiplications and
input string used in the next call to the generate function an equal number of fixed base point multiplications. Next,
as s = s •" H(adin). This requires the attacker to iterate the additional input string needs to be guessed. For each
through a set of candidate adin input strings, executing guess, this takes two fixed base point multiplications.
the steps of the generate algorithm to recover a candidate There are at most 235+k additional input strings to try. A
ECDHE private key, and comparing this value to the guess can be validated by comparing to the server random
intercepted ECDHE public key from a real handshake field. Finally, the ECDHE secret and public keys need to
trace. be computed for each guess of the second additional input
[ Pobierz całość w formacie PDF ]