Evaluation of PP-1 Cipher Resistance against Differential and Linear Cryptanalysis in Comparison to a DES-like Cipher

• Autorzy: Chmiel K. , Grocholewska-Czurylo A. , Stoklosa J.
• Języki publikacji: EN

Abstrakty

EN

In the paper we present an involutional block cipher PP-1, which is a scalable SPN. The cipher has very low memory requirements and uses only simple and fast arithmetic operations. The paper discusses in detail the PP-1 cipher design, including the S-box construction, the permutation and the round key scheduling. The quality of the PP-1 cipher is evaluated with respect to differential and linear cryptanalysis. Its quality is compared to the quality of a comparative algorithm with the same block length, as well as to the quality of the class of balanced Feistel ciphers, and in particular to DES quality.

Słowa kluczowe

EN

block cipher; S-box construction; cryptanalysis; differential approximation; linear approximation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 114, nr 3/4
• Strony: 239--269
• Opis fizyczny: Bibliogr. 60 poz., tab., wykr.

Twórcy

autor

Chmiel K.

autor

Grocholewska-Czurylo A.

autor

Stoklosa J.

• Institute of Control and Information Engineering Poznan University of Technology pl. Marii Sklodowskiej Curie 5, 60-965 Poznan, Poland,

Bibliografia

• [1] Proceedings of the Global Communications Conference, 2008. GLOBECOM 2008, New Orleans, LA, USA, 30 November - 4 December 2008, IEEE, 2008.
• [2] Biham, E.: New Types of Cryptoanalytic Attacks Using related Keys (Extended Abstract), EUROCRYPT, 1993.
• [3] Biham, E., Ed.: Fast Software Encryption, 4th International Workshop, FSE '97, Haifa, Israel, January 20-22, 1997, Proceedings, vol. 1267 of Lecture Notes in Computer Science, Springer, 1997, ISBN 3-540-63247-6.
• [4] Biham, E., Biryukov, A., Shamir, A.: Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials, EUROCRYPT, 1999.
• [5] Biham, E., Dunkelman, O., Keller, N.: The Rectangle Attack - Rectangling the Serpent, in: Pfitzmann [55], 340-357.
• [6] Biham, E., Dunkelman, O., Keller, N.: Differential-Linear Cryptanalysis of Serpent, in: Johansson [39], 9-21.
• [7] Biham, E., Dunkelman, O., Keller, N.: Related-Key Boomerang and Rectangle Attacks, in: Cramer [27], 507-525.
• [8] Biham, E., Dunkelman, O., Keller, N.: A Unified Approach to Related-Key Attacks, in: Nyberg [53], 73-96.
• [9] Biham, E., Shamir, A.: Differential Cryptanalysis of the Full 16-Round DES, in: Brickell [17], 487-496.
• [10] Biham, E., Shamir, A.: Differential cryptanalysis of the data encryption standard, Springer-Verlag, London, UK, 1993, ISBN 0-387-97930-1.
• [11] Biham, E., Youssef, A. M., Eds.: Selected Areas in Cryptography, 13th International Workshop, SAC 2006, Montreal, Canada, August 17-18, 2006 Revised Selected Papers, vol. 4356 of Lecture Notes in Computer Science, Springer, 2007, ISBN 978-3-540-74461-0.
• [12] Biryukov, A.: Analysis of involutional ciphers: Khazad and Anubis, in: Johansson [39], 45-53.
• [13] Biryukov, A., Ed.: Fast Software Encryption, 14th International Workshop, FSE 2007, Luxembourg, Luxembourg, March 26-28, 2007, Revised Selected Papers, vol. 4593 of Lecture Notes in Computer Science, Springer, 2007, ISBN 978-3-540-74617-1.
• [14] Biryukov, A., Khovratovich, D.: Related-Key Cryptanalysis of the Full AES-192 and AES-256, in: Matsui [51], 1-18.
• [15] Biryukov, A., Khovratovich, D., Nikolic, I.: Distinguisher and Related-Key Attack on the Full AES-256, in: Halevi [36], 231-249.
• [16] Biryukov, A., Wagner, D.: Slide Attacks, in: Knudsen [44], 245-259.
• [17] Brickell, E. F., Ed.: Advances in Cryptology - CRYPTO '92, 12th Annual International Cryptology Conference, Santa Barbara, California, USA, August 16-20, 1992, Proceedings, vol. 740 of Lecture Notes in Computer Science, Springer, 1993, ISBN 3-540-57340-2.
• [18] Bucholc, K., Chmiel, K., Grocholewska-Czurylo, A., Idzikowska, E., Janicka-Lipska, I., Stoklosa, J.: Scalable PP-1 block cipher, Applied Mathematics and Computer Science, 20(2), 2010, 401-411.
• [19] Bucholc, K., Chmiel, K., Grocholewska-Czurylo, A., Stoklosa, J.: PP-1 block cipher, Proceedings of 14th International Multi-Conference on Advanced Computer Systems ACS 2007, 2007, 315-320.
• [20] Chmiel, K.: Linear Approximation of Arithmetic Sum Function, Artificial Intelligence and Security in Computing Systems, 2003, 293-302.
• [21] Chmiel, K.: Differential Approximation of Arithmetic Sum Function, Polish Journal of Environmental Studies, 16 No. 5B, 2007, 299-303.
• [22] Chmiel, K.: Rough Evaluation of Block Ciphers, Measurements, Automation and Monitoring (PAK), 55 No. 10, 2009, 835-838.
• [23] Chmiel, K., Grocholewska-Czurylo, A., Socha, P., Stoklosa, J.: Scalable Cipher for Limited Resources, Polish Journal of Environmental Studies, 17 No. 4C, 2008, 371-377.
• [24] Chmiel, K., Grocholewska-Czurylo, A., Stoklosa, J.: Involutional Block Cipher for Limited Resources, in: GLOBECOM [1], 1852-1856.
• [25] Courtois, N.: Feistel Schemes and Bi-linear Cryptanalysis, in: Franklin [32], 23-40.
• [26] Courtois, N., Bard, G. V., Wagner, D.: Algebraic and Slide Attacks on KeeLoq, in: Nyberg [53], 97-115.
• [27] Cramer, R., Ed.: Advances in Cryptology - EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings, vol. 3494 of Lecture Notes in Computer Science, Springer, 2005, ISBN 3-540-25910-4.
• [28] Daemen, J., Rijmen, V.: AES Proposal: Rijndael, 1999.
• [29] Desmedt, Y., Ed.: Advances in Cryptology - CRYPTO '94, 14th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1994, Proceedings, vol. 839 of Lecture Notes in Computer Science, Springer, 1994, ISBN 3-540-58333-5.
• [30] Dunkelman, O., Keller, N.: An Improved Impossible Differential Attack on MISTY1, in: Pieprzyk [56], 441-454.
• [31] Dunkelman, O., Keller, N., Kim, J.: Related-Key Rectangle Attack on the Full SHACAL-1, in: Biham and Youssef [11], 28-44.
• [32] Franklin, M. K., Ed.: Advances in Cryptology - CRYPTO 2004, 24th Annual International CryptologyConference, Santa Barbara, California, USA, August 15-19, 2004, Proceedings, vol. 3152 of Lecture Notes in Computer Science, Springer, 2004, ISBN 3-540-22668-0.
• [33] Fuller, J., Millan, W.: On Linear Redundancy in the AES S-Box, Cryptology ePrint Archive, http://eprint.iacr.org, 2002.
• [34] Fuller, J., Millan, W.: Linear Redundancy in S-Boxes, in: Johansson [39], 74-86.
• [35] Gerard, B., Tillich, J.-P.: On Linear Cryptanalysis with Many Linear Approximations, Proceedings of the 12th IMA International Conference on Cryptography and Coding, Cryptography and Coding '09, Springer-Verlag, Berlin, Heidelberg, 2009, ISBN 978-3-642-10867-9.
• [36] Halevi, S., Ed.: Advances in Cryptology - CRYPTO 2009, 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2009. Proceedings, vol. 5677 of Lecture Notes in Computer Science, Springer, 2009, ISBN 978-3-642-03355-1.
• [37] Harpes, C., Massey, J. L.: Partitioning Cryptanalysis, in: Biham [3], 13-27.
• [38] Hatano, Y., Sekine, H., Kaneko, T.: Higher Order Differential Attack of Camellia (II), in: Nyberg and Heys [54], 129-146.
• [39] Johansson, T., Ed.: Fast Software Encryption, 10th InternationalWorkshop, FSE 2003, Lund, Sweden, February 24-26, 2003, Revised Papers, vol. 2887 of Lecture Notes in Computer Science, Springer, 2003, ISBN 3-540-20449-0.
• [40] Kaliski Jr., B. S., Robshaw, M. J. B.: Linear Cryptanalysis Using Multiple Approximations and FEAL, in: Preneel [57], 249-264.
• [41] Kelsey, J., Schneier, B., Wagner, D.: Mod n Cryptanalysis, with Applications Against RC5P and M6, in: Knudsen [44], 139-155.
• [42] Kim, J., Hong, S., Preneel, B.: Related-Key Rectangle Attacks on Reduced AES-192 and AES-256, in: Biryukov [13], 225-241.
• [43] Knudsen, L. R.: Truncated and Higher Order Differentials, in: Preneel [57], 196-211.
• [44] Knudsen, L. R., Ed.: Fast Software Encryption, 6th International Workshop, FSE '99, Rome, Italy, March 24-26, 1999, Proceedings, vol. 1636 of Lecture Notes in Computer Science, Springer, 1999, ISBN 3-540-66226-X.
• [45] Knudsen, L. R., Robshaw, M. J. B.: Non-Linear Approximations in Linear Cryptoanalysis, EUROCRYPT, 1996.
• [46] Langford, S. K., Hellman, M. E.: Differential-Linear Cryptanalysis, in: Desmedt [29], 17-25.
• [47] Liu, Z., Gu, D., Zhang, J.: Multiple Linear Cryptanalysis of Reduced-Round SMS4 Block Cipher, IACR Cryptology ePrint Archive, 2009, 256.
• [48] Lu, J., Dunkelman, O., Keller, N., Kim, J.: New Impossible Differential Attacks on AES, IACR Cryptology ePrint Archive, 2008, 540.
• [49] Matsui, M.: Linear Cryptoanalysis Method for DES Cipher, EUROCRYPT, 1993.
• [50] Matsui, M.: The First Experimental Cryptanalysis of the Data Encryption Standard, in: Desmedt [29], 1-11.
• [51] Matsui, M., Ed.: Advances in Cryptology - ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6-10, 2009. Proceedings, vol. 5912 of Lecture Notes in Computer Science, Springer, 2009, ISBN 978-3-642-10365-0.
• [52] Misztal, M.: Differential Cryptanalysis of PP-1 Cipher, Proceedings of International Cryptology Conference - Recent Advances in Cryptology and National Telecommunication Security Systems, Warsaw, 2011.
• [53] Nyberg, K., Ed.: Fast Software Encryption, 15th International Workshop, FSE 2008, Lausanne, Switzerland, February 10-13, 2008, Revised Selected Papers, vol. 5086 of Lecture Notes in Computer Science, Springer, 2008, ISBN 978-3-540-71038-7.
• [54] Nyberg, K., Heys, H. M., Eds.: Selected Areas in Cryptography, 9th Annual International Workshop, SAC 2002, St. John's, Newfoundland, Canada, August 15-16, 2002. Revised Papers, vol. 2595 of Lecture Notes in Computer Science, Springer, 2003, ISBN 3-540-00622-2.
• [55] Pfitzmann, B., Ed.: Advances in Cryptology - EUROCRYPT 2001, International Conference on the Theory and Application of Cryptographic Techniques, Innsbruck, Austria, May 6-10, 2001, Proceeding, vol. 2045 of Lecture Notes in Computer Science, Springer, 2001, ISBN 3-540-42070-3.
• [56] Pieprzyk, J., Ed.: Advances in Cryptology - ASIACRYPT 2008, 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 7-11, 2008. Proceedings, vol. 5350 of Lecture Notes in Computer Science, Springer, 2008, ISBN 978-3-540-89254-0.
• [57] Preneel, B., Ed.: Fast Software Encryption: Second International Workshop. Leuven, Belgium, 14-16 December 1994, Proceedings, vol. 1008 of Lecture Notes in Computer Science, Springer, 1995.
• [58] Reichardt, B., Wagner, D.: Markov Truncated Differential Cryptanalysis of Skipjack, in: Nyberg and Heys [54], 110-128.
• [59] Wagner, D.: The Boomerang Attack, in: Knudsen [44], 156-170.
• [60] Zhang, H., Wang, S., Wang, X.: The Probability Advantages of Two Linear Expressions in Symmetric Ciphers, IACR Cryptology ePrint Archive, 2006, 242.