Orpheus' Lyre
puts Kerberos
to Sleep!
On Tuesday, 11 July 2017, at 1PM New York time, Microsoft, and various Linux distros and BSDs, released patches for Orpheus' Lyre.
We will be updating this blog post with more details as time passes. This vulnerability is quite serious, and we wish to give users a chance to apply patches before we discuss the full scope of the vulnerability. We urge users to apply and deploy patches forthwith and without delay.
In Greek mythology, Orpheus was a bard who put Cerberus to sleep with his music, and was then able to bypass Hades' guard. This vulnerability defeats Kerberos in a critical way permitting a bypass of mutual authentication. Thus we name it after Orpheus' Lyre much as Kerberos is named after Cerberus.
Kerberos is a venerable cryptographic authentication protocol named after the mythological three-headed dog guardian of Hades, Cerberus. It is as old as x.509/PKIX, and, really, the Needham-Schroeder symmetric key dual of public key infrastructures. Kerberos is very widely used, particularly in sites using Microsoft Active Directory, though often users are unaware of it.
Kerberos was invented in the mid 1980s, with the first production version, Kerberos IV, deployed at MIT in September 1986. x.509 is only slightly younger, having been issued on July 3rd, 1988. Today we'll be talking about Kerberos V5 (RFC4120), which dates to the early 1990s. The symmetric cryptography version of the Needham-Schroeder protocol was published in 1978, and is still sound when used with modern cryptographic techniques, such as Authenticated Encryption.
Like all old protocols, the Kerberos V5 specification incorporates some original sins that have caused security problems. Its not actually a broken protocol, but it's all too easy to make subtle but disastrous implementation mistakes. Orpheus' Lyre is a serious vulnerability in some implementations of the Kerberos protocol.
The original cryptographic sin of Kerberos is an abundance of unauthenticated plaintext in the protocol. That is, portions of Kerberos messages are neither encrypted nor integrity-protected in some direct cryptographic manner. In some cases that sin is likely born of premature optimization -- the mother of many bugs. Kerberos can be secure despite this surfeit of unauthenticated plaintext, but it requires extreme care by implementors to get every detail right so as to authenticate said plaintext. Orpheus' Lyre happened because of one instance of unauthenticated plaintext, and the ease with which the specific plaintext could accidentally be used instead of an authenticated copy of the same text.
The unauthenticated plaintext issue at hand is this: the Ticket issued in KDC responses. This is a well-known weakness that is mitigated by the metadata in the encrypted portion of a KDC response, and proper use of it. Well, in this case, a two-line bug in several independently developed implementations of Kerberos, caused that metadata to be taken from the unauthenticated plaintext (the Ticket) rather than the authenticated and encrypted KDC response.
This vulnerability can be exploited in a number of ways, and in some cases it can lead to remote credential theft, and thus remote privilege escalation, largely defeating Kerberos. Attackers do have to be on-path (logically, at least) between the victim client and a KDC.
Readers who are not familiar with Kerberos should nonetheless already understand from the above that Orpheus' Lyre is a grave vulnerability, and the gist of it. But readers probably want a more detailed explanation.
Kerberos is a lot like a PKI, but instead of public key cryptography, with certification authorities (CAs) and certificates, Kerberos has a trusted third-party, the Key Distribution Centers (KDCs) that issue short-lived tickets. These tickets are encrypted using a symmetric key known to the relying party (usually a service) and the KDC for that party's administrative "realm". The encrypted portion of a Kerberos ticket bears the name of the client principal (usually a user) being authenticated to the service principal, metadata such as the ticket's expiration time, and -crucially!- a "session key" that the KDC will arrange for the user to also know. The client principal (user) uses this session key to create an Authenticator with which to prove knowledge of the session key to the service principal, and that's how one uses Kerberos to authenticate a client user to some service. If the client presents a Ticket and Authenticator, and the service can decrypt the Ticket, extract the "session key", and decrypt the Authenticator with the session key, then the client is whoever the Ticket says they are, for they possessed the cryptographic key with which to make that Authenticator.
Orpheus' Lyre allows an attacker who is on-path (physically or logically) between the client and the services it talks to (including the KDCs) to mount a service impersonation attack on the client. That is, a man-in-the-middle (MITM) on the wire can impersonate some services to the client.
We'll stop here for now, but we'll add more details in the coming days. We urge all users to apply all patches related to this vulnerability without delay.
Note that this vulnerability is a client-side vulnerability. You must patch all affected clients. You cannot patch servers to mitigate or defeat this vulnerability.
We should say a little about how we found this.
Jeffrey Altman, founder of AuriStor, Inc, visited Viktor Dukhovni and Nicolas Williams at Two Sigma Investments, LP for a meeting about the Heimdal 7.3 maintenance release. Heimdal is an open source implementation of Kerberos and PKIX, among other things.
As it happened, Viktor and Nico were researching a bug involving a Two Sigma-specific feature they added to Heimdal. The bug involved confusion in the "non-referrals" codepath in Heimdal for talking to the KDC, whereby a referral was treated as a non-referral. This was funny because we had been under the impression that "referral TGTs" should not be stored in the local ticket cache, and yet that was happening anyways. This forced us to re-examine everything we knew about referrals in the Kerberos protocol. Jeff and Nico each have nearly two decades of experience with Kerberos, while Viktor is not as expert in Kerberos, but extremely inquisitive. We worked through everything. We questioned the "canonicalization" extension in the Kerberos protocol. It took us an hour or so to realize that there was a serious bug here.
Once we knew the nature of the problem, we set about finding vulnerable implementations. The MIT implementation is not vulnerable, and looking through its version history, never had been. On the other hand, Heimdal has been vulnerable since late 1996. We checked Darwin (OS X), and found it to be vulnerable. At that point we decided to start a disclosure process. Jeff managed all the disclosures, and just in case, disclosed to Microsoft so that they could check their implementation. Surely enough, Microsoft's implementation turned out to be vulnerable, also since the beginning. (Microsoft first started using Kerberos in Windows NT5, aka, Windows 2000.)
First, we speculate that the reason that the Ticket in the KDC-REP (KDC reply) message was not authenticated directly as a premature optimization: since the Ticket's payload is encrypted in the service's secret key, why super-encrypt it in the KDC reply key?
Second, the relevant fields of the Ticket's plaintext part naming the service (which is redundant) and the equivalent fields in the encrypted portion of the KDC reply, are named very similarly. This makes all too easy to decode a KDC reply and... use the correct fields of the wrong structure to obtain the name of the service principal!
Third, this mistake does not cause the implementation to fail. It does not break interoperability with other implementations. It merely violates an assumption of the specification that should have been noted more carefully. Since nothing breaks, and no one thought to check for this vulnerability, no one noticed it for more than twenty years! It took a bug in a new feature, which interacted with the Kerberos referrals feature, for us to chase it down and notice a rather subtle oddity.
Please keep checking here for updates. There are more twists related to this vulnerability that we will be reporting over the next few days. Please patch your systems!