[Cryptography] Weak keys in chosen-plaintext attack on 2-round Wring

[Pierre Abbat]

A weak key in Wring (and Twistree, which uses the same key schedule) is a key 
which results in the three S-boxes being identical or nearly so. Because of 
the complicated nonlinear key schedule, which adds plenty of confusion even 
before the S-boxes are used to encipher the message, it is difficult to find 
actual weak keys. So I made a weak set of S-boxes by rotating each byte by its 
population count (what I call a twisted function, which satisfies one-bit 
strict avalanche criterion) and setting all three S-boxes to this permutation.

Two-round Wring is, of course, easily broken. 0.86% of all pairs of 10 kB 
messages that differ by one byte rotate together through two rounds. (I haven't 
tried changing three bytes in such a way that one byte changes after 
mix3parts.) Several hundred such pairs give enough clues to figure out how many 
bits are set in each entry of each S-box. Having done this, you can figure out 
by how many bits each message rotates in the first round. Then you can figure 
out how many one-bits are in each part of a byte, when the first-round rotation 
is not a multiple of 8, and thus determine all the bytes in the S-boxes.

In April 2024, I graphed what happened to pairs of messages which have the 
same total rotation in two rounds, but not in just the first round. For all 12 
actual keys I used, the number of matching bits looks like the matching bits 
of two 10 kB (or 8 KiB or 7776 B) random vectors. This held even for S-boxes 
that are all linear, but different. Several days ago, I did the same with three 
identical nonlinear S-boxes, simulating a weak key. This time, when the 
difference in first-round rotation is ±8 bits, more bits match than would happen 
by chance.

Graphs: http://bezitopo.org/~phma/Crypto/WringTwistree/clutch.html
Code: https://github.com/phma/WringTwistreeCryptanalysis.jl
This is a work in progress, not well commented. To run it, in Pkg type "dev 
WringTwistree", because I added the weak S-boxes after the last tagged 
version, and will probably do the same for Twistree before tagging another 
version.

Pierre
-- 
Por H o por B, los campos magnéticos se difieren dentro de un imán.