Approximation table computing algorithms in cryptanalysis of block ciphers

• Autorzy: Chmiel K.

Warianty tytułu

PL

Algorytmy obliczania tablic aproksymacji w kryptoanalizie szyfrów blokowych

• Języki publikacji: EN

Abstrakty

EN

Approximation algorithms based on definitions of differential and linear equations, developed for computation of single element of the approximation tables, are of exponential time complexity. Fast general algorithms, for computation the best nonzero approximations in at worst linear time for a single element, without memory needed for storage of the whole table are presented in the paper. To frequently used components of block ciphers belong arithmetic sum and subtraction functions. For these functions are presented fast specialized algorithms computing a single element of the approximation tables in linear time.

PL

Do najważniejszych ogólnych metod analizy kryptograficznej szyfrów blokowych należą kryptoanaliza różnicowa i kryptoanaliza liniowa. W obu metodach wykorzystywane są równania, które w sposób przybliżony, z pewnym prawdopodobieństwem, opisują działanie szyfru. Równania te nazywane są aproksymacjami różnicowymi lub liniowymi. Dla dowolnej funkcji f o n binarnych wejściach i m binarnych wyjściach zbiór wszystkich aproksymacji różnicowych lub liniowych może być reprezentowany w postaci tablicy aproksymacji o rozmiarze O(2n+m). W artykule przedstawiono algorytmy obliczania tych tablic. Oparte na definicji aproksymacji różnicowej lub liniowej algorytmy obliczają pojedynczą wartość tablicy aproksymacji w czasie wykładniczym. Ogranicza to zastosowanie tych podstawowych algorytmów do funkcji składowych szyfru o niewielkiej liczbie binarnych wejść i wyjść. Przedstawione w artykule szybkie ogólne algorytmy obliczają najlepszą niezerową aproksymację różnicową i liniową w co najwyżej liniowym czasie O(n+m) dla pojedynczego elementu bez angażowania pamięci potrzebnej do przechowania całych tablic. Do często stosowanych elementów składowych szyfrów blokowych należą funkcje sumy i różnicy arytmetycznej. Dla tych funkcji przedstawiono w artykule szybkie specjalizowane algorytmy obliczające pojedynczy element tablic aproksymacji w czasie liniowym.

Słowa kluczowe

EN

block cipher; cryptanalysis; differential approximation; linear approximation

PL

szyfr blokowy; kryptoanaliza; aproksymacja różnicowa

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2010
• Tom: R. 56, nr 10
• Strony: 1174--1178
• Opis fizyczny: Bibliogr. 42 poz., rys., tab., wzor

Twórcy

autor

Chmiel K.

• Poznań University of Technology, Institute of Control and Information Engineering, pl. Marii Curie 5, 60-965 Poznań,

Bibliografia

• [1] Benoit G., Tillich J. -P.: On Linear Cryptanalysis with Many Linear Approximations. http://eprint.iacr.org/2009/463.
• [2] Biham E., Shamir A.: Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, Berlin Heidelberg New York 1993.
• [3] Biham E.: New Types of Cryptanalytic Attacks Using Related Keys. EUROCRYPT’93, LNCS 765, 398-409, Springer 1994.
• [4] Biham E., Biryukov A., Shamir A.: Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials, EUROCRYPT’99, LNCS 1592, 12-23, Springer 1999.
• [5] Biham E., Dunkelman O., Keller N.: The Rectangle Attack - Rectangling the Serpent. EUROCRYPT 2001, LNCS 2045, 340-357, Springer 2001.
• [6] Biham E., Dunkelman O., Keller N.: Differential-Linear Cryptanalysis of Serpent. FSE 2003, LNCS 2887, 9-21, Springer 2003.
• [7] Biham E., Dunkelman O., Keller N.: Related-Key Boomerang and Rectangle Attacks. EUROCRYPT 2005, LNCS 3494, 507-525, Springer 2005.
• [8] Biham E., Dunkelman O., Keller N.: A Unified Approach to Related-Key Attacks, FSE 2008, LNCS 5086, 73-96, Springer 2008.
• [9] Biryukov A., Wagner D.: Slide Attacks. FSE’99, LNCS 1636, 245-259, Springer 1999.
• [10] Biryukov A., Khovratovich D., Nikolic I.: Distinguisher and Related-Key Attack on the Full AES-256. CRYPTO 2009, LNCS 5677, 231–249, Springer 2009.
• [11] Biryukov A., Khovratovich D.: Related-key Cryptanalysis of the Full AES-192 and AES-256. ASIACRYPT 2009, LNCS 5912, 1-18, Springer 2009.
• [12] Bucholc K., Chmiel K., Grocholewska-Czuryło A., Idzikowska E., Janicka-Lipska I., Stokłosa J.: Scalable PP-1 Block Cipher, International Journal of Applied Mathematics and Computer Science, Vol. 20, No 2 (2010), 401-411.
• [13] Chmiel K.: Linear Approximation of Arithmetic Sum Function. In Sołdek J., Drobiazgiewicz L. (Eds): Artificial Intelligence and Security in Computing Systems, Kluwer Academic Publishers, 293-302, Boston/Dordrecht/London 2003.
• [14] Chmiel K.: Linear Approximation of Structures with Selectors, Proceedings of 6-th NATO Regional Conference on Military Communications and Information Systems 2004, WIŁ, 269-273, Zegrze 2004.
• [15] Chmiel K.: On Arithmetic Subtraction Linear Approximation. In Pejaś J., Piegat A. (Eds): Enhanced Methods in Computer Security, Biometric and Artificial Intelligence Systems, Kluwer Academic Publishers, 125-134, New York 2005.
• [16] Chmiel K.: Fast Computation of Approximation Tables. In Saeed K., Pejaś, J. (Eds): Information Processing and Security Systems, Springer Verlag, 125-134, Berlin Heidelberg New York 2005.
• [17] Chmiel K.: On Differential and Linear Approximation of S-box Functions. In Saeed K., Pejaś, J., Mosdorf R. (Eds): Biometrics, Computer Security Systems and Artificial Intelligence Applications, Springer, 111-120, New York 2006.
• [18] Chmiel K.: Distribution of the Best Nonzero Differential and Linear Approximations of S-box Functions. Journal of Telecommunications and Information Technology, vol. 3, 2006, 8-13.
• [19] Chmiel K.: Intermediate Evaluation of DES-like Cryptosystems. Proceedings of Military CIS Conference, MCC 2007, (Bonn, Sept. 25-26), ISBN 978-3-934401-16-7, 1-7, Bonn 2007.
• [20] Chmiel K.: On intermediate evaluation of block ciphers. In Pejaś J., Saeed K. (Eds): Advances in Information Processing and Protection, Springer, 251-261, New York 2007.
• [21] Chmiel K.: Differential Approximation of Arithmetic Sum Function. Polish Journal of Environmental Studies, Vol. 16, No 5B (2007), 299-303.
• [22] Chmiel K., Grocholewska-Czuryło A., Stokłosa J.: Involutional Block Cipher for Limited Resources. Proceedings of IEEE GLOBECOM Conference, 1852-1856, New Orleans 2008.
• [23] Chmiel K.: Rough Evaluation of Block Ciphers. Measurements, Automation and Monitoring (PAK), vol. 55, nr 10, 2009, 835-838.
• [24] Courtois N. T.: Feistel Schemes and Bi-linear Cryptanalysis. CRYPTO 2004, LNCS 3152, 23-40, Springer 2004.
• [25] Courtois N. T., Bard G. V., Wagner D.: Algebraic and Slide Attacks on KeeLoq, FSE 2008, LNCS 5086, 97-115, Springer 2008.
• [26] Dunkelman O., Keller N., Kim J.: Related-Key Rectangle Attack on the Full SHACAL-1, SAC 2006, LNCS 4356, 28-44, Springer 2007.
• [27] Dunkelman O., Keller N.: An Improved Impossible Differential Attack on MISTY1. ASIACRYPT 2008, LNCS 5350, 441-454, Springer 2008.
• [28] Harpes C., Massey J.: Partitioning Cryptanalysis, FSE’97, LNCS 1267, 13-27. Springer 1997.
• [29] Hatano Y., Sekine H., Kaneko T.: Higher Order Differential Attack of Camellia (II). SAC 2002, LNCS 2595, 129-146, Springer 2003.
• [30] Kaliski Jr. B. S., Robshaw M. J. B.: Linear Cryptanalysis Using Multiple Approximations and FEAL, FSE’94, LNCS 1008, 249-264, Springer 1995.
• [31] Kelsey J., Schneier B., Wagner D.: Mod n Cryptanalysis, with Applications Against RC5P and M6. FSE’99, LNCS 1636, 139–155, Springer 1999.
• [32] Kim J., Hong S., Preneel B.: Related-Key Rectangle Attacks on Reduced AES-192 and AES-256. FSE 2007, LNCS 4593, 225-241, Springer 2007.
• [33] Knudsen L.: Truncated and Higher Order Differential, FSE’94, LNCS 1008, 196-211, Springer 1995.
• [34] Knudsen L. R., Robshaw M. J. B.: Non-linear Approximations in Linear Cryptanalysis. EUROCRYPT’96, LNCS 1070, 224-236, Springer 1996.
• [35] Langford S., Hellman M.: Differential-Linear Cryptanalysis, CRYPTO’94, LNCS 839, 17-25, Springer 1994.
• [36] Liu Z., Gu D., Zhang J.: Multiple Linear Cryptanalysis of Reduced-Round SMS4 Block Cipher. http://eprint.iacr.org/2009/256
• [37] Lu J., Dunkelman O., Keller N., Kim J.: New Impossible Differential Attacks on AES. http://eprint.iacr.org/2008/540
• [38] Matsui M.: Linear Cryptanalysis Method for DES Cipher, EUROCRYPT’93, LNCS 765, 386-397, Springer 1994.
• [39] Matsui M.: The First Experimental Cryptanalysis of the Data Encryption Standard. CRYPTO’94, LNCS 839, 1-11, Springer 1994.
• [40] Reichardt B. W., Wagner D.: Markov Truncated Differential Cryptanalysis of Skipjack. SAC 2002, LNCS 2595, 110-128, Springer 2003.
• [41] Wagner D.: A Boomerang Attack. FSE’99, LNCS 1636, 156-170, Springer 1999.
• [42] Zhang H., Wang S., Wang X.: The Probability Advantages of Two Linear Expressions in Symmetric Ciphers, http://eprint.iacr.org/ 2006/242