DES properties and strength
There are many desirable characteristics for block ciphers. These include: each bit of the ciphertext should depend on all bits of the key and all bits of the plaintext; there should be no statistical relationship evident between plaintext and ciphertext; altering any single plaintext or key bit should alter each ciphertext bit with probability i; and altering a ciphertext bit should result in an unpredictable change to the recovered plaintext block. Empirically, DES satisfies these basic objectives. Some known properties and anomalies of DES are given below.
 (i) Complementation property
 7.87 Fact Let E denote DES, and x the bitwise complement of x. Then у = Ек(х) implies V = %(*)■ That is, bitwise complementing both the key К and the plaintext x results in complemented DES ciphertext.
Justification: Compare the first round output (see Figure 7.10) to (L_{0}. /?«) for the uncomplemented case. The combined effect of the plaintext and key being complemented results in the inputs to the XOR preceding the Sboxes (the expanded R,i and subkey K,) both being complemented; this double complementation cancels out in the XOR operation, resulting in Sbox inputs, and thus an overall result /(До, Кi), as before. This quantity is then XORed (Figure 7.9) to L_{0} (previously L_{0}), resulting in L (rather than L). The same effect follows in the remaining rounds.
The complementation property is normally of no help to a cryptanalyst in knownplain text exhaustive key search. If an adversary has, for a fixed unknown key K, a chosen plaintext set of (x, y) data (Pi, Ci), (Pi, Cr), then C2 = Ek(P) implies C2 = Ey(Pi) Checking if the key К with plaintext P yields either C or C2 now rules out two keys with one encryption operation, thus reducing the expected number of keys required before success from 2^{55} to 2^{54}. This is not a practical concern.
(ii) Weak keys, semiweak keys, and fixed points
If subkeys Кi to К_{1G} are equal, then the reversed and original schedules create identical subkeys: K = Км, K_{2} = Км, and so on. Consequently, the encryption and decryption functions coincide. These are called weak keys (and also: palindromic keys).
7.88 Definition ADES weakkeyis akey К such that Ek(Ek(x)) = x for all x,i.e., defining an involution. A pair of DES semiweak keys is a pair (K, K>) with Ek, (Ek_{2} (x)) = x.
Encryption with one key of a semiweak pair operates as does decryption with the other.
7.89 Fact DES has four weak keys and six pairs of semiweak keys.
The four DES weak keys are listed in Table 7.5, along with corresponding 28bit variables Co and D_{0} of Algorithm 7.83; here {()}^{J} represents j repetitions of bit 0. Since C_{0 }and Do are allzero or allone bit vectors, and rotation of these has no effect, it follows that all subkeys Ki are equal and an involution results as noted above.
The six pairs of DES semiweak keys are listed in Table 7.6. Note their defining property (Definition 7.88) occurs when subkeys K through Км of the first key, respectively, equal subkeys Km through K of the second. This requires that a 1bit circular leftshift of each of Co and D_{0} for the first 56bit key results in the (Co, Do) pair for the second 56bit key (see Note 7.84), and thereafter leftrotating C, and D, one or two bits for the first results in the same value as rightrotating those for the second the same number of positions. The values in Table 7.6 satisfy these conditions. Given any one 64bit semiweak key, its paired semiweak key may be obtained by splitting it into two halves and rotating each half through 8 bits.
7.90 Fact Let E denote DES. For each of the four DES weak keys K, there exist 2^{32} fixed points of ЕкЛЪ; plaintexts x such that Ek(x) = x. Similarly, four of the twelve semiweak keys К each have 2^{32} antifixed points, i.e., x such that Ek(x) = x.
The four semiweak keys of Fact 7.90 are hi the upper portion of Table 7.6. These are called antipalindromic keys, since for these K = K_{G}, K_{2} = Km, and so on.
(iii) DES is not a group
For a fixed DES key К, DES defines a permutation from {0, l}^{64} to {0, l}^{64}. The set of DES keys defines 2^{5G} such (potentially different) permutations. If this set of permutations was closed under composition (i.e., given any two keys К1, K_{2}, there exists a thud key К_{л }such that Ej{_{3} (x) = Ек, (Ek, (x)) for all x) then multiple encryption would be equivalent to single encryption. Fact 7.91 states that this is not the case for DES.
weak key (hexadecimal) 
Co 
D_{0} 
0101 0101 0101 0101 
{0}^{28} 
{0}^{28} 
FEFE FEFE FEFE FEFE 
{l}^{28} 
{l}^{28} 
1F1F 1F1F 0E0E 0E0E 
{0}^{28} 
{l}^{28} 
E0E0 E0E0 F1F1 F1F1 
{l}^{28} 
{0}^{28} 
Table 7.5: Four DES weak keys.
Co 
Do 
semiweak key pair (hexadecimal) 
Co 
Do 
О о 
{01}^{14} {10}^{14} 
01FE 01FE 01FE 01FE, FE01 FE01 FE01 FE01 1FE0 1FE0 0EF1 0EF1, E01F E01F F10E F10E 
{10}^{14} {10}^{14} 
{10}^{14} {01}^{14} 
{01}^{14} {01}^{14} {0}^{28} m^{28} 
{0}^{28} m^{28} {01}^{14} {01}^{14} 
01E0 01E0 01F1 01F1, E001 E001 F101 F101 1FFE 1FFE OEFE OEFE, FE1F FE1F FEOE FEOE 011F 011F 010E 010E, 1F01 1F01 0E01 0E01 EOFE EOFE FIFE FIFE, FEEO FEEO FEF1 FEF1 
{10}^{14} {10}^{14} {0}^{28} {l}^{28} 
{0}^{28} {l}^{28} {10}^{14} {10}^{14} 
Table 7.6: Six pairs of DES semiweak keys (one pair per line).
7.91 Fact The set of 2^{5e} permutations defined by the 2^{5e} DES keys is not closed under functional composition. Moreover, a lower bound on the size of the group generated by composing this set of permutations is 10^{2499}.
The lower bound in Fact 7.91 is important with respect to using DES for multiple encryption. If the group generated by functional composition was too small, then multiple encryption would be less secure than otherwise believed.
(iv) Linear and differential cryptanalysis of DES
Assuming that obtaining enormous numbers of knownplaintext pans is feasible, linear cryptanalysis provides the most powerful attack on DES to date; it is not, however, considered a threat to DES hi practical environments. Linear cryptanalysis is also possible in a ciphertextonly environment if some underlying plaintext redundancy is known (e.g., parity bits or highorder Оbits in ASCII characters).
Differential cryptanalysis is one of the most general cryptanalytic tools to date agamst modern iterated block ciphers, including DES, Lucifer, and FEAL among many others. It is, however, primarily a chosenplaintext attack. Further information on linear and differential cryptanalysis is given in §7.8.
7.92 Note (strength of DES) The complexity (see §7.2.1) of the best attacks currently known against DES is given in Table 7.7; percentages mdicate success rate for specified attack parameters. The ‘processing complexity’ column provides only an estimate of the expected cost (operation costs differ across the various attacks); for exhaustive search, the cost is in DES operations. Regarding storage complexity, both linear and differential cryptanalysis require only negligible storage in the sense that known or chosen texts can be processed individually and discarded, but in a practical attack, storage for accumulated texts would be required if ciphertext was acquired prior to commencing the attack.
attack method 
data complexity 
storage complexity 
processing complexity 

known 
chosen 

exhaustive precomputation 
 
1 
2 ^{56} 
1 (table lookup) 
exhaustive search 
1 
 
negligible 
2^{55} 
linear cryptanalysis 
2^{43} (85%) 
 
for texts 
2^{43} 
2^{38} (10%) 
 
for texts 
_{2}so 

differential cryptanalysis 
 
2^{47} 
for texts 
2^{47} 
_{2}5S 
 
for texts 
_{2}S5 
Table 7.7: DES strength against various attacks.
7.93 Remark (practicality of attack models) To be meaningful, attack comparisons based on different models (e.g., Table 7.7) must appropriately weigh the feasibility of extracting (acquiring) enormous amounts of chosen (known) plaintexts, which is considerably more difficult to arrange than a comparable number of computing cycles on an adversary’s own machine. Exhaustive search with one known plaintextciphertext pair (for ciphertextonly, see Example 7.28) and 2^{55} DES operations is significantly more feasible in practice (e.g., using highly parallelized custom hardware) than linear cryptanalysis (LC) requiring 2^{43} known pairs.
While exhaustive search, linear, and differential cryptanalysis allow recovery of a DES key and, therefore, the entire plaintext, the attacks of Note 7.8, which become feasible once about 2^{32} ciphertexts are available, may be more efficient if the goal is to recover only part of the text.