Exercise 3.7 from Cryptography Engineering:

Describe an example system that uses DES but is insecure because of the DES complementation property. Specifically, describe the system, and then present an attack against that system; the attack should utilize the DES complementation property.

Complementation Property of DES

The complementation property of DES says that , where is the value of DES encrypted with key .

Example System

A multi-user file system where each file is DES encrypted with a single key, .

Attack

The attacker sends two 64-bit blocks to be written to the file system, and . The file system writes out two encrypted blocks to physical storage, and .

For each key candidate , compute . This is a single cryptographic operation. If the value is equal to , then (i.e., the key was found).

Otherwise, compute the complement of the previous crypgraphic operation, namely , which by the complementation property is . If , then (i.e., the key was found).

The attack is thus able to check 2 key candidates for each cryptographic operation, reducing the attack on the possible DES keys in half to .

References

The main idea for this answer is taken from fgrieu’s answer on Cryptography Stack Exchange.