[Cryptography] Wring isn't as secure on big messages as I thought

[Pierre Abbat]

Continuing clutch cryptanalysis, I estimated the probability that two long 
messages which start out differing by one byte rotate together for the first n 
rounds. This depends on the number of different bytes after the mix3 step, 
which is inaccessible; the encryptN! function returns the number of different 
bytes after the whole round. So I computed it from the fraction that remain 
rotating together after up to five rounds. (Only one pair of 10 kB messages 
rotated together for six rounds, out of over 500M pairs.)

I designed Wring so that the number of different bytes would increase by a 
factor of at least three each round. I figured that, with the rotation 
splitting the bits of a byte across two bytes, it would increase by somewhere 
between three and six. It didn't.

The actual ratios are 3.85, 3.5, 3, 2.6, and 2.1 for the first five rounds. I 
figured I could extrapolate with 2 for the rest of the rounds. This means that 
after 11 rounds I'd have 14118 different bytes in an infinite message, or 2437 
bytes unaffected in a 10 kB message, enough to easily tell that two messages 
rotated together. This would happen 2.25e-21 of the pairs. Since one group of 
256 chosen plaintexts yields 255*128 pairs, that means I'd have to try 
3.485e18 plaintexts to learn something about the population count of a byte in 
an S-box.

To fix this, I could rearrange the mix3 operation, or I could increase the 
number of rounds. I'm not sure what rearrangement of mix3 would improve the 
security, so I'll consider increasing the number of rounds. Currently it 
starts at 3 for 1 byte and increases at every power of 3. If it increases at 
every power of 2, that means that a 10 kB message takes 16 rounds.

After 16 rounds, I'd have 452036 different bytes in an infinite message, or 
2.34e-16 byte unaffected in a 10 kB message. There is thus no way to tell that 
a pair of messages rotated together through 16 rounds, which would happen to 
only 4.9e-37 of the pairs of plaintexts anyway.

Can you think of a better mix3parts pattern, or should I simply increase the 
number of rounds?

Here's the computation. The second column is the number of different bytes 
after mixing and before rotating; the third is the incremental ratio, and the 
fourth is the fraction of pairs that made it through all those rounds rotating 
together.
1 2.5428467355896336 0.12432304600402871 0.12432304600402871
2 8.229543819393 0.06940130311625133 0.008628181400061255
3 23.949203545149512 0.04073344947055979 0.00035145559108221895
4 59.60756120082263 0.025829473359532652 9.077912826916976e-6
5 143.03141112374047 0.016676961087090846 1.5139199896649726e-7
6 286.06282224748094 0.011793036402589198 1.7853713548726485e-9
7 572.1256444949619 0.00833916375412329 1.488850409020398e-11
8 1144.2512889899238 0.005896759760741033 8.779393181674311e-14
9 2288.5025779798475 0.004169667282705026 3.6607148511630963e-16
10 4577.005155959695 0.0029484100765654405 1.079328855460203e-18
11 9154.01031191939 0.002084844316999031 2.250232630479273e-21
12 18308.02062383878 0.0014742088126869213 3.317312774448217e-24
13 36616.04124767756 0.001042423493137231 3.4580447701690695e-27
14 73232.08249535512 0.0007371048789983909 2.5489416718864906e-30
15 146464.16499071024 0.0005212119126197861 1.328538763960233e-33
16 292928.3299814205 0.00036855249723405045 4.8963627912978255e-37

Pierre
-- 
Don't buy a French car in Holland. It may be a citroen.