Ted_Anderson@TRANSARC.COM (06/15/90)
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 Andersonpato@APOLLO.COM (Joe Pato) (06/15/90)
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
-------wes@terminator.cc.umich.edu (Wesley Craig) (06/15/90)
In article <UaSBcy=0Bww25YSmBx@transarc.com> Ted_Anderson@TRANSARC.COM writes: > 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. I believe that the confounder was introduced to (surprisingly) confound this attack. The confounder is a random number at the beginning of the encrypted packet, thus removing the possibility for the attack above. wes
jb7m+@andrew.cmu.edu (Jon C. R. Bennett) (06/16/90)
> In article <UaSBcy=0Bww25YSmBx@transarc.com> Ted_Anderson@TRANSARC.COM writes: > > I believe that the confounder was introduced to (surprisingly) confound > this attack. The confounder is a random number at the beginning of the > encrypted packet, thus removing the possibility for the attack above. > > wes you better make sure that the (psudo)random number generator you are using is REALY good, if not, all you are doing is effectivly give the attacker more cleartext to play with! in general having the server send the ticket back encrypted in the users key in reponse to any request is bad simply because it gives away information with can be used in an attack, forcing the client to send the request encrpted in the users key (where the request can be time stamped to prevent reuse by someone with access to the subnet and have a random number appended to the front to hinder stream encrypted DES attacks) prevents the release of more information then necessary. jon