CryptoDB
Kazumaro Aoki
Publications
Year
Venue
Title
2018
CRYPTO
Fast Correlation Attack Revisited
📺
Abstract
A fast correlation attack (FCA) is a well-known cryptanalysis technique for LFSR-based stream ciphers. The correlation between the initial state of an LFSR and corresponding key stream is exploited, and the goal is to recover the initial state of the LFSR. In this paper, we revisit the FCA from a new point of view based on a finite field, and it brings a new property for the FCA when there are multiple linear approximations. Moreover, we propose a novel algorithm based on the new property, which enables us to reduce both time and data complexities. We finally apply this technique to the Grain family, which is a well-analyzed class of stream ciphers. There are three stream ciphers, Grain-128a, Grain-128, and Grain-v1 in the Grain family, and Grain-v1 is in the eSTREAM portfolio and Grain-128a is standardized by ISO/IEC. As a result, we break them all, and especially for Grain-128a, the cryptanalysis on its full version is reported for the first time.
Program Committees
- FSE 2015
- FSE 2014
- FSE 2013
- Asiacrypt 2011
- FSE 2006
- FSE 2005
Coauthors
- Kazumaro Aoki (12)
- Joppe W. Bos (1)
- Jens Franke (2)
- Pierrick Gaudry (1)
- Jian Guo (1)
- Takanori Isobe (1)
- Thorsten Kleinjung (2)
- Kunio Kobayashi (1)
- Alexander Kruppa (1)
- Arjen K. Lenstra (2)
- Krystian Matusiewicz (1)
- Willi Meier (1)
- Peter L. Montgomery (1)
- Shiho Moriai (2)
- Kazuo Ohta (2)
- Dag Arne Osvik (2)
- Herman J. J. te Riele (1)
- Yu Sasaki (4)
- Emmanuel Thomé (1)
- Andrey Timofeev (1)
- Yosuke Todo (1)
- Hiroki Ueda (1)
- Lei Wang (1)
- Bin Zhang (1)
- Paul Zimmermann (1)