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 ]