Generalized Boomerang Connectivity Table and Improved Cryptanalysis of GIFT

Boomerang connectivity table (BCT), an essential tool in boomerang attack, gives a unified description of the probability in the middle round of a boomerang distinguisher. However, it suffers the drawback that the asymmetric relationship between the upper and lower differentials in the middle round is ignored. To make up for this deficiency, we propose the generalized boomerang connectivity table (GBCT), which characterizes all combinations of upper and lower differentials to provide a more precise probability in the middle round. We first study the cryptographic properties of GBCT and introduce its variants applied in multiple rounds and Feistel structure. Then, we provide an automatic search algorithm to increase the probability of the boomerang distinguisher by adding thorough considerations that more trails can be included, which is applicable to all S-box based ciphers. Finally, we increase the probabilities of the 20-round GIFT-64 distinguisher from $$2^{-58.557}$$ to $$2^{-57.43}$$ and the 19-round GIFT-128 distinguisher from $$2^{-109.626}$$ to $$2^{-108.349}$$ , both of which are the highest so far. Applying the key recovery attack proposed by Dong et al. at Eurocrypt 2022 on the new distinguisher, we achieve the lowest complexities of the attack on GIFT-64 and the best rectangle attack on GIFT-128.