Skip to main content
Erschienen in: The Journal of Supercomputing 10/2021

24.03.2021

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

verfasst von: Pei Li, Shihao Zhou, Jiageng Chen

Erschienen in: The Journal of Supercomputing | Ausgabe 10/2021

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Literatur
1.
Zurück zum Zitat 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 (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
2.
Zurück zum Zitat 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 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
3.
Zurück zum Zitat 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, 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
4.
Zurück zum Zitat 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 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
5.
Zurück zum Zitat 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 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
6.
Zurück zum Zitat 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 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
7.
Zurück zum Zitat 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 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
8.
Zurück zum Zitat 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 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
9.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Gaster BR, abd David R. Kaeli LH, Mistry P, Schaa D (2013) Heterogeneous Computing with OpenCL (Second Edition). Morgan Kaufmann Gaster BR, abd David R. Kaeli LH, Mistry P, Schaa D (2013) Heterogeneous Computing with OpenCL (Second Edition). Morgan Kaufmann
12.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Knudsen LR, Robshaw M (2011) The Block Cipher Companion. Springer, Information Security and CryptographyCrossRef Knudsen LR, Robshaw M (2011) The Block Cipher Companion. Springer, Information Security and CryptographyCrossRef
17.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Shane C (2012) CUDA Programming: A Developer’s Guide to Parallel Computing with GPUs, 1st edn. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA Shane C (2012) CUDA Programming: A Developer’s Guide to Parallel Computing with GPUs, 1st edn. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA
Metadaten
Titel
A CPU-GPU-based parallel search algorithm for the best differential characteristics of block ciphers
verfasst von
Pei Li
Shihao Zhou
Jiageng Chen
Publikationsdatum
24.03.2021
Verlag
Springer US
Erschienen in
The Journal of Supercomputing / Ausgabe 10/2021
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-021-03703-w

Weitere Artikel der Ausgabe 10/2021

The Journal of Supercomputing 10/2021 Zur Ausgabe