Paper 2020/1133

Security Analysis of Subterranean 2.0

Ling Song and Yi Tu and Danping Shi and Lei Hu

Abstract

Subterranean 2.0 is a cipher suite that can be used for hashing, authenticated encryption, MAC computation, etc. It was designed by Daemen, Massolino, Mehrdad, and Rotella, and has been selected as a candidate in the second round of NIST's lightweight cryptography standardization process. Subterranean 2.0 is a duplex-based construction and utilizes an extremely simple one-round permutation in the duplex. It is the simplicity of the round function that makes it an attractive target of cryptanalysis. In this paper, we examine the one-round permutation in various phases of Subterranean 2.0 and specify three related attack scenarios that deserve further investigation: keystream biases in the keyed squeezing phase, state collisions in the keyed absorbing phase, and one-round differential analysis in the nonce-misuse setting. First, to facilitate cryptanalysis, we propose two size-reduced toy versions of Subterranean 2.0: Subterranean-m and Subterranean-s. Then we exploit the resemblance between the non-linear layer in the round function of Subterranean 2.0 and SIMON's round function to construct our models for searching characteristics to be used in the keystream bias evaluation and state collision attack. Our results show that there exists no linear trail under the constraint of data limit imposed by the designers with a minimal number of output blocks. This partially confirms the designers' claim on the bias of keystream. Regarding state collisions in keyed modes, we find useful characteristics of two toy versions with which forgery attacks can be mounted successfully. However, due to the time-consuming search, the security of Subterranean 2.0 against the state collision attack in keyed modes still remains an open question. Finally, we observe that one-round differentials allow to recover state bits in the nonce-misuse setting. By proposing nested one-round differentials, we obtain a sufficient number of state bits, leading to a practical state recovery with only 20 repetitions of the nonce and 88 blocks of data. It is noted that our work does not threaten the security of Subterranean 2.0.