Vectorized linear approximations for attacks on SNOW 3G

Jing Yang; Thomas Johansson; Alexander Maximov

doi:10.13154/tosc.v2019.i4.249-271

Vectorized linear approximations for attacks on SNOW 3G

Jing Yang, Thomas Johansson, Alexander Maximov

Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding › peer-review

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.

Original language	English
Title of host publication	Fast Software Encryption conference
Pages	249-271
DOIs	https://doi.org/10.13154/tosc.v2019.i4.249-271
Publication status	Published - 2019
Event	27th Annual Fast Software Encryption Conference, FSE 2020 - Athens, Greece Duration: 2020 Mar 22 → 2020 Mar 26

Publication series

Name	IACR Transactions on Symmetric Cryptology
Publisher	IACR
Number	4
Volume	2019
ISSN (Electronic)	2519-173X

Conference

Conference	27th Annual Fast Software Encryption Conference, FSE 2020
Country/Territory	Greece
City	Athens
Period	2020/03/22 → 2020/03/26

Subject classification (UKÄ)

Signal Processing

Access to Document

10.13154/tosc.v2019.i4.249-271

Cite this

@inproceedings{80dd21a751114af389b29a9661c040c2,

title = "Vectorized linear approximations for attacks on SNOW 3G",

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.",

author = "Jing Yang and Thomas Johansson and Alexander Maximov",

year = "2019",

doi = "10.13154/tosc.v2019.i4.249-271",

language = "English",

series = " IACR Transactions on Symmetric Cryptology",

publisher = "IACR",

number = "4",

pages = "249--271",

booktitle = "Fast Software Encryption conference",

note = "27th Annual Fast Software Encryption Conference, FSE 2020 ; Conference date: 22-03-2020 Through 26-03-2020",

}

TY - GEN

T1 - Vectorized linear approximations for attacks on SNOW 3G

AU - Yang, Jing

AU - Johansson, Thomas

AU - Maximov, Alexander

PY - 2019

Y1 - 2019

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

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

U2 - 10.13154/tosc.v2019.i4.249-271

DO - 10.13154/tosc.v2019.i4.249-271

M3 - Paper in conference proceeding

T3 - IACR Transactions on Symmetric Cryptology

SP - 249

EP - 271

BT - Fast Software Encryption conference

T2 - 27th Annual Fast Software Encryption Conference, FSE 2020

Y2 - 22 March 2020 through 26 March 2020

ER -

Vectorized linear approximations for attacks on SNOW 3G

Abstract

Publication series

Conference

Subject classification (UKÄ)

Access to Document

Other files and links

Fingerprint

Contributions to Confidentiality and Integrity Algorithms for 5G

Cite this