Linux/Unix Password Hashing Algorithm(s)
Focus of the data gathered for this section concerns the following flavors of *NIX based operating systems, mainly the following versions used:
Red Hat Enterprise 3.0
Solaris 7, 8, 9, and 10
Unix Hashing Algorithm (aka the crypt(3) function) – This is the traditional stuff in *NIX based systems:
General Information can be found at: http://en.wikipedia.org/wiki/Crypt_(Unix)
http://vorlon.case.edu/~jrh29/paper.pdf (excellent paper) the following were the important parts:
DES and its Weaknesses
According to Robert Morris, the original author of the crypt(3) function, the original algorithm used in crypt(3) was far too fast, so a slower algorithm needed to be created. This was DES, standardized by the National Bureau of Standards (now the National Institute of Standards and Technology). and designed to be slow when implemented in software. The Data Encryption Standard was first developed in 1988 and later revised in 1993 to fix some weaknesses. UNIX and UNIX-like systems use a variation of the DES algorithm with extensions to discourage hardware implementations of key searches.
The DES algorithm used in the crypt(3) function on many UNIX-like systems, including
Linux and FreeBSD, works as follows:
1. A random 2 character (12 bits, as only the lower 6 bits are used) is chosen to hash the password.
2. The password is truncated to 8 characters, and the lower 7 bits of each character, since the algorithm is only a 56-bit hash.
3. The password itself is perturbed in one of 4096 ways (using the salt), following the DES algorithm.
4. This string is used to repeatedly encrypt a constant string, usually all NUL characters, but may be different. In one implementation, it encrypts the string 25 times.
5. The resulting string is repacked into 11 printable characters, and stored in the password file, usually /etc/passwd.
As the listing suggests, DES encrypted passwords only allow a maximum of 8 characters in the password. For this reason, the MD5 digest algorithm replaced the DES algorithm for many implementations, as it allows a maximum of 127 characters in the password, much stronger than DES passwords. Additionally, DES encrypted passwords have a keyspace of only 256, or 7.2 1016, which makes exhaustive searches of the namespace feasible using massively parallel systems. Although DES is slow in software, there are several chips that are commercially available which perform DES encryption. These chips are as much as three orders of magnitude faster than software implementations, but are very expensive. Additionally, to slow down the chips, the internal tables are wired to depend on the random salt. The only thing preventing an attacker from using one of these chips is the unthinkable cost associated with a custom chip, since commercial chips are crippled.
MD5 and Shadow Passwords
MD5 is an extension to the cryptographically weak MD4 algorithm. Among other additions, it adds a fourth iteration to the algorithm, to decrease its vulnerability to two-round attacks. However, it is still not proven cryptographically strong. In fact, it may be subject to the two-round attack against the MD4 algorithm, or at least a variation of it. However, it is still more secure than MD4, although to what degree is unknown. The MD5 algorithm works as follows (from [10]):
1. The password is padded to a length congruent to 448 modulo 512 (also -64 mod 512). The padding is performed as follows: A single “1” bit is appended, followed by zero or more “0” bits, until it is congruent to 448 mod 512. At least 1 bit, and at most 512 bits are appended.
2. A 64-bit representation of the length of the password before padding is appended to the padded password.
3. Four 4-word registers are initialized with the following values to compute the message digest:
• Word A: 01 23 45 67
• Word B: 89 ab cd ef
• Word C: fe dc ba 98
• Word D: 76 54 32 10
4. The password is encrypted as in Appendix A.
5. The password is output in the registers (A,B,C,D). This password is generally stored in the password file as $1$<string>$, where <string> consists of an 8-byte salt (as opposed to the 2-byte salt of DES), followed by a 22 character string from the characters [a-zA-Z0-9./].
MD5 passwords are used on Linux, BSD, Solaris, and probably most other UNIX and UNIX-like systems, although most systems still default to DES for backwards compatibility.
This may also be by design, to ensure that system administrators understand the system that they are deploying, and lock it down themselves, instead of blind deployment, which is done in many corporate settings. Linux and other UNIX-like operating systems, such as Solaris and Mac OS version 10.3 use shadow passwords. Shadow passwords hide the actual password in a separate file, so as to be unviewable by normal users, and placing all the relevant data into the global password file. This augments the security of MD5 password hashes, by preventing users from reading the hash. Shadow passwords improve security of passwords greatly, since most login systems allow only 3 login attempts before locking the user out for a period of time. This prevents brute-force attacks, by allowing time for the system administrator to lock a user’s account before the password is cracked. MD5 is considered strong enough for most cases, however it is recommended to use SHA-1, as it is 160-bit encryption, and has been found to be collision resistant. Nothing can be completely collision proof. Blowfish is another very strong algorithm, and has been uncrackable as of yet. (There are more details on this, but since they’re not being used on Red Hat or Solaris I’ll skip it; Also there’s a whole appendix to this paper that details the MD5 algorithm).
Blowfish
Blowfish is a relatively new algorithm developed by Bruce Schneier in 1993. It is a secret key cipher, with the block size being 64-bits, and the key size being any length up to 448 bits. From [1], “data encryption occurs via a 16-round Feistel network.” Each round consists of a key permutation and a key and data substitution. All operations are on 32 bit words, and consist only of XOR and addition operations, along with four indexed array lookups during each round. [8] Blowfish uses 18 32-bit subkeys, which must be precomputed before any encryption. These subkeys are generated in this case from the user’s password. These subkeys are labelled P1, …P18 and are collectively known as the P Array ([8]). The encryption of the Blowfish algorithm is done as follows:
1. Each 64-bit block is divided into two 32-bit blocks, labelled L0 and R0.
2. L0 is XORed against P1, and the result is XORed against R0. The two halves are then swapped. This is repeated 15 times, with keys P2 − P16, using Li−1 and Ri−1, from 2 i 16. This process uses four arrays called Substitution Boxes, or S-boxes.
3. After 16 iterations, the halves are swapped again, undoing the last swap, and each half is XORed with another key, as follows:
• R17 = L16 P17
• L17 = R16 P18
EksBlowfish uses Blowfish for actual encryption, only the subkey generation algorithm differs. The EksBlowfish algorithm initializes the subkey generation using parameters for cost, salt, and key. The cost parameter “controls how expensive the key schedule is to compute.” ([8]). The salt is a 128-bit random number, used so that the same key need not generate the same hash. Finally, the key is the user’s password.
The keys are generated by first copying the digits of into the subkeys, then into the S-boxes. Then the P-Array and S-boxes are modified using the 128-bit salt, and the key. First, the P-Array is XORed with the key, XORing the first 32 bits of the key with P1, the second 32-bits with P2, and so on. If the key runs out of bits, it cycles back to the beginning, and continues to XOR with the subkeys. The first 64 bits of the salt are then blowfish encrypted using the current state of the key. The result replaces P1 and P2. The result is also XORed with the second 64 bits of the salt, and this result is then encrypted with blowfish, replacing subkeys P3 and P4. This is then XORed with the first 64 bits of the salt, and replaces P5 and P6. The process continues until all 18 subkeys are replaced, and the S-boxes. This final set of subkeys is then used to encrypt a constant string. In OpenBSD, the string is ”OrpheanBeholderScryDoubt”. The password is then stored in /etc/passwd. Since the Blowfish algorithm has not been cracked, some may consider it safe to keep in /etc/passwd, even though it is readable by everyone.
Cracking UNIX Passwords
The Shadow password suite was designed to prevent people from getting a hold of the password listing, since given the password listing, one can crack a large number of passwords, since it is statistically proven that many people use dictionary passwords.
There are two popular UNIX password crackers on the internet today: Crack and John the Ripper, both using compiled dictionaries as a crack reference. Crack was one of the earliest, and still powerful crackers. However, John the Ripper is more popular, as it can enumerate dictionary entries into so-called “leet-speak” and subtle misspellings. Dictionary crackers, although very useful, may be against institution policy, or, in some cases, even illegal. Some system administrators have even been fired and/or put in jail for using dictionary crackers for auditing purposes. Anyone wishing to perform even light password checking should do so with the consent of his/her boss, to make sure it complies with company policy. Because of this, some password suites, such as PAM (see further data gathered on this, relevant to our research), later discussed, use libcrack, a password cracking library and weak-password verifier, to verify the strength of passwords, and prevent the unintentional, or even intentional, use of weak passwords. Some network policies even force constraints on passwords, such as requiring punctuation as well as alphanumeric (both upper and lowercase) and requiring passwords to have a certain minimum length, the most popular being 8 characters minimum.
Red Hat Linux
http://www.linux.com/feature/39115 — Red Hat Enterprise Linux AS 3.0 uses the PAM Framework. The framework uses three password methods:
The first, pam_cracklib.so, checks the password against common words and disallows them as passwords. We have it set to allow three attempts to find a non-dictionary password; this method is set to required. After checking the word, pam_unix is used with this method. For hardening a system, we'll want to remove nullok, which would allow a blank password. We're also set up for using an authentication token (already supplied password), md5, and shadow passwords. The use_authtok parameter tells the module to use the already supplied password instead of prompting for it. Since the user was already prompted for a password, this is obviously good behavior, and ensures that the password has been through pam_cracklib.so.
The md5 parameter says that the system should have the password using the Message Digest 5 hashing function. This function is more secure than the traditional DES-based Unix password hashing method.
Finally, the shadow parameter tells the module to store the password hash in the /etc/shadow file, which should only be accessible to the root user ID, rather than in the traditional /etc/password file, which is world-readable. This module is marked as sufficient, because it's followed by the "default deny" of pam_deny.so.
Sun Solaris
Solaris 9 Update 2 and forward give several hashing options:
http://blog.unix-security.net/2007/02/07/md5-password-hashing-on-solaris/
Starting with Solaris 9 12/02 Solaris now supports using MD5 password hashing, instead of the legacy DES hashing used by crypt(). Using MD5 has several advantages. With MD5, passwords can be longer than 8 characters, and are much harder to crack.
Unfortunately, this functionality is not enabled by default
Details on this options available from:
http://learningsolaris.com/archives/2006/01/19/password-hashing-algorithm/
From Solaris 9 update 2, a new framework was introduced that would make it possible to select among a number of hash algorithms the famous one that would be used to compute the encrypted version of the passwords. Before that time, the traditional crypt() routine was used, limiting the size of passwords to 8 characters and providing the even more famous 13 characters found in the /etc/shadow file.
The Solaris Pluggable Crypt Framework makes it possible to choose from 3 new algorithms, all allowing a maximal password size of 255 characters:
- cat /etc/security/crypt.conf
(…)
1 crypt_bsdmd5.so.1
2a crypt_bsdbf.so.1
md5 crypt_sunmd5.so.1
What are these libraries?
From the man pages:
- man crypt_bsdmd5
(…)The crypt_bsdmd5 module is a one-way password hashing module for use with crypt(3C) that uses the MD5 message hash algorithm. (…) The output is compatible with md5crypt on BSD and Linux systems.
- man crypt_bsdbf
(…)The crypt_bsdbf module is a one-way password hashing module for use with crypt(3C) that uses the Blowfish cryptographic algorithm. (…)
- man crypt_sunmd5
(…)The crypt_sunmd5 module is a one-way password hashing module for use with crypt(3C) that uses the MD5 message hash algorithm. (…)
Solaris 10
http://www2.petervg.nl/cgi-bin/docs.cgi?a=read&doc=81