Cryptography Reference
In-Depth Information
In this situation, Alice exploits the shortness of the checksum. She doesn't
know how to calculate the checksum. But she knows what information Bob's
chip can use to check Alice's LEAF: it knows neither Alice's serial number
nor her unit key. It can compute itself a checksum only from the session key,
the IV, and the LEAF. It will then decrypt the LEAF using the global family
key and compare the resulting checksum with the one it calculated.
Alice proceeds as follows: just like in the first attack, she creates a session key
and an IV on her chip and terminates. She then switches her chip to reception
and feeds it with the session key, the IV, and a
random
LEAF. The chip takes
these pieces to compute a checksum. It then decrypts that nonsensical LEAF
diligently and, from the result, takes a checksum that will naturally not match
the one it computed.
But the checksum is only 16 bits long. 16 bits correspond to 2
16
=
65 536
possibilities. On average, the two checksums will match after 32 768 trials, i.e.,
the LEAF will be accepted. Alice sends this LEAF instead of the correct one
along with the rest. Bob's chip will accept it and decrypt Alice's message with
the session key previously agreed upon. (The chip has to load the session key
directly; it cannot compute it from the LEAF since it doesn't know Alice's unit
key.)
The next thing Uncle Sam hears is perfect noise, for its 'session key' is a
random number.
A Capstone chip requires about 38 ms to check a LEAF. This translates to a
mean time of 42 minutes for finding a random but valid LEAF. This much time
passes between negotiating the session key and starting the communication. It's
too much for a telephone conversation. Bob's software could have a timeout
set to a couple of seconds so that Alice's chance to outsmart Uncle Sam fades
to improbable.
Alice can solve the problem by buying many chips and paralleling her brute-
force attack. The NSA who designed the chip could easily defend itself from
this: it suffices that one Capstone or Clipper chip refuses its service for one
minute after every 50th wrong LEAF (and apart from that, it should take a
minute to start up; otherwise, Alice might briefly disconnect the chip from the
power source after each failed attempt).
And what does the NSA do? They have the chip reset itself after every tenth
failed attempt. This extends these 42 minutes to 46 minutes. In his article,
Blaze thanked the NSA staff for their extensive help in his analyses.
