Paper 2017/1252

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

Jacqueline Brendel, Marc Fischlin, and Felix Günther


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 number-theoretic assumptions, hash functions, signature schemes, key derivation functions, etc. We then apply our security model to analyze two real-world protocols, showing that breakdown resilience for certain primitives is achieved by both an authenticated variant of the post-quantum secure key encapsulation mechanism NewHope (Alkim et al.) which is a second round candidate in the Post Quantum Cryptography standardization process by NIST, as well as by TLS 1.3, which has recently been standardized as RFC 8446 by the Internet Engineering Task Force. Finally, we analyze the security of a generic hybrid key exchange protocol, formally showing how such designs ensure resilience against breakdowns of one of their key exchange components.

Note: ESORICS 2019 publication

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.24th European Symposium on Research in Computer Security (ESORICS 2019)
key exchangebreakdown resiliencehybrid key exchangeNewHopeTLS 1.3
Contact author(s)
jacqueline brendel @ cryptoplexity de
2019-09-16: last of 3 revisions
2017-12-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jacqueline Brendel and Marc Fischlin and Felix Günther},
      title = {Breakdown Resilience of Key Exchange Protocols: NewHope, TLS 1.3, and Hybrids},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1252},
      year = {2017},
      doi = {10.1007/978-3-030-29962-0_25},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.