Paper 2019/879

Cryptanalysis of Subterranean-SAE

Fukang Liu and Takanori Isobe and Willi Meier

Abstract

Subterranean 2.0 designed by Daemen, Massolino and Rotella is a Round 1 candidate of the NIST Lightweight Cryptography Standardization process. In the official document of Subterranean 2.0, the designers have made a cryptanalysis of the state collisions in unkeyed absorbing by reducing the number of rounds to absorb the message from 2 to 1. However, little cryptanalysis of the authenticated encryption scheme Subterranean-SAE is made. For Subterranean-SAE, the designers introduce 8 blank rounds to separate the controllable input and output, and expect that 8 blank rounds can achieve a sufficient diffusion. Therefore, it is meaningful to investigate the security by reducing the number of blank rounds. Moreover, the designers make no security claim but expect a non-trivial effort to achieve full-state recovery in a nonce-misuse scenario. In this paper, we present the first full-state recovery attack in a nonce-misuse scenario with practical time complexity $2^{16}$. In addition, in a nonce-respecting scenario and if the number of blank rounds is reduced to 4, we can mount a key-recovery attack with time complexity $2^{122}$ and data complexity $2^{69.5}$. The distinguishing attack can also be achieved with time and data complexity $2^{33}$. Our cryptanalysis does not threaten the security claim for Subterranean-SAE and we hope it can enhance the understanding of Subterranean-SAE.

Note: 1. Provide more quadratic boolean equations in the state recovery attack. 2. Correct some editorial errors.