eprint.iacr.orgpaper

Cube Attacks with Elimination Strategy: Key Recovery Attacks on Trivium

Introduces a cube-attack framework with an elimination strategy. It finds key conditions and cubes whose conditional superpolies are cheap to compute, then solves the resulting equation systems to recover key bits. The supporting techniques are a nested coefficient solver, conditional monomial prediction, an automated cube search combining numeric mapping with monomial prediction, and two testing methods for large equation systems. Against round-reduced Trivium it gives a practical key recovery at 840 rounds (complexity below 2^55, 77.8% success) and at 845 rounds (below 2^56, 98.1% success on 59.1% of keys). It also gives a theoretical weak-key attack at 855 rounds for 2^74 keys. These are the best known results, extending prior practical attacks by 13 rounds and theoretical attacks by 4.