“Dictionary attack” is the name for a category of cryptanalysis techniques for recovering user passwords. It is a known fact that the Kerberos protocol is vulnerable to off-line dictionary attacks. This article provides an overview of the dictionary attack and explains how and why Kerberos is vulnerable to it.
The Kerberos AS exchange allows a client C to obtain a Ticket Granting Ticket (TGT) from the Kerberos Key Distribution Center (KDC). The TGT is then used to obtain authentication materials for accessing different services in the network.
The AS exchange consists of the two following messages (simplified):
(1) C -> KDC : C, "krbtgt", Nonce (2) KDC -> C : K(C, "krbtgt", K1, Nonce ...), TGT
K is a cryptographic key derived from the client password “P” using a well known function that we will call P2K. We have thus K = P2K(P). K(X) denotes the cipher-text encrypted using the key K. The key “K” is used the encrypt the first component of As reply (message 2) that accompanies the TGT.
“Dictionary attack” is the name for a category of cryptanalysis techniques for recovering user passwords by actively interacting with other entities in the network or by processing a pre-captured data. The most common form of dictionary attack occurs when three conditions are met.
- First, when the subject protocol being attacked derives keys directly from passwords, using a known function.
- Second, when at a certain phase of the subject protocol, a known text message is encrypted using a key directly generated from a password.
- Finally, when the attacker is able to obtain a copy of the encrypted known text message. Such as by eavesdropping or by provoking the issuance of this message.
When these three conditions are met, the attacker can use a list of possible passwords (dictionary) and iteratively create keys using the password-to-key function, then attempt to decrypt the captured message. In order to verify if the guessed password is correct, the attacker checks the result of the decryption. If the known text appears, it indicates that the decryption was successful using the guessed password.
The vulnerability of the Kerberos protocol to dictionary attacks has beeing initially documented in in  and experimentally proven in . In short, if an attacker can intercept the AS reply message from the KDC to the client, he can perform a dictionary attack that eventually yields to the disclosure of the password of the user to whom the TGT was issued.
Kerberos in deed shows the three characteristics, discussed in the previous section, which indicates vulnerability to dictionary attacks. The first condition is verified since Kerberos derives encryption keys from passwords using a known function (K=P2K(P)). The second condition is also verified since the first component of the AS reply message, K(C, “krbtgt”, K1, …), is encrypted using a key derived directly from client's password, and contains the know plain text “krbtgt”. Finally, as Kerberos is an authentication protocol for open systems, it was designed with the assumption that any entity can eavesdrop Kerberos exchanges. Which makes the third condition applicable to Kerberos.
We have thus the three conditions for vulnerability to dictionary attack that we described above satisfied. The attacker can use a dictionary, compute the key from a chosen password using the P2K function, then use the guessed key to decrypt the first component of the AS reply message. In order to verify whether the guess was correct, the attacker checks the decryption output for the string “krbtgt”.
At a first glance, it seems that in order to strengthen the Kerberos against this category of threats, at least one of the three conditions must be avoided. We will go into this analysis in a future article, in which we will examine existing approaches to tackle dictionary-attack vulnerability in Kerberos. So stay tuned.
-  “Limitations of the Kerberos Authentication System”, Steven, Bellovin et al.
-  ”Real-World Analysis of Kerberos Password Security”, Thomas D. Wu
|Labels: kerberos, security|