Paper 2017/1185
Complete Attack on RLWE Key Exchange with reused keys, without Signal Leakage
Jintai Ding and 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 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 by requiring the initiator of the key exchange to send the signal, which is the one pass case of the KE protocol. The initial attack described bu 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 the Ding’s key exchange that uses the least significant bits to derive a shared key. 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 make the adversary’s keys random looking to the party being compromised. 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. This work shows that when a party fixes their public key for a long term, the protocol can always be broken by a malicious user. 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)
- Publication info
- Preprint.
- Keywords
- RLWEkey exchangepost quantumkey reuseactive attacks.
- Contact author(s)
- jintai ding @ gmail com;rvsaras86 @ gmail com
- History
- 2018-04-25: revised
- 2017-12-12: received
- See all versions
- Short URL
- https://ia.cr/2017/1185
- License
-
CC BY