Crypt (C)

crypt is the library function which is used to compute a password hash that can be used to store user account passwords while keeping them relatively secure (a passwd file). The output of the function is not simply the hash – it is a text string which also encodes the salt (usually the first two characters are the salt itself and the rest is the hashed result), and identifies the hash algorithm used (defaulting to the "traditional" one explained below). This output string is what is meant for putting in a password record which may be stored in a plain text file.

More formally, crypt provides cryptographic key derivation functions for password validation and storage on Unix systems.

Relationship to Unix crypt utility

There is a crypt utility in Unix, which is often confused with the C library function. To distinguish between the two, writers often refer to the utility program as crypt(1), because it is documented in section 1 of the Unix manual pages, and refer to the C library function as crypt(3), because its documentation is in manual section 3.

Details

This same crypt function is used both to generate a new hash for storage and also to hash a proffered password with a recorded salt for comparison.

Modern Unix implementations of the crypt library routine support a variety of different hash schemes. The particular hash algorithm used can be identified by a unique code prefix in the resulting hashtext, following a de facto standard called Modular Crypt Format.^[1][2][3]

The crypt() library function is also included in the Perl,^[4] PHP,^[5] Pike,^[6] Python,^[7] and Ruby^[8] programming languages.

Key derivation functions supported by crypt

Over time various algorithms have been introduced and to enable backward compatibility each scheme started using some convention of serializing the password hashes that later was called Modular Crypt Format (MCF).^[2] Since any standard wan't formed at beginning and old crypt(3) hashes may vary from schemes to scheme. During Password Hashing Competition was formed an following format that represents and average form:^[9]

$<id>[$<param>=<value>(,<param>=<value>)*][$<salt>[$<hash>]]

where

• id an identificator of scheme that representing the hashing algorithm (such as 1 for MD5, 5 for SHA-256 etc.)
• param name and its value: hash complexity parameters, like rounds/iterations count.
• salt Base64-like encoded salt
• hash Base64-like encoded result of hashing password and salt.

Original implementation using the password as a key

The original implementation of the crypt() library function^[10] in Third Edition Unix^[11] mimicked the M-209 cipher machine. Rather than encrypting the password with a key, which would have allowed the password to be recovered from the encrypted value and the key, it used the password itself as a key, and the password database contained the result of encrypting the password with this key.

Traditional DES-based scheme

The original password encryption scheme was found to be too fast and thus subject to brute force enumeration of the most likely passwords.^[10] In Seventh Edition Unix,^[12] the scheme was changed to a modified form of the DES algorithm. A goal of this change was to make encryption slower. In addition, the algorithm incorporated a 12-bit salt in order to ensure that an attacker would be forced to crack each password independently as opposed to being able to target the entire password database simultaneously.

In detail, the user's password is truncated to eight characters, and those are coerced down to only 7-bits each; this forms the 56-bit DES key. That key is then used to encrypt an all-bits-zero block, and then the ciphertext is encrypted again with the same key, and so on for a total of 25 DES encryptions. A 12-bit salt is used to perturb the encryption algorithm, so standard DES implementations can't be used to implement crypt(). The salt and the final ciphertext are encoded into a printable string in a form of base64.

This is technically not encryption since the data (all bits zero) is not being kept secret; it's widely known to all in advance. However, one of the properties of DES is that it's very resistant to key recovery even in the face of known plaintext situations. It is theoretically possible that two different passwords could result in exactly the same hash. Thus the password is never "decrypted": it is merely used to compute a result, and the matching results are presumed to be proof that the passwords were "the same."

The advantages of this method have been that the hashtext can be stored and copied among Unix systems without exposing the corresponding plaintext password to the system administrators or other users. This portability has worked for over 30 years across many generations of computing architecture, and across many versions of Unix from many vendors.

Weaknesses of the traditional scheme

The traditional DES-based crypt algorithm was originally chosen because DES was resistant to key recovery even in the face of "known plaintext" attacks, and because it was computationally expensive. On the earliest Unix machines it took over a full second to compute a password hash. This also made it reasonably resistant to dictionary attacks in that era. At that time password hashes were commonly stored in an account file (/etc/passwd) which was readable to anyone on the system. (This account file was also used to map user ID numbers into names, and user names into full names, etc.).

In the three decades since that time, computers have become vastly more powerful. Moore's Law has generally held true, so the computer speed and capacity available for a given financial investment has doubled over 20 times since Unix was first written. This has long since left the DES-based algorithm vulnerable to dictionary attacks, and Unix and Unix-like systems such as Linux have used "shadow" files for a long time, migrating just the password hash values out of the account file (/etc/passwd) and into a file (conventionally named /etc/shadow) which can only be read by privileged processes.

To increase the computational cost of password breaking, some Unix sites privately started increasing the number of encryption rounds on an ad hoc basis. This had the side effect of making their crypt() incompatible with the standard crypt(): the hashes had the same textual form, but were now calculated using a different algorithm. Some sites also took advantage of this incompatibility effect, by modifying the initial block from the standard all-bits-zero. This did not increase the cost of hashing, but meant that precomputed hash dictionaries based on the standard crypt() could not be applied.

BSDi extended DES-based scheme

BSDi used a slight modification of the classic DES-based scheme. BSDi extended the salt to 24 bits and made the number of rounds variable (up to 2²⁴-1). The chosen number of rounds is encoded in the stored password hash, avoiding the incompatibility that occurred when sites modified the number of rounds used by the original scheme. These hashes are identified by starting with an underscore (_), which is followed by 4 bytes representing the number of rounds.

The BSDi algorithm also supports longer passwords, using DES to fold the initial long password down to the eight 7-bit bytes supported by the original algorithm.

MD5-based scheme

Poul-Henning Kamp designed a baroque and (at the time) computationally expensive algorithm based on the MD5 message digest algorithm. MD5 itself would provide good cryptographic strength for the password hash, but it is designed to be quite quick to calculate relative to the strength it provides. The crypt() scheme is designed to be expensive to calculate, to slow down dictionary attacks. The printable form of MD5 password hashes starts with $1$.

This scheme allows users to have any length password, and they can use any characters supported by their platform (not just 7-bit ASCII). (In practice many implementations limit the password length, but they generally support passwords far longer than any person would be willing to type.) The salt is also an arbitrary string, limited only by character set considerations.

First the passphrase and salt are hashed together, yielding an MD5 message digest. Then a new digest is constructed, hashing together the passphrase, the salt, and the first digest, all in a rather complex form. Then this digest is passed through a thousand iterations of a function which rehashes it together with the passphrase and salt in a manner that varies between rounds. The output of the last of these rounds is the resulting passphrase hash.

The fixed iteration count has caused this scheme to lose the computational expense that it once enjoyed and variable numbers of rounds are now favoured. In June 2012, Poul-Henning Kamp declared the algorithm insecure and encouraged users to migrate to stronger password scramblers.^[13]

Blowfish-based scheme

Niels Provos and David Mazières designed a crypt() scheme called bcrypt based on Blowfish, and presented it at USENIX in 1999.^[14] The printable form of these hashes starts with $2$, $2a$, $2b$, $2x$ or $2y$ depending on which variant of the algorithm is used:

• $2$ – Currently obsolete
• $2a$ – The current key used to identify this scheme. Since a major security flaw was discovered in 2011 in a third-party implementation of the algorithm,^[15] hashes indicated by this string are now ambiguous and might have been generated by the flawed implementation, or a subsequent fixed, implementation. The flaw may be triggered by some password strings containing non-ASCII characters, such as specially crafted password strings.
• $2b$ – Used by some recent implementations^[16] which include a mitigation to a wraparound problem. Previous versions of the algorithm have a problem with long passwords. By design, long passwords are truncated at 72 characters, but there is an 8-bit wraparound problem^[17] with certain password lengths resulting in weak hashes.
• $2x$ – Post-2011 bug discovery, old hashes can be renamed to be $2x$ to indicate that they were generated with the broken algorithm. These hashes are still weak, but at least it's clear which algorithm was used to generate them.
• $2y$ – Post Post-2011 bug discovery, $2y$ may be used to unambiguously use the new, corrected algorithm. On an implementation suffering from the bug, $2y$ simply won't work. On a newer, fixed implementation, it will produce the same result as using $2a$.

Blowfish is notable among block ciphers for its expensive key setup phase. It starts off with subkeys in a standard state, then uses this state to perform a block encryption using part of the key, and uses the result of that encryption (really, a hashing) to replace some of the subkeys. Then it uses this modified state to encrypt another part of the key, and uses the result to replace more of the subkeys. It proceeds in this fashion, using a progressively modified state to hash the key and replace bits of state, until all subkeys have been set.

The number of rounds of keying is a power of two, which is an input to the algorithm. The number is encoded in the textual hash, e.g. $2y$10...

NT hash scheme

FreeBSD implemented support for the NT LAN Manager hash algorithm to provide easier compatibility with NT accounts.^[18] The NT-Hash algorithm is known to be weak, as it uses the deprecated md4 hash algorithm without any salting.^[19] FreeBSD used the $3$ prefix for this. Its use is not recommended, as it is easily broken.^[20]

SHA2-based scheme

The commonly used MD5 based scheme has become easier to attack as computer power has increased. Although the Blowfish-based system has the option of adding rounds and thus remain a challenging password algorithm, it does not use a NIST-approved algorithm. In light of these facts, Ulrich Drepper of Red Hat led an effort to create a scheme based on the SHA-2 (SHA-256 and SHA-512) hash functions.^[21] The printable form of these hashes starts with $5$ (for SHA-256) or $6$ (for SHA-512) depending on which SHA variant is used. Its design is similar to the MD5-based crypt, with a few notable differences:^[21]

• It avoids adding constant data in a few steps.
• The MD5 algorithm would repeatedly add the first letter of the password; this step was changed significantly.
• Inspired by Sun's crypt() implementation, functionality to specify the number of iterations (rounds) the main loop in the algorithm performs was added^[22][23]

The specification and sample code have been released into the public domain.^[24]

Support in operating systems

Archaic Unix schemes

BigCrypt is the modified version of DES-Crypt used on HP-UX, Digital Unix, and OSF/1. The main difference between it and DES is that BigCrypt uses all the characters of a password, not just the first 8, and has a variable length hash.^[25]

Crypt16 is the minor modification of DES, which allows passwords of up to 16 characters. Used on Ultrix and Tru64.^[26]

GNU/Linux

The GNU C Library used by almost all GNU/Linux distributions provides an implementation of the crypt function which supports the DES, MD5, and (since version 2.7) SHA-2 based hashing algorithms mentioned above. Ulrich Drepper, the glibc maintainer, rejected bcrypt support since isn't approved by NIST.^[27]

Mac OS

MacOS X Darwin’s native crypt() provides limited functionality, supporting only DES and BSDi. OS X uses a separate system for its own password hashes.^[28][29]

References

1. ↑ Simson Garfinkel, Alan Schwartz, Gene Spafford. "Practical Unix & Internet Security". 2003. section "4.3.2.3 crypt16( ), DES Extended, and Modular Crypt Format". "The Modular Crypt Format (MCF) specifies an extensible scheme for formatting encrypted passwords. MCF is one of the most popular formats for encrypted passwords"
2. 1 2 "Modular Crypt Format: or, a side note about a standard that isn’t".
3. ↑ "Binary Modular Crypt Format"
4. ↑ http://perldoc.perl.org/functions/crypt.html
5. ↑ http://us.php.net/manual/en/function.crypt.php
6. ↑ http://pike.ida.liu.se/generated/manual/modref/ex/predef_3A_3A/crypt.html
7. ↑ https://docs.python.org/library/crypt.html
8. ↑ http://ruby-doc.org/core/classes/String.html#M001174
9. ↑ "Password Hash Competition string format". 
10. 1 2 Morris, Robert; Thompson, Ken (1978-04-03). "Password Security: A Case History.". Bell Laboratories. Retrieved 2013-12-17. 
11. ↑ "crypt – password encoding". UNIX Third Edition Programmers' Manual. 1973-01-15. 
12. ↑ "crypt, setkey, encrypt – DES encryption". UNIX Seventh Edition Programmers' Manual. 1979. 
13. ↑ http://phk.freebsd.dk/sagas/md5crypt_eol.html
14. ↑ Provos, Niels; Mazières, David (1999). "A Future-Adaptable Password Scheme". Proceedings of 1999 USENIX Annual Technical Conference: 81–92. 
15. ↑ Designer, Solar (2011-06-21). "crypt_blowfish 1.1; Owl glibc security update".  See also CVE-2011-2483.
16. ↑ "src/lib/libc/crypt/bcrypt.c - view - 1.27". cvsweb.openbsd.org. Retrieved 2016-05-14. 
17. ↑ Designer, Solar (2012-01-02). "OpenBSD bcrypt 8-bit key_len wraparound". 
18. ↑ http://www.mail-archive.com/freebsd-current@freebsd.org/msg52586.html
19. ↑ http://davenport.sourceforge.net/ntlm.html#theNtlmResponse
20. ↑ http://www.freebsd.org/cgi/man.cgi?query=crypt&apropos=0&sektion=3&manpath=FreeBSD+8.2-RELEASE&format=html
21. 1 2 Drepper, Ulrich. "Unix crypt with SHA-256/512". 
22. ↑ Sun Microsystems. "crypt_sunmd5(5) man page". Retrieved 2008-03-05. 
23. ↑ Muffett, Alec (2005-12-05). "OpenSolaris, Pluggable Crypt, and the SunMD5 Password Hash Algorithm". Retrieved 2012-08-11. 
24. ↑ Drepper, Ulrich. "Unix crypt using SHA-256 and SHA-512". 
25. ↑ https://pythonhosted.org/passlib/lib/passlib.hash.bigcrypt.html
26. ↑ https://pythonhosted.org/passlib/lib/passlib.hash.crypt16.html
27. ↑ https://access.redhat.com/articles/1519843
28. ↑ http://www.dribin.org/dave/blog/archives/2006/04/07/os_x_passwords/
29. ↑ http://www.onlinehashcrack.com/how-to-extract-hashes-crack-mac-osx-passwords.php

External links

• Source code for crypt(3) from Seventh Edition Unix (implements proposed DES)
• Sample password hash encoding strings
• Usage example
• Online glibc2 compatible crypt(3)
• .NET crypt implementation