Cryptology ePrint Archive: Report 2016/1068

On Finding Short Cycles in Cryptographic Algorithms

Elena Dubrova and Maxim Teslenko

Abstract: We show how short cycles in the state space of a cryptographic algorithm can be used to mount a fault attack on its implementation which results in a full secret key recovery. The attack is based on the assumption that an attacker can inject a transient fault at a precise location and time of his/her choice and more than once. We present an algorithm which uses a SAT-based bounded model checking for finding all short cycles of a given length. 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 problem instances, however, they cannot guarantee the detection of all cycles of a given length. The same holds for general-purpose SAT-based model checkers. The presented algorithm can find all short cycles in cryptographic algorithms with very large state spaces. We evaluate it by analyzing Trivium, Bivium, Grain-80 and Grain-128 stream ciphers. The analysis shows these ciphers have short cycles whose existence, to our best knowledge, was previously unknown.

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

Date: received 15 Nov 2016, last revised 20 Jun 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: 20170620:155852 (All versions of this report)

Short URL: ia.cr/2016/1068

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]