Guessing Bits: Improved Lattice Attacks on (EC)DSA with Nonce Leakage

The lattice reduction attack on (EC)DSA (and other Schnorr-like signature schemes) with partially known nonces, originally due to Howgrave-Graham and Smart, has been at the core of many concrete cryptanalytic works, side-channel based or otherwise, in the past 20 years. The attack itself has seen l...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Chao Sun, Thomas Espitau, Mehdi Tibouchi, Masayuki Abe
Formato:	article
Lenguaje:	EN
Publicado:	Ruhr-Universität Bochum 2021
Materias:	ECDSA Lattice Attacks Hidden Number Problem Success-Time Trade-Off Cryptanalysis Computer engineering. Computer hardware TK7885-7895 Information technology T58.5-58.64
Acceso en línea:	https://doaj.org/article/573e14eacdef43528ea26eb8266d6124
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:573e14eacdef43528ea26eb8266d6124
record_format	dspace
spelling	oai:doaj.org-article:573e14eacdef43528ea26eb8266d61242021-11-19T14:36:08ZGuessing Bits: Improved Lattice Attacks on (EC)DSA with Nonce Leakage10.46586/tches.v2022.i1.391-4132569-2925https://doaj.org/article/573e14eacdef43528ea26eb8266d61242021-11-01T00:00:00Zhttps://tches.iacr.org/index.php/TCHES/article/view/9302https://doaj.org/toc/2569-2925 The lattice reduction attack on (EC)DSA (and other Schnorr-like signature schemes) with partially known nonces, originally due to Howgrave-Graham and Smart, has been at the core of many concrete cryptanalytic works, side-channel based or otherwise, in the past 20 years. The attack itself has seen limited development, however: improved analyses have been carried out, and the use of stronger lattice reduction algorithms has pushed the range of practically vulnerable parameters further, but the lattice construction based on the signatures and known nonce bits remain the same. In this paper, we propose a new idea to improve the attack based on the same data in exchange for additional computation: carry out an exhaustive search on some bits of the secret key. This turns the problem from a single bounded distance decoding (BDD) instance in a certain lattice to multiple BDD instances in a fixed lattice of larger volume but with the same bound (making the BDD problem substantially easier). Furthermore, the fact that the lattice is fixed lets us use batch/preprocessing variants of BDD solvers that are far more efficient than repeated lattice reductions on non-preprocessed lattices of the same size. As a result, our analysis suggests that our technique is competitive or outperforms the state of the art for parameter ranges corresponding to the limit of what is achievable using lattice attacks so far (around 2-bit leakage on 160-bit groups, or 3-bit leakage on 256-bit groups). We also show that variants of this idea can also be applied to bits of the nonces (leading to a similar improvement) or to filtering signature data (leading to a data-time trade-off for the lattice attack). Finally, we use our technique to obtain an improved exploitation of the TPM–FAIL dataset similar to what was achieved in the Minerva attack. Chao SunThomas EspitauMehdi TibouchiMasayuki AbeRuhr-Universität BochumarticleECDSALattice AttacksHidden Number ProblemSuccess-Time Trade-OffCryptanalysisComputer engineering. Computer hardwareTK7885-7895Information technologyT58.5-58.64ENTransactions on Cryptographic Hardware and Embedded Systems, Vol 2022, Iss 1 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	ECDSA Lattice Attacks Hidden Number Problem Success-Time Trade-Off Cryptanalysis Computer engineering. Computer hardware TK7885-7895 Information technology T58.5-58.64
spellingShingle	ECDSA Lattice Attacks Hidden Number Problem Success-Time Trade-Off Cryptanalysis Computer engineering. Computer hardware TK7885-7895 Information technology T58.5-58.64 Chao Sun Thomas Espitau Mehdi Tibouchi Masayuki Abe Guessing Bits: Improved Lattice Attacks on (EC)DSA with Nonce Leakage
description	The lattice reduction attack on (EC)DSA (and other Schnorr-like signature schemes) with partially known nonces, originally due to Howgrave-Graham and Smart, has been at the core of many concrete cryptanalytic works, side-channel based or otherwise, in the past 20 years. The attack itself has seen limited development, however: improved analyses have been carried out, and the use of stronger lattice reduction algorithms has pushed the range of practically vulnerable parameters further, but the lattice construction based on the signatures and known nonce bits remain the same. In this paper, we propose a new idea to improve the attack based on the same data in exchange for additional computation: carry out an exhaustive search on some bits of the secret key. This turns the problem from a single bounded distance decoding (BDD) instance in a certain lattice to multiple BDD instances in a fixed lattice of larger volume but with the same bound (making the BDD problem substantially easier). Furthermore, the fact that the lattice is fixed lets us use batch/preprocessing variants of BDD solvers that are far more efficient than repeated lattice reductions on non-preprocessed lattices of the same size. As a result, our analysis suggests that our technique is competitive or outperforms the state of the art for parameter ranges corresponding to the limit of what is achievable using lattice attacks so far (around 2-bit leakage on 160-bit groups, or 3-bit leakage on 256-bit groups). We also show that variants of this idea can also be applied to bits of the nonces (leading to a similar improvement) or to filtering signature data (leading to a data-time trade-off for the lattice attack). Finally, we use our technique to obtain an improved exploitation of the TPM–FAIL dataset similar to what was achieved in the Minerva attack.
format	article
author	Chao Sun Thomas Espitau Mehdi Tibouchi Masayuki Abe
author_facet	Chao Sun Thomas Espitau Mehdi Tibouchi Masayuki Abe
author_sort	Chao Sun
title	Guessing Bits: Improved Lattice Attacks on (EC)DSA with Nonce Leakage
title_short	Guessing Bits: Improved Lattice Attacks on (EC)DSA with Nonce Leakage
title_full	Guessing Bits: Improved Lattice Attacks on (EC)DSA with Nonce Leakage
title_fullStr	Guessing Bits: Improved Lattice Attacks on (EC)DSA with Nonce Leakage
title_full_unstemmed	Guessing Bits: Improved Lattice Attacks on (EC)DSA with Nonce Leakage
title_sort	guessing bits: improved lattice attacks on (ec)dsa with nonce leakage
publisher	Ruhr-Universität Bochum
publishDate	2021
url	https://doaj.org/article/573e14eacdef43528ea26eb8266d6124
work_keys_str_mv	AT chaosun guessingbitsimprovedlatticeattacksonecdsawithnonceleakage AT thomasespitau guessingbitsimprovedlatticeattacksonecdsawithnonceleakage AT mehditibouchi guessingbitsimprovedlatticeattacksonecdsawithnonceleakage AT masayukiabe guessingbitsimprovedlatticeattacksonecdsawithnonceleakage
_version_	1718420070450855936

Guessing Bits: Improved Lattice Attacks on (EC)DSA with Nonce Leakage

Ejemplares similares