Minerva: The curse of ECDSA nonces Systematic analysis of lattice attacks on noisy leakage of bit-length of ECDSA nonces
We present our discovery of a group of side-channel vulnerabilities in implementations of the ECDSA signature algorithm in a widely used Atmel AT90SC FIPS 140-2 certified smartcard chip and five cryptographic libraries (libgcrypt, wolfSSL, MatrixSSL, SunEC/OpenJDK/Oracle JDK, Crypto++). Vulnerable i...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2020-08-01
|
| Series: | Transactions on Cryptographic Hardware and Embedded Systems |
| Subjects: | |
| Online Access: | https://tches.iacr.org/index.php/TCHES/article/view/8684 |
| _version_ | 1819031997773774848 |
|---|---|
| author | Jan Jancar Vladimir Sedlacek Petr Svenda Marek Sys |
| author_facet | Jan Jancar Vladimir Sedlacek Petr Svenda Marek Sys |
| author_sort | Jan Jancar |
| collection | DOAJ |
| description | We present our discovery of a group of side-channel vulnerabilities in implementations of the ECDSA signature algorithm in a widely used Atmel AT90SC FIPS 140-2 certified smartcard chip and five cryptographic libraries (libgcrypt, wolfSSL, MatrixSSL, SunEC/OpenJDK/Oracle JDK, Crypto++). Vulnerable implementations leak the bit-length of the scalar used in scalar multiplication via timing. Using leaked bit-length, we mount a lattice attack on a 256-bit curve, after observing enough signing operations. We propose two new methods to recover the full private key requiring just 500 signatures for simulated leakage data, 1200 for real cryptographic library data, and 2100 for smartcard data. The number of signatures needed for a successful attack depends on the chosen method and its parameters as well as on the noise profile, influenced by the type of leakage and used computation platform. We use the set of vulnerabilities reported in this paper, together with the recently published TPM-FAIL vulnerability [MSE+20] as a basis for real-world benchmark datasets to systematically compare our newly proposed methods and all previously published applicable lattice-based key recovery methods. The resulting exhaustive comparison highlights the methods’ sensitivity to its proper parametrization and demonstrates that our methods are more efficient in most cases. For the TPM-FAIL dataset, we decreased the number of required signatures from approximately 40 000 to mere 900. |
| first_indexed | 2024-12-21T06:54:56Z |
| format | Article |
| id | doaj.art-9f475132a461455faa5bb5553140c15c |
| institution | Directory Open Access Journal |
| issn | 2569-2925 |
| language | English |
| last_indexed | 2024-12-21T06:54:56Z |
| publishDate | 2020-08-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | Transactions on Cryptographic Hardware and Embedded Systems |
| spelling | doaj.art-9f475132a461455faa5bb5553140c15c2022-12-21T19:12:22ZengRuhr-Universität BochumTransactions on Cryptographic Hardware and Embedded Systems2569-29252020-08-012020410.13154/tches.v2020.i4.281-308Minerva: The curse of ECDSA nonces Systematic analysis of lattice attacks on noisy leakage of bit-length of ECDSA noncesJan Jancar0Vladimir Sedlacek1Petr Svenda2Marek Sys3Masaryk University, Brno, CzechiaMasaryk University, Brno, Czechia; Ca’ Foscari University of Venice, ItalyMasaryk University, Brno, CzechiaMasaryk University, Brno, CzechiaWe present our discovery of a group of side-channel vulnerabilities in implementations of the ECDSA signature algorithm in a widely used Atmel AT90SC FIPS 140-2 certified smartcard chip and five cryptographic libraries (libgcrypt, wolfSSL, MatrixSSL, SunEC/OpenJDK/Oracle JDK, Crypto++). Vulnerable implementations leak the bit-length of the scalar used in scalar multiplication via timing. Using leaked bit-length, we mount a lattice attack on a 256-bit curve, after observing enough signing operations. We propose two new methods to recover the full private key requiring just 500 signatures for simulated leakage data, 1200 for real cryptographic library data, and 2100 for smartcard data. The number of signatures needed for a successful attack depends on the chosen method and its parameters as well as on the noise profile, influenced by the type of leakage and used computation platform. We use the set of vulnerabilities reported in this paper, together with the recently published TPM-FAIL vulnerability [MSE+20] as a basis for real-world benchmark datasets to systematically compare our newly proposed methods and all previously published applicable lattice-based key recovery methods. The resulting exhaustive comparison highlights the methods’ sensitivity to its proper parametrization and demonstrates that our methods are more efficient in most cases. For the TPM-FAIL dataset, we decreased the number of required signatures from approximately 40 000 to mere 900.https://tches.iacr.org/index.php/TCHES/article/view/8684ECDSAHidden Number Problemside-channel attacklattice attacksmartcards |
| spellingShingle | Jan Jancar Vladimir Sedlacek Petr Svenda Marek Sys Minerva: The curse of ECDSA nonces Systematic analysis of lattice attacks on noisy leakage of bit-length of ECDSA nonces Transactions on Cryptographic Hardware and Embedded Systems ECDSA Hidden Number Problem side-channel attack lattice attack smartcards |
| title | Minerva: The curse of ECDSA nonces Systematic analysis of lattice attacks on noisy leakage of bit-length of ECDSA nonces |
| title_full | Minerva: The curse of ECDSA nonces Systematic analysis of lattice attacks on noisy leakage of bit-length of ECDSA nonces |
| title_fullStr | Minerva: The curse of ECDSA nonces Systematic analysis of lattice attacks on noisy leakage of bit-length of ECDSA nonces |
| title_full_unstemmed | Minerva: The curse of ECDSA nonces Systematic analysis of lattice attacks on noisy leakage of bit-length of ECDSA nonces |
| title_short | Minerva: The curse of ECDSA nonces Systematic analysis of lattice attacks on noisy leakage of bit-length of ECDSA nonces |
| title_sort | minerva the curse of ecdsa nonces systematic analysis of lattice attacks on noisy leakage of bit length of ecdsa nonces |
| topic | ECDSA Hidden Number Problem side-channel attack lattice attack smartcards |
| url | https://tches.iacr.org/index.php/TCHES/article/view/8684 |
| work_keys_str_mv | AT janjancar minervathecurseofecdsanoncessystematicanalysisoflatticeattacksonnoisyleakageofbitlengthofecdsanonces AT vladimirsedlacek minervathecurseofecdsanoncessystematicanalysisoflatticeattacksonnoisyleakageofbitlengthofecdsanonces AT petrsvenda minervathecurseofecdsanoncessystematicanalysisoflatticeattacksonnoisyleakageofbitlengthofecdsanonces AT mareksys minervathecurseofecdsanoncessystematicanalysisoflatticeattacksonnoisyleakageofbitlengthofecdsanonces |