Cryptology ePrint Archive: Report 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.

Category / Keywords: Shift register, stream cipher, Trivium, Grain, cycle, SAT, fault attack, fault injection

Date: received 15 Nov 2016, last revised 6 Feb 2017

Contact author: dubrova at kth se

Available format(s): PDF | BibTeX Citation

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

Version: 20170206:084229 (All versions of this report)

Short URL: ia.cr/2016/1068

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]