Cryptography Reference
In-Depth Information
XOR in the feedback are referred to as a
tap sequence
. Such an LFSR is very
easy to implement in hardware, of course.
What has all this got to do with cryptology? Well, we could fill an LFSR with
a secret content — the key — and then use the bit sequence created for a stream
cipher. That's far from being secure yet. First, LFSRs have a period, which
means that, after a finite number of steps, a state repeats itself. If this period
is too short and much of the ciphertext is known, we could mount an attack
similar to how we would attack the Vigenere cipher. The period length can
be maximally 2
n
−
1 for an LFSR
n
bits long (though the LFSR can accept
2
n
values at most, value 0 is not applicable: once all bits are equal to 0, they
will remain equal to 0). The period is maximal if the tap sequence corre-
sponds to a so-called
primitive polynomial modulo 2
. Rather than explaining
this term, I refer to [SchnCr] and the large number of literature references
included therein.
LFSRs have been interesting for a long time and formed the backbone of mili-
tary cryptography because they are particularly easy to implement in switching
circuits, and because of the high ciphering speed. On the one hand, there is
a mature mathematical theory of LFSRs. On the other hand, little is known
about their use in devices, and most developments are secret [SchnCr, 16.4].
It is interesting that almost all Cray supercomputers process a strange machine
command that determines the number of bits set in a register. This means that
an LFSR can also be implemented very efficiently in software. It is believed that
this command is a requirement in almost all computer contracts with the NSA.
It has meanwhile become an open secret that Cray computers were initially
built mainly for cryptanalysis.
Simple LFSRs don't offer cryptological security any longer; they are easily
cracked. A plaintext attack with 2
n
successive plaintext - ciphertext bit pairs
suffices to break an
n
-bit LFSR. For this reason, several LFSRs are linked in
as complicated a way as possible. We will only look at a brief outline of A5
in this topic.
The A5 algorithm uses three LFSRs with lengths of 19, 22, and 23 bits, i.e., 64
bits in total (and that's also the key length). The tap sequences (bits counted
from 0 on) are:
18, 17, 16, 13 for the 19-bit register,
21, 20, 16, 12 for the 22-bit register,
22, 21, 18, 17 for the 23-bit register.
