Cryptology ePrint Archive: Report 2017/1252

Breakdown Resilience of Key Exchange Protocols and the Cases of NewHope and TLS 1.3

Jacqueline Brendel and Marc Fischlin and Felix GŁnther

Abstract: Broken cryptographic algorithms and hardness assumptions are a constant threat to real-world protocols. Prominent examples are hash functions for which collisions become known, or number-theoretic assumptions which are threatened by advances in quantum computing. Especially when it comes to key exchange protocols, the switch to quantum-resistant primitives has begun and aims to protect today's secrets against future developments, moving from common Diffie-Hellman-based solutions to Learning-With-Errors-based approaches. Remarkably, the authentication step in such protocols is usually still carried out with quantum-vulnerable signature schemes. The intuition here is that the adversary would need to break this protocol primitive today, without having quantum power yet. The question we address here is if this intuition is justified, and if so, if we can show this rigorously.

To this date there exists no security notion for key exchange protocols that could capture the scenario of breakdowns of arbitrary cryptographic primitives to argue security of prior sessions. In this work we introduce an extension to the common Bellare-Rogaway model that can provide security guarantees in what we call the breakdown scenario and we term the resulting security notion breakdown resilience. The model allows to make security claims even in case of unexpected failure of primitives in the protocol, may it be hash functions, signature schemes, key derivation functions, etc. To validate the proposed security model with respect to real-world protocols we show that breakdown resilience for certain primitives is achieved by both an authenticated variant of the recently introduced post-quantum secure key exchange protocol NewHope (Alkim et al., USENIX Security 2016), as well as by TLS 1.3, which is currently being developed by the Internet Engineering Task Force.

Category / Keywords: cryptographic protocols / key exchange, hybrid key exchange

Date: received 28 Dec 2017

Contact author: jacqueline brendel at cryptoplexity de

Available format(s): PDF | BibTeX Citation

Version: 20171230:183039 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]