International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 31 August 2022

Amit Jana, Mostafizar Rahman, Dhiman Saha
ePrint Report ePrint Report
Automated cryptanalysis has taken center stage in the arena of cryptanalysis since the pioneering work by Mouha et al. which showcased the power of Mixed Integer Linear Programming (MILP) in solving crypto problems that otherwise required significant effort. Since this inception, research in this area has moved in primarily two directions. One is to model more and more classical cryptanalysis tools as an optimization problem to leverage the ease provided by state-of-the-art solvers. The other direction is to improve existing models to make them more efficient and/or accurate. The current work is an attempt to contribute to the latter. In this work, a general model referred to as DEEPAND has been devised to capture the correlation between AND gates in NLFSR-based lightweight block ciphers. DEEPAND builds upon and generalizes the idea of joint propagation of differences through AND gates captured using refined MILP modeling of TinyJAMBU by Saha et al. in FSE 2020. The proposed model has been applied to TinyJAMBU and KATAN and can detect correlations that were missed by earlier models. This leads to more accurate differential bounds for both the ciphers. In particular, a 384-round type-4 trail is found for TinyJAMBU with 14-active AND gates using the new model, while the refined model reported this figure to be 19. Moreover, we have found a full round type-4 trail of TinyJAMBU keyed permutation $P_{1024}$ with probability $2^{-108}$ ($\gg2^{-128}$), which violates designer's security claim. Thus, our results shows that TinyJAMBU's underlying keyed-permutation have non-random properties. As a result, it cannot be expected to provide the same security levels as robust block ciphers and also, the provable security of TinyJAMBU AEAD scheme should be carefully revisited.

Similarly, for KATAN32, DEEPAND modeling improves the 42-round trail with $2^{-11}$ probability to $2^{-7}$. DEEPAND seems to capture the underlying correlation better when multiple AND gates are at play and can be adapted to other classes of ciphers as well.
Expand

Additional news items may be found on the IACR news page.