19.7.2 Dictionary attack
We already learned that a cryptographic hash function is pre-image resistant. This is just another way of saying that given a hash value h(m), it is computationally infeasible for Eve to find the pre-image m.
This property is what password security mechanisms in operating systems rely upon. Recall that modern operating systems such as Linux use hash functions to store the hash values of passwords rather than the passwords themselves. The rationale is that even if Eve gets hold of a hashed password, she cannot use it to log in as the victim because the password system requires her to enter the plaintext password. However, because a cryptographic hash function is pre-image resistant, Eve cannot reconstruct the plaintext password from its hash value.
Figure 19.16: Working principle of a dictionary attack
A common way for Eve to defeat pre-image resistance is a dictionary attack. In a dictionary attack, Eve systematically computes the hash value for all plaintexts contained in Eve’s dictionary, hence the name of the attack. If Eve’s goal is to determine the plaintext password given the password’s hash value, the dictionary would be typically composed of popular words and their combinations, typical phrases, and a list of common passwords.
Figure 19.16 illustrates the working principle of a dictionary attack. In the initial attack phase (which only needs to be done once), Eve computes the hash values for all dictionary entries di using the same hash function h, like Alice.
In the second phase, after obtaining the hash value for Alice’s password, Eve searches the pre-computed hashes for the hash value of Alice’s password. If Eve finds such a hash value, we say that the dictionary attack succeeded because Eve now knows a plaintext, namely di, that yields the desired hash value.
Note that Eve’s dictionary entry resulting in Alice’s hash value does not necessarily have to be Alice’s actual password because any hash function will, at some point, produce collisions. But this doesn’t matter in practice since, for example, the password security system only checks if the password entered maps to the hash value stored.
Dictionary attacks were successfully deployed against computer systems – especially against systems that allow weak passwords such as simple words and common phrases found in dictionaries – as early as the late 1980s.
As an example, in early November 1988, the internet – at that time, a collection of networks connecting about 60,000 hosts – was attacked by a virus that broke into Berkeley Standard Distribution (BSD) Unix and derivative systems [61]. A group at MIT who discovered and dealt with the virus published their experience and a detailed analysis of the virus in [61].
After entering a vulnerable system, the virus applied a dictionary attack on encrypted passwords stored in /etc/passwd. It used the dictionary attack as the method to verify password guesses in order to avoid being noticed in the system’s security logs. The virus first used a built-in dictionary of 432 words and subsequently the local /usr/dict/words file, a 24,474-word spelling dictionary distributed with BSD version 4.3.
An important takeaway from dictionary attacks is that the entropy of the plaintext has a strong effect on the practical security of most cryptographic primitives. If Alice uses only 10 different plaintext messages as input to a hash function or an encryption function, it is very simple for Eve to find their pre-images even if these functions themselves are computationally secure. This, in turn, illustrates the difference between the security of a cryptographic primitive itself and the security of its mode of operation.
Leave a Reply