access icon free All-subkeys-recovery attacks on a variation of Feistel-2 block ciphers

The Feistel-2 cipher is a type of Feistel ciphers proposed by Isobe and Shibutani at Asiacrypt 2013. Its round functions consist of a public F-function and a subkey XORed before the F-function. Recently, a variation of the Feistel-2 cipher, in which the subkey is XORed after the F-function, has been widely used in proposals such as SIMON and Simeck. The authors denote this type of Feistel ciphers as Feistel-2. In this study, they study the security of Feistel-2* ciphers. First, they propose the differential function reduction technique. Then, they present all-subkeys-recovery attacks against Feistel-2* ciphers based on this technique. Let z be the key size to block size ratio of block ciphers. It is shown that their attacks can break up 6, 8 and 10 rounds of the Feistel-2* cipher for z = 1, 3/2 and 2, respectively. Thanks to the meet-in-the-middle approach, their attacks only need a few chosen plaintexts. Moreover, with higher-data complexity, all attacks can be improved by one round. This implies that a secure Feistel-2* cipher should at least iterate 8, 10 and 12 rounds for z = 1, 3/2 and 2, respectively.

Inspec keywords: iterative methods; cryptography

Other keywords: key size; Feistel-2 block ciphers; Feistel-2* ciphers; block size ratio; public F-function; all-subkeys-recovery attacks; meet-in-the-middle approach; differential function reduction technique; subkey XORed

Subjects: Data security; Interpolation and function approximation (numerical analysis); Cryptography theory; Cryptography; Interpolation and function approximation (numerical analysis)

References

    1. 1)
      • 2. ISO/IEC: ‘Information technology – security techniques – encryption algorithms – part 3: block ciphers’. 2010.
    2. 2)
      • 10. Knudsen, L.R.: ‘The security of Feistel ciphers with six rounds or less’, J. Cryptol., 2002, 15, (3), pp. 207222.
    3. 3)
      • 17. Suzuki, K., Tonien, D., Kurosawa, K., et al: ‘Birthday paradox for multi-collisions’. Proc. Information Security and Cryptology – ICISC 2006, Busan, Korea, 30 November–1 December 2006 (LNCS, 4296), pp. 2940.
    4. 4)
      • 18. Bouillaguet, C., Derbez, P., Fouque, P.-A.: ‘Automatic search of attacks on round-reduced AES and applications’. Proc. Advances in Cryptology – CRYPTO 2011, Sanra Barbara, CA, USA, 14–18 August 2011 (LNCS, 6841), pp. 169187.
    5. 5)
      • 8. Isobe, T., Shibutani, K.: ‘Generic key recovery attack on Feistel scheme’. Proc. Advances in Cryptology – ASIACRYPT 2013, Bengaluru, India, 1–5 December 2013 (LNCS, 8269), pp. 464485.
    6. 6)
      • 1. Coppersmith, D.: ‘The data encryption standard (DES) and its strength against attacks’, IBM J. Res. Dev., 1994, 38, (3), pp. 243250.
    7. 7)
      • 28. Wang, Q., Liu, Z., Varıcı, K., et al: ‘Cryptanalysis of reduced-round SIMON32 and SIMON48’. INDOCRYPT 2014, 2014 (LNCS, 8885), pp. 143160, doi: 10.1007/978-3-319-13039-29.
    8. 8)
      • 23. Kolbl, S., Leander, G., Tiessen, T.: ‘Observations on the SIMON block cipher family’. Proc. Advances in Cryptology – CRYPTO 2015, Santa Barbara, CA, USA, 16–20 August 2015 (LNCS, 9215), pp. 161185.
    9. 9)
      • 16. Isobe, T., Shibutani, K.: ‘Improved all-subkeys recovery attacks on FOX, KATAN and SHACAL-2 block ciphers’. Proc. Fast Software Encryption – FSE 2014, London, UK, 3–5 March 2014 (LNCS, 8540), pp. 104126.
    10. 10)
      • 13. Todo, Y.: ‘Upper bounds for the security of several Feistel networks’. Proc. Information Security and Privacy – ACISP 2013, Brisbane, Australia, 1–3 July 2013 (LNCS, 7959), pp. 302317.
    11. 11)
      • 21. Abed, F., List, E., Lucks, S., et al: ‘Differential cryptanalysis of round-reduced SIMON and SPECK’. Proc. Fast Software Encryption – FSE 2014, London, UK, 3–5 March 2014 (LNCS, 8540), pp. 525545.
    12. 12)
      • 19. Bouillaguet, C., Derbez, P., Dunkelman, O., et al: ‘Low-data complexity attacks on AES’, IEEE Trans. Inf. Theory, 201, 58, (11), pp. 70027017.
    13. 13)
      • 5. Wu, W., Zhang, L.: ‘LBlock: a lightweight block cipher’. Proc. Applied Cryptography and Network Security – ACNS 2011, Nerja, Spain, 7–10 June 2011, (LNCS, 6715), pp. 327344.
    14. 14)
      • 15. Guo, J., Jean, J., Nikolić, I., et al: ‘Meet-in-the-middle attacks on generic Feistel constructions’. Proc. Advances in Cryptology – AISACRYPT 2014, Kaoshiung, Taiwan, 7–11 December 2014 (LNCS, 8873), pp. 458477.
    15. 15)
      • 22. Biryukov, A., Roy, A., Velichkov, V.: ‘Differential analysis of block ciphers SIMON and SPECK’. Proc. Fast Software Encryption – FSE 2014, London, UK, 3–5 March 2014 (LNCS, 8540), pp. 546570.
    16. 16)
      • 7. Yang, G., Zhu, B., Suder, V., et al: ‘The Simeck family of lightweight block ciphers’. Proc. in Cryptographic Hardware and Embedded Systems – CHES 2015, Saint-Malo, France, 13–16 September 2015 (LNCS, 9293), pp. 307329.
    17. 17)
      • 9. Isobe, T., Shibutani, K.: ‘All subkeys recovery attack on block ciphers: extending meet-in-the-middle approach’. Proc. Selected Areas in Cryptography – SAC 2012, Windsor, ON, Canada, 15–16 August 2012 (LNCS, 7707), pp. 202221.
    18. 18)
      • 4. Aoki, K., Ichikawa, T., Kanda, M., et al: ‘Camellia: a 128 bit block cipher suitable for multiple platforms – design and analysis’. Proc. Selected Areas in Cryptography – SAC 2001, Toronto, ON, Canada, 16–17 August 2001 (LNCS, 2012), pp. 3956.
    19. 19)
      • 25. Alkhzaimi, H.A., Lauridsen, M.M.: ‘Cryptanalysis of the SIMON family of block ciphers’. Cryptology ePrint Archive, Report 2013/543, 2013.
    20. 20)
      • 3. Adams, C.: ‘The CAST-128 encryption algorithm’. RFC-2144, May 1997.
    21. 21)
      • 11. Biham, E., Biryukov, A., Shamir, A.: ‘Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials’. Proc. Advances in Cryptology – EUROCRYPT 1999, Czech Republic, 2–6 May 1999 (LNCS, 1592), pp. 1223.
    22. 22)
      • 26. Boura, C., Naya-Plasencia, M., Suder, V.: ‘Scrutinizing and improving impossible differential attacks: applications to CLEFIA, Camellia, LBlock and SIMON’. Proc. Advances in Cryptology – AISACRYPT 2014, Kaoshiung, Taiwan, 7–11 December 2014 (LNCS, 8873), pp. 179199.
    23. 23)
      • 27. Yu, X., Wu, W., Shi, Z., et al: ‘Zero-correlation linear cryptanalysis of reduced-round SIMON’, J. Comput. Sci. Technol., 2015, 30, (6), pp. 13581369.
    24. 24)
      • 30. Song, L., Hu, L., Ma, B., et al: ‘Match box meet-in-the-middle attacks on the SIMON family of block ciphers’. LightSec 2014, Istanbul, Turkey, 1–2 September 2014 (LNCS, 8898), pp. 140151.
    25. 25)
      • 20. Abed, F., List, E., Lucks, S., et al: ‘Differential and linear cryptanalysis of reduced-round SIMON’. Cryptology ePrint Archive, Report 2013/526, 2013.
    26. 26)
      • 14. Bogdanov, A., Rijmen, V.: ‘Linear hulls with correlation zero and linear cryptanalysis of block ciphers’, Des. Codes Cryptogr., 2014, 70, (3), pp. 369383.
    27. 27)
      • 12. Patarin, J.: ‘Security of random Feistel schemes with 5 or more rounds’. Proc. Advances in Cryptology – CRYPTO 2004, Santa Barbara, CA, USA, 15–19 August 2004 (LNCS, 3152), pp. 106122.
    28. 28)
      • 29. Todo, Y.: ‘Structural evaluation by generalized integral property’. Proc. Advances in Cryptology – EUROCRYPT 2015, Sofia, Bulgaria, 26–30 April 2015 (LNCS, 9056), pp. 287314.
    29. 29)
      • 6. Beaulieu, R., Shors, D., Smith, J., et al: ‘The SIMON and SPECK families of lightweight block ciphers’. Available at http://www.eprint.iacr.org/2013/404.pdf, accessed December 2015.
    30. 30)
      • 24. Bagheri, N.: ‘Linear cryptanalysis of reduced-round SIMECK variants’. Proc. Progress in Cryptology – INDOCRYPT 2015, Bangalore, India, 6–9 December 2015 (LNCS, 9462), pp. 140152.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2016.0014
Loading

Related content

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