IACR News item: 22 March 2014
Subhabrata Samajder, Palash Sarkar
ePrint ReportWe consider whether it is possible to compute the algebraic normal form (ANF) of such functions.
Since the key and the IV together make up 160 variables, doing this directly is not possible.
Instead, one can choose a subset of the key and IV variables of size $n$ and fix the other variables to constants.
As an application of this tool, we run some randomness experiments on the first output bit of TRIVIUM.
Three types of tests were conducted on full (and reduced) round TRIVIUM.
For the tests done, we fix a subset of $n$ key variables and vary the remaining $160 - n$ key and IV bit positions.
The first test tried to find polynomials which are non-random in some sense.
This is along the line of work done by Aumasson et. al. on their work on cube testers.
However, here we do not use any cube.
We try to find polynomials corresponding to the first output bit of TRIVIUM which are non-random.
Our experiments did reveal a number of polynomials which showed deviation from randomness.
The second test conducted checks the balancedness amongst the first $l$ output bits of TRIVIUM.
A proper statistical model for conducting such a test is proposed.
Tests results shows that the first $8$ output bits are unbalanced.
For the third test we consider $N$ random choices of the constant values keeping the $n$ key variables fixed.
A simple test of hypothesis is applied to detect possible non-randomness in the distributions.
Mostly, the results are negative.
In a few cases, the results seem to indicate the presence of possible non-randomness, though, nothing conclusive can be inferred from this test.
The symbolic computation tool developed here can conceivably be used for exploring other features of TRIVIUM.
Further, the idea behind the development of the tool can be used to build similar tools for other ciphers.
Additional news items may be found on the IACR news page.