New Related-Tweakey Boomerang and Rectangle Attacks on Deoxys-BC Including BDT Effect

Boxin Zhao, Xiaoyang Dong, Keting Jia

Introduction

This research presents a significant advancement in the cryptanalysis of the Deoxys family of authenticated encryption schemes. By leveraging refined search techniques and the "Boomerang Difference Table" (BDT) effect, the authors break more rounds of the underlying block cipher than any previous research. The study improves the best-known attacks on Deoxys-BC, the core cipher of a CAESAR competition winner, by finding more efficient boomerang distinguishers.

The Deoxys-BC Primitive

Deoxys-BC is a tweakable block cipher (TBC) that serves as the internal primitive for the Deoxys-I and Deoxys-II authenticated encryption schemes. Deoxys-II was selected as a final choice for the CAESAR portfolio, making its security a high-priority topic for the cryptographic community. The core challenge in cryptanalysis is finding a "distinguisher"—a property of the cipher that behaves differently from a random permutation. Boomerang and Rectangle attacks are advanced techniques that stitch together two short, high-probability differential paths to create a long distinguisher.

Methodology

The authors employ several sophisticated techniques to improve upon previous work:

  1. MILP-Based Search: Mixed Integer Linear Programming (MILP) was used to automate the search for differential trails. By modifying models to account for "truncated" differentials at the ends of the trails, more effective distinguishers were found.
  2. The BDT Effect: A central contribution is the application of the Boomerang Difference Table (BDT). While previous attacks used the Boomerang Connectivity Table (BCT), the BDT allows for a systematic evaluation of the "boomerang switch"—the point where the two differential paths meet—across multiple rounds. This often reveals a higher probability for the distinguisher than previously calculated.
Structure of a boomerang attack showing the interaction of differential paths.
  1. Optimized Key Recovery: A "guess and filter" approach was introduced. Instead of guessing all subtweakey bits simultaneously, small fractions of the key are guessed to filter out "wrong quartets" early, significantly lowering the overall time complexity of the attack.

Results and Comparative Analysis

The paper sets new records for the number of rounds attacked on Deoxys-BC. Experimental verification using $2^{20}$ randomly chosen plaintexts and tweakeys confirmed the theoretical probabilities calculated using the BDT, validating the mathematical models.

Summary of attack complexities and round coverage for Deoxys-BC variants.

The attacks successfully extended to 11 rounds for Deoxys-BC-256 and 14 rounds for Deoxys-BC-384, significantly reducing the security margin of these ciphers. For the authenticated encryption scheme Deoxys-I-256-128, the complexity of the 12-round attack was reduced by a factor of $2^{28}$ compared to previous results.

Conclusion

While these attacks are "breaks" in a cryptographic sense (faster than brute force), they remain computationally massive. For example, the 14-round attack on Deoxys-BC-384 requires $2^{286.2}$ operations—far beyond the reach of current hardware. Furthermore, the authors note that these attacks cannot be applied to Deoxys-II due to its different operating mode designed for "defense in depth." Future work may involve further refinements to MILP models or exploring other types of switches to push attacks toward full-round versions of the ciphers.

Summary updated

BibTeX
@article{zhao2019new,
  author = {Boxin Zhao and Xiaoyang Dong and Keting Jia},
  title = {{New Related-Tweakey Boomerang and Rectangle Attacks on Deoxys-BC Including BDT Effect}},
  journal = {IACR Trans. Symmetric Cryptol.},
  year = {2019},
  doi = {10.13154/tosc.v2019.i3.121-151},
}
Figure