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 Jj ∈ testj 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 ≤ i ≤ N. 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 i ∈ I, 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