[Resource Topic] 2022/1123: DEEPAND: In-Depth Modeling of Correlated AND Gates for NLFSR-based Lightweight Block Ciphers

Welcome to the resource topic for 2022/1123

Title:
DEEPAND: In-Depth Modeling of Correlated AND Gates for NLFSR-based Lightweight Block Ciphers

Authors: Amit Jana, Mostafizar Rahman, Dhiman Saha

Abstract:

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.

ePrint: https://eprint.iacr.org/2022/1123

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .