Clutch cryptanalysis of Wring

Clutch cryptanalysis (named for the car part, not the bird litter) is applicable to ciphers with data-dependent rotations. It is a chosen-plaintext attack which tries to find pairs of plaintexts which are rotated by the same number of bits for some number of rounds. As applied to Wring, it consists of the following steps:

  1. Pick a plaintext and either one byte or three bytes affected by the mix3 operation.
  2. Change the selected byte(s) to all possible values.
  3. Encrypt all the plaintexts, using full or reduced rounds.
  4. Find pairs of ciphertexts that match more than chance; they were probably rotated together.
  5. From the bytes that changed, try to figure out which bytes in the S-boxes have the same number of bits, or even what the bytes in the S-boxes are.

These graphs are from running a version of clutch cryptanalysis in which the reduced-round encryption function returns the number of bits that the message was rotated by in each block as well as the ciphertext. This enables me to check what happens when the total number of bits two plaintexts were rotated is the same, but the number of bits they were rotated by in some round differs. I use four keys each of three different lengths, originally chosen for a related-key attack, and a Wring with linear S-boxes, and encrypt random-looking 10000-byte, 8192-byte, and 7776-byte messages. All these message sizes take 11 rounds [6561,19683), but I do only 8 rounds, by which no messages are rotated together all the way through.

Graphs by key, 10000 byte messages:

key96_0 key96_1 key96_2 key96_3
key30_0 key30_1 key30_2 key30_3
key6_0 key6_1 key6_2 key6_3
Linear

Graphs by key, 8192 byte messages:

key96_0 key96_1 key96_2 key96_3
key30_0 key30_1 key30_2 key30_3
key6_0 key6_1 key6_2 key6_3
Linear

Graphs by key, 7776 byte messages:

key96_0 key96_1 key96_2 key96_3
key30_0 key30_1 key30_2 key30_3
key6_0 key6_1 key6_2 key6_3
Linear