Paper 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.

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

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Shift registerstream cipherTriviumGraincycleSATfault attackfault injection
Contact author(s)
dubrova @ kth se
History
2017-06-20: last of 2 revisions
2016-11-15: received
See all versions
Short URL
https://ia.cr/2016/1068
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1068,
      author = {Elena Dubrova and Maxim Teslenko},
      title = {On Finding Short Cycles in Cryptographic Algorithms},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1068},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1068}},
      url = {https://eprint.iacr.org/2016/1068}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.