next up previous contents
Next: Link Differences Up: Block Differences Previous: Block Differences

Differential cryptanalysis of rule 30.

The toggle property has a clear signature in differential cryptanalysis. To see this, let us consider the differential cryptanalysis of the rule 30 cryptosystem introduced in section 3.1. We begin with 4-bit plaintext blocks, encrypted 4 iterations, and fix the link at 00001110. All possible 4-bit blocks are encrypted, and the ciphertexts examined. The resulting pairs-XOR table is shown in figure 10. The rows are indexed by the plaintext XOR's, and the columns by the ciphertext XOR's. The table entries give the number of ways the given plaintext XOR/ciphertext XOR can be achieved. The non-uniformities in the table are potential handholds for cryptanalysts.

In practice, differential cryptanalysts are not permitted to fix the link as was done to generate figure 10. The link is chosen, at random, by the encryption apparatus. If the cryptosystem is functioning correctly, all possible links have the same probability. For a block-link cryptosystem, then, the observable pairs-XOR table is an average over the pairs-XOR tables corresponding to fixed link information, as in figure 10. This observable pairs-XOR table for the rule 30 cryptosystem is shown in figure 11. The entries in this table give the probability of the corresponding plaintext pair/ciphertext pair XOR's. The observable pairs-XOR table is again highly nonuniform. It has an evident fractal structure. This structure is the result of the toggle property. A plaintext difference at a given position in the plaintext always produces a ciphertext difference at position away from the given position under a radius r toggle rule iterated n times.

In CA-1.0 fully nonlinear cellular automata are used in addition to partially linear toggle rules in order to destroy this sort of structure in the pairs XOR-tables. Numerical evidence indicates that the fractal structure is fragile; it is easily destroyed by nonlinear substitutions such as performed in CA-1.0. Further numerical evidence suggests that if only toggle rules are used for encryption, but the radius of the toggle CA is sufficiently large, then the only significant structure in observable pairs-XOR tables is due the the toggle property.



next up previous contents
Next: Link Differences Up: Block Differences Previous: Block Differences



Howard A. Gutowitz
Fri May 12 06:16:18 MDT 1995