Searching all truncated impossible differentials in SPN

Searching all truncated impossible differentials in SPN

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IET Information Security — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

This study concentrates on finding all truncated impossible differentials in substitution–permutation networks (SPNs) ciphers. Instead of using the miss-in-the-middle approach, the authors propose a mathematical description of the truncated impossible differentials. First, they prove that all truncated impossible differentials in an r + 1 rounds SPN cipher could be obtained by searching entry ‘0’ in D ( P ) r , where D ( P ) denotes the differential pattern matrix (DPM) of P-layer, thus the length of impossible differentials of an SPN cipher is upper bounded by the minimum integer r such that there is no entry ‘0’ in D ( P ) r . Second, they provide two efficient algorithms to compute the DPMs for both bit-shuffles and matrices over GF(2 n ). Using these tools they prove that the longest truncated impossible differentials in SPN structure is 2-round, if the P-layer is designed as an maximum distance separable (MDS) matrix. Finally, all truncated impossible differentials of advanced encryption standard (AES), ARIA, AES-MDS, PRESENT, MAYA and Puffin are obtained.


    1. 1)
      • 1. Daemen, J., Rijmen, V.: ‘The design of Rijndael – AES – the advanced encryption standard’ (Springer, Heidelberg, 2002).
    2. 2)
      • 2. Kwon, D., Kim, J., Park, S., et al: ‘New block cipher: ARIA’. ICISC 2003, Seoul, Korea, November 2003, pp. 432445.
    3. 3)
      • 3. Bogdanov, A., Knudsen, L.R., Leander, G., et al: ‘PRESENT: an ultra-lightweight block cipher’. Proc. of Cryptographic Hardware and Embedded Systems – CHES 2007, Vienna, Austria, September 2007, pp. 450466.
    4. 4)
      • 4. Knudsen, L.: ‘DEAL-A 128 bit block cipher’. Technical Report, 151, Department of Informatics, University of Bergen, Bergen, Norway, February 1998.
    5. 5)
      • 5. Biham, E., Biryukov, A., Shamir, A.: ‘Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials’. EUROCRYPT99, Prague, Czech Republic, May 1999, pp. 1223.
    6. 6)
      • 6. Zhang, W., Wu, W., Feng, D.: ‘New results on impossible differential cryptanalysis of reduced AES’. ICISC07, Seoul, Korea, November 2007, pp. 239250.
    7. 7)
      • 7. Mala, H., Dakhilalian, M., Rijmen, V., et al: ‘Improved impossible differential cryptanalysis of 7-round AES-128’. INDOCRYPT 2010, Hyderabad, India, December 2010, pp. 282291.
    8. 8)
      • 8. Li, R., Sun, B., Zhang, P., et al: ‘New impossible differential cryptanalysis of ARIA’. Cryptology ePrint Archive, Report 2008/227. Available at
    9. 9)
      • 9. Kim, J., Hong, S., Sung, J., et al: ‘Impossible differential cryptanalysis for block cipher structures’. Indocrypt 2003, New Delhi, India, December 2003, pp. 8296.
    10. 10)
      • 10. Luo, Y., Wu, Z., Lai, X.: ‘A unified method for finding impossible differentials of block cipher structures’. Cryptology ePrint Archive, Report 2009/627. Available at
    11. 11)
      • 11. Wei, Y., Li, P., Sun, B., et al: ‘Impossible differential cryptanalysis on Feistel ciphers with SP and SPS round functions’. ACNS 2010, Beijing, China, June 2010, pp. 105122.
    12. 12)
      • 12. Wu, S., Wang, M.: ‘Automatic search of truncated impossible differentials for word-oriented block ciphers’. INDOCRYPT 2012, Kolkata, India, December 2012, pp. 283302.
    13. 13)
      • 13. Biham, E., Shamir, A.: ‘Differential cryptanalysis of DES-like cryptosystem (extended abstract)’. CRYPTO, 1990, pp. 221.
    14. 14)
      • 14. Kanda, M., Matsumoto, T.: ‘Security of camellia against truncated differential cryptanalysis’. FSE 2001, Yokohama, Japan, April 2001, pp. 286299.
    15. 15)
      • 15. Cheng, H., Heys, H.M., Wang, C.: ‘Puffin: a novel compact block cipher targeted to embedded digital systems’. Proc. of Digital System Design Architectures, Methods and Tools (DSD) 2008, Lubeck, Germany, August 2007, pp. 383390.
    16. 16)
      • 16. Gomathisankaran, M., Lee, R.B.L.: ‘MAYA: a novel block encryption function’. Int. Workshop on Coding and Cryptography 2009, Proc., 2009. Available at, accessed 14 February 2010.
    17. 17)
      • 17. Liu, B., Lai, H. J.: ‘Matrices in combinatorics and graph theory’ (Springer, 2000).
    18. 18)
      • 18. Sugita, M., Kobara, K., Uehara, K., et al: ‘Relationships among differential, truncated differential, impossible differential cryptanalyses against block-oriented block ciphers like Rijndael, E2’. Third AES Workshop, 2000. Available at, accessed October 2014.
    19. 19)
      • 19. MacWilliams, F.J., Sloane, N.J.A.: ‘The theory of error correcting codes’ (Elsevier, North Holland, 1986).
    20. 20)
      • 20. Nakahara, J.Jr., Abrahao, É.: ‘A new involutory MDS matrix for the AES’, Int. J. Netw. Sec., 2009, 9, pp. 109116.
    21. 21)
      • 21. Biham, E., Keller, N.: ‘Cryptanalysis of reduced variants of Rijndael’. Third AES Conf., 2000. Available at, accessed December 2013.

Related content

This is a required field
Please enter a valid email address