13-11-2012, 04:40 PM
A Real-World Analysis of Kerberos Password Security
A Real-World Analysis.pdf (Size: 207.08 KB / Downloads: 15)
Abstract
Kerberos is a distributed authentication system that
many organizations use to handle domain-wide pass-
word security. Although it has been known for quite
some time that Kerberos is vulnerable to brute-force
password searches, there has so far been little analy-
sis of the scope and extent of this vulnerability. This
paper discusses the nature of this weakness in detail
and attempts to quantify the severity of the danger
it poses to existing Kerberized installations. The re-
sults of a controlled experiment, in which a large num-
ber of passwords from a Kerberos realm were broken
o-line and subjected to analysis, will be presented.
The author explores possible strategies for repairing
this security hole, the most viable of which is the use
of Kerberos V5 preauthentication coupled with a se-
cure password authentication protocol such as SRP,
SPEKE, or EKE.
Introduction
Kerberos [18], developed at MIT about ten years ago,
was an authentication infrastructure designed to as-
sure the security of user accounts and system ser-
vices on potentially insecure networks. By distribut-
ing secret keys and using cryptographic protocols like
Needham-Schroeder [14] to verify possession of these
keys, Kerberos supposedly prevented unauthorized
parties from compromising system security even if
they had the means to subvert the network.
In 1989, Bellovin & Merritt outlined a number of
security weaknesses in Kerberos [2]. While most of
those problems have been addressed in some way
since they were rst brought to light, others still re-
main with us to this very day.
Anatomy of a Security Hole
We start with a very brief summary of how Kerberos
is structured, followed by a closer look at the actual
password authentication protocol. For more in-depth
information on Kerberos, the original paper [18] is
recommended, along with papers describing the un-
derlying component protocols [14].
Kerberos Tickets
All entities in Kerberos, be they human users or non-
human servers, such as those for E-mail or print ser-
vices, have a secret key, which is shared only with
the central authentication server. To obtain services
from an application server in a \Kerberized" environ-
ment, a client must rst obtain what is known as a
Kerberos ticket from the authentication server. This
ticket contains, among other things, a section of data
encrypted with the secret key belonging to the re-
quested service. The client presents this ticket to the
application server, which can then verify the ticket
for authenticity. Since the client does not know the
server's secret key, it cannot forge a valid ticket, nor
can it tamper with the contents of a ticket without
being detected.
In Enemy Hands
Normally, if the user enters an incorrect password,
the initial decryption attempt produces a gibberish
packet, which causes the the Kerberos client soft-
ware to notify the user and discard the packet. But
what if the client software, instead of throwing away
the packet after each attempt, allowed the user to
try decrypting the same packet again with dierent
passwords? And what if, instead of having a human
typing in dierent passwords, the software automated
the procedure, pulling in passwords from a dictionary
as fast as it could check them? Since the TGT has
a xed, publicly-known format, the software could
determine if it had found the correct password by
looking for one that decrypted the TGT properly.
Veriable Plaintext
To determine whether or not a given key produces
a valid ticket, the Kerberos client software examines
the decrypted ticket elds to see if they make sense. If
the wrong key was used, and if the software attempts
to nd a null terminator for each string, it may nd
too many or not enough of them for the number of
strings in a ticket. It may also discover that some of
the other elds, like the timestamp or length elds,
are internally inconsistent.
DES Parity Optimization
The format of the Kerberos TGT packet permits a
further renement of the password verication pro-
cedure. The DES algorithm requires its keys to have
odd parity, i.e. the number of \1" bits in each byte
of a DES key must be odd [15]. Since the rst block
B0 of the plaintext TGT is a DES session key (see
Table 2), we know each of its bytes must have odd
parity.
Instead of computing both B0 and B1 for each
guess, the attacker can compute just B0 and check
the parity of all 8 bytes. If any of them are not odd-
parity bytes, he can conclude that the guess was in-
correct without having to decrypt the second TGT
block. 255 out of every 256 tries will, on average,
fail the parity check right away, so most guesses now
require only one DES decryption instead of two.
Analysis by Rules
The password cracker combines user-specic informa-
tion, like the username and full name, with a series
of precompiled word lists to obtain a list of password
candidates. To each word in this list, it applies a set
of transformation rules to generate even more poten-
tial passwords. Of the successfully guessed passwords
in the experiment, 283 passwords were based on ei-
ther the corresponding username or some derivation
of the person's full name. The remainder originated
from one of the word lists.
Software and Hardware
The preceding experiment used a well-known Inter-
net password cracking package, modied to decrypt
and verify Kerberos V4 tickets. This package gen-
erates password candidates by reading words from
dictionaries and applying the same transformations
that users often use to generate their passwords. The
list of rules can be extended to accommodate nearly
any type of password-generating transformation, in-
cluding common ones like adding digits to the end of
words or substituting digits for letters that resemble
them.
The running time of the password cracker is di-
vided into two components. Let k denote the amount
of time needed to convert each password guess into
a key. Most of this time is taken by the STRING-
TO-KEY function of Section 2.4. Let c denote the
amount of time needed to apply this key to a pass-
word entry and check if the key results in a valid
decryption. This time is mostly determined by the
speed of the DES decryption code. Table 5 shows
the relative performance gures for some well-known
hardware platforms.
Dictionary Construction
An important part of the success of this password-
cracking eort was the input dictionary used to con-
struct the password guesses. Because this experiment
was conducted at a site that already implemented
password-checking, it would have been pointless to
try passwords that were already in the password
checker's dictionary. It thus improves our chances
to have more words in the cracker's dictionary than
in the dictionary used to screen passwords. At the
same time, it is desirable to ensure that any such
words added to the dictionary are still likely pass-
word choices.
Conclusion
Vulnerability to dictionary attacks has long been an
acknowledged weakness in Kerberos [2], yet at the be-
ginning of this experiment, there existed little hard
data on its severity. Could simple password-checking
prevent a password cracker from revealing any pass-
words, as some have claimed in the past?
That question was answered exactly nine seconds
into the experiment, when the rst cracked password
appeared on the screen.