Top

The Journal of Supercomputing

Published in:

24-03-2021

A CPU-GPU-based parallel search algorithm for the best differential characteristics of block ciphers

Authors: Pei Li, Shihao Zhou, Jiageng Chen

Published in: The Journal of Supercomputing | Issue 10/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The differential characteristics with high probability are critical for differential cryptanalysis. The process of searching such differential characteristics, especially the best one, is time-consuming. We believe that the modern hybrid computing systems can be used to accelerate the search process. However, to the best of our knowledge, the existing solutions are not designed for heterogeneous architectures. In this paper, we propose a parallel search algorithm for the best differential characteristic. Our method can be applied to any substitution–permutation network (SPN) block ciphers after making minor modifications. We implemented the proposed parallel search algorithm for PRESENT block cipher and also a sequential version, which based on the classic Matsui’s method, for comparison. The experimental result shows that the parallel algorithm using both CPU and GPU can achieve at least 4.4x and up to 18x speed-up compared to the sequential version.

previous article Correction to: EDVWDD: Event‑Driven Virtual Wheel‑based Data Dissemination for Mobile Sink‑Enabled Wireless Sensor Networks

next article Algorithms and software for data mining and machine learning: a critical comparative view from a systematic review of the literature

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Biham E, Shamir A (1990) Differential cryptanalysis of des-like cryptosystems. In: A. Menezes, S.A. Vanstone (eds.) Advances in Cryptology—CRYPTO ’90, 10th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11-15, 1990, Proceedings, Lecture Notes in Computer Science, vol. 537, pp. 2–21. Springer

Biham E, Shamir A (1992) Differential cryptanalysis of the full 16-round des. In: E.F. Brickell (ed.) Advances in Cryptology—CRYPTO’92, 12th Annual International Cryptology Conference, Santa Barbara, California, USA, August 16-20, 1992, Proceedings, Lecture Notes in Computer Science, vol. 740, pp. 487–496. Springer

Biryukov A, Nikolic I (2010) Automatic search for related-key differential characteristics in byte-oriented block ciphers: Application to aes, camellia, khazad and others. In: H. Gilbert (ed.) Advances in Cryptology—EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30—June 3, 2010. Proceedings, Lecture Notes in Computer Science, vol. 6110, pp. 322–344. Springer

Biryukov A, Velichkov V (2014) Automatic search for differential trails in ARX ciphers. In: J. Benaloh (ed.) Topics in Cryptology—CT-RSA 2014—The Cryptographer’s Track at the RSA Conference 2014, San Francisco, CA, USA, February 25-28, 2014. Proceedings, Lecture Notes in Computer Science, vol. 8366, pp. 227–250. Springer

Bogdanov A, Knudsen LR, Leander G, Paar C, Poschmann A, Robshaw MJB, Seurin Y, Vikkelsoe C (2007) PRESENT: an ultra-lightweight block cipher. In: P. Paillier, I. Verbauwhede (eds.) Cryptographic Hardware and Embedded Systems— CHES 2007, 9th International Workshop, Vienna, Austria, September 10-13, 2007, Proceedings, Lecture Notes in Computer Science, vol. 4727, pp. 450–466. Springer

Carneiro T, Muritiba AEF, Negreiros M, de Campos GAL (2011) A new parallel schema for branch-and-bound algorithms using GPGPU. In: J.L. Gaudiot, A.C.M.A. Melo, A.F.D. Souza, L. Catabriga (eds.) 23rd International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2011, Vitória, Espírito Santo, Brazil, October 26-29, 2011, pp. 41–47. IEEE Computer Society

Chakroun I, Melab N (2013) Operator-level gpu-accelerated branch and bound algorithms. In: V.N. Alexandrov, M. Lees, V.V. Krzhizhanovskaya, J.J. Dongarra, P.M.A. Sloot (eds.) Proceedings of the International Conference on Computational Science, ICCS 2013, Barcelona, Spain, 5-7 June, 2013, Procedia Computer Science, vol. 18, pp. 280–289. Elsevier

Chen J, Miyaji A, Su C, Teh J (2015) Improved differential characteristic searching methods. In: IEEE 2nd International Conference on Cyber Security and Cloud Computing, CSCloud 2015, New York, NY, USA, November 3-5, 2015, pp. 500–508. IEEE Computer Society

Chen K, Tang X, Xu P, Guo M, Qiu W, Gong Z (2016) An improved automatic search method for differential trails in TEA cipher. Int. J. Netw. Secur. 18(4):644–649

10.

Chen Z, Chen J, Meng W, Teh JS, Li P, Ren B (2020) Analysis of differential distribution of lightweight block cipher based on parallel processing on GPU. J. Inf. Secur. Appl. 55:102565

11.

Gaster BR, abd David R. Kaeli LH, Mistry P, Schaa D (2013) Heterogeneous Computing with OpenCL (Second Edition). Morgan Kaufmann

12.

Gmys J, Mezmaz M, Melab N, Tuyttens D (2015) Ivm-based work stealing for parallel branch-and-bound on GPU. In: Wyrzykowski R, Deelman E, Dongarra JJ, Karczewski K, Kitowski J, Wiatr K (eds) Parallel Processing and Applied Mathematics—11th International Conference, PPAM 2015, Krakow, Poland, September 6–9, 2015. Revised Selected Papers, Part I, Lecture Notes in Computer Science Springer

13.

Gmys J, Mezmaz M, Melab N, Tuyttens D (2016) A gpu-based branch-and-bound algorithm using integer-vector-matrix data structure. Parallel Comput. 59:119–139MathSciNetCrossRef

14.

Harpes C, Kramer GG, Massey JL (1995) A generalization of linear cryptanalysis and the applicability of matsui’s piling-up lemma. In: L.C. Guillou, J. Quisquater (eds.) Advances in Cryptology—EUROCRYPT ’95, International Conference on the Theory and Application of Cryptographic Techniques, Saint-Malo, France, May 21-25, 1995, Proceeding, Lecture Notes in Computer Science, vol. 921, pp. 24–38. Springer

15.

Knudsen LR, Leander G (2011) PRESENT— block cipher. In: H.C.A. van Tilborg, S. Jajodia (eds.) Encyclopedia of Cryptography and Security, 2nd Ed, pp. 953–955. Springer

16.

Knudsen LR, Robshaw M (2011) The Block Cipher Companion. Springer, Information Security and CryptographyCrossRef

17.

Lalami ME, Baz DE (2012) Gpu implementation of the branch and bound method for knapsack problems. In: 26th IEEE International Parallel and Distributed Processing Symposium Workshops & PhD Forum, IPDPS 2012, Shanghai, China, May 21-25, 2012, pp. 1769–1777. IEEE Computer Society

18.

Lin L, Wu W, Zheng Y (2017) Improved automatic search tool for related-key differential characteristics on byte-oriented block ciphers. In: P.Q. Nguyen, J. Zhou (eds.) Information Security—20th International Conference, ISC 2017, Ho Chi Minh City, Vietnam, November 22-24, 2017, Proceedings, Lecture Notes in Computer Science, vol. 10599, pp. 58–76. Springer

19.

Matsui M (1995) On correlation between the order of s-boxes and the strength of des. In: De Santis A (ed) Advances in Cryptology—EUROCRYPT’94. Springer, Berlin Heidelberg, Berlin, Heidelberg, pp 366–375CrossRef

20.

Shane C (2012) CUDA Programming: A Developer’s Guide to Parallel Computing with GPUs, 1st edn. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA

Title: A CPU-GPU-based parallel search algorithm for the best differential characteristics of block ciphers
Authors: Pei Li
Shihao Zhou
Jiageng Chen
Publication date: 24-03-2021
Publisher: Springer US
Published in: The Journal of Supercomputing / Issue 10/2021
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-021-03703-w

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 10/2021

iHRNL: Iterative Hessian-based manifold regularization mechanism for localization in WSN

Navigation in the social internet-of-things (SIoT) for discovering the influential service-providers using distributed learning automata

A task recommendation framework for heterogeneous mobile crowdsensing

Cyberattack detection model using deep learning in a network log system with data visualization

Correction to: EDVWDD: Event‑Driven Virtual Wheel‑based Data Dissemination for Mobile Sink‑Enabled Wireless Sensor Networks

Reliability-aware task scheduling for energy efficiency on heterogeneous multiprocessor systems

Premium Partner