access icon free Searching all truncated impossible differentials in SPN

© The Institution of Engineering and Technology
Received 14/02/2015, Accepted 12/05/2016, Revised 11/12/2015, Published 13/05/2016

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.

Inspec keywords: cryptography; Galois fields; matrix algebra

Other keywords: truncated impossible differentials; r + 1 rounds SPN cipher; bit-shuffles; substitution-permutation network ciphers; MDS matrix; differential pattern matrix; GF(2n); DPM; miss-in-the-middle approach

Subjects: Cryptography; Algebra; Cryptography theory; Algebra

References

    1. 1)
      • 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. 105–122.
    2. 2)
      • 20. Nakahara, J.Jr., Abrahao, É.: ‘A new involutory MDS matrix for the AES’, Int. J. Netw. Sec., 2009, 9, pp. 109–116.
    3. 3)
      • 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. 282–291.
    4. 4)
      • 19. MacWilliams, F.J., Sloane, N.J.A.: ‘The theory of error correcting codes’ (Elsevier, North Holland, 1986).
    5. 5)
      • 21. Biham, E., Keller, N.: ‘Cryptanalysis of reduced variants of Rijndael’. Third AES Conf., 2000. Available at http://www.madchat.fr/crypto/codebreakers/35-ebiham.pdf, accessed December 2013.
    6. 6)
      • 8. Li, R., Sun, B., Zhang, P., et al: ‘New impossible differential cryptanalysis of ARIA’. Cryptology ePrint Archive, Report 2008/227. Available at http://www.eprint.iacr.org/2008/227.
    7. 7)
      • 13. Biham, E., Shamir, A.: ‘Differential cryptanalysis of DES-like cryptosystem (extended abstract)’. CRYPTO, 1990, pp. 2–21.
    8. 8)
      • 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. 383–390.
    9. 9)
      • 4. Knudsen, L.: ‘DEAL-A 128 bit block cipher’. Technical Report, 151, Department of Informatics, University of Bergen, Bergen, Norway, February 1998.
    10. 10)
      • 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. 450–466.
    11. 11)
      • 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 http://www.csrc.nist.gov/archive/aes/round2/conf3/papers/AES3papers-5.zip, accessed October 2014.
    12. 12)
      • 9. Kim, J., Hong, S., Sung, J., et al: ‘Impossible differential cryptanalysis for block cipher structures’. Indocrypt 2003, New Delhi, India, December 2003, pp. 82–96.
    13. 13)
      • 6. Zhang, W., Wu, W., Feng, D.: ‘New results on impossible differential cryptanalysis of reduced AES’. ICISC07, Seoul, Korea, November 2007, pp. 239–250.
    14. 14)
      • 1. Daemen, J., Rijmen, V.: ‘The design of Rijndael – AES – the advanced encryption standard’ (Springer, Heidelberg, 2002).
    15. 15)
      • 14. Kanda, M., Matsumoto, T.: ‘Security of camellia against truncated differential cryptanalysis’. FSE 2001, Yokohama, Japan, April 2001, pp. 286–299.
    16. 16)
      • 12. Wu, S., Wang, M.: ‘Automatic search of truncated impossible differentials for word-oriented block ciphers’. INDOCRYPT 2012, Kolkata, India, December 2012, pp. 283–302.
    17. 17)
      • 5. Biham, E., Biryukov, A., Shamir, A.: ‘Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials’. EUROCRYPT99, Prague, Czech Republic, May 1999, pp. 12–23.
    18. 18)
      • 2. Kwon, D., Kim, J., Park, S., et al: ‘New block cipher: ARIA’. ICISC 2003, Seoul, Korea, November 2003, pp. 432–445.
    19. 19)
      • 16. Gomathisankaran, M., Lee, R.B.L.: ‘MAYA: a novel block encryption function’. Int. Workshop on Coding and Cryptography 2009, Proc., 2009. Available at http://www.palms.princeton.edu/system/files/maya.pdf, accessed 14 February 2010.
    20. 20)
      • 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 http://www.eprint.iacr.org/2009/627.
    21. 21)
      • 17. Liu, B., Lai, H. J.: ‘Matrices in combinatorics and graph theory’ (Springer, 2000).
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2015.0052
Loading

Related content

content/journals/10.1049/iet-ifs.2015.0052
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading