Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / SNOW 3G, stream cipher, fault attack, FPGA, bitstream modification, reverse engineering.

Original Publication (with major differences): Proceedings of the 2020 Design, Automation & Test in Europe Conf. & Exhibition (DATE’20)

Date: received 14 Jan 2020, last revised 13 May 2020

Contact author: micmor at kth se

Available format(s): PDF | BibTeX Citation

Version: 20200513:114411 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]