Differential cryptanalysis of PP-1 cipher

• Autorzy: Misztal M.
• Języki publikacji: EN

Abstrakty

EN

In this paper we present a differential attack on the block cipher PP-1 which was designed at Poznan University of Technology. Complexity of the attack is smaller than that of brute force attack for every version of the cipher (for every block length). The attack is possible is spite of the fact that the S-box exhibits optimal security against the differential cryptanalysis. The attack is based on the fact that the design of the cipher S-box and permutation were constructed independently. The permutation operates on individual bits, and in the XOR profile table of S-box 1 bit to 1 bit transitions are possible. It allows constructing a simple one-round differential characteristic which is almost iterative with the probability 1.5 · 2^-6. By 9 times concatenation of the characteristic and its relaxation in the last round we obtained a 10-round characteristic with the probability 2-48.7. Using this characteristic with 1R attack makes differential cryptanalysis of full 11-round cipher with complexity smaller than exhaustive search possible. By carefully exploiting similar characteristics it is possible to find analogous attacks on different versions of cipher PP-1, with higher a larger of rounds.

Słowa kluczowe

EN

differential attack; block cipher PP-1; cipher S-box

• Wydawca: Wydawnictwo UMCS
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
• Rocznik: 2011
• Tom: Vol. 11, no. 2
• Strony: 9--24
• Opis fizyczny: Bibliogr. 15 poz., rys., tab.

Twórcy

autor

Misztal M.

• Institute of Mathematics and Cryptology, Cybernetics Faculty, Military University of Technology, ul. S. Kaliskiego 2, 00-908 Warsaw, Poland

Bibliografia

• [1] Biham E., Shamir A., Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, New York (1993).
• [2] Matsui M., Linear Cryptanalysis Method for DES Cipher, EuroCrypt ’93, Springer-Verlag (1993).
• [3] Matsui M., The first experimental Cryptanalysis of the Data Encryption Standard, CRYPTO ’94, Springer-Verlag (1994).
• [4] Courtois N. T., Pieprzyk J., Cryptanalysis of Block Ciphers with Overdefined Systems of Equations, AsiaCrypt 2002, Springer-Verlag (2002).
• [5] Misztal M., Methods of cryptanalysis of block ciphers,(in polish). Bulletin WAT Cryptology part IV, Warszawa (2004).
• [6] McBride L., Q: A Proposal for NESSIE v2.00, submission to NESSIE (2000).
• [7] Biham E., Furman V., Misztal M., Rijmen V., Differential Cryptanalysis of Q, FSE 2002, LNCS 2355, Springer-Verlag (2002).
• [8] Courtois N. T., Misztal M., Aggregated Differentials and Cryptanalysis of PP-1 and GOST, To appear in 11th Central European Conference on Cryptology (2011), 30 June - 2 July, Debrecen, Hungary.
• [9] Chmiel K., Differential and linear methods of cryptanalysis of block ciphers, (in polish), Habilitation dissertation, Pozna´n (2009).
• [10] Chmiel K. Grocholewska-Czury lo A., Stok losa J., Involutional Block Cipher for Limited Resources, IEEE ”GLOBECOM” (2008) – proceedings.
• [11] Misztal M., Practical differential cryptanalysis of DES reduced to 8 rounds, (in polish). Bulletin WAT Cryptology part I, Warszawa (1999).
• [12] Deamen J., Rijmen V., The Design of Rijndael, Springer-Verlag (2002).
• [13] Rijmen V., Cryptanalysis and design of iterated block ciphers, PhD Thesis, October (1997), K.U.Leuven.
• [14] Seki H., Kaneko T., Differential Cryptanalysis of Reduced Rounds of GOST, SAC 2000, Springer-Verlag LNCS 2012 (2001): 315.
• [15] Misztal M., The S/N ratio in differential cryptanalysis of 9 rounds of DES, Journal of Telecommunications and Information Technology (JTIT) 3 (2006): 49.