Unix and Linux Password Security

©2006–2013 by Wayne Pollock, Tampa Florida USA

Background:

Unix/Linux systems have never stored plain text passwords on the disk.  When someone tries to login, they supply a username (or account ID or login name) and a password.  The username is used to locate the encrypted version of the password.  This is often stored in the file /etc/shadow (older systems used /etc/passwd, which is publicly readable), or in some central (organization-wide, networked) database.

For managing a single host, the shadow suite can be used instead of a more complex database.  This keeps the password in /etc/shadow (and only an “x” as a place-holder in /etc/passwd).  The shadow file has root-only access, so utilities that manage passwords are often setUID to root.  (See the man pages for the format of the passwd and shadow files.)

There are ways to prove a user's identity, other than supplying a password (something you know).  This include bio-metrics (something you are), and various security devices such as smart cards and dongles (something you have).  However, all these mechanisms have their vulnerabilities and drawbacks.  For all their faults, passwords are very convenient and in many contexts, offer a reasonable level of security if used correctly.  (Increasingly, two- or multi- factor authentication is used, where two of the three types of authentication must be used together.)

Secure Hash Codes:

Actually the stored password is a secure hash and not an encryption at all.  The phrase encrypted password is (mis-) used to refer to a hash of a password, possibly because the hash was originally calculated by the crypt library using the encryption algorithm DES.

A hash is also called a hashcode, digest, message digest, fingerprint, signature, checksum, message integrity code (MIC), although technically these aren't all the same thing.  A hash function is any well-defined procedure or mathematical function which converts a possibly large amount of data (a message) into a small datum (the hash, hash value, or hash code).  The hash is usually a single integer with the property that a change to the message will change the hash.  A hash is often used to speed database lookups.

A cryptographic hash is a one-way function that supposedly can't be easily reversed (i.e., you can't find the original message just given the hash), faked (i.e., you can't easily change the message without also changing the hash), or spoofed (i.e., you can't easily find a second message with the same hash as another message).  Some better known cryptographic hash functions include MD5 and SHA-1.

There are compiled lists of hash values for known (common) files, both "good" files (so you can validate your copy of some standard DLL) and "bad" files (so you can check for malware without viewing the files).  Many vendors keep such lists for (some) versions of (some) their software, including Microsoft, Sun, etc.

Hashkeeper (www.usdoj.gov/ndic/domex/hashkeeper.htm) was created by the U.S. National Drug Intelligence Center (NDIC).  It uses the MD5 file signature algorithm to establish unique numeric identifiers (hash values) for known files and compares those known hash values against the hash values of files, such as files on a seized computer system.  HashKeeper is available free-of-charge to law enforcement, military, and other government agencies throughout the world.  It is available to the public by sending a Freedom of Information Act (FOIA) request to NDIC.

The National Software Reference Library (NSRL at www.nsrl.nist.gov) is designed to collect software from various sources and incorporate file profiles computed from this software into a Reference Data Set (RDS) of information.  The RDS is a collection of digital signatures (both MD5 and SHA-1 hashes) of known, traceable software applications.  There are application hash values in the hash set which may be considered malicious, i.e. steganography tools and hacking scripts.  There are no hash values of illicit data, i.e. child abuse images.

In 2004, MD5 was shown to have some theoretical weaknesses.  While still considered safe at the time, in 2008 a more severe weakness was discovered.  It is possible for virus writers to craft a virus-infected file to have the same MD5 sum as the real file!  See www.phreedom.org/research/rogue-ca/ for more information.

The NIST is phasing out acceptance of MD5 and SHA-1 by 2010.  Instead it is recommend to migrate to SHA-2, SHA-3, or another more secure algorithm (see U.S. Gov. standard FIPS-180-2).  For a list of approved ciphers, hashes, and related algorithms see secure hashing at csrc.nist.gov/groups/ST/toolkit.

There are a number of authentication systems available and each is configured independently of the others.  This can lead to confusion (and hence bad security)!  For example, any settings in the file /etc/login.defs or (for Solaris) /etc/default/passwd, such as for minimum password length or expiration data, only apply when using the shadow suite and not for LDAP, NIS, Kerberos, etc.  Locking passwords in the shadow file may have no effect on ssh (and it's subsystems such as scp and sftp), if using keys.  PAM may or may not be used for FTP, rsh.  And so on.

Change Default Passwords:

Default passwords are an easily and commonly exploited vulnerability.  You need to change all default passwords before any system is exposed to the Internet.  (Today the time to attack for a vulnerable system connected to the Internet is seconds to minutes.)  Don't forget to change passwords on network devices such as routers, switches, wireless access points, etc.  New user accounts need good passwords as well.

Don't use the same password on multiple sites!  The average user has about 25 accounts, but only uses about 5 passwords.  You should use different passwords for each site, even if only a little different.  Note it is perfectly safe to write down passwords on paper, as long as you keep that paper safe (such as in your wallet or purse).  A better solution is to use some password management system (such as KeePass), and use very strong passwords that are different for each site.  (See xkcd.com/792.)

A System Administrator (SA) should use password generators (pwgen, apg) to set initial passwords for user accounts.  (See FIPS–181).  These passwords can be encoded in a form suitable for use with the Gnu useradd ... -p 'encrypted-password' using openssl to encrypt the passwords.  (Note Solaris through version 10 lacks a non-interactive standard method to set passwords.)  If humans pick the passwords, the SA should provide guidelines on picking safe passwords (and avoiding “obvious” but non-safe ones).

Although apg generates “better” passwords than pwgen, apg uses /dev/random while pwgen uses /dev/urandom.  This means apg may appear to “hang” at times; see Random Numbers below for why that happens.

Good passwords:

Use the first letter of words (or better, each syllable) of a quote or poetry, plus symbols or digits.  Some examples include “Rar,Vab” (“Roses are red, Violets are blue”), “Iafyds,civ1.0.” (“If at first you don't succeed, call it version 1.0.”), and “"Rd"isnaip!” (“"RAM disk" is not an installation procedure!”).

Treat your password like your toothbrush.  Don't let anybody else use it, and get a new one every six months.  — Clifford Stoll

A password that is allowed to contain spaces is called a passphrase.  When possible, use a mix of upper-case and lower-case letters, plus digits, punctuation marks, and other symbols.  Not all systems accepts strong passwords or passphrases, particularly those with a web interface.  (Gmail permits passwords as long as 200 characters, Yahoo Mail allows 32-character passwords.  Hotmail only allows 16; for years it has accepted longer passwords, but ignored all but the first 16 characters.)

U.S. federal standard FIPS-112 mandates passwords should only be composed of the 95 printable ASCII characters.  (However there is no requirement to actually use ASCII to store the passwords.)  Also the minimal length of an acceptable password is four (4) characters.

Although the password changing command “passwd” does a minimal amount of checking for poor passwords, on modern systems PAM is used to set a password policy.  On many systems, you use arguments to the pam_cracklib.so PAM module to force very strong passwords, disallow (or allow) null (no) passwords.  You can even prevent users from reusing their last few passwords.  Setting minimal password length in other files (such as /etc/default/useradd or /etc/login.defs) generally has no effect.

Facebook has released a statistic (see this 11/2011 blog post) showing that 0.06 percent of logins into their social network are compromised.  That doesn't sound bad; however, since more than 1 billion Facebook logins occur each day, this adds up to 600,000 breaches every 24 hours, or roughly eight every second.

[ From www.hfes.org/web/Newsroom/HFES09-Hoonaker-CIS.pdf. ]
In 1979, Morris & Thompson (1979) reported that many UNIX-users choose very weak passwords, for example very short or obvious passwords.  They analyzed 3289 passwords and results showed that passwords mainly consisted of: strings of three ASCII characters (14%); strings of 4 alphanumerics (a set of characters, including letters, numbers, and, often, special characters, such as punctuation marks) (15%); 5 letters, all upper-case or all lower-case (21%), or 6 letters, all lower case (18%).  Furthermore, 15% of the passwords appeared in various available dictionaries, etc.  They concluded that a total of 86% of all passwords fitted in one the classes above.

2006, a separate survey of 34,000 MySpace passwords revealed that the most common were “password1”, “abc123”, “myspace1”, and “password”.

In 2012, 450,000 Yahoo! email addresses and passwords were leaked (they were stored by Yahoo in plain text, not hashed) and published on the Internet.  An analysis by CNET found “123456” to be the most popular password (nearly 3,000 were sequential numbers), while 780 users used “password”.

The purpose of picking hard to guess passwords is to prevent attacker from using lists of common passwords.  But instead of forcing users to pick complex passwords, it turns out it is sufficient just to prevent them from picking common ones.  For example, Twitter allows any password not in a list of about 400 common ones (such as “p@ssword” or “ABCD”).  There is a list of 106 passwords Blackberry forbids.  Also, an organization can track how often a given password is used, and add them to the list if too many users try to use it.  Any password, even if a dictionary word, would be allowed as long as it is rarely used.

The average Web user maintains 25 separate accounts, but uses just 6 to 7 passwords to protect them, according to a 2007 Microsoft research study.

How long should a key be?  Entropy and key length

The strength of passwords (and keys) are measured in the number of random-bits they are equivalent to, also called its entropy.  It has been estimated that normal English text only contains about 2 to 2.5 bits of entropy per character, and that the 2,000 most common words have about 10-12 bits per word.  So a four word phrase would seem to provide about 40 bits, except that most phrases aren't selected at random, and so contain much less entropy.  About 1% of passphrases used by Amazon's PayPhrase system users, were guessed from a dictionary containing 20,656 phrases of movie titles, sports team names, and other proper nouns; that's less than 15 bits of entropy.

Guessing random keys until you get the right one is known as a brute-force attack; randomly guessing the passwords used to generate the keys is known as a dictionary attack.  While most communications are protected by keys, the keys are generated with, or protected by, passwords.  Thus the strength of keys are tied to the strength of passwords.

While vendors and others like to talk about password or key length, it is the entropy that matters.  A trivial example makes this clear.  Suppose a key-generator uses this method to generate a key of some desired length:

	key = 1;
	while ( key.length < desiredKeyLength )
 	    append a "1" to the key;
	return key;

No matter how long the key, it has zero bits of entropy.  Recording the gender of a random person as a key has one bit of entropy.  The reason longer keys are thought to be more secure than shorter keys, is the assumption that longer keys contain more entropy.  That is generally true for passwords (where each additional character adds entropy), but not for keys.

Additionally, a poor algorithm does not use all the entropy in a key.  For example, the original HTTPS implemented in Netscape Navigator generated 128-bit keys, but the random number generator's algorithm meant such keys had a maximum of 20 bits of entropy.  Similarly, the A5/1 algorithm used for GSM cell phone encryption uses 64-bit strong keys, but the algorithm can be cracked as easily as if it had a 30-bit key.

This is why ECC (elliptical curve cryptography) is said to provide similar security to AES or other currently used algorithms, while having shorter keys.  ECC algorithms use much more of the entropy of a given key than these other algorithms.

Microsoft (and others) used to use a user-entered password of eight characters to generate long keys of 128 bits or longer.  But the entropy of such keys is not 128, it is the entropy of the password, about 16 bits.  And in reality, it is much less than that, as humans don't pick truly random strings for passwords.  An attacker could probably guess the correct key by trying only a few thousand passwords, so advertising the security as 128-bit keys is misleading.

If you use GPG and password protect the file containing the private key with a five-character password, does it matter that the key length is 1,024 bits?  (Probably yes, since you expect attackers to intercept messages, but not to have access to the hard disk containing your private key.  If they do get a copy of your key, you have a few days to change it before they can break your password, assuming you picked a good, long passphrase.)

So back to the question this section started with:  How long should a key be?  It is a common mistake to believe that longer keys are always better than shorter ones.  The point of long keys (those having lots of entropy) is to make it unfeasible to try a brute-force attack.  A good analogy I read in Bruce Schneier's excellent book Secrets and Lies is to consider the lock on your home's front door.  These are usually five pin tumbler locks, where each pin could be in one of ten positions, for a total of 100,000 possible keys.  If a burglar could carry around that many keys, and had to try (on average) 50,000 of them, they would need to stand at your door day and night for about three days, constantly trying the keys.  This is not feasible, and no burglar would do that.  Now, suppose I came along and offered to sell you a lock with eight pins, each of which as 12 positions.  Would you feel any more secure if you installed such a lock?  Probably not!  Once brute-force attacks are not feasible, making them even less feasible does not enhance security.

An analogy may help:  Suppose your computer is slow because it doesn't have enough RAM, and is swapping a lot.  Adding more RAM will reduce swapping and speed up your computer.  After a certain point, adding more RAM does nothing.  Key length is like that; too short is bad, but after a certain point, making it longer does nothing to enhance security.  The minimal length depends on the entropy in the key as well as how the algorithm uses that key.

The DES encryption standard used 56-bit keys.  In 1998, the EFF funded a machine that could brute-force attack on DES; they called the machine “DES Deep Crack” and it tried around 90 billion keys a second.  It could crack a DES encrypted message in about 4 and a half days.  A year later, a distributed grid of computers on the Internet could be used to guess 250 billion DES keys every second.  Triple-DES has 112-bit keys.

Question:  Most modern algorithms including AES use 128-bit keys.  Is that long enough?  Answer:  Consider if you could build a computer a billion times as fast as Deep Crack, it would still take a million years to brute-force guess the key.  (Of course, systems may have other vulnerabilities including side-channel attacks, which make the key entropy moot as the attackers break in using other means.)

The hashing algorithms typically used with passwords work a bit differently.  They generally require about twice the key length for the same level of security.  Thus, SHA-256 is good enough in 2011, while SHA-512 would probably be overkill.  Of course, if the protected information is valuable enough, an attacker can always use a cluster or grid of computers, so even longer keys are needed.  (Analogy: your home's front door, versus a bank's safe door.)

Many companies now use DomainKeys Identified Mail (DKIM) to include a digital signature and to confirm that an email originated from their domain.  These are created using RSA public keys.  However, in late 2012, it was found that companies such as Google, eBay, Yahoo, Twitter, and Amazon use 512-bit keys.  According to one researcher, these keys can be cracked within three days in the cloud, using Amazon Web Services (AWS), at a cost of about $75.  Financial institutions such as PayPal, US Bank and HSBC reportedly use 768-bit keys; that are also considered insecure for the purpose.

To make digital signatures highly secure, keys with a minimum length of 1,024 bits must be used for RSA.  The US National Institute of Standards and Technology (NIST) currently recommends a minimum length of 2,048 bits for RSA keys.

Most password related policies come from the US Government (DoD), technical report CSC-STD-002-85, Password Management Guideline, also known as the green book (part of the rainbow series).  This was produced in 1985, and although the advice is outdated, it is still followed.

How long should a password be?

The situation for passwords and passphrases is only a little different than for keys.  Since passwords contain so little entropy, they can be attacked by brute-force.  So making them longer makes them harder to crack.  (It is doubtful a usable password or passphrase would contain so much entropy that it would not be feasible to attack this way.)

It is recommended that a passphrase of at least 5 random words or 14 completely random letters be used.  For high security needs, 8 random words or 22 random characters should be employed (if you can remember them, of course).  Passphrases should be changed whenever an individual with access is no longer authorized to use the network or when a device configured to use the network is lost or compromised.

Examples of passphrases:  “Sheriff town, 4 Prison keep?”, “salami-pavement, gracious volvo”, and “Why use XKCD when, the Nerf-Herder from Tatooine is the key?”.

While there are several available programs that can be used to generate good passwords, there are no well-known programs to generate quality passphrases.  You can generate good passphrases with:

shuf /usr/share/dict/words | head -n 4

If you don't have shuf on your system, try this Perl shell script:

WORDS=/usr/share/dict/words
MAX=$(wc -l </usr/share/dict/words)
for i in 1 2 3 4
do NUM=$(perl -e "print int(rand( $MAX ))+1;")
   sed -n "${NUM}p" $WORDS
done | tr '\n' ' '

If you don't have Perl, but do have /dev/*random, you can generate the random integers with this instead (or write a C program):

NUM=$(( $(od -An -N4 -tu4 /dev/urandom)%MAX+1 ))

Lock Down System Accounts:

The definition of a locked account is system dependent.  Mostly commonly accounts are locked by changing the password hash in /etc/shadow.  This generally prevents creating new processes via at, cron, etc.  On Linux account locking is done by adding a “!” to the front of the password hash, making it impossible for any entered password to match (but allowing an unlock operation to restore the previous password).  Empty or null passwords are locked with “!!” instead.  A leading “*LOCKED*” is used on FreeBSD systems.  On other systems the tools locking passwords replace the hash completely, with “*LK*” on Solaris and Unixware, with “*” on HP-UX, and with “Nologin” on Tru64.  So if there is a requirement to disable password authentication for some account while still allowing public-key authentication, then the password should be set to something other than these values (e.g. “NP” or “*NP*”).

Enabling/disabling (that is, unlocking and locking) accounts can be done a number of ways.  Generally you lock and unlock accounts with passwd -l (and “-u”) or usermod -L (and “-U”), rather than edit password files by hand (say by using vipw).

If the encrypted password field of the /etc/passwd file is set to an asterisk (“*”), the user will be unable to login using login, but (on Linux anyway) may still login using rlogin or ssh, run existing processes and initiate new ones through rsh,ssh, cron, at, mail filters, etc.  If set to “*NP*” the password is obtained via NIS+.  If an “x” the /etc/shadow file is used.  Otherwise this field contains the password hash.  (On older Unix systems this can be followed by a comma and then password aging fields separated with commas.)

Locking an account by changing the shell field to something that won't run (such as /bin/false) yields the same result as locking the password field.  While this method of locking allows the use of su and other programs, that isn't likely useful if the shell is /bin/false.  The system maintains a list of valid shells (often in /etc/shells).  Any account with an invalid shell (any program not in the list) is considered locked.  Using an invalid shell (often /bin/false) prevents su and may prevent other access as well (e.g., FTP; see pam_shells).  Unfortunately an account with an invalid shell is still a valid account as far as PAM (pam_unix) is concerned.

Where possible replace the shell with “/sbin/nologin” (which politely refuses login) or “/bin/false” (which just fails).  This will disable at, cron, and su on many systems.  Note a missing shell (empty shell field in /etc/passwd) implies /bin/sh, however PAM or other mechanisms may consider a missing shell to lock the account.  Run pwck and grpck, and fix any reported problems.  (Missing home directories is common.  Consider using /var/empty or /var/empty/username as the home directory.)

Locking a password doesn't prevent login or remote command execution via ssh (or scp or sftp)!  (Users can still use SSH keys, even though the sshd_config implies otherwise.)  You must also change the shell to an invalid one.  Unfortunately using an invalid shell will prevent su and may prevent cron jobs, at, etc. as well (depends on your system).  If your system allows cron jobs for accounts with invalid shells, or your system accounts don't use any cron jobs, you should change the shell to an invalid shell.

Some versions of sshd do check for locked accounts, when not configured to use PAM.  When configured to use PAM and sshd uses keys to authenticate the user, then it only uses the PAM account modules, not the auth modules, and pam_unix doesn't check for locked accounts.  (The designers apparently assumed the authentication will fail if the account is locked.)  While Linux PAM doesn't contain any modules that can check for locked accounts in the account context, you may be able to find one you can use from a list of non-standard PAM modules on the Internet, or create one, but make sure the module you find can work in the account context and not just in the auth context.

Most SSH servers can be configured to use PAM, and a PAM module could check for locked accounts (currently there isn't one).  Also sshd can deny access to a configured list of users or groups.  (See sshd_config).

For maximum safety, lock accounts by both setting an invalid, non-working shell and locking the password.  Also, don't rely on passwd -l to lock passwords unless using the shadow suite.  Configure SSH to use PAM, and configure PAM to use pam_shells.so to check for valid shells in both auth and account sections.

Password Aging:

Passwords and accounts can be disabled after some time has elapsed.  This is known as aging.  Use chage on Linux, passwd on Solaris.  Use chage -l to see aging info for some account.  Aging defaults for newly created logins are found in /etc/login.defs on Linux, /etc/default/login on Solaris.  Aging data originally was kept in the second (password) field of the /etc/passwd file using commas as field separators.  Modern systems don't do that; they use fields in the /etc/shadow file or columns in databases such as LDAP.

For each account the system holds

  1. the date the password was last changed (#days since 1969),
  2. the min # days that must pass between password changes,
  3. the max # days since last change before a password expires and must be changed,
  4. password expiration warning #days,
  5. # days of inactivity before an account is locked (confusingly called password inactivity), and
  6. a date the account expires.

You can force a password change (by setting the date of last change to zero or one, and setting the max # days reasonably), force users to change their passwords regularly, and prevent them from changing passwords too often.  (If min > max then users can't change their own passwords at all.)

It is probably safer to require very strong passwords and not force the user to change the password, for as long as their account is active.

Use Aging and PAM:

Use password aging and PAM (the pam_cracklib module or equivalent) to enforce a password policy.  The policy can include if null (no password at all) passwords are allowed, minimum length of passwords, non-trivial passwords, and passwords that must differ from the last few previous passwords used.  You can also set the time before a password expires and must be changed.  (Note!  Having strong passwords provides better security than forcing users to change passwords frequently!)  To make the passwd command record the last few old password hashes to /etc/security/opasswd you need an entry in your PAM configuration file such as:

password required pam_unix.so use_authtok md5 shadow remember=3

When you enter a new password the pam_cracklib hashes it and checks that against your old saved password hashes in opasswd.  It also tries a few hundred variations of what you type, to see if any of those match the old hashes.  It hashes what you entered, the reverse of that, and with all variations of case.  It also checks the length of the password you entered and performs some triviality checks on it:  length (strength) of what you entered, your user name, or a (small) dictionary of common passwords.  The “diffok” argument controls how many variations pam_cracklib will try.  Set this too big and it will take a long time to change a password!

For Solaris without pam_cracklib, you can the line “HISTORY=n” to /etc/default/passwd.  This causes old password hashes to be saved in /etc/security/passhistory.  Note n should be at least 2.  So setting n=4 prevents a user from reusing their last three passwords.

Password Mechanisms:

Originally only a single mechanism, “crypt” was used in Unix.  Today most platforms provide several different crypto mechanisms that can be used to create password hashes.  The list of crypto mechanisms available varies by platform.  Since Unix is used in high-security environments the crypto stuff is often part of the platform's “trusted base” and adding new mechanisms is involved (since the OS must then be re-certified).

On Solaris, the list of available crypto mechanisms is listed in the file /etc/security/crypt.conf.  The mechanism used for passwords is listed in the file /etc/security/policy.conf (the “CRYPT_DEFAULT=” line).  Some versions of Solaris use “unix” (which is really the old crypt mechanism under a different name) by default.

An SA should implement the password policy as part of the post-install procedures of any host.

The mechanism used to hash new passwords (when you run the passwd command) is defined by an option in the PAM module used to set passwords (e.g., “password sufficient pam_unix.so md5 ...”).

A password hash stored in /etc/shadow (or elsewhere) could have used any mechanism, so the one used must be stored with the password.  If the first character is not a dollar sign the old crypt mechanism is assumed.  Otherwise the first part is “$mechanism$”, where mechanism can vary depending on your system and which mechanisms are installed.

For Linux, the mechanisms are defined in the source for glibc2 as: $1$ (the BSD/Linux MD5), $5$ (SHA-256), and $6$ (SHA-512).  Other values are used on other systems: $md5$ (Solaris MD5 variant, supposedly harder to crack), $2a$, $2x$, or $2y$ (Blowfish, on OpenBSD and some Linux distros).  A flaw in the original Blowfish implementation was corrected in 2011; the newer version is identified as $2y$, while $2x$ is the old, buggy version with a unique name.  ($2a$ could be either version.)  These newer mechanisms can use up to 16 characters of salt.

You can see the list of supported mechanisms from your system's crypt(3) man page.  (See wikipedia.org/wiki/Crypt_(C) for more details.)

The Original Unix crypt Password Mechanism:

(Adapted from Robert Morris and Ken Thompson, Password Security: A case study, Published in Communications of the ACM, vol. 22, issue 11 (Nov. 1979), pages 594–597)

Although not used as much on modern systems it is instructive to examine how the crypt mechanism works:

  1. Read the first eight characters of the password (the rest is ignored).  If a shorter password is used, pad with zeros.    Using 7-bit ASCII this results in a 56 bit partial key.
  2. Next a 12 bit random value is chosen and encoded to form a two character string from the ASCII letters and digits.  This is called the salt.  Often the current time is used to generate the salt.
  3. The salt is added to the partial key to generate the longer key that is used with DES encryption.
  4. A message (a string of eight bytes initialized to all zeros) is then encrypted with DES using the key.  This results in 64 bits (eight bytes) of encrypted output.
  5. The encrypted output is used as the input message (in place of the zeros) and the encryption is repeated, for a total of 25 DES encryption cycles.  (Although DES encryption is used, the original message is known and thus this is more of a hash of the password than an encryption of the all zero message.)
  6. The 64 bit result is then encoded to be all printable characters (letters and digits ?and periods? only) that results in an 11 character ASCII string.
  7. The two character salt plus the 11 character encrypted text is stored in the password file.

To validate a user's password, the entered password plus the retrieved salt value is used to generate the 11 character result.  This result is compared, byte for byte, with the copy in the password file.

The salt serves several purposes:

Today implementations of DES are much faster, as is the hardware used.  A moderately priced cluster or multi-computer (SMP or multi-core system) can perform over 6 million DES encryption cycles per second.  Today's hard disk size also means that an opponent can pre-compute all possible 13 character crypt passwords at their leisure (there are 62^13 = 200,000,000,000,000,000,000), and quickly look up any given password. 

MD5 (and other) Password Mechanisms:

Today crypt should be considered insecure.  Instead passwords are encrypted using MD5 (rather than crypt).  (See RFC–1321.)  This is actually a hash of your entire password (not just the first 8 characters, and all 8 bits in the bytes are used, not just 7).

Next this is combined with a salt value of up to eight characters (not just two), selected from all letters, digits, period, and forward slash.  (If a two character salt increases the strength 4,000 times imagine how much harder it would be to crack the MD5 version of crypt with a variable length salt up to eight characters!)

The result is padded with a single 1 bit followed by 0 bits, to a length of 448 bits.

The length of the password is now appended as a 64 bit number.  This results in a message exactly 512 bits (64 bytes) long.  It has been discovered that adding the message length to the message greatly strengthens the security of the hash.

Finally the MD5 hash of this message is calculated.  The resulting hash is 128 bits (16 bytes).  It is then encoded as a string of 22 characters from letters, digits, slash and period (double the old crypt length).

You will notice a password stored in /etc/shadow begins with $1$.  This indicates that this is a password hashed using the MD5 algorithm.  The (up to) 8 characters following the second dollar sign compose the salt, also known as the seed.  Note that this is much larger than the two characters allocated for the older crypt method that used a plain DES-based hash.  Obviously, this allows for a more random hash value.  The salt is separated from the actual hash by a '$' character (unless the salt is the max length of 8 characters in which case the dollar-sign is optional).

Following the salt is the actual hash of the password.  The result stored in the shadow file looks like this: $1$salt$hash.

As with crypt in the 1970s, MD5 today is believed difficult to implement in hardware cheaply.  The huge range of hashes possible would be difficult to pre-compute and store on disk, and might take hundreds or thousands of years of constant computing to guess on relatively available computers today.  Multi-million dollar special password cracking computers could be built that could cut the time down to mere decades.  So, how often should you change your password to be safe?  (See discussion below.)

SHA–1 is a similar secure hashing algorithm.  It includes a specific 64 byte value that is added to the password and salt.  The resulting hash is 160 bits (20 bytes) long.  While some systems allow SHA–256, SHA–384, and SHA–512, for its intended use the MD–5 password hashes as used in the Unix/Linux shadow suite should be considered secure.  Methods that use these longer hashes that are similar to the current MD–5 scheme but use SHA–384 instead should be harder to crack.  The U.S. government has decided to phase out support for MD–5 in favor of SHA–384 or SHA–512, at least for digital signature applications.  (It is still allowed and considered safe to use MD5 for password hashing, last time I checked.) (See FIPS–180.)

Comparing Password Hashing Mechanisms:

In June 2012, 6.5 million LinkedIn password hashes were made public.  They used SHA-1, so it didn't matter, right?  Wrong.  Because SHA-1 uses a single iteration to generate hashes, it took security researcher Jeremi Gosney just six days to crack 90 percent of the list.  SHA-1, MD5, and a variety of other algorithms widely used to protect passwords are unsuited to the job, because they were designed to generate hashes quickly using a minimal amount of computing resources.  Compare that with the original crypt algorithm, which was specifically designed to take lots of time and resources to compute.

Today, there are better hashing algorithms for passwords known, such as Bcrypt, PBKDF2, or SHA512crypt, that take lots of memory and CPU cycles to generate.

The official SHA-1 specification calls for 1,448 distinct steps to calculate a hash.  By 2012, crackers had figured out how to reduce the number to 1,372, and by using special hardware instructions supported by GPUs, the number of steps needed was cut to 868.  Jens Steube (who is better known as Atom, as the pseudonymous developer of the Hashcat password-recovery program) then figured out a way to remove identical computations that are performed multiple times from the process of generating of SHA-1 hashes.  That reduced the number of steps needed to 734 (meaning those LinkedIn passwords could have been recovered in only 5 days).

In 12/2012, a researcher demonstrated a cluster of five servers equipped with 25 AMD Radeon GPUs, communicating at 10 Gbps and 20 Gbps over Infiniband switched fabric.  The machine is designed to brute-force crack passwords from their hashes.  The system was able to generate 348 billion NTLM password hash checks per second; a 14-character Windows XP password hashed using LM, for example, would fall in just six minutes.  The system is less effective against stronger hashing mechanisms; it “only” generates 77 million brute force attempts per second against MD5crypt, 71,000 guesses against Bcrypt, and 364,000 guesses against SHA512crypt.  (Note, these attacks depend on the attacker obtaining the password hashes.)  While the ability to crack such weak mechanisms is old news (Windows XP's LM hashes can be cracked using a rainbow table on one PC, in seconds), consider how easily the five server cluster could become a 5,000 server cluster and how that would work against SHA-1.

Centralized User/Password Databases:

Rather than a password data file per host, it makes sense to use a single central repository for user authentication information.  This supports single sign-on.  Some choices are: LDAP, NIS, NIS+, and Kerberos.  Take care to encrypt passwords while in transit across the network!

All real security policies require detection of old or rogue user accounts, as well as enforcing password strength (see below).  Only SOHOs use per-host password, group, and shadow files.  Larger organizations use a central repository.  In the past NIS/NIS+ were used, but today LDAP and Kerberos are common.  Very large organizations may use PeopleSoft or SAP HR (human resources) systems to manage employees.  You need some way to “diff” the HR system and the list of user accounts.  Note some user accounts for non-employees are always present, e.g., system accounts.

Once you have a list of valid accounts, you must monitor all systems (per host files and LDAP) for any changes.  Nagios, Samhain, or other monitoring systems can do that.  Auditors will want to know how you maintain the legitimate accounts list, and what your incident response policy is when unexpected changes are made.

How Often To Change Passwords:

It seems intuitive that to defeat a brute force attack you only need to change your password every so often.  A three month lifetime is commonly used in business organizations.  FIPS-112 requires the maximum lifetime of a password is one (1) year.  However, real-world results as well as mathematical analysis don't support this theory.  (Reference: Howard, Mike (mike@clove.com), how often should you change your password? published in ;login: Usenix vol. 31, no. 6 (12/2006), pages 48–51.)

Making users invent new passwords for each account several times a year forces users to pick poor passwords, use the same password everywhere (so if any one system is vulnerable, all your systems are), or write them down.  This is clearly bad security as well as highly annoying to users!  If the same password is used for POP3, IMAP and other services which transmits usernames and passwords in plain text, it won't be long before attackers get a copy of those passwords!

Writing down passwords is a good practice as long as you store them in a secure location, such as a wallet or purse.  If that gets lost along with your credit cards and other IDs, those passwords are just one more item you need to cancel.  Writing down passwords may be required for various legal compliance reasons, but in that case the passwords are often stored in a bank safe deposit box or other secure location with limited access.

It is safer to enforce good passwords and use a strong hashing algorithm (MD5 is okay for medium or low risk situations, SHA–384 or SHA–512 is currently good for high risk situations).  Having very strong passwords and using a strong hashing algorithm should mean you don't have to change passwords more than once every 3 to 5 years (or never).  This will be safer than using poor passwords that are quickly guessed.

Also consider using smart cards or biometrics (e.g., fingerprint scanner) instead of (or better, in addition to) passwords to authenticate users.

Regulatory compliance can determine how often an organization must change passwords.  PCI has the strictest policy requirements (as of 2011), and requires 90 day password rotation for systems dealing with protected credit card data and any infrastructure supporting such.  PCI also requires two-factor authentication for remote VPN access; a single password isn't sufficient.  (Certificates plus passwords are often used.)

Password Auditing:

It is possible to bypass the PAM mechanism and set a weak password (root can do that, or can copy some password hash and paste it in /etc/shadow.)  A good SA will periodically try to crack passwords, just to make sure only good passwords are used.  One such tool is John the Ripper, which is easy to install and use:

yum install john
unshadow /etc/passwd /etc/shadow >~/pwlist
john pwlist

(As of v1.7.3.4, JtR doesn't know about SHA hashes, but there is a patch.  You can DL the source, apply the patch, and build a working version.  This should have been fixed by now.)  Other checkers work well to audit Windows passwords (useful when using Samba for example).

Password Cracking:

In general, a passphrase is stronger (harder to guess) than a password, and good ones are easier to remember than good passwords.  The weak passwords users typically employ create a major vulnerability to password cracking attacks.

A 2012 commodity PC running a single AMD Radeon HD7970 GPU can try on average over 8 billion password combinations each second, depending on the algorithm used to scramble them.  Using botnets or clouds can bring thousands of such computers to bear on cracking a single key.

In 2012, a $12,000 computer called Project Erebus v2.5, contains eight AMD Radeon HD7970 cards, and requires just 12 hours to brute force the entire keyspace for any eight-character password containing upper- or lower-case letters, digits or symbols, using a version of the hashcat program.

An attacker can defeat password authentication in a number of ways.  (A good reason to use two factor authentication!)

If weak physical security is used, an attacker may be able to see a password as it is typed in.  Also, some people write down passwords, leaving the paper with the password lying around, or stored in unprotected files or in emails.  I suggest picking very strong passwords (perhaps generated ones) and writing down the password on a paper you keep on your person (i.e., a wallet or purse.)

Passwords can also be stolen with key loggers, a type of malware.

If weak passwords are allowed, many people will chose easily guessable passwords.  An attacker can do a bit of Internet search for a person to find their name, family members' names, pet names, car models they've owned (and license numbers), the addresses where they or their family has ever lived, etc.  This will yield a few hundred proper nouns and numbers.  By trying combinations and simple variations, a surprisingly high percentage of passwords can be cracked.  In a dictionary attack a standard (English) dictionary of words and proper nouns are tried, including simple variations (e.g., reverse, mix in a few digits, strange capitalization, substitute one for ell, zero for oh, eight for bee, etc.)  Using PAM cracklib or other system settings to prevent weak passwords is effective.  Using password auditing software (such as John the Ripper) can be even more effective.

In 6/2012, 6 million LinkedIn passwords were stolen, cracked, and published.  These and other stolen password lists have allowed security firms to compile a list of the 25 weakest, worst passwords that are still popular:
password, 123456, 12345678, qwerty, abc123, monkey, 1234567, letmein, trustno1, dragon, baseball, 111111, iloveyou, master, sunshine, ashley, bailey, passw0rd, (a space), shadow, 123123, 654321, superman, qazwsx, michael, and football.  Other cracked popular passwords include ihatemyjob, f***mylife (and other profane passwords), nobama, iwantanewjob, and strongpassword.  The list is now compiled each year by SplashData, from stolen password lists that were published.  See their list of worst passwords of 2012.

The security hashing scheme used (e.g., MD5) may have flaws unknown to any but an attacker.  However this is extremely unlikely!  (As mentioned previously, flaws in MD5 were discovered in 2008.  (For this reason Fedora 11 uses SHA-256 or SHA-512 everywhere (passwords, package digests, etc.)

The final method of cracking passwords is a brute force attack.  Here the attacker tries all possible passwords until one works.  The strength of various encryption and secure hashing methods is measured by counting how hard such a brute force attack would be.  Statistically speaking if there are N possible passwords an attacker would on average need to try N/2 of them.  Since only so many passwords can be hashed per second and compared with some hashed result on modern (and predicted) hardware, you can estimate how many days/months/years it would take to crack a password.  The original Unix crypt algorithm would take less than a week on a modern COTS computer.

[Adapted from Anatomy of a crack Ars Technica Post 5/28/13]
Ars asked three experts to crack passwords.  The list contained 16,449 passwords converted into hashes using the MD5.  One expert's first stage cracked 10,233 hashes, or 62 percent of the leaked list, in just 16 minutes.  It started with a brute-force crack for all passwords containing one to six characters, meaning his computer tried every possible combination starting with “a” and ending with “//////”.  Because guesses have a maximum length of six and are comprised of 95 characters — that's 26 lower-case letters, 26 upper-case letters, 10 digits, and 33 symbols — there are a manageable number of total guesses.  This is calculated by adding the sum of 956 + 955 + 954 + 953 + 952 + 95.  It took just two minutes and 32 seconds to complete the round, and it yielded the first 1,316 plains [passwords] of the exercise.

The first stage of each attack typically cracked in excess of 50 percent of the hashes, with each stage that came later cracking smaller and smaller percentages.  By the time they got to the latest rounds, they considered themselves lucky to get more than a few hundred plains.  Beyond a length of six, however, Gosney was highly selective about the types of brute-force attacks he tried.  That's because of the exponentially increasing number of guesses each additional character creates.  While it took only hours to brute-force all passwords from one to six characters, it would have taken Gosney days, weeks, or even years to brute-force longer passwords.  ...  He took a good word list and tried adding every possible 2-character combo of digits and symbols to the end, then three, then four. Next he appended each possible 4-digit number to the end, and finally tried appending four lowercase letters or digits.  This was repeated by prepending and splitting (adding the extra characters in the middle).  In under 5.5 hours, over 78% of all passwords were cracked.

It turns out that passwords on any given site are similar, even if the users don't know each other.  For the final phase of the cracking exercise, Gosney generated a statistical model of my likely passwords from the ones already cracked, and use that list to brute-force the rest.  The model, Markov attack, guesses all possible passwords with a given length and a number of the most likely characters for each position.  For length of seven and only 65 characters (of 95), it drops the keyspace of a classic brute-force from 957 to 657, a benefit that saves an attacker about four hours.

Like SHA1, SHA3, and most other algorithms, MD5 was designed to convert plaintext into hashes quickly and with a minimal amount of computation.  That works in the favor of crackers.  Armed with a single graphics processor, they can cycle through more than eight billion password combinations each second when attacking “fast” hashes.  By contrast, algorithms specifically designed to protect passwords require significantly more time and computation.  For instance, the SHA512crypt function included by default in Mac OS X and most Unix-based operating systems passes text through 5,000 hashing iterations.  This hurdle would limit the same one-GPU cracking system to slightly less than 2,000 guesses per second.  Examples of other similarly “slow” hashing algorithms include bcrypt, scrypt, and PBKDF2.

Today an attacker has additional tools available to speed up the cracking process:

Russian-based "password recovery" company Elcomsoft was in the news in 2003 when Adobe had one of the company's programmers, Dmitry Sklyarov, arrested for cracking its eBook Reader software.  Elcomsoft's new password cracking method attacks the NTLM hashing in Windows using brute force and a GPU.  The company claims this speeds up the time it takes to crack a Vista password from two months to a little over three days.  Elcomsoft says they have filed for a US patent on this approach.

In 2008, an Elcomsoft spokesman said that without dictionary words being involved, cracking WPA and WPA2 (the password, or keys, used for wireless networking) is still quite intensive: perhaps three months to crack a lowercase-only random eight-character password using a PC with two Nvidia GTX 280 video cards.

(In September of 2009, computer scientists in Japan reported they've developed a way to break the WPA encryption system in about one minute.  The attack works only on WPA systems that use the Temporal Key Integrity Protocol (TKIP) algorithm.  They do not work on newer WPA2 devices or on WPA systems that use the stronger Advanced Encryption Standard (AES) algorithm.)

Preventing Brute Force Attacks:

As mentioned above (how often to change passwords), forcing users to frequently change passwords (and not reuse old passwords) is a common practice, but one that doesn't help improve security.

Two common ways to thwart such brute force attacks are account lockouts and forced delays.  With account lockouts a number of incorrect attempts (e.g., 3 to 5) in a row locks an account either for a pre-determined number of minutes or until manually unlocked.  This method can be used in a DoS attack, preventing the legitimate user from accessing the account.

With forced delays a delay of a few seconds is used before returning the result.  This limits how many attempts can be made to a one or two dozen per minute, and is the common Unix approach.  Additionally after a number of unsuccessful attempts the connection is dropped (further delaying the attacker who must now negotiate a new TCP/IP (and SSH) connection.  Note that unlike account lockouts, this method doesn't lend itself to a DoS attack.

It can be effective to limit the number of network attempts per minute to your SSH port.  (Changing that from port 22 will only stop script-kiddies who don't bother to run a port scan first.  But that may be a lot of attempts!)

The problem with this is low and slow attacks: attacks meant to be slow enough that IDS systems aren't tripped, but fast enough where the attacker has a decent chance of getting access.  Typically, there are about one or two attempts per minute against the root (or other) account, each coming from a different IP address (maybe a botnet).  While this doesn't sound like much, it's enough for an attacker to cycle through 1440 common passwords in a single day.  Admins who use passwords like “root”, “test”, “admin”, “password”, etc., are likely to fall victim.  A good IDS/IPS system such as ossec should be used and tuned to prevent such attacks (and don't forget using cracklib to enforce strong passwords!)

SRP is the Stanford Secure Remote Password protocol.  It is a public key cryptosystem designed to securely store and validate passwords without storing them in the clear or transmitting them in the clear.  This is similar to MS-CHAPv2.  While the University of Stanford holds a patent on this method, it is available for use for free.  The WoW and Warcraft III systems use SRP.  The IETF has standards for it, RFC-2945 (SRP) and RFC-5054 (TLS-SRP).

Never send any passwords through email.  It goes through too many hops unencrypted, gets indexed by search features on email servers, etc.  Login names can be sent this way, but passwords must go by SMS, or voice, or telegram, or postal mail.

The French government has passed a law requiring organizations such as Google, Yahoo, etc., to record and save user's personal data, including their passwords, and to turn them over to authorized (French) government agencies when legally requested.  This is being challenged in the French Supreme Court (2011).

The interesting part to me is about saving passwords.  Currently no major company saves those, so there is no way to turn them over to anyone.  But if they are saved, there is a possibility they can be stolen or exposed.  In addition, if organizations do save such personal data for the French, it will also be available to other governments, such as the U.S. (using a National Security Letter, or NSL, under the Patriot Act) with no warrant required, and no notice given.

Once good way to help protect yourself is to use different passwords for each on-line site.

Keeping passwords different for every website can be difficult, but there are several techniques you can use to help.  One is to use a mnemonic technique, combining the site or project name with a standard password you always use (and can remember).

For instance, say your standard password is CatDogRat.  (I would hope it is stronger, something like “:xT9/qwB”; try apg to make one.)  The last few letters (or last+first) of the site name goes between the Cat and Dog, and the number of letters of the site name (or the difference between that and the number of letters in the username used on that site) goes between Dog and Rat.  So my password for the site wpollock.com would be CatckDog8Rat.  Of course, the standard password should not be words but a normal, strong password.  Using such a mnemonic means one can use a different and strong password for every site, while only having to remember one good password.

Of course there are many possible mnemonic techniques you can use.  Here's another:  Take the first letters of a sentence you like, say the first line from the poem “Jabberwocky”:  Twas brillig, and the slithy toves”, gives “Tbatst”, add (say) every other character of your user name (e.g., “wpollock” gives “wolc”) to get “TbatstWolc”.  Then add (say) every 3rd character from the site name, e.g. hccfl.edu yields “TbatstWolcHfd”, and finally convert all lowercase letters to 7331-speak (or “leet-speak”), giving a final password of something like “T8@7$7W0LChFd”.  The idea is that the password is strong, hard to guess, and different for every site.  But if you forget it, you can easily recreate it by remembering the poem and the general method used.

Another technique is to use a password manager.  This is software that stores your user IDs and passwords for various websites, mail services, etc., in a securely encrypted file.  To use any of the passwords, you only need to remember one (very strong!) master password.  Some popular password manager software is included with web browsers (e.g., Firefox Sync and Xmarks) and MUAs, and there are stand-alone ones such as gpg-agent, ssh-agent, and keyring for Linux and Unix systems.  Some others include LastPass, KeePass, and 1Password.  The encrypted password files can be backed up on a service such as DropBox or Box.net.  With this method, you can use a password generator such as “apg” or “pwgen” to create very strong, different passwords for every site (and for the one master password you must remember).

Microsoft's Safety & Security Center provides a guide on creating strong passwords, which includes using Microsoft's online password strength checking service.  See also Google's guide to creating sensible and more secure passwords.

One last point:  Many websites allow a password reset using your email address.  So if an attacker gains access to your email, they can reset your passwords!  Protect your email accounts with very strong passwords.

Facebook has a new system for resetting passwords: Trusted Contacts.  This feature requires the help of several friends you designate in advance.  If a user forgets their password or is otherwise locked out of an account, they can request that Facebook send different one-time security codes to up to five friends.  You then contact your friends to get the codes; hopefully, they won't give them to anyone but you.  Once the user supplies three of the security codes sent, Facebook will reset the account password.

Random Numbers

The heart of cryptography is the use of random numbers.  (See RFC 4086, Randomness Requirements for Security.  Basically, the numbers should be evenly distributed in their range, and completely unpredictable.)  But, how can a computer generate high quality (truly random, or at least totally unpredictable by an attacker)?  FIPS-140-2 contains tests of random number sequence quality; see testrng(1)

The original Netscape web browser used a 40-bit random number to generate the keys for HTTPS.  However, this number wasn't truly random, composed of the current time, the PID and the PPID.  Even in 1995 it would only take about 30 hours to crack such a key; as an attacker knows the current time (roughly), and can guess the PPID (and possibly the PID too) fairly easily.

In Unix or Linux, /dev/random is usually a special file that serves as a random number generator (RNG) or as a pseudo-random number generator (PRNG).  It allows access to environmental noise collected from device drivers and other sources (for example, the number of milliseconds between key presses or mouse clicks, the time between TCP packet arrivals, the seek time of the disk since the last head movement, etc).  All these random numbers are stored in a list called the entropy pool by the kernel.  As each value is added, the kernel adds to the estimate of the available entropy.  When /dev/random is read, the data from the pool is hashed using a cryptographically secure hashing algorithm (e.g., SHA-256), the results are returned, and the estimate of available entropy is decremented.

Random numbers are used for more than just key generation.  For example, TCP sequence numbers need to be random.  Also, a lack of randomness can lead to DoS attacks against web applications.  (Web application servers or platforms commonly parse POST form data into hash tables automatically, so that they can be accessed by the application.  If the programming language used does not provide a randomized hash function, or the application server does not recognize attacks using multi-collisions, an attacker can degenerate the hash table by sending lots of colliding keys.  The algorithmic complexity of inserting n elements into the table then goes to O(n**2), making it possible to exhaust hours of CPU time using a single HTTP request.)

Although not all systems implement /dev/random this way, this method does provide cryptographically secure random numbers.  However, any attempt to read more random bits than the entropy pool currently contains will block the reader, which must wait for more random noise to be added to the pool.  Linux was the first operating system to implement a true RNG this way (Theodore Ts'o's implementation for /dev/random in 1994).  This feature can be exploited in a side-channel attack; an attacker can obtain keyboard interrupt timings by exhausting the pool and waiting.  Some patches by Ts'o in 2012 mitigate this and other issues.

In 11/2012, another side-channel attack was reported.  Researchers have devised a virtual machine that can extract private cryptographic keys stored on a separate virtual machine when it resides on the same piece of hardware.  The technique they used took several hours to recover the private key for a 4096-bit El Gamal-generated public key (used with GPG and elsewhere).  You can read the details from Ars Technica.

For years, one could obtain true random number from lavarand.com, which set up digital cameras in front of some lava lamps in their server room.  The digital photos were then hashed using SHA-1 and the result was a truly random number.  A replacement service is available since 11/2011, from lavarnd.org.

On Linux, there is also /dev/urandom, which works the same except that if the entropy pool runs out, it uses PRNG techniques and so will never block.  But the quality (“randomness”) suffers.  That can be taken into account by the software using it, by using a secure one-way function to reseed frequently.  But most people forget to do so when implementing their own security system.  (So don't do that.)

On some (BSD at least) systems, /dev/random is reserved for hardware RNG (e.g., counting cosmic ray particles per second that hit the chip).  These OSes have /dev/srandom that is similar to Linux /dev/random.

In 2008, Debian-based Linux systems were patched to fix a serious bug in the random number library.  It didn't use any source for random numbers correctly, resulting in perfectly predictable numbers!  Some SSL certificates, and even some CA certificates were generated using the broken random number library, although all known ones were quickly revoked.  (From the Register.)

Using pseudo-random numbers for security results in pseudo-security. — Unknown

Random numbers should not be generated with a method chosen at random. — Donald Knuth

Modern systems make the /dev/random method of random number generation invalid, as solid-state disks and virtual hardware eliminate those sources of random data, or make them less random.  This has been a long-known problem with embedded systems such as those found on routers and switches.  Reportedly, 1 in 250 SSL or SSH keys generated by these devices can be broken by an attacker in a matter of hours.  This happens because OpenSSH and OpenSSL rely on the quality of random numbers from /dev/random.  But they didn't have to!

A related problem is that during or just after booting, the entropy pool is empty.  Many systems generate host keys then, and between 5% and 10% of such keys wind up as identical.  This is not good.  Recent patches to Linux have added a bunch of data to the pool at boot time, such as MAC address, serial numbers of attached devices, etc.  While not random, such data does vary from system to system and may be hard for an attacker to predict.

Recently (2011), Intel has added new random number generator hardware (“Bull Mountain”) for their CPUs, which can generate truly random numbers.