Meaningful results against Trivium with reduced key setup

Michael Vielhaber presents an interesting result against a reduced version of the eSTREAM submitted cipher Trivium in a paper on the IACR ePrint archive. By reducing the key setup from 4 full rounds (1152 clock cycles) to two cycles (576 cycles) he is able to mount a chosen IV algebraic attack using a total of 2^6 chosen IV resyncs. This reduced version is called ONE.FIVIUM by him. The impact of the attack against ONE.FIVIUM that 47 of the 80 key bits are claimed to be determined with probability 1 by this attack. The write up needs polishing but most of the results indeed mostly check out. Unfortunately the method by which he arrived at these results is (in my opinion, at least) only superficially described. I strongly suspect this paper is intended to mark a claim. Further results against a clock setup with more cycles are to be expected. Trivium is living dangerously.If you want to check out Michael Vielhaber’s results yourself, I have written Python code for just that. My colleague Andrey Pyshkin initially confirmed the 6 out of the first 7 approximations listed in the table, aidatest.py checks all of them. Below is the output of 256 runs.

approx. for key bits [1] was correct 256 out of 256 times
approx. for key bits [2, 65] was correct 256 out of 256 times
approx. for key bits [3, 66] was correct 0 out of 256 times
approx. for key bits [4] was correct 256 out of 256 times
approx. for key bits [5] was correct 256 out of 256 times
approx. for key bits [6] was correct 256 out of 256 times
approx. for key bits [8] was correct 256 out of 256 times
approx. for key bits [9] was correct 256 out of 256 times
approx. for key bits [11] was correct 256 out of 256 times
approx. for key bits [14] was correct 256 out of 256 times
approx. for key bits [16] was correct 256 out of 256 times
approx. for key bits [17] was correct 256 out of 256 times
approx. for key bits [19] was correct 256 out of 256 times
approx. for key bits [25] was correct 256 out of 256 times
approx. for key bits [26] was correct 256 out of 256 times
approx. for key bits [27] was correct 256 out of 256 times
approx. for key bits [36] was correct 256 out of 256 times
approx. for key bits [38] was correct 256 out of 256 times
approx. for key bits [39] was correct 256 out of 256 times
approx. for key bits [55] was correct 256 out of 256 times
approx. for key bits [56] was correct 256 out of 256 times
approx. for key bits [57, 63] was correct 256 out of 256 times
approx. for key bits [59, 65] was correct 256 out of 256 times
approx. for key bits [60, 66] was correct 256 out of 256 times
approx. for key bits [61] was correct 256 out of 256 times
approx. for key bits [62] was correct 256 out of 256 times
approx. for key bits [63] was correct 256 out of 256 times
approx. for key bits [64] was correct 256 out of 256 times
approx. for key bits [65] was correct 256 out of 256 times
approx. for key bits [66] was correct 256 out of 256 times
approx. for key bits [67] was correct 0 out of 256 times
approx. for key bits [68] was correct 0 out of 256 times
approx. for key bits [15] was correct 256 out of 256 times
approx. for key bits [18] was correct 256 out of 256 times
approx. for key bits [20] was correct 256 out of 256 times
approx. for key bits [23] was correct 256 out of 256 times
approx. for key bits [30] was correct 256 out of 256 times
approx. for key bits [32] was correct 256 out of 256 times
approx. for key bits [33] was correct 256 out of 256 times
approx. for key bits [35] was correct 256 out of 256 times
approx. for key bits [58] was correct 166 out of 256 times
approx. for key bits [21] was correct 256 out of 256 times
approx. for key bits [22] was correct 256 out of 256 times
approx. for key bits [10] was correct 115 out of 256 times
approx. for key bits [12] was correct 141 out of 256 times
approx. for key bits [58] was correct 256 out of 256 times
approx. for key bits [69] was correct 256 out of 256 times

1 thought on “Meaningful results against Trivium with reduced key setup

  1. Pingback: Kryptoblog » Blog Archive » FSE 2008 och slutspurt i eSTREAM

Leave a Reply