Welcome to the resource topic for 2016/1068
Title:
On Finding Short Cycles in Cryptographic Algorithms
Authors: Elena Dubrova, 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.
ePrint: https://eprint.iacr.org/2016/1068
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .