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 (L0. /?«) for the uncomplemented case. The combined effect of the plaintext and key being complemented results in the inputs to the XOR preceding the S-boxes (the expanded R,-i and subkey K,) both being complemented; this double complementation cancels out in the XOR operation, resulting in S-box inputs, and thus an overall result /(До, Кi), as before. This quantity is then XORed (Figure 7.9) to L0 (previously L0), 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 known-plain- 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 255 to 254. This is not a practical concern.

(ii) Weak keys, semi-weak keys, and fixed points

If subkeys Кi to К1G are equal, then the reversed and original schedules create identical subkeys: K = Км, K2 = Км, 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 semi-weak keys is a pair (K, K>) with Ek, (Ek2 (x)) = x.

Encryption with one key of a semi-weak pair operates as does decryption with the other.

7.89 Fact DES has four weak keys and six pairs of semi-weak keys.

The four DES weak keys are listed in Table 7.5, along with corresponding 28-bit variables Co and D0 of Algorithm 7.83; here {()}J represents j repetitions of bit 0. Since C0 and Do are all-zero or all-one 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 semi-weak 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 1-bit circular left-shift of each of Co and D0 for the first 56-bit key results in the (Co, Do) pair for the second 56-bit key (see Note 7.84), and thereafter left-rotating C, and D, one or two bits for the first results in the same value as right-rotating those for the second the same number of positions. The values in Table 7.6 satisfy these conditions. Given any one 64-bit semi-weak key, its paired semi-weak 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 232 fixed points of ЕкЛ-Ъ; plaintexts x such that Ek(x) = x. Similarly, four of the twelve semi-weak keys К each have 232 anti-fixed points, i.e., x such that Ek(x) = x.

The four semi-weak keys of Fact 7.90 are hi the upper portion of Table 7.6. These are called anti-palindromic keys, since for these K = KG, K2 = 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 25G such (potentially different) permutations. If this set of permutations was closed under composition (i.e., given any two keys К1, K2, 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

D0

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

semi-weak 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

m28

{0}28

m28

{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 semi-weak keys (one pair per line).

7.91 Fact The set of 25e permutations defined by the 25e 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 102499.

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 known-plaintext 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 ciphertext-only environment if some underlying plaintext redundancy is known (e.g., parity bits or high-order О-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 chosen-plaintext 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

255

linear cryptanalysis

243 (85%)

-

for texts

243

238 (10%)

-

for texts

2so

differential cryptanalysis

-

247

for texts

247

25S

-

for texts

2S5

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 plaintext-ciphertext pair (for ciphertext-only, see Example 7.28) and 255 DES operations is significantly more feasible in practice (e.g., using highly parallelized custom hardware) than linear cryptanalysis (LC) requiring 243 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 232 ciphertexts are available, may be more efficient if the goal is to recover only part of the text.

 
Source
< Prev   CONTENTS   Source   Next >