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
-
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},
url = {https://eprint.iacr.org/2016/1068}
}
