[1016] in Kerberos
Re: Dictionary attacks
daemon@ATHENA.MIT.EDU (Joe Pato)
Fri Jun 15 12:57:39 1990
From: pato@apollo.com (Joe Pato)
Date: Fri, 15 Jun 90 11:36:45 EDT
To: Ted_Anderson@transarc.com
Cc: kerberos@ATHENA.MIT.EDU
In-Reply-To: Ted_Anderson@transarc.com, fri, 15 jun 90 09:03:02
I believe people in this recent exchange have been mis-using the term
"dictionary attack". It seems that people have been using this to refer
to a situation where the sought key is a word in the dictionary. This
limits the search space from 2^56 to something more manageable like the
size of the dictionary, 10K-100K words. This is certainly a problem.
However, my understanding of the term is that it is a bit more
complicated. The case Joe Pato mentions is a good one. You request a
ticket for each user in the database. The tickets you receive surely
contain verifible plaintext, but even more useful, they START with
CONSTANT plaintext, in this case the name of the requester and a few
other controllable bytes. As long as there are more than eight bytes we
can predict the plaintext to the first round of encryption in the CBC.
Now we separately compute the encryption of this text with all the
passwords of interest. This list is sorted and becomes the
"dictionary". Now we look each of the responses from the first step up
in this "dictionary", every match gives us someone's key.
The power of this appoach is that we attack everyone's password in
parallel. Each trial key can be tested against each user with little
extra cost. This is useful only if we don't really care which key we
find. This is the same basic idea as the Birthday Paradox. In
principle, this reduces the effort to about the square root of the key
size, in this case (sqrt(2^56) == 2^26) about 67 million. In practice
to really attack the whole key space is foolish, and would take a great
deal of memory and a large space of users to attack. But in common
cases the attack wins by a factor of the number of users in the
database.
Ted Anderson
When we were designing the extensions to Kerberos V5 for DEcorum (and
subsequently the OSF DCE) we considered forcing "good passwords". We had two
strategies in mind:
1) Have the password changing interface pass the plaintext of the password
to the server encrypted under the appropriate session key. This allows
the server to enforce passwords selected from a suitable alphabet and
passwords that do not appear in dictionaries. The specific
restrictions are expressed at the server via policy data. This would
be in lieu of the current kpasswd - thereby disallowing unevaluated
passwords.
2) Decouple a principal's password from their secret key. Have the secret
key be generated by an appropriately random algorithm at the KDC when
the principal changes their simple password. The secret key
(encrypted under the simple password) would then be retrievable by an
appropriate challenge/response protocol.
This has two benefits. All principal's will use a "good" key chosen
from the complete 2^56 key space to thwart dictionary attacks of the
form I suggested (An attack by a principal possessing a valid tgt on
another principal by requesting a ticket with that other principal as
the server). And the initial key retrival operation can be of the form
that Jonathan was looking for - it requires a priori proof of possesion
of the simple password, it can be "slow" to limit the effectiveness of
brute force attacks, it can audit repeated attempts to detect attacks
and it can choose to deny requests that exhibit an attack pattern.
The attack detection threshold will be affected by the number of
replicas servicing the KDS, but should be low enough in all practical
environments so that the number of replicas is inconsequential.
We did not implement either of these extensions in order to remain true to the
Kerberos V5 protocol. I am inclined to at least implement the first since it
simply affects kpasswd. Comments?
-- Joe Pato
Cooperative Object Computing Operation
Hewlett-Packard Company
pato@apollo.hp.com
-------
