Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Divide and Rule: DiFA  - Division Property Based Fault Attacks on PRESENT and GIFT

  • Conference paper
  • First Online:
Applied Cryptography and Network Security (ACNS 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13905))

Included in the following conference series:

  • 819 Accesses

Abstract

The division property introduced by Todo in Crypto 2015 is one of the most versatile tools in the arsenal of a cryptanalyst which has given new insights into many ciphers primarily from an algebraic perspective. On the other end of the spectrum we have fault attacks which have evolved into the deadliest of all physical attacks on cryptosystems. The current work aims to combine these seemingly distant tools to come up with a new type of fault attack. We show how fault invariants are formed under special input division multi-sets and are independent of the fault injection location. It is further shown that the same division trail can be exploited as a multi-round Zero-Sum distinguisher to reduce the key-space to practical limits. As a proof of concept division trails of PRESENT and GIFT are exploited to mount practical key-recovery attacks based on the random nibble fault model. For GIFT-64, we are able to recover the unique master-key with 30 nibble faults with faults injected at rounds 21 and 19. For PRESENT-80, DiFA reduces the key-space from \(2^{80}\) to \(2^{16}\) with 15 faults in round 25 while for PRESENT-128, the unique key is recovered with 30 faults in rounds 25 and 24. This constitutes the best fault attacks on these ciphers in terms of fault injection rounds. We also report an interesting property pertaining to fault induced division trails which shows its inapplicability to attack GIFT-128. Overall, the usage of division trails in fault based cryptanalysis showcases new possibilities and reiterates the applicability of classical cryptanalytic tools in physical attacks.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 89.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 119.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Aumasson, J.P., Meier, W.: Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi. In: Rump Session of Cryptographic Hardware and Embedded Systems-CHES 2009, p. 67 (2009)

    Google Scholar 

  2. Bagheri, N., Ebrahimpour, R., Ghaedi, N.: New differential fault analysis on PRESENT. EURASIP J. Adv. Signal Process. 2013, 145 (2013)

    Article  Google Scholar 

  3. Banik, S., Pandey, S.K., Peyrin, T., Sasaki, Yu., Sim, S.M., Todo, Y.: GIFT: a small present. In: Fischer, W., Homma, N. (eds.) CHES 2017. LNCS, vol. 10529, pp. 321–345. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66787-4_16

    Chapter  Google Scholar 

  4. Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B., Wingers, L.: The SIMON and SPECK lightweight block ciphers. In: Proceedings of the 52nd Annual Design Automation Conference, DAC 2015. Association for Computing Machinery, New York (2015)

    Google Scholar 

  5. Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: The keccak reference. In: Submission to NIST, vol. 3, no. 30, pp. 320–337 (2011)

    Google Scholar 

  6. Biham, E.: New types of cryptanalytic attacks using related keys. J. Cryptol. 7(4), 229–246 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  7. Biham, E., Anderson, R., Knudsen, L.: Serpent: a new block cipher proposal. In: Vaudenay, S. (ed.) FSE 1998. LNCS, vol. 1372, pp. 222–238. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-69710-1_15

    Chapter  Google Scholar 

  8. Biham, E., Biryukov, A., Dunkelman, O., Richardson, E., Shamir, A.: Initial observations on skipjack: cryptanalysis of skipjack-3XOR. In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, pp. 362–375. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48892-8_27

    Chapter  Google Scholar 

  9. Biryukov, A., Khovratovich, D.: PAEQ: parallelizable permutation-based authenticated encryption. In: Chow, S.S.M., Camenisch, J., Hui, L.C.K., Yiu, S.M. (eds.) ISC 2014. LNCS, vol. 8783, pp. 72–89. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13257-0_5

    Chapter  Google Scholar 

  10. Bogdanov, A., et al.: PRESENT: an ultra-lightweight block cipher. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 450–466. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74735-2_31

    Chapter  Google Scholar 

  11. Boneh, D., DeMillo, R.A., Lipton, R.J.: On the importance of checking cryptographic protocols for faults. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 37–51. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-69053-0_4

    Chapter  Google Scholar 

  12. Boura, C., Canteaut, A.: Zero-sum distinguishers for iterated permutations and application to Keccak-f and Hamsi-256. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) SAC 2010. LNCS, vol. 6544, pp. 1–17. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19574-7_1

    Chapter  Google Scholar 

  13. Boura, C., Canteaut, A., De Cannière, C.: Higher-order differential properties of Keccak and Luffa. In: Joux, A. (ed.) FSE 2011. LNCS, vol. 6733, pp. 252–269. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21702-9_15

    Chapter  Google Scholar 

  14. Breier, J., et al.: Extensive laser fault injection profiling of 65 nm FPGA. J. Hardw. Syst. Secur. 1(3), 237–251 (2017). https://doi.org/10.1007/s41635-017-0016-z

    Article  Google Scholar 

  15. Colombier, B., et al.: Multi-spot laser fault injection setup: new possibilities for fault injection attacks. In: 20th Smart Card Research and Advanced Application Conference-CARDIS 2021 (2021)

    Google Scholar 

  16. Daemen, J., Knudsen, L., Rijmen, V.: The block cipher square. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 149–165. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0052343

    Chapter  Google Scholar 

  17. Daemen, J., Rijmen, V.: The Design of Rijndael: AES - The Advanced Encryption Standard. Information Security and Cryptography, Springer, Heidelberg (2002). https://doi.org/10.1007/978-3-662-04722-4

    Book  MATH  Google Scholar 

  18. Derbez, P., Fouque, P.-A., Leresteux, D.: Meet-in-the-middle and impossible differential fault analysis on AES. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 274–291. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23951-9_19

    Chapter  Google Scholar 

  19. Dobraunig, C., Eichlseder, M., Korak, T., Mangard, S., Mendel, F., Primas, R.: SIFA: exploiting ineffective fault inductions on symmetric cryptography. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2018(3), 547–572 (2018)

    Article  Google Scholar 

  20. Dutertre, J., et al.: Laser fault injection at the CMOS 28 nm technology node: an analysis of the fault model. In: 2018 Workshop on Fault Diagnosis and Tolerance in Cryptography, FDTC 2018, Amsterdam, The Netherlands, 13 September 2018, pp. 1–6. IEEE Computer Society (2018). https://doi.org/10.1109/FDTC.2018.00009

  21. Eskandari, Z., Kidmose, A.B., Kölbl, S., Tiessen, T.: Finding integral distinguishers with ease. In: Cid, C., Jacobson, M., Jr. (eds.) SAC 2018. LNCS, vol. 11349, pp. 115–138. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-10970-7_6

    Chapter  Google Scholar 

  22. Fuhr, T., Jaulmes, É., Lomné, V., Thillard, A.: Fault attacks on AES with faulty ciphertexts only. In: FDTC, pp. 108–118. IEEE Computer Society (2013)

    Google Scholar 

  23. Ghosh, S., Dunkelman, O.: Automatic search for bit-based division property. In: Longa, P., Ràfols, C. (eds.) LATINCRYPT 2021. LNCS, vol. 12912, pp. 254–274. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-88238-9_13

    Chapter  Google Scholar 

  24. Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual (2023). https://www.gurobi.com

  25. Hu, K., Wang, Q., Wang, M.: Finding bit-based division property for ciphers with complex linear layers. IACR Trans. Symmetric Cryptol. 2020(1), 396–424 (2020)

    Article  Google Scholar 

  26. Jeong, K., Lee, Y., Sung, J., Hong, S.: Improved differential fault analysis on PRESENT-80/128. Int. J. Comput. Math. 90(12), 2553–2563 (2013)

    Google Scholar 

  27. Knudsen, L.R.: Truncated and higher order differentials. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 196–211. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-60590-8_16

    Chapter  Google Scholar 

  28. Lai, X.: Higher order derivatives and differential cryptanalysis. In: Blahut, R.E., Costello, D.J., Maurer, U., Mittelholzer, T. (eds.) Communications and Cryptography: Two Sides of One Tapestry, pp. 227–233. Springer, Boston (1994). https://doi.org/10.1007/978-1-4615-2694-0_23

    Chapter  Google Scholar 

  29. Luo, H., Chen, W., Ming, X., Wu, Y.: General differential fault attack on PRESENT and GIFT cipher with nibble. IEEE Access 9, 37697–37706 (2021)

    Article  Google Scholar 

  30. Mendel, F., Rechberger, C., Schläffer, M., Thomsen, S.S.: The rebound attack: cryptanalysis of reduced whirlpool and grøstl. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 260–276. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03317-9_16

    Chapter  Google Scholar 

  31. Min, X., Feng, T., Jiaqi, L.: Differential fault attack on GIFT. Chin. J. Electron. 30(4), 669–675 (2021)

    Article  Google Scholar 

  32. Mouha, N., Wang, Q., Gu, D., Preneel, B.: Differential and linear cryptanalysis using mixed-integer linear programming. In: Wu, C.-K., Yung, M., Lin, D. (eds.) Inscrypt 2011. LNCS, vol. 7537, pp. 57–76. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34704-7_5

    Chapter  MATH  Google Scholar 

  33. Ross, S.M.: A First Course in Probability, 5th edn. Prentice Hall, Upper Saddle River (1998)

    MATH  Google Scholar 

  34. Saha, D., Chowdhury, D.R.: Encounter: on breaking the nonce barrier in differential fault analysis with a case-study on PAEQ. In: Gierlichs, B., Poschmann, A.Y. (eds.) CHES 2016. LNCS, vol. 9813, pp. 581–601. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53140-2_28

    Chapter  Google Scholar 

  35. Sakiyama, K., Sasaki, Y., Li, Y.: Security of Block Ciphers - From Algorithm Design to Hardware Implementation. Wiley, Hoboken (2015)

    Book  Google Scholar 

  36. Sun, L., Wang, W., Liu, R., Wang, M.: MILP-aided bit-based division property for ARX ciphers. Sci. China Inf. Sci. 61(11), 118102:1–118102:3 (2018)

    Google Scholar 

  37. Sun, L., Wang, W., Wang, M.: MILP-aided bit-based division property for primitives with non-bit-permutation linear layers. IET Inf. Secur. 14(1), 12–20 (2020)

    Article  Google Scholar 

  38. Sun, S., et al.: Analysis of AES, skinny, and others with constraint programming. IACR Trans. Symmetric Cryptol. 2017(1), 281–306 (2017)

    Article  MathSciNet  Google Scholar 

  39. Todo, Y.: Integral cryptanalysis on full MISTY1. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 413–432. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_20

    Chapter  Google Scholar 

  40. Todo, Y.: Structural evaluation by generalized integral property. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 287–314. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_12

    Chapter  Google Scholar 

  41. Todo, Y., Morii, M.: Bit-based division property and application to Simon family. In: Peyrin, T. (ed.) FSE 2016. LNCS, vol. 9783, pp. 357–377. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-52993-5_18

    Chapter  Google Scholar 

  42. Vafaei, N., Zarei, S., Bagheri, N., Eichlseder, M., Primas, R., Soleimany, H.: Statistical effective fault attacks: the other side of the coin. IACR Cryptol. ePrint Arch. 642 (2022)

    Google Scholar 

  43. Wagner, D.: The boomerang attack. In: Knudsen, L. (ed.) FSE 1999. LNCS, vol. 1636, pp. 156–170. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48519-8_12

    Chapter  Google Scholar 

  44. Wang, G., Wang, S.: Differential fault analysis on PRESENT key schedule. In: Liu, M., Wang, Y., Guo, P. (eds.) 2010 International Conference on Computational Intelligence and Security, CIS 2010, Nanning, Guangxi Zhuang Autonomous Region, China, 11–14 December 2010, pp. 362–366. IEEE Computer Society (2010)

    Google Scholar 

  45. Wang, Q., Grassi, L., Rechberger, C.: Zero-sum partitions of PHOTON permutations. In: Smart, N.P. (ed.) CT-RSA 2018. LNCS, vol. 10808, pp. 279–299. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76953-0_15

    Chapter  Google Scholar 

  46. Xiang, Z., Zhang, W., Bao, Z., Lin, D.: Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 648–678. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_24

    Chapter  Google Scholar 

  47. Zhang, F., et al.: A framework for the analysis and evaluation of algebraic fault attacks on lightweight block ciphers. IEEE Trans. Inf. Forensics Secur. 11(5), 1039–1054 (2016)

    Article  Google Scholar 

  48. Zhang, F., et al.: Persistent fault analysis on block ciphers. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2018(3), 150–172 (2018)

    Article  Google Scholar 

  49. Zhang, F., et al.: Persistent fault attack in practice. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2020(2), 172–195 (2020)

    Article  Google Scholar 

  50. Zhao, X., Wang, T., Guo, S.: Fault-propagation pattern based DFA on SPN structure block ciphers using bitwise permutation, with application to PRESENT and printcipher (2011)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Indian Statistical Institute, Kolkata, 700108, India

    Anup Kumar Kundu & Mostafizar Rahman

  2. Department of Computer Science, University of Haifa, Haifa, Israel

    Shibam Ghosh

  3. de.ci.phe.red Lab, Department of Computer Science and Engineering, Indian Institute of Technology, Bhilai, 492015, India

    Dhiman Saha

Authors
  1. Anup Kumar Kundu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shibam Ghosh
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dhiman Saha
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Mostafizar Rahman
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Anup Kumar Kundu .

Editor information

Editors and Affiliations

  1. NTT Social Informatics Laboratories, Tokyo, Japan

    Mehdi Tibouchi

  2. Indiana University at Bloomington, Bloomington, IN, USA

    XiaoFeng Wang

Appendices

A Results on GIFT-128

The balanced bits from 5-round property is given below. Using a random nibble fault we get a total 80 balanced bits after 5 rounds. However the balanced bits are divided into two sets. If the active nibble belongs to \(\{N_0,...,N_{15}\}\) we get the following balanced bits

  • \(\mathcal {A}\) = 0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 16, 17, 18, 20, 21, 22, 24, 25, 28, 29, 32, 33, 34, 36, 37, 38, 40, 41, 44, 45, 48, 49, 50, 52, 53, 54, 56, 57, 60, 61, 64, 65, 66, 68, 69, 70, 72, 73, 76, 77, 80, 81, 82, 84, 85, 86, 88, 89, 92, 93, 96, 97, 98, 100, 101, 102, 104, 105, 108, 109, 112, 113, 114, 116, 117, 118, 120, 121, 124, 125.

If the active nibble belongs to \(\{N_{16},...,N_{31}\}\) we get the following balanced bits

  • \(\mathcal {B}\) = 0, 1, 4, 5, 8, 9, 10, 12, 13, 14, 16, 17, 20, 21, 24, 25, 26, 28, 29, 30, 32, 33, 36, 37, 40, 41, 42, 44, 45, 46, 48, 49, 52, 53, 56, 57, 58, 60, 61, 62, 64, 65, 68, 69, 72, 73, 74, 76, 77, 78, 80, 81, 84, 85, 88, 89, 90, 92, 93, 94, 96, 97, 100, 101, 104, 105, 106, 108, 109, 110, 112, 113, 116, 117, 120, 121, 122, 124, 125, 126.

While the intersection of these two sets contains the following 64 balanced bits

  • \(\mathcal {A} \cap \mathcal {B}\) = {0, 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32, 33, 36, 37, 40, 41, 44, 45, 48, 49, 52, 53, 56, 57, 60, 61, 64, 65, 68, 69, 72, 73, 76, 77, 80, 81, 84, 85, 88, 89, 92, 93, 96, 97, 100, 101, 104, 105, 108, 109, 112, 113, 116, 117, 120, 121, 124, 125 }.

Thus we have 64 balanced bits after 5 round in fault invariant setting, i.e., any random active nibble at the input results to 64 output bits. Moreover, input of each sbox in the 6-th round contains two balanced bits, namely the first and second input bit.

B Sbox Division Trail Algorithm

figure i

C PRESENT Partial Subkeys Recovery of the Last Two Rounds

Here we discuss partial recovery of the last two round keys. To recover the partial subkeys of the last two rounds we use our random nibble fault distinguisher for 4 and 5 rounds. For this we construct an active nibble at the input of \(R^{25}\) by injecting 15 faults. From Table 3, we can observe that all the 64 bits at \(R^{28}\) and the first 4 bits of \(R^{29}\) become balanced. Now take all possible key values of the nibbles \(N^{30}_j\) for \(j\in \{0, 4, 8, 12\}\) and partially decrypt the corresponding nibbles of the ciphertext. Due to the propagation of the division property, we get balanced bits at \(N^{29}_0\) (from Table 3). We take the xorsum of the partially decrypted ciphertexts and check for which key nibble values the xorsum at \(N^{29}_0\) becomes 0. We take those as possible key choice for the nibbles \(\{0, 4, 8, 12\}\) in \(R^{30}\) and proceed in the next step. Upto this point we get \(2^{12}\) key choices for the nibbles as we have 4 bit filters at \(R^{29}\). In the next step we take all the key values of the nibbles \(N^{29}_j\) for \(j \in \{0, \cdots , 3\}\) and partially decrypt one more round. In the output of \(R^{28}\) we check whether the xorsum of the decrypted ciphertexts becomes 0 or not. As 16 bits at \(R^{28}\) becomes balanced hence the key choices of the nibbles \(N^{30}_j\) for \(j\in \{0, 4, 8, 12\}\) and \(N^{29}_j\) for \(j \in \{0, \cdots , 3\}\) reduces to \(2^{12}\). Thus total 20 bit subkey of the last two rounds can be recovered using this attack. The algorithm for the last round key recovery of this attack is given in Appendix C.1 while the pictorial view of the full attack is given in Fig. 6 (red-colored bits are the balanced bits).

Fig. 6.
figure 6

Partial key recovery attack on PRESENT

Full size image

Complexity of the Attack: The data complexity for this case is \(2^{16}\) as we have used 16 plaintext-ciphertext pairs to recover the partial subkeys. In this case also instead of decrypting the whole ciphertext at once we partially decrypt the 0-th \(\mathcal{Q}\mathcal{R}\) group i.e. the nibbles \(N^{30}_j\) for \(j\in \{0, 4, 8, 12\}\) in the last round and \(N^{29}_j\) for \(j\in \{0, 1, 2, 3\}\) in the second last. In the last round we have 16 bit keys and 4 bit filters for this \(\mathcal{Q}\mathcal{R}\) group. Hence the number of keys that passes through the filter is \(2^{12}\). For each of the key in the last round we take all possible values in the second last round and check the zero-sum. Hence the complexity for this group is \(2^{12}\times 2^{16} = 2^{28}\) sbox inversions and the number of keys that passes through the filer is \(2^{12}\) for 0-th \(\mathcal{Q}\mathcal{R}\) group.

1.1 C.1 Last Round Key Recovery of PRESENT

figure j

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Kundu, A.K., Ghosh, S., Saha, D., Rahman, M. (2023). Divide and Rule: DiFA  - Division Property Based Fault Attacks on PRESENT and GIFT. In: Tibouchi, M., Wang, X. (eds) Applied Cryptography and Network Security. ACNS 2023. Lecture Notes in Computer Science, vol 13905. Springer, Cham. https://doi.org/10.1007/978-3-031-33488-7_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-33488-7_4

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-33487-0

  • Online ISBN: 978-3-031-33488-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation