Cryptography Reference
In-Depth Information
Describe in detail how such a cipher can be attacked. Specify exactly what Oscar
has to know in terms of plaintext/ciphertext, and how he can decrypt all ciphertext.
2.7.
Compute the first two output bytes of the LFSR of degree 8 and the feedback
polynomial from Table 2.3 where the initialization vector has the value FF in hex-
adecimal notation.
2.8.
In this problem we will study LFSRs in somewhat more detail. LFSRs come in
three flavors:
LFSRs which generate a maximum-length sequence. These LFSRs are based on
primitive polynomials
.
LFSRs which do not generate a maximum-length sequence but whose sequence
length is independent of the initial value of the register. These LFSRs are based
on
irreducible polynomials
that are not primitive. Note that all primitive polyno-
mials are also irreducible.
LFSRs which do not generate a maximum-length sequence and whose sequence
length depends on the initial values of the register. These LFSRs are based on
reducible polynomials
.
We will study examples in the following. Determine
all
sequences generated by
1.
x
4
+
x
+ 1
2.
x
4
+
x
2
+ 1
3.
x
4
+
x
3
+
x
2
+
x
+ 1
Draw the corresponding LFSR for each of the three polynomials. Which of the
polynomials is primitive, which is only irreducible, and which one is reducible?
Note that the lengths of all sequences generated by each of the LFSRs should add
up to 2
m
−
1.
2.9.
Given is a stream cipher which uses a single LFSR as key stream generator. The
LFSR has a degree of 256.
1. How many plaintext/ciphertext bit pairs are needed to launch a successful attack?
2. Describe all steps of the attack in detail and develop the formulae that need to be
solved.
3. What is the key in this system? Why doesn't it make sense to use the initial
contents of the LFSR as the key or as part of the key?
2.10.
We conduct a known-plaintext attack on an LFSR-based stream cipher. We
know that the plaintext sent was:
1001 0010 0110 1101 1001 0010 0110
By tapping the channel we observe the following stream:
1011 1100 0011 0001 0010 1011 0001
1. What is the degree
m
of the key stream generator?
2. What is the initialization vector?
3. Determine the feedback coefficients of the LFSR.
