Cryptanalysis of Selected SPN and NLFSR-based Symmetric-Key Ciphers

Abstract

The thesis focuses on the cryptanalysis of private-key ciphers, which are widely used encryption methods due to their fast encryption/decryption computing ability and low memory requirements. The thesis covers two different aspects of cryptanalysis: traditional attack techniques and physical attacks. For physical attacks, the thesis presents a differential fault attack on the CAESAR scheme NORX with parallelism levels of 2 and 4. By introducing faults in NORX in parallel mode, the state collides with the internal branches to produce an all-zero state, which can be replayed despite different nonces and messages. The secret key of NORX is recovered using secondary faults and faulty tags, utilizing both internal and classical differentials. The attack strategy is demonstrated using different fault models to showcase its versatility. Additionally, the thesis identifies and solves a new variant of the coupon collector problem called the Non-circular Consecutive Coupon Collector Problem, which estimates the expected faults for the consecutive bit-fault model. The problem is extended to the circular variant and validated using hypothesis testing. The outcomes of this study may hold significance and relevance to the research community as a standalone contribution. Furthermore, the thesis investigates the faulty forgery attack on the decryption query to recover the state, leading to key recovery, for sponge-based authentication schemes with internal permutations following the SPN-based GFN structure. The attack is then extended to retrieve the secret key of any SPN-based sponge/SIV-like schemes. For traditional cryptanalysis, the thesis analyzes differential cryptanalysis of single or multiple AND-based NLFSR-like ciphers. Recent trends in automated cryptanalysis involve modeling classical cryptanalysis tools as optimization problems to leverage state-of-the-art solvers and improving existing models to make them more efficient and accurate. The thesis contributes to this trend by devising a general MILP model referred to as “DEEPAND” that captures the correlations among multiple AND gates in NLFSR-based lightweight block ciphers. The DEEPAND model 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 ciphers.