Cryptology ePrint Archive: Report 2020/1056

Optimized GPU Framework for Block Cipher Differential Search

Wei-Zhu Yeoh and Je Sen Teh and Jiageng Chen

Abstract: Differential cryptanalysis of block ciphers require the identification of differential characteristics (trails) that occur with high probabilities. The effort required to search for these characteristics increases exponentially as the number of rounds and block size increases. Differentials, which are clusters of differential characteristics sharing the same input and output differences, can be constructed to improve the overall distinguishing probability, thus improving the efficiency of a key recovery attack. Matsui's branch-and-bound algorithm that automates the search for differential characteristics is commonly used to construct these differentials. However, the algorithm is still inefficient when enumerating a large number of characteristics, especially for block ciphers with large block sizes or number of rounds. In this paper, we improve upon the differential search by proposing a GPU-accelerated branch-and-bound framework that is more efficient and cost-effective as compared to its CPU counterpart. Efficiency is optimized by parallelizing all operations involved in a typical branch-and-bound algorithm by completing the entire search without transferring intermediate results back to the CPU. The meet-in-the-middle (MITM) approach is also adopted for further performance gains. We analyze the proposed framework in terms of both financial and computational costs based on simulations on the Google Cloud VM environment. When optimizing for performance, the proposed framework can achieve up to 90x speedup while saving up to 47% of the running cost as compared to a single CPU core. If cost-saving is the goal, the proposed framework can save up to 83% of the running cost while retaining a speedup of up to 40x as compared to single CPU core. The proposed framework is then applied to 128-bit TRIFLE-BC, 64-bit PRESENT and 64-bit GIFT, leading to the discovery of improved differentials. Notably, we identified the best differentials for PRESENT and 64-bit GIFT to date, with probabilities of $2^{-61.7964}$ and $2^{-60.66}$ for 16 and 13 rounds respectively. Although the differential probability for 43 rounds of TRIFLE-BC was not significantly improved, we were able to construct larger differentials with approximately 5.8x more characteristics than existing ones. Thus, the proposed GPU framework is currently the most efficient approach for enumerating 128-bit block cipher differentials, especially for a large number of rounds.

Category / Keywords: secret-key cryptography / Automatic search, block cipher, branch-and-bound, cryptanalysis, differential, differential cryptanalysis, GPU

Date: received 1 Sep 2020

Contact author: yeohweizhu at gmail com, jesen_teh@usm my

Available format(s): PDF | BibTeX Citation

Version: 20200901:174538 (All versions of this report)

Short URL: ia.cr/2020/1056


[ Cryptology ePrint archive ]