Path: utzoo!attcan!uunet!samsung!sdd.hp.com!elroy.jpl.nasa.gov!ames!eos!shelby!TRANSARC.COM!Ted_Anderson From: Ted_Anderson@TRANSARC.COM Newsgroups: comp.protocols.kerberos Subject: Dictionary attacks Message-ID: Date: 15 Jun 90 12:53:18 GMT Sender: daemon@shelby.Stanford.EDU Organization: The Internet Lines: 30 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