Paper 2019/1216

Automated Search for Block Cipher Differentials: A GPU-Accelerated Branch-and-Bound Algorithm

Wei-Zhu Yeoh, Je Sen Teh, and Jiageng Chen

Abstract

Differential cryptanalysis of block ciphers requires the identification of differential characteristics with high probability. For block ciphers with large block sizes and number of rounds, identifying these characteristics is computationally intensive. The branch-and-bound algorithm was proposed by Matsui to automate this task. Since then, numerous improvements were made to the branch-and-bound algorithm by bounding the number of active s-boxes, incorporating a meet-in-the-middle approach, and adapting it to various block cipher architectures. Although mixed-integer linear programming (MILP) has been widely used to evaluate the differential resistance of block ciphers, MILP is still inefficient for clustering singular differential characteristics to obtain differentials (also known as the differential effect). The branch-and-bound method is still better suited for the task of trail clustering. However, it requires enhancements before being feasible for block ciphers with large block sizes, especially for a large number of rounds. Motivated by the need for a more efficient branch-and-bound algorithm to search for block cipher differentials, we propose a GPU-accelerated branch-and-bound algorithm. The proposed approach substantially increases the performance of the differential cluster search. We were able to derive a branch enumeration and evaluation kernel that is 5.95 times faster than its CPU counterpart. To showcase its practicality, the proposed algorithm is applied on TRIFLE-BC, a 128-bit block cipher. By incorporating a meet-in-the-middle approach with the proposed GPU kernel, we were able to improve the search efficiency (on 20 rounds of TRIFLE-BC) by approximately 58 times as compared to the CPU-based approach. Differentials consisting of up to 50 million individual characteristics can be constructed for 20 rounds of TRIFLE, leading to slight improvements to the overall differential probabilities. Even for larger rounds (43 rounds), the proposed algorithm is still able to construct large clusters of over 500 thousand characteristics. This result depicts the practicality of the proposed algorithm in constructing large differentials even for a 128-bit block cipher, which could be used to improve cryptanalytic findings against other block ciphers in the future.

Note: This is a pre-print version of the paper that has been published in Lecture Notes in Computer Science for ACISP 2020. The final authenticated version is available at https://doi.org/10.1007/978-3-030-55304-3_9.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Minor revision. 25th Australasian Conference on Information Security and Privacy (ACISP 2020)
DOI
10.1007/978-3-030-55304-3_9
Contact author(s)
yeohweizhu @ gmail com
jesen_teh @ usm my
History
2020-08-10: last of 6 revisions
2019-10-17: received
See all versions
Short URL
https://ia.cr/2019/1216
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1216,
      author = {Wei-Zhu Yeoh and Je Sen Teh and Jiageng Chen},
      title = {Automated Search for Block Cipher Differentials: A GPU-Accelerated Branch-and-Bound Algorithm},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1216},
      year = {2019},
      doi = {10.1007/978-3-030-55304-3_9},
      note = {\url{https://eprint.iacr.org/2019/1216}},
      url = {https://eprint.iacr.org/2019/1216}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.