“Cube attack” less effective against Trivium than we thought?
It looks like there are errors in the tables at the back of the “cube attack” paper which show how to apply the attack to Trivium: some of the entries don’t work. This could mean simply that there are typos in the table, or it could mean that the attack is somewhat less effective against Trivium than the authors believed. Or, of course, it could mean that there’s a bug in my software.
As discussed in my previous entry, to apply the “cube attack” to a cipher like Trivium, you start by searching for a set of “maxterms”. A maxterm is an affine relation between the key bits and the parity of all the values of an output bit for a particular large set of IVs known as a “cube”. Once you have enough maxterms, you can collect the output bits for all the IVs in all the cubes in the maxterms, then find the parity for each maxterm, and then use linear algebra to invert and find the key bits; so you have a complete set of maxterms when you have as many maxterms as key bits and they are all linearly independent in key bits. In practice you would make do with fewer linearly independent maxterms and make up the difference with exhaustive search.
Trivium has 1152 initialization steps, and no-one currently knows how to break it. Before the cube attack, the best attack on Trivium broke a weakened variant with 672 initialization rounds in 255 steps. The cube attack paper presents three tables of maxterms for Trivium: one set of 63 to break the 672 step variant in 219, one set of 52 to break a stronger 735-step variant in less than 230 steps, and one set of four that might form part of an attack on 770-step Trivium requiring around 236 steps.
However, it looks like 15 of these 119 maxterms presented don’t work. Of these, two work 0% of the time, and so are easily converted to working maxterms by adding or removing a “1+” to the first column. Five appear to be a little unreliable, working 79%-99.2% of the time; a slightly unreliable maxterm is useful to an attacker, but the success probability of the attack is the product of the success probabilities of all the maxterms, so too many unreliable ones will make the attack unlikely to work. But eight seem have empirical success probabilities between 46% and 58%, suggesting that in practice they work 50% of the time ie no better than guesswork.
This could of course be an error in my software; I’d love to see these results verified. You can test for yourself by downloading the latest version of the software here:
Updated: In correspondence between myself and Dinur we’ve fixed another two of the maxterms – fixes to the other 11 are on the way.