Cryptography: Theory and Practice:The Data Encryption Standard

cryptography: theory and practice Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210   Pub Date: 03/17/95
  

Previous Table of Contents Next


Example 3.4

Suppose we have the following plaintext-ciphertext pair:


plaintext ciphertext

86FA1C2B1F51D3BE 1E23ED7F2F553971
C6F21C2B1B51D3BE 296DE2B687AC6340

Observe that and . The S-box inputs and outputs for round 6 are computed to be the following:

Then, the sets testj are as follows:

We see that both test5 and test7 are empty sets, so this pair is a wrong pair and is discarded by the filtering operation.

Now suppose that we have a pair such that |testj| > 0 for j = 2, 5, 6, 7, 8, so that it survives the filtering operation. (Of course, we do not know if the pair is a right pair or a wrong pair.) We say that the bitstring J2J5J6J7J8 of length 30 is suggested by the pair if Jjtestj for j = 2, 5, 6, 7, 8. The number of suggested bitstrings is

It is not unusual for the number of suggested bitstrings to be quite large (for example, greater than 80000).

Suppose we were to tabulate all the suggested bitstrings obtained from the N pairs that were not discarded by the filtering operation. For every right pair, the correct bitstring J2J5J6J7J8 will be a suggested bitstring. This correct bitstring will be counted about 3N/16 times. Incorrect bitstrings should occur much less often, since they will occur essentially at random and there are 230 possibilities (a very large number).

It would get extremely unwieldy to tabulate all the suggested bitstrings, so we use an algorithm that requires less space and time. We can encode any testj as a vector Tj of length 64, where the ith coordinate of Tj is set to 1 (for 0 ≤ i ≤ 63) if the bitstring of length six that is the binary representation of i is in the set testj; and the ith coordinate is set to 0 otherwise (this is essentially the same as the counter array representation that we used in the 3-round attack).

For each remaining pair, construct these vectors as described above, and name them , j = 2, 5, 6, 7, 8, 1 ≤ iN. For I ⊆ {1, . . . , N}, we say that I is allowable if for each j ∈ {2, 5, 6, 7, 8}, there is at least one coordinate equal to |I| in the vector

If the ith pair is a right pair for every iI, then the set I is allowable. Hence, we expect there to be an allowable set of size (approximately) 3N/16, which we hope will suggest the correct key bits and no other. It is a simple matter to construct all the allowable sets I by means of a recursive algorithm.

Example 3.5

We did some computer runs to test this approach. A random sample of 120 pairs of plaintexts with the specified x-ors was generated, and these were encrypted using the same (random) key. We present the 120 pairs of ciphertexts and corresponding plaintexts in hexadecimal form in Table 3.1.

When we compute the allowable sets, we obtain ni allowable sets of cardinality i, for the following values:

The unique allowable set of size 10 is

In fact, it does arise from the 10 right pairs. This allowable set suggests the correct key bits for J2, J5, J6, J7 and J8 and no others. They are as follows:


Figure 3.14  Another 3-round characteristic

Note that all the allowable sets of cardinality at least 6, and all but three of the allowable sets of cardinality 5, arise from right pairs, since and for 6 ≤ i ≤ 10.

This method yields 30 of the 56 key bits. By means of a different 3-round characteristic, presented in Figure 3.14, it is possible to compute 12 further key bits, namely those in J1 and J4. Now only 14 key bits remain unknown. Since 214 = 16384 is quite small, an exhaustive search can be used to determine the remaining 14 key bits.

The entire key (in hexadecimal, including parity-check bits) is:

34E9F71A20756231.

As mentioned above, the 120 pairs are given in Table 3.1. In the second column, a * denotes that a pair is a right pair, while a ** denotes that the pair is an identifiable wrong pair and is discarded by the filtering operation. Of the 120 pairs, 73 are identified as being wrong pairs by the filtering process, so 47 pairs remain as “possible” right pairs.


Previous Table of Contents Next

Copyright © CRC Press LLC



Cryptography. Theory and Practice
Modern Cryptography: Theory and Practice
ISBN: 0130669431
EAN: 2147483647
Year: 1995
Pages: 133
Authors: Wenbo Mao

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net