[1008] in Kerberos
Dictionary attacks
daemon@ATHENA.MIT.EDU (Ted_Anderson@transarc.com)
Fri Jun 15 09:46:06 1990
Date: Fri, 15 Jun 1990 08:53:18 -0400 (EDT)
From: Ted_Anderson@transarc.com
To: kerberos@ATHENA.MIT.EDU
Cc:
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
