A reduction-based proof for authentication and session key security in 3-party Kerberos

The 3-party form of Kerberos v5 protocol


Kerberos is one of the earliest network security protocols, providing authentication between clients and servers with the assistance of trusted servers. It remains widely used, notably as the default authentication protocol in Microsoft Active Directory (thus shipped with every major operating system), and is the ancestor of modern single sign-on protocols like OAuth and OpenID Connect.

There have been many analyses of Kerberos in the symbolic (Dolev–Yao) model, which is more amenable to computer-aided verification tools than the computational model, but also idealizes messages and cryptographic primitives more. Reduction-based proofs in the computational model can provide assurance against a richer class of adversaries, and proofs with concrete probability analyses help in picking security parameters, but Kerberos has had no such analyses to date.

We give a reduction-based security proof of Kerberos authentication and key establishment, focusing on the mandatory 3-party mode. We show that it is a secure authentication protocol under standard assumptions on its encryption scheme; our results can be lifted to apply to quantum adversaries as well.

As has been the case for other real-world authenticated key exchange (AKE) protocols, the standard AKE security notion of session key indistinguishability cannot be proven for Kerberos since the session key is used in the protocol itself, breaking indistinguishability. We provide two positive results despite this: we show that the standardized but optional sub-session mode of Kerberos does yield secure session keys, and that the hash of the main session key is also a secure session key under Krawczyk's generalization of the authenticated and confidential channel establishment (ACCE) model.

Keywords: Kerberos, authenticated key exchange


Jörg Schwenk, Douglas Stebila. A reduction-based proof for authentication and session key security in 3-party Kerberos. International Journal of Applied Cryptography. April 2020. To appear. © Inderscience.




This research was supported by:
  • Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery grant RGPIN-2016-05146
  • NSERC Discovery Accelerator Supplement grant RGPIN-2016-05146