Quasidifferential Saves Infeasible Differential
摘要
GIFT, including GIFT-64 and GIFT-128, is a family of lightweight block ciphers with outstanding implementation performance and high security, which is a popular underlying primitive chosen by many AEADs such as SUNDAE-GIFT. Currently, differential cryptanalysis is the best key-recovery attack on both ciphers, but they have stuck at 21 and 27 rounds for GIFT-64 and GIFT-128, respectively. Recently, Beyne and Rijmen proposed the quasidifferential transition matrix for differential cryptanalysis at CRYPTO 2022 and showed that the fixed-key probability of a differential (characteristic) can be expressed as the sum of correlations of all quasidifferential trails corresponding to this differential (characteristic). As pointed out by Beyne and Rijmen in their paper, the quasidifferential methodology is useful in identifying weak-key differential attacks. In this paper, we apply Beyne and Rijmen’s method to GIFT. Some differential characteristics with small (average) probabilities can have much larger probabilities when weak-key conditions hold. Improved weak-key differential attacks on GIFT-64 and GIFT-128 are thus obtained. For GIFT-64, the probability of a 13-round differential is improved from \(2^{-62.06}\) to \(2^{-57.82}\) with 4 bits of weak-key conditions, then an improved differential key-recovery attack on 21-round GIFT-64 is obtained with \(2^{117.42}/2^{64}\) time/data complexities; the probability of a 13-round multiple differential (containing 33 characteristics) is improved from \(2^{-58.96}\) to \(2^{-55.67}\) with 4 bits of weak-key conditions, then an improved multiple differential key-recovery attack on 21-round GIFT-64 is obtained with \(2^{123.27}/2^{64}\) time/data complexities. For GIFT-128, the probability of a 20-round differential is improved from \(2^{-121.83}\) to \(2^{-114.77}\) with 6 bits of weak-key conditions; the probability of a 21-round multiple differential (containing 2 differentials) is improved from \(2^{-128.38}\) to \(2^{-122.77}\) with 4 bits of weak-key conditions. Improved (multiple) differential weak-key key-recovery attacks are obtained for 27 and 28 rounds of GIFT-128 with \(2^{115.77}\) / \(2^{115.77}\) and \(2^{123.77}\) / \(2^{123.77}\) time/data complexities, respectively. As far as we know, this is the first time that a (weak-key) key-recovery attack can reach 28 rounds of GIFT-128. Additionally, as an independent interest, we perform the first differential attack on SUNDAE-GIFT . The differential used in this attack is checked with quasidifferential trails, thus the probability is reliable. Our attack is nonce-respecting and has significantly better complexities than the currently best attack.