Cryptography Reference
In-Depth Information
We look at the middle bit of each register (i.e., positions 9, 11, and 13). Every
ciphering step moves a register forward exactly when either its middle bit is
equal to 1 and the middle bits of the other two registers are equal to 0, or vice
versa (the bit considered is 0, the others are equal to 1). The feedback bit — and
not the bit pushed out in that step — goes into the key stream. That's all!
The points of departure for cryptanalyzing A5 are the register lengths and the
tap sequences — both are too short. The register lengths allow you to mount a
plaintext attack with 2
40
trial-and-error encryptions on average: you guess the
first two registers and compute the third from the key stream. Little plaintext
will suffice, because one single 23-bit LFSR can be broken with 46 bits of
plaintext. Ross Anderson estimates that the computing performance required
can be handled by programmed Xilinx chips: if each chip trial-and-error tests
two keys per microsecond and 50 chips are housed in a special computer, the
key should be found in about 3 hours on average. The insufficient lengths of
the tap sequences appear to have been exploited by Dr Shepherd.
Birkyukov and Shamir put an end to all the speculation around A5 in 2000.
They showed how to crack A5 in their publication [BirShamA5]. You need
a computer with two 73-GB hard disks. You fill them with data computed
in advance. This is certainly costly, but you need to do it only once. You
then
replay 2 minutes' worth of plaintext and ciphertext
of a communication
and put the computer to work; it will compute for
1 second
, and you will
have the session key. Alternatively, you need a 2-second plaintext and several
minutes of computation time. This is more realistic for data transmission, if the
beginning of the data stream is known. This method doesn't work for normal
voice communication, though. You would proceed differently.
GSM handsets know an additional algorithm called
A5/2
(probably the reason
why A5 is sometimes called 'A5/1'), which is much more insecure than A5.
In 2003, Barkan, Biham, and Keller published an article (
cryptome.org/gsm-
crack-bbk.pdf
on the Web site to this topic) describing how to practically and
effectively attack A5/2. They exploited an error in the protocol: the checksum
of the data packets is a CRC, an algebraic function of the packet's bits, and
this CRC is included in the cipher. Now, A5/2 is so weak that the algebraic
dependency between CRC and data is not sufficiently blurred (insufficient con-
fusion). You can reveal the key by
replaying a few hundredths of seconds
of the
ciphertext within a
1-second computation time
. In practice, Mallory could use
an IMSI catcher, play the man in the middle, and convince the handset at the
beginning of the conversation to use A5/2 instead of A5/1. The cost amounts
to a couple of thousand dollars and sufficient know-how.
