The Spritz stream cipher algorithm has been shown to have a special class of states that can be used to do a full state recovery attack better than brute force.
While the authors of the paper clearly show what states are special, the behaviour of the cipher when in one of these states, and how to exploit them, they do not offer any insights as to how to mitigate them.
My understanding of all of this is that the probability of entering a weak state is low, but the consequences of doing so is high. It would seem that a way to mitigate this would be desirable.
Based on the second paper linked above, the following conditions are required for a state to be considered special/weak :
- All odd entries of the state S are even, and
- All even entries of the state S are odd, and
- Both 'j' and 'k' control variables are even
If any of these conditions fail, the state is not special/weak.
My first thought was to use the output generated by each 'squeeze' call to swap adjacent state elements (mod N). If the state was special, it is not anymore. If it was not, then there is a probability (not sure how to compute this) that it now is.
My second thought was to add an extra control variable (call it $h$) that after every 'squeeze' call would swap $s [h \bmod N]$ and $s [ h+1 \bmod N]$, then increment $h \pmod N$. Effectively swapping adjacent state entries progressively until the end of the array and then wrap around.
My third thought was to add a LFSR as part of the internal state to act as a pseudo random generator that will generate the swap index after each successive 'squeeze'. To clarify, the LFSR would act as an equivalent to the $h$ above, only pseudo random instead of consecutive values.
Based on some initial testing, all of these changes seem to work fine (apparent randomness, quick-n-dirty statistical tests). However, this is not a security proof and does not give insight into the impact on the overall security of the modified algorithm.
Can these approaches be considered "safe" as in that they retain the overall security or does it add some kind of new bias, etc. that an attacker can exploit?
Is there a more secure/elegant way to ensure :
- Special state is never entered?
- Special state is quickly exited before enough output is generated to be exploitable?
- Special state no longer exists, eliminated by design change?
In short, how best to mitigate the special state issue?
