Automated Search for Block Cipher Differentials: A GPU-Accelerated Branch-and-Bound Algorithm
| Autor: | Je Sen Teh, Wei-Zhu Yeoh, Jiageng Chen |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
020203 distributed computing
Branch and bound Computer science Differential (mechanical device) 02 engineering and technology Construct (python library) law.invention law Kernel (statistics) 0202 electrical engineering electronic engineering information engineering Enumeration 020201 artificial intelligence & image processing Central processing unit Cryptanalysis Algorithm Block cipher |
| Zdroj: | Information Security and Privacy ISBN: 9783030553036 ACISP |
| DOI: | 10.1007/978-3-030-55304-3_9 |
| Popis: | In this paper, 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|