access icon free New zero-sum distinguishers on full 24-round Keccak-f using the division property

© The Institution of Engineering and Technology
Received 28/05/2018, Accepted 25/02/2019, Revised 04/02/2019, Published 25/02/2019

The authors analyse the security of Keccak (the winner in SHA-3 competition) by focusing on the zero-sum distinguishers of its underlying permutation (named Keccak-f). The authors’ analyses are developed by using the division property, a generalised integral property that was initially used in the integral cryptanalysis of symmetric-key algorithms. Following the work pioneered by Todo at CRYPTO 2015, they first formalise and prove a more delicate propagation rule of the division property under the assumption that the S-box's specification is known to attackers. Then, they apply this rule to the inverse S-box in Keccak-f with a further study on properties of its algebraic degree. They find that the rate of decline in the division property is gentler than that of a randomly chosen S-box. Meanwhile, they get the same results for the S-box in Ascon permutation. Thanks to this vulnerable property, they can improve the higher-order differential characteristics against the inverse of Keccak-f in terms of the required number of chosen plaintexts. As an application, they give new zero-sum distinguishers on full 24-round Keccak-f of size . To the authors’ knowledge, this is currently the best zero-sum distinguishers of full-round Keccak-f permutation. Incidentally, they give the corresponding results for 12-round Ascon permutation.

Inspec keywords: algebra; cryptography

Other keywords: S-box specification; zero-sum distinguishers; higher-order differential characteristics; algebraic degree; generalised integral property; KECCAK-f; Ascon permutation; propagation rule; vulnerable property; symmetric-key algorithms; division property; integral cryptanalysis

Subjects: Algebra; Cryptography; Algebra; Data security

References

    1. 1)
      • 33. Göloglu, F., Rijmen, V., Wang, Q.: ‘On the division property of S-boxes’, IACR Cryptology ePrint Archive, 2016, 2016, p. 188.
    2. 2)
      • 28. Todo, Y., Isobe, T., Hao, Y., et al: ‘Cube attacks on non-blackbox polynomials based on division property’, IEEE Trans. Comput., 2018, 67, (12), pp. 1720–1736.
    3. 3)
      • 23. Todo, Y.: ‘Integral cryptanalysis on full MISTY1’, J. Cryptol., 2017, 30, (3), pp. 920–959.
    4. 4)
      • 5. Daemen, J., Van Assche, G.: ‘Differential propagation analysis of keccak’. Fast Software Encryption, Washington, USA, 2012, vol. 7549, pp. 422–441.
    5. 5)
      • 31. Xiang, Z., Zhang, W., Bao, Z., et al: ‘Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers’. Int. Conf. on the Theory and Application of Cryptology and Information Security, Berlin, Heidelberg, 2016, pp. 648–678.
    6. 6)
      • 26. Todo, Y.: ‘Division property: efficient method to estimate upper bound of algebraic degree’. Int. Conf. on Cryptology in Malaysia, Cham, 2016, pp. 553–571.
    7. 7)
      • 35. Dobraunig, C., Eichlseder, M., Mendel, F., et al: ‘Ascon v1. 2’, Submission to the CAESAR Competition, https://competitions.cr.yp.to/round3/asconv12.pdf, 2016.
    8. 8)
      • 27. Sun, L., Wang, W., Wang, M.: ‘Automatic search of bit-based division property for ARX ciphers and word-based division property’. Int. Conf. on the Theory and Application of Cryptology and Information Security, Cham, 2017, pp. 128–157.
    9. 9)
      • 18. Boura, C., Canteaut, A., De Canniere, C.: ‘Higher-Order differential properties of keccak and Luffa’. Fast Software Encryption, Lyngby, Denmark, 2011, vol. 6733, pp. 252–269.
    10. 10)
      • 32. Dobraunig, C., Eichlseder, M., Mendel, F., et al: ‘Cryptanalysis of ascon’. Cryptographersąŕ Track at the RSA Conf., Cham, 2015, pp. 371–387.
    11. 11)
      • 9. Jean, J., Nikolić, I.: ‘Internal differential boomerangs: practical analysis of the round-reduced keccak-f permutation’. Fast Software Encryption, Istanbul, Turkey, 2015, pp. 537–556.
    12. 12)
      • 17. Boura, C., Canteaut, A.: ‘Zero-sum distinguishers for iterated permutations and application to keccak-f and hamsi-256’. Selected Areas in Cryptography, Waterloo, Canada, 2010, pp. 1–17.
    13. 13)
      • 25. Xiang, Z., Zhang, W., Lin, D.: ‘On the division property of SIMON48 and SIMON64’. Int. Workshop on Security, Cham, 2016, pp. 147–163.
    14. 14)
      • 3. Dworkin, M.J.: ‘Sha-3 standard: permutation-based hash and extendable-output functions’, Federal Inf. Process. Stds. (NIST FIPS)-202, 2015.
    15. 15)
      • 29. Wang, S., Hu, B., Guan, J., et al: ‘MILP method of searching integral distinguishers based on division property using three subsets’, IACR ePrint Report 2018/1186, https://eprint.iacr.org/2018/1186.pdf.
    16. 16)
      • 14. Bertoni, G., Daemen, J., Peeters, M., et al: ‘Cryptographic sponges’, http://sponge.noekeon.org/, 2009.
    17. 17)
      • 16. Guo, J., Liu, M., Song, L.: ‘Linear structures: applications to cryptanalysis of round-reduced keccak’. ASIACRYPT 2016, Hanoi, Vietnam, 2016, vol. 2016, pp. 249–274.
    18. 18)
      • 37. Bogdanov, A., Knudsen, L.R., Leander, G., et al: ‘PRESENT: An ultra-lightweight block cipher’. Cryptographic Hardware and Embedded Systems, Vienna, Austria, 2007, vol. 4727, pp. 450–466.
    19. 19)
      • 10. Mendel, F., Nad, T., Schläffer, M.: ‘Finding SHA-2 characteristics: searching through a minefield of contradictions’. Advances in Cryptology – ASIACRYPT 2011, Seoul, Korea, 2011, pp. 288–307.
    20. 20)
      • 22. Matsui, M.: ‘New block encryption algorithm MISTY’. Fast Software Encryption, Haifa, Israel, 1997, Vol. 1267, pp. 54–68.
    21. 21)
      • 2. NIST.: Sha-3 competition. http://csrc.nist.gov/groups/ST/hash/sha-3/index.html, 2002–2012.
    22. 22)
      • 38. Wang, Q., Grassi, L., Rechberger, C.: ‘Zero-sum partitions of PHOTON permutations’. Cryptographersąŕ Track at the RSA Conf., Cham, 2018, pp. 279–299.
    23. 23)
      • 20. Todo, Y.: ‘Structural evaluation by generalized integral property’. Advances in Cryptology – EUROCRYPT 2015, Sofia, Bulgaria, 2015, pp. 287–314.
    24. 24)
      • 19. Duan, M., Lai, X.J.: ‘Improved zero-sum distinguisher for full round keccak-f permutation’, Chin. Sci. Bull., 2012, 57, (6), pp. 694–697.
    25. 25)
      • 36. Daemen, J., Rijmen, V.: ‘The design of Rijndael: AES-the advanced encryption standard’ (Springer Science and Business Media, Berlin, Heidelberg, 2013).
    26. 26)
      • 21. Knudsen, L., Wagner, D.: ‘Integral cryptanalysis’. Fast Software Encryption, Leuven, Belgium, 2002, pp. 629–632.
    27. 27)
      • 15. Lai, X.: ‘Higher order derivatives and differential cryptanalysis’ Communications and Cryptography (Springer, Boston, MA, 1994), pp. 227–233.
    28. 28)
      • 12. Bertoni, G., Daemen, J., Peeters, M., et al: ‘Note on zero-sum distinguishers of Keccak-f. Public comment on the NIST Hash competition (2010)’, https://keccak.team/files/NoteZeroSum.pdf.
    29. 29)
      • 34. Boura, C., Canteaut, A.: ‘Another view of the division property’. Annual Cryptology Conf., Berlin, Heidelberg, 2016, pp. 654–682.
    30. 30)
      • 8. Dinur, I., Morawiecki, P., Pieprzyk, J., et al: ‘Cube attacks and cube-attack-like cryptanalysis on the round-reduced keccak sponge function’. Advances in Cryptology – EUROCRYPT 2015, Sofia, Bulgaria, 2015, pp. 733–761.
    31. 31)
      • 4. Aumasson, J.P., Meier, W.: ‘Zero-sum distinguishers for reduced keccak-f and for the core functions of Luffa and Hamsi’. Rump Session of Cryptographic Hardware and Embedded Systems-CHES, 2009, vol. 2009, p. 67.
    32. 32)
      • 7. Dinur, I., Dunkelman, O., Shamir, A.: ‘Collision attacks on up to 5 rounds of SHA-3 using generalized internal differentials’. Fast Software Encryption, Singapore, Singapore, 2013, pp. 219–240.
    33. 33)
      • 30. Hu, K., Wang, M.: ‘Automatic Search for a Variant of Division Property Using Three Subsets’. IACR ePrint Report 2018/1187, https://eprint.iacr.org/2018/1187.pdf.
    34. 34)
      • 1. Bertoni, G., Daemen, J., Peeters, M., et al: ‘The Keccak reference’. https://keccak.team/files/Keccak-reference-3.0.pdf, (January 2011) Version 3.0.
    35. 35)
      • 6. Dinur, I., Dunkelman, O., Shamir, A.: ‘New attacks on keccak-224 and keccak-256’. Fast Software Encryption, Washington, USA, 2012, vol 12, pp. 442–461.
    36. 36)
      • 13. Bertoni, G., Daemen, J., Peeters, M., et al: ‘On the indifferentiability of the sponge construction’. Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques, Berlin, Heidelberg, 2008, pp. 181–197.
    37. 37)
      • 24. Todo, Y., Morii, M.: ‘Bit-based division property and application to simon family’. Int. Conf. on Fast Software Encryption, Berlin, Heidelberg, 2016, pp. 357–377.
    38. 38)
      • 11. Naya Plasencia, M., Röck, A., Meier, W.: ‘Practical analysis of reduced-round Keccak’. INDOCRYPT, Chennai, India, 2011, Vol. 7107, pp. 236–254.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2018.5263
Loading

Related content

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