Algebraic Structure Defectoscopy Background

At some point in history, assessment of the quality of pseudo-random number generators has become automated, despite the ongoing criticism and scepticism of the scientific community, and is now believed to be a fairly trivial task. The famous DIEHARD battery of tests by George Marsaglia, followed by the US government standardising randomness testing as a NIST Statistical Test Suite described in their special publication 800-22 demonstrate that such testing is taken seriously.

A stream cipher besides being a good PRNG (that is having a strong round function) also needs to be able to survive a number of complex attacks against its initialisation process. In other words, all the functions defining relationships between each output bit and bits of the key, seed or IV, internal state and other output bits must be indistinguishable from random functions of a certain size. Both pseudo-random number generators and stream ciphers are required to possess all other technical characteristics such as high speed, small size, guaranteed long periods, usage simplicity, etc. We believe that neither PRNGs that pass randomness tests but demonstrate simple algebraic relationships between output bits nor stream ciphers that fail randomness tests qualify to be used for their intended purposes.

As Shannon postulated in 1949, breaking a good cipher should require “as much work as solving a system of simultaneous equations in a large number of unknowns of a complex type”. Computational complexity of the latter can be estimated for iterated cryptographic primitives yielding an automated measure of a cipher's security by Shannon's definition. There have been many attempts to automate cryptanalysis in the past. Our ASD tests are a step in that direction, a much further step than the basic low-degree monomial counts used by Markku-Juhani O. Saarinen in his work or by Eric Filiol in his Moebius. ASD tests allow us to measure the number of rounds required for the cipher to randomise the distribution of monomials in ANFs of all the polynomials up to the degree of square root of the intended security level thus showing solid polynomial growth. Two such solid rounds can then build a PRF with the necessary number of variables and the necessary algebraic degree, and of course, two such rounds are naturally required to protect the cipher iterated in both directions, therefore at least four solid rounds are required for any cipher to be secure. In principle, Luby-Rackoff theorem directly supports our practical experimental results.

We test differences in the bits of:

1. The key
2. The IV or Data
3. The secret state

We believe that any bias in the distribution of monomials of any degree in the algebraic equations determining relationships between any output bits can result in a successful cryptanalytic attack. With our available computational resources we can detect local non-randomness in the distribution of monomials for degrees up to 24, which is sufficient to test even 512-bit secure ciphers. The recommended minimum number of sealing rounds that can build a sufficiently large and sufficiently random uncompressible PRF is thus calculated as the number of solid rounds x4.

The recommended maximum output per round is determined as a minimum between {the size of the secret state} divided by {6x solid rounds} and between {the size of the secret state less the cipher's security rating} divided by {4x solid rounds}. Please note: we will correct all our recommended values if we find reasonable argumentation to support better formulas.

Of course our tests have certain limitations that prevent them from being able to serve as an automatic proof of security. Our tests assume that the same round function is used in all iterations, that no part of the cipher can be easily dismissed from the attacks and that the size of the secret state is chosen correctly for the required security rating. Only when all those conditions are met, our tests can serve as a good measure of the required sealing rounds or maximum secure output bits per round. Detailed cryptanalysis including testing individual cipher components, measurement of the cipher's resistance against algebraic attacks, search for exploitable linearities, differentials and other potentially exploitable biases and weaknesses is a complex task outside the scope of automated cryptanalysis. Please contact us if you want basic or detailed testing of your proprietary cipher. We are currently working on additional automated tests specific for collision resistance.