Cryptography Reference
In-Depth Information
This table actually gives the difference of each count from half of the total number of plaintexts (equivalent to
the bias). In this test case, we had 1,800 plaintext-ciphertext pairs (slightly more than required). The one with
the highest bias (usually fairly close to the expected value) is normally the key. The difference for entry number
9 above, which is the highest value, is 121/1800 ≈ 0.0672. This is fairly close to the expected value of approx-
imately 0.0684.
6.7 Linear Cryptanalysis of DES
Performing linear cryptanalysis on the EASY1 cipher is pretty straightforward: Simply trace the bits forward.
The analysis is not quite as easy when integrating more complicated structures, such as Feistel structures.
No Feistel structure will be quite the same, but we can adapt the same technique as before to trace our way
through the cipher. I'll show how this is done for DES, as outlined in Reference [4]. Note that for this, and other
techniques working with DES, we ignore the initial and final permutations, as they do nothing to thwart crypt-
analysis of the algorithm.
First, note that the following linear expression holds for the round function of DES (with input X , round key
K, and round function value F):
This equation is true with a probability of 12/64 = 0.1875 (bias -0.3125).
When we are doing analysis on larger ciphers (such as the 64-bit DES), it is necessary to introduce a more
compact way of specifying the bits to be used. Instead of writing F 7 F 1 8 F 24 F 29 , we would rather use
brackets to denote which bits we are extracting and XORing, so that instead we could write F [7,18,24,29] .
This lets us write the previous equation as
Now that we have a round function equation, we can extend this into an equation for the entire round, by
XORing it with the appropriate bits in the other half in the round.
For example, in the first round of DES, we have L 1 = R 0 and R 1 = L 0 f ( R 0 , K 1 ). Obviously, there isn't much
to do for L 1 , since it is just a copy of R 0 , but by using the linear equation above, we can get a linear equation
for the entire round. Denote the output of the round function for the first round as F 2 (and the other rounds will,
naturally, be F 2 , etc.), with the corresponding keys K 1 , and so on, as well. Therefore, we have the following
linear expression:
Search WWH ::




Custom Search