Paper 2017/1185

Complete Attack on RLWE Key Exchange with reused keys, without Signal Leakage

Jintai Ding, Scott Fluhrer, and Saraswathy RV

Abstract

Key Exchange (KE) from RLWE (Ring-Learning with Errors) is a potential alternative to Diffie-Hellman (DH) in a post quantum setting. Key leakage with RLWE key exchange protocols in the context of key reuse has already been pointed out in previous work. The initial attack described by Fluhrer is designed in such a way that it only works on Peikert's KE protocol and its variants that derives the shared secret from the most significant bits of the approximately equal keys computed by both parties. It does not work on Ding's key exchange that uses the least significant bits to derive a shared key. The Signal leakage attack relies on changes in the signal sent by the responder reusing his key, in a sequence of key exchange sessions initiated by an attacker with a malformed key. A possible defense against this attack would be to require the initiator of a key exchange to send the signal, which is the one pass case of the KE protocol. In this work, we describe a new attack on Ding's one pass case without relying on the signal function output but using only the information of whether the final key of both parties agree. We also use LLL reduction to create the adversary's keys in such a way that the party being compromised cannot identify the attack in trivial ways. This completes the series of attacks on RLWE key exchange with key reuse for all variants in both cases of the initiator and responder sending the signal. Moreover, we show that the previous Signal leakage attack can be made more efficient with fewer queries and how it can be extended to Peikert's key exchange, which was used in the BCNS implementation and integrated with TLS and a variant used in the New Hope implementation.

Note: modified abstract to remove cite commands

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Major revision. ACISP Proceedings 2018
Keywords
RLWEkey exchangepost quantumkey reuseactive attacks.
Contact author(s)
jintai ding @ gmail com
History
2018-04-25: revised
2017-12-12: received
See all versions
Short URL
https://ia.cr/2017/1185
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1185,
      author = {Jintai Ding and Scott Fluhrer and Saraswathy RV},
      title = {Complete Attack on RLWE Key Exchange with reused keys, without Signal Leakage},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1185},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1185}},
      url = {https://eprint.iacr.org/2017/1185}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.