Weak-keys and key-recovery attack for TinyJAMBU

In this paper, we study NIST lightweight 3rd round candidate TinyJAMBU. The core component of TinyJAMBU is the keyed permutation P-n, which is based on a non-linear feedback shift register. By analysing this permutation carefully, we are able to find good cubes that are used to build distinguishers in the weak-key setting. In particular, we show that there are at least 2(108) keys for which TinyJAMBU can be distinguished from a random source for up to 476 rounds. These distinguishers outperform the best-known distinguishers, which were proposed in 'Scientific Reports - Nature' by Teng et al. We are the first to study the exact degree of the feedback polynomial P-n in the nonce variables. This helped us in concluding that TinyJAMBU with more than 445 rounds is secure against distinguishers using 32 sized cubes in the normal setting. Finally, we give new key-recovery attacks against TinyJAMBU using the concepts of monomial trail presented by Hu et al. at ASIACRYPT 2020. Our attacks are unlikely to jeopardise the security of the entire 640 rounds TinyJAMBU, but we strongly anticipate that they will shed new lights on the cipher's security.

Automated summary

This paper studies the NIST lightweight 3rd round candidate TinyJAMBU and analyzes its core component, the keyed permutation P-n. It discovers good cubes that can be used to build distinguishers and determines that TinyJAMBU is secure against distinguishers using 32 sized cubes for more than 445 rounds. The paper also presents new key-recovery attacks based on the concept of monomial trail.