Samhain Labs

By Rainer Wichmann rainer@nullla-samhna.de    (last update: Sep 24, 2004)

Introduction

Passwords are notoriously a weak point in security and authentication schemes. If a valid password becomes known to an unauthorized person, most security systems, like firewalls and network intrusion detection, will become utterly useless. Basically, passwords may leak in at least two different ways:

1. If passwords are sent in cleartext over the network for remote authentication, as e.g. with telnet, ftp, but also with browser-based WWW access control, they usually will pass through several hosts on the way, and on each of them may get "sniffed" with readily available software.
2. Usually, passwords are stored encrypted on the server. If an encrypted password is stolen, the encryption may be cracked, and the password revealed.
3. Out of ignorance or lazyness, users may choose trivial passwords (like first names) that can be guessed successfully with only few trials.

To avoid the danger of password sniffing, for any critical application only encrypted protocols (like ssh for shell access, and ssl for web access) should be used to ensure that passwords are sent encrypted rather than in cleartext.

The two last points are more problematic. Ideally, users should use passwords that are difficult to crack, and easy to remember (to avoid the need to write them down somewhere). Unfortunately, these two requirements are somewhat contradictionary.

To get a better understanding of what comprises a good password, consider the way a typical password cracking program works. It starts with a list of popular words, such as first names, and words like "gandalf" (one of the wizards in J.R.R. Tolkiens "Lord of the Rings"). First, it tries each word "as is", then it starts trying spelling variations (capital letters, replace 'o' by '0', add a digit at the beginning or end, ...). If all else fails, it will try to crack the password by brute force, i.e. trying all possible combinations of letters and numbers.

Thus, a "good" password should

• not be a name,
• not be in the dictionary,
• not consist of any dictionary word with trivial spelling variations,
• be 7 or 8 characters long (shorter ones can be cracked by brute force, and for longer ones anything beyond 8 chars is ignored by many systems), and
• be easy to remember.

A useful method to create such passwords is to take the first char of each word in a sentence, such as WhJs0mt ("Why has John spent no money today ?".)
Experiments[1] with password-cracking programs show that such passwords are as secure as completely random ones. In addition, they have the benefit that they can be memorized without writing them down somewhere.

User compliance

While user compliance (i.e. the willingness to use good passwords) will improve if users are educated about proper choice of passwords, still a large minority (about 10 per cent) of users does not comply with such instructions[1].
Given the fact that a single leaked password can undermine the security of a system, it appears necessary to enforce the use of proper passwords by using password cracking software on a regular basis, and to disable accounts with weak passwords, until the owner changes that password.

Automated password generators

There are many programs available that can generate "almost random" password that are pronounceable, e.g. follow some rules about the proper order of vowels and consonants. In theory, such passwords are also both secure and easy to memorize.

We have audited the source code of several such programs, and found that almost all programs tested by us are insecure. All such programs are based on some software Pseudo-Random Number Generator (PRNG) to generate random sequences, from which letters are selected. It is important to understand that the sequences produced by PRNGs have the mathematical properties of random sequences, but are predictable, once the so-called seed value is known.

E.g., if the current time is used as seed, then it suffices to determine the time of last access (= the time of last usage) for the program to know the seed. If the seed is thus known, the passwords generated by the program can be reproduced. On Unix, the time of last access is stored on the file system, and can trivially be investigated with the "ls" command.

For our test, we searched the popular software index freshmeat.net with the keywords 'password generate'. Out of ten matches, one was a broken link, one works by just concatenating words from a dictionary, three used the time of last access as seed for the PRNG, four others use only slightly more sophisticated methods to seed the PRNG (e.g. the Perl srand() function without argument, which is documented as insecure in the Perl manual.)

Only one program (passwdgen) uses a secure, cryptographic source (the /dev/random device) for seeding the PRNG. Note that we have not checked for the presence or absence of other flaws, and that we do not recommend the usage of any program for password generation.
Also, we expect that this experiment would show similar results for proprietary, closed-source programs.

(Update: Shortly after the publication of this article, another open-source program (apg) announced support for the /dev/random device.)

[1] Yan J., Blackwell A., Andersson R., Grant A.: The memorability and security of passwords - Some empirical results