Cryptography Reference
In-Depth Information
to compute one key stream bit. In the latter case, they tend to be based on operations
which can easily be realized in hardware. A popular example is shift registers with
feedback, which are discussed in the next section. A third class of stream ciphers
is realized by using block ciphers as building blocks. The cipher feedback mode,
output feedback mode and counter mode to be introduced in Chap. 5 are examples
of stream ciphers derived from block ciphers.
It could be argued that the state-of-the-art in block cipher design is more ad-
vanced than stream ciphers. Currently it seems to be easier for scientists to design
“secure” block ciphers than stream ciphers. Subsequent chapters deal in great detail
with the two most popular and standardized block ciphers, DES and AES.
2.3 Shift Register-Based Stream Ciphers
As we have learned so far, practical stream ciphers use a stream of key bits
s
1
,
s
2
,...
that are generated by the key stream generator, which should have certain properties.
An elegant way of realizing long pseudorandom sequences is to use linear feedback
shift registers (LFSRs). LFSRs are easily implemented in hardware and many, but
certainly not all, stream ciphers make use of LFSRs. A prominent example is the
A5/1 cipher, which is standardized for voice encryption in GSM. As we will see,
even though a plain LFSR produces a sequence with good statistical properties, it
is cryptographically weak. However, combinations of LFSRs, such as A5/1 or the
cipher Trivium, can make secure stream ciphers. It should be stressed that there
are many ways for constructing stream ciphers. This section only introduces one of
several popular approaches.
2.3.1 Linear Feedback Shift Registers (LFSR)
An LFSR consists of clocked storage elements (
flip-flops
) and a
feedback path
.The
number of storage elements gives us the
degree
of the LFSR. In other words, an
LFSR with
m
flip-flops is said to be of degree
m
. The feedback network computes
the input for the last flip-flop as XOR-sum of certain flip-flops in the shift register.
Example 2.3.
Simple LFSR
We consider an LFSR of degree
m
= 3 with flip-flops
FF
2
,
FF
1
,
FF
0
, and a feedback path as shown in Fig. 2.6. The internal state bits are
denoted by
s
i
and are shifted by one to the right with each clock tick. The rightmost
state bit is also the current output bit. The leftmost state bit is computed in the
feedback path, which is the XOR sum of some of the flip-flop values in the previous
clock period. Since the XOR is a linear operation, such circuits are called linear
feedback shift registers. If we assume an initial state of (
s
2
= 1
,
s
1
= 0
,
s
0
= 0),
Table 2.2 gives the complete sequence of states of the LFSR. Note that the rightmost
column is the output of the LFSR. One can see from this example that the LFSR
