Douglas Stebila

Improved attacks against key reuse in learning with errors key exchange

Noisy periodic binary signal, highlighting concentration of noise around a boundary

Abstract

Basic key exchange protocols built from the learning with errors (LWE) assumption are insecure if secret keys are reused in the face of active attackers. One example of this is Fluhrer's attack on the Ding, Xie, and Lin (DXL) LWE key exchange protocol, which exploits leakage from the signal function for error correction. Protocols aiming to achieve security against active attackers generally use one of two techniques: demonstrating well-formed keyshares using re-encryption like in the Fujisaki–Okamoto transform; or directly combining multiple LWE values, similar to MQV-style Diffie–Hellman-based protocols.

In this work, we demonstrate improved and new attacks exploiting key reuse in several LWE-based key exchange protocols. First, we show how to greatly reduce the number of samples required to carry out Fluhrer's attack and reconstruct the secret period of a noisy square waveform, speeding up the attack on DXL key exchange by a factor of over 200. We show how to adapt this to attack a protocol of Ding, Branco, and Schmitt (DBS) designed to be secure with key reuse, breaking the claimed 128-bit security level in under a minute. We also apply our technique to a second authenticated key exchange protocol of DBS that uses an additive MQV design, although in this case our attack makes use of ephemeral key compromise powers of the eCK security model, which was not in scope of the claimed BR-model security proof. Our results show that building secure authenticated key exchange protocols directly from LWE remains a challenging and mostly open problem.

Keywords: learning with errors, key exchange, key reuse

Reference

Nina Bindel, Douglas Stebila, Shannon Veitch. Improved attacks against key reuse in learning with errors key exchange. In Patrick Longa, Carla Ràfols, editors, Proc. 7th International Conference on Cryptology and Information Security in Latin America (LATINCRYPT) 2021, LNCS, vol. 12912, pp. 168-188. Springer, October 2021. © Springer.

Download

Code

• https://git.uwaterloo.ca/ssveitch/improved-key-reuse

BibTeX

@inproceedings{LATINCRYPT:BinSteVei21,
 	Author = {Nina Bindel and Douglas Stebila and Shannon Veitch},
 	Booktitle = {Proc. 7th International Conference on Cryptology and Information Security in Latin America (LATINCRYPT) 2021},
 	Editor = {Patrick Longa and Carla R{\` a}fols},
 	Month = {October},
 	Pages = {168--188},
 	Publisher = {Springer},
 	Series = {LNCS},
 	Title = {Improved attacks against key reuse in learning with errors key exchange},
 	Volume = {12912},
 	Year = {2021}
 }

Funding

• Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery grant RGPIN-2016-05146
• NSERC Discovery Accelerator Supplement grant RGPIN-2016-05146
• This work benefited from the use of the CrySP RIPPLE Facility at the University of Waterloo
• This work was supported by the University of Waterloo Institute for Quantum Computing; IQC is supported in part by the Government of Canada and the Province of Ontario