Bitstream Modification Attack on SNOW 3G

Michail Moraitis; Elena Dubrova

Paper 2020/038

Bitstream Modification Attack on SNOW 3G

Michail Moraitis and Elena Dubrova

Abstract

SNOW 3G is one of the core algorithms for confidentiality and integrity in several 3GPP wireless communication standards, including the new Next Generation (NG) 5G. It is believed to be resistant to classical cryptanalysis. In this paper, we show that a key can be extracted from an unprotected FPGA implementation of SNOW 3G by a fault attack. The faults are injected by modifying the content of Look- Up Tables (LUTs) directly in the bitstream. The main challenge is to identify target LUTs whose modification reduces the non-linear state updating function of SNOW 3G to a linear one. We present an algorithm for finding all k-input LUTs implementing a given k-variable Boolean function in the bitstream. We also introduce a key independent bitstream exploration technique which reduces the complexity of some search tasks from exponential to linear. This idea has not been exploited in previous bitstream modification attacks. Finally, we propose a countermeasure which makes the identification of target LUTs an intractable problem by considerably increasing the number of candidates into target LUTs.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Major revision. Proceedings of the 2020 Design, Automation & Test in Europe Conf. & Exhibition (DATE’20)
Keywords: SNOW 3G stream cipher fault attack FPGA bitstream modification reverse engineering.
Contact author(s): micmor @ kth se
History: 2020-05-13: last of 2 revisions; 2020-01-15: received; See all versions
Short URL: https://ia.cr/2020/038
License: CC BY

BibTeX

@misc{cryptoeprint:2020/038,
      author = {Michail Moraitis and Elena Dubrova},
      title = {Bitstream Modification Attack on {SNOW} {3G}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/038},
      year = {2020},
      url = {https://eprint.iacr.org/2020/038}
}