Paper 2023/299

Approximate Modeling of Signed Difference and Digraph based Bit Condition Deduction: New Boomerang Attacks on BLAKE

Yonglin Hao, State Key Laboratory of Cryptology
Qingju Wang, University of Luxembourg
Lin Jiao, State Key Laboratory of Cryptology
Xinxin Gong, State Key Laboratory of Cryptology

The signed difference is a powerful tool for analyzing the Addition, XOR, Rotation (ARX) cryptographic primitives. Currently, solving the accurate model for the signed difference propagation is infeasible. We propose an approximate MILP modeling method capturing the propagation rules of signed differences. Unlike the accurate signed difference model, the approximate model only focuses on active bits and ignores the possible bit conditions on inactive bits. To overcome the negative effect of a lower accuracy arising from ignoring bit conditions on inactive bits, we propose an additional tool for deducing all bit conditions automatically. Such a tool is based on a directed-graph capturing the whole computation process of ARX primitives by drawing links among intermediate words and operations. The digraph is also applicable in the MILP model construction process: it enables us to identify the parameters upper bounding the number of bit conditions so as to define the objective function; it is further used to connect the boomerang top and bottom signed differential paths by introducing proper constraints to avoid incompatible intersections. Benefiting from the approximate model and the directed-graph based tool, the solving time of the new MILP model is significantly reduced, enabling us to deduce signed differential paths efficiently and accurately. To show the utility of our method, we propose boomerang attacks on the keyed permutations of three ARX hash functions of BLAKE. For the first time we mount an attack on the full 7 rounds of BLAKE3, with the complexity as low as $2^{180}$. Our best attack on BLAKE2s can improve the previously best result by 0.5 rounds but with lower complexity. The attacks on BLAKE-256 cover the same 8 rounds with the previous best result but with complexity $2^{16}$ times lower. All our results are verified practically with round-reduced boomerang quartets.

Available format(s)
Attacks and cryptanalysis
Publication info
Signed DifferenceBoomerang AttackARXMILP modeling
Contact author(s)
haoyonglin @ yeah net
qjuwang @ gmail com
jiaolin_jl @ 126 com
xinxgong @ 126 com
2023-02-28: approved
2023-02-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yonglin Hao and Qingju Wang and Lin Jiao and Xinxin Gong},
      title = {Approximate Modeling of Signed Difference and Digraph based Bit Condition Deduction: New Boomerang Attacks on BLAKE},
      howpublished = {Cryptology ePrint Archive, Paper 2023/299},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.