Differential Cryptanalysis - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 171

Wewill also toggle bits 1,9,15,and23of L 0 :These are the output bits ofthe S-box S 1 (which isalso affected
by 6 bits of the key). Bits 29 and 30 are also used as the input to S 1 (and no other S-box in round 1); thus, our
changes affect only S 1 . This gives a total of 64 plaintexts, with their ciphertexts.
At first glance, none of these plaintext-ciphertext pairs are really ''paired'' in the way that differential crypt-
analysis requires. However, it turns out that there are several such pairings. We can pair each plaintext value
(there are 64) with three other plaintexts: one with bit 29 of R 0 toggled, one with bit 30 of R 0 toggled, and one
with both bits toggled in R 0 . This way, we have three pairs, for a theoretical total of 64 × 3 = 192 pairings. In
reality, we get half as many (96), since half of the pairings are redundant.
This way, we are getting 96 pairings for 64 plaintexts (a ratio of 3-for-2), instead of the normal 1-for-2
of standard differential cryptanalysis because in differential cryptanalysis, we generate one plaintext, and then
XOR it with a fixed value to obtain another plaintext. Thus, we have two plaintexts and one pairing, for a ratio
of 1-for-2, which is approximately three times less efficient than combining the two techniques.
While this technique doesn't yield more key bits than either differential or linear cryptanalysis, it does allow
us to derive these key bits with fewer plaintext-ciphertext pairs, while still maintaining a high success rate.
There are some issues with scalability, though: This method works well for fewer numbers around and doesn't
apply well to more rounds.
7.10 Conditional Characteristics
It is difficult to apply differential cryptanalysis to certain classes of ciphers. For example, if we have certain
portions of the cipher modify the structure of the cipher itself based on the key, then we would not be able to
effectively develop iterative characteristics to use in differential cryptanalysis. Ben-Aroya and Biham explore a
particular method against two particular ciphers thought to be strong against differential cryptanalysis using a
technique called conditional characteristics [1].
One of the ciphers they analyze is called RandomizedDES ( RDES ). Many cryptologists thought that a way
to limit the susceptibility of DES to differential cryptanalysis was to swap the left and right halves during some
of the rounds: which rounds depended on the key value. Since there are 16 different rounds, there would be 2 16
= 65,536 different combinations of swapping and not swapping, thereby making normal differential analysis
extremely difficult.
Naturally, there is one problem. For a certain number of keys (one out of every 2 15 of them), there would be
no swapping at all! If subjected to a known-plaintext attack, the entire right half would not be affected by the
encryption, passing through the rounds untouched. Similarly, for another set of one out of every 2 15 keys, there
would only be a swap on the last round, allowing us to easily derive most of the key bits using simple analysis
of the inputs and outputs of the round function.
The rest of the keys is where the concept of a conditional characteristic comes in handy. A conditionalchar-
acteristic is a characteristic that is dependent on the key being used. Typically, the characteristic is only effect-
ive against keys with certain properties (such as certain bits being set). The number of keys that the conditional
characteristic is good for, divided by the total number of keys, is called the key ratio .
The attack uses two different round function characteristics of DES:
When combined, they provide a two-round iterative characteristic: