International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Vectorized linear approximations for attacks on SNOW 3G

Authors:
Jing Yang , Dept. of Electrical and Information Technology, Lund University, Lund, Sweden
Thomas Johansson , Dept. of Electrical and Information Technology, Lund University, Lund, Sweden
Alexander Maximov , Ericsson Research, Lund, Sweden
Download:
DOI: 10.13154/tosc.v2019.i4.249-271
URL: https://tosc.iacr.org/index.php/ToSC/article/view/8464
Search ePrint
Search Google
Abstract: SNOW 3G is a stream cipher designed in 2006 by ETSI/SAGE, serving in 3GPP as one of the standard algorithms for data confidentiality and integrity protection. It is also included in the 4G LTE standard. In this paper we derive vectorized linear approximations of the finite state machine in SNOW3G. In particular,we show one 24-bit approximation with a bias around 2−37 and one byte-oriented approximation with a bias around 2−40. We then use the approximations to launch attacks on SNOW 3G. The first approximation is used in a distinguishing attack resulting in an expected complexity of 2172 and the second one can be used in a standard fast correlation attack resulting in key recovery in an expected complexity of 2177. If the key length in SNOW 3G would be increased to 256 bits, the results show that there are then academic attacks on such a version faster than the exhaustive key search.
Video from TOSC 2020
BibTeX
@article{tosc-2020-30094,
  title={Vectorized linear approximations for attacks on SNOW 3G},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2019, Issue 4},
  pages={249-271},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/8464},
  doi={10.13154/tosc.v2019.i4.249-271},
  author={Jing Yang and Thomas Johansson and Alexander Maximov},
  year=2020
}