Analysis of Solitaire
This work addresses security vulnerabilities in a manually implementable cipher, though it is incremental as it builds on known issues without achieving broad SOTA impact.
The authors analyzed the Solitaire cipher, identifying a model for keystream repetition bias that explains most of the observed patterns, and proposed modifications to reduce this bias at the cost of increased complexity.
The Solitaire cipher was designed by Bruce Schneier as a plot point in the novel Cryptonomicon by Neal Stephenson. The cipher is intended to fit the archetype of a modern stream cipher whilst being implementable by hand using a standard deck of cards with two jokers. We find a model for repetitions in the keystream in the stream cipher Solitaire that accounts for the large majority of the repetition bias. Other phenomena merit further investigation. We have proposed modifications to the cipher that would reduce the repetition bias, but at the cost of increasing the complexity of the cipher (probably beyond the goal of allowing manual implementation). We have argued that the state update function is unlikely to lead to cycles significantly shorter than those of a random bijection.