Loop Aborts Strike Back: Defeating Fault Countermeasures in Lattice Signatures with ILP
At SAC 2016, Espitau et al. presented a loop-abort fault attack against lattice-based signature schemes following the Fiat–Shamir with aborts paradigm. Their attack recovered the signing key by injecting faults in the sampling of the commitment vector (also called masking vector) y, leaving its coe...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2023-08-01
|
| Series: | Transactions on Cryptographic Hardware and Embedded Systems |
| Subjects: | |
| Online Access: | https://tches.iacr.org/index.php/TCHES/article/view/11170 |
| _version_ | 1827845403159035904 |
|---|---|
| author | Vincent Quentin Ulitzsch Soundes Marzougui Alexis Bagia Mehdi Tibouchi Jean-Pierre Seifert |
| author_facet | Vincent Quentin Ulitzsch Soundes Marzougui Alexis Bagia Mehdi Tibouchi Jean-Pierre Seifert |
| author_sort | Vincent Quentin Ulitzsch |
| collection | DOAJ |
| description |
At SAC 2016, Espitau et al. presented a loop-abort fault attack against lattice-based signature schemes following the Fiat–Shamir with aborts paradigm. Their attack recovered the signing key by injecting faults in the sampling of the commitment vector (also called masking vector) y, leaving its coefficients at their initial zero value. As possible countermeasures, they proposed to carry out the sampling of the coefficients of y in shuffled order, or to ensure that the masking polynomials in y are not of low degree. In this paper, we show that both of these countermeasures are insufficient. We demonstrate a new loop-abort fault injection attack against Fiat–Shamir with aborts lattice-based signatures that can recover the secret key from faulty signatures even when the proposed countermeasures are implemented. The key idea of our attack is that faulted signatures give rise to a noisy linear system of equations, which can be solved using integer linear programming. We present an integer linear program that recovers the secret key efficiently in practice, and validate the efficacy of our attack by conducting a practical end-to-end attack against a shuffled version of the Dilithium reference implementation, mounted on an ARM Cortex M4. We achieve a full (equivalent) key recovery in under 3 minutes total execution time (including signature generation), using only 5 faulted signatures. In addition, we conduct extensive theoretical simulations of the attack against Dilithium. We find that our method can achieve key recovery in under 5 minutes given a (sufficiently large) set of signatures where just one of the coefficients of y is zeroed out (or left at its initial value of zero). Furthermore, we find that our attack works against all security levels of Dilithium. Our attack shows that protecting Fiat–Shamir with aborts lattice-based signatures against fault injection attacks cannot be achieved using the simple countermeasures proposed by Espitau et al. and likely requires significantly more expensive countermeasures.
|
| first_indexed | 2024-03-12T08:56:09Z |
| format | Article |
| id | doaj.art-cb59a30ade1e4f2b8a025a00e32e2561 |
| institution | Directory Open Access Journal |
| issn | 2569-2925 |
| language | English |
| last_indexed | 2024-03-12T08:56:09Z |
| publishDate | 2023-08-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | Transactions on Cryptographic Hardware and Embedded Systems |
| spelling | doaj.art-cb59a30ade1e4f2b8a025a00e32e25612023-09-02T16:01:05ZengRuhr-Universität BochumTransactions on Cryptographic Hardware and Embedded Systems2569-29252023-08-012023410.46586/tches.v2023.i4.367-392Loop Aborts Strike Back: Defeating Fault Countermeasures in Lattice Signatures with ILPVincent Quentin Ulitzsch0Soundes Marzougui1Alexis Bagia2Mehdi Tibouchi3Jean-Pierre Seifert4Technical University Berlin, Berlin, GermanyTechnical University Berlin, Berlin, Germany; STMicroelectronics, Diegem, BelgiumTechnical University Berlin, Berlin, GermanyNTT Social Informatics Laboratories, Tokyo, JapanTechnical University Berlin, Berlin, Germany; Fraunhofer Institute for Secure Information Technology, Darmstadt, Germany At SAC 2016, Espitau et al. presented a loop-abort fault attack against lattice-based signature schemes following the Fiat–Shamir with aborts paradigm. Their attack recovered the signing key by injecting faults in the sampling of the commitment vector (also called masking vector) y, leaving its coefficients at their initial zero value. As possible countermeasures, they proposed to carry out the sampling of the coefficients of y in shuffled order, or to ensure that the masking polynomials in y are not of low degree. In this paper, we show that both of these countermeasures are insufficient. We demonstrate a new loop-abort fault injection attack against Fiat–Shamir with aborts lattice-based signatures that can recover the secret key from faulty signatures even when the proposed countermeasures are implemented. The key idea of our attack is that faulted signatures give rise to a noisy linear system of equations, which can be solved using integer linear programming. We present an integer linear program that recovers the secret key efficiently in practice, and validate the efficacy of our attack by conducting a practical end-to-end attack against a shuffled version of the Dilithium reference implementation, mounted on an ARM Cortex M4. We achieve a full (equivalent) key recovery in under 3 minutes total execution time (including signature generation), using only 5 faulted signatures. In addition, we conduct extensive theoretical simulations of the attack against Dilithium. We find that our method can achieve key recovery in under 5 minutes given a (sufficiently large) set of signatures where just one of the coefficients of y is zeroed out (or left at its initial value of zero). Furthermore, we find that our attack works against all security levels of Dilithium. Our attack shows that protecting Fiat–Shamir with aborts lattice-based signatures against fault injection attacks cannot be achieved using the simple countermeasures proposed by Espitau et al. and likely requires significantly more expensive countermeasures. https://tches.iacr.org/index.php/TCHES/article/view/11170Fault analysisFiat–Shamir with abortsDilithiumSide-channel attacksInteger linear programming |
| spellingShingle | Vincent Quentin Ulitzsch Soundes Marzougui Alexis Bagia Mehdi Tibouchi Jean-Pierre Seifert Loop Aborts Strike Back: Defeating Fault Countermeasures in Lattice Signatures with ILP Transactions on Cryptographic Hardware and Embedded Systems Fault analysis Fiat–Shamir with aborts Dilithium Side-channel attacks Integer linear programming |
| title | Loop Aborts Strike Back: Defeating Fault Countermeasures in Lattice Signatures with ILP |
| title_full | Loop Aborts Strike Back: Defeating Fault Countermeasures in Lattice Signatures with ILP |
| title_fullStr | Loop Aborts Strike Back: Defeating Fault Countermeasures in Lattice Signatures with ILP |
| title_full_unstemmed | Loop Aborts Strike Back: Defeating Fault Countermeasures in Lattice Signatures with ILP |
| title_short | Loop Aborts Strike Back: Defeating Fault Countermeasures in Lattice Signatures with ILP |
| title_sort | loop aborts strike back defeating fault countermeasures in lattice signatures with ilp |
| topic | Fault analysis Fiat–Shamir with aborts Dilithium Side-channel attacks Integer linear programming |
| url | https://tches.iacr.org/index.php/TCHES/article/view/11170 |
| work_keys_str_mv | AT vincentquentinulitzsch loopabortsstrikebackdefeatingfaultcountermeasuresinlatticesignatureswithilp AT soundesmarzougui loopabortsstrikebackdefeatingfaultcountermeasuresinlatticesignatureswithilp AT alexisbagia loopabortsstrikebackdefeatingfaultcountermeasuresinlatticesignatureswithilp AT mehditibouchi loopabortsstrikebackdefeatingfaultcountermeasuresinlatticesignatureswithilp AT jeanpierreseifert loopabortsstrikebackdefeatingfaultcountermeasuresinlatticesignatureswithilp |