Paper 2017/1252

Breakdown Resilience of Key Exchange Protocols: NewHope, TLS 1.3, and Hybrids

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, often via intermediate hybrid designs. 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 or even ongoing and future sessions. In this work we extend the common Bellare–Rogaway model to capture breakdown resilience of key exchange protocols. Our extended model allows us to study security of a protocol even in case of unexpected failure of employed primitives, may it be hash functions, signature schemes, key derivation functions, etc. We then apply our security model to analyze two real-world protocols, showing that resilience breakdown resilience for certain primitives is achieved by both an authenticated variant of the post-quantum secure key exchange protocol NewHope (Alkim et al., USENIX Security 2016), as well as by TLS 1.3, which has recently been standardized as RFC 8446 by the Internet Engineering Task Force. Furthermore, we provide a security analysis of a generic hybrid key exchange protocol, where one of the key exchange components may become insecure. This demonstrates the utility of our stronger notion for such designs.

Note: editorial revisions; updated NewHope to NIST PQ Cryptography standardization candidate