Paper 2016/1068

A SAT-Based Algorithm for Finding Short Cycles in Shift Register Based Stream Ciphers

Elena Dubrova and Maxim Teslenko

Abstract

This paper addresses the problem of finding short cycles in the internal state space of shift register based stream ciphers.The existing Boolean Decision Diagram (BDD) based algorithms for finding cycles have limited capacity due to the excessive memory requirements of BDDs. The simulation-based algorithms can be applied to larger instances, however, they cannot guarantee the detection of all cycles of a given length. The same holds for general-purpose SAT-based model checkers. We present a SAT-based algorithm which can find all short cycles in real cryptographic systems with very large state spaces. The algorithm is evaluated by analyzing Trivium, Bivium, and Grain family of stream ciphers. The analysis shows that Trivium, Bivium, Grain-80 and Grain-128 contain short cycles whose existence, to our best knowledge, was previously unknown. We describe how short cycles can theoretically be used to mount a fault attack which results in a full secret key recovery.

Note: The paper has been extended with one new section (Section 5).