International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 22 March 2014

Subhabrata Samajder, Palash Sarkar
ePrint Report ePrint Report
This paper develops two methods for exploring the structure of the stream cipher TRIVIUM.

We 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.

Expand

Additional news items may be found on the IACR news page.