Ph.D. Defense of Dissertation Announcement

Provable Security Support for Kerberos (and Beyond)

Virendra Kumar
School of Computer Science
College of Computing
Georgia Institute of Technology

When: Friday, April 27th at 1:00pm
Where: KACB #3126

Committee:

• Dr. Alexandra Boldyreva (Advisor, School of Computer Science, Georgia Institute of Technology)
• Dr. Mustaque Ahamad (School of Computer Science, Georgia Institute of Technology)
• Dr. Vladimir Kolesnikov (Cryptography and Security Research, Bell Labs, Alcatel-Lucent)
• Dr. Christopher J. Peikert (School of Computer Science, Georgia Institute of Technology)
• Dr. Patrick Traynor (School of Computer Science, Georgia Institute of Technology)

Summary:
Kerberos is a widely-deployed network authentication protocol that is being considered for standardization. Like other standard protocols, Kerberos is no exception to security flaws and weaknesses, as has been demonstrated in several prior works. Provable security guarantees go a long way in restoring users' faith, thus making a protocol an even stronger candidate for standards. In this thesis, our goal was thus to provide provable security support for Kerberos. Our contributions are three-fold:

1. We first look at the symmetric encryption schemes employed in the current version 5 of Kerberos. Several recent results have analyzed a significant part of Kerberos v.5 using formal-methods-based approaches, which are meaningful only if the underlying encryption schemes satisfy strong cryptographic  notions of privacy and authenticity. However, to our knowledge these schemes were never analyzed and proven to satisfy such notions. This thesis aims to bridge this gap. Our provable security analyses confirm that some of the encryption scheme options in Kerberos v.5 already provide privacy and authenticity, and for the remaining we suggest slight modifications for the same.
2. We next turn our attention to the ways in which the keys and other random strings needed in cryptographic schemes employed by Kerberos are generated. Randomness needs to be carefully generated for the provable security guarantees to hold. We propose an efficient pseudorandom generator (PRG) based on hash functions. The security of our PRG relies on exponential collision-resistance and regularity of the underlying hash function. Our PRG can be used to generate various strings, like session keys, sequence numbers, confounders, etc., which are all {\em suggested} to be generated randomly in the Kerberos v.5 specification, but no  algorithms are mentioned. Each of the above strings are required to satisfy different properties, all of which are trivially satisfied by the pseudorandom strings output by a PRG.
3. Finally, we look at the problem of revocation associated with two relatively new types of encryption schemes: identity-based encryption (IBE) and attribute-based encryption (ABE). While the Kerberos protocol relies primarily on symmetric-key primitives, a recently proposed functionality added to Kerberos v.5 known as PKINIT facilitates public-key authentication by the use of public-key cryptography. And it seems likely that future revisions of the protocol might incorporate IBEs and ABEs for new functionalities due to their attractive features. Any setting, public-key, identity-based, or attribute-based, must provide a means to revoke users from the system. However, unlike public-key encryption, there has been little prior work on studying the revocation mechanisms in an IBE or ABE. We propose new primitives and their efficient and provably secure instantiations, focusing on the revocation problem.

We would like to note that even though all the results presented in this thesis are motivated mainly by Kerberos, only the first bullet above has a direct impact on Kerberos. Our PRG is the most efficient construction among theoretical PRGs, but it may still not be efficient enough to be directly usable in practical protocols. And our results and techniques for revocation in IBE and ABE have found much wider applications in information security, such as mobile social networks, cloud-based secure health records, data outsourcing systems, vehicular ad-hoc networks, etc.