--------------------------------------------------------------------------------------------- | CONTENTS | DESCRIPTON | |-------------------------------------------|-------------------------------------------------| | 0X00 PREFACE | TITLE: PASSWORDS PART1: THEORY, HASHING, SALTING| | 0X01 HOW PASSWORDS ARE STORED | BY : keisterstash | | 0X02 PUTTING IT TOGETHER | DATE : 04/06/11 | | 0X03 SALTING | EMAIL: jonschipp [at] gmail | | 0X04 TRADITIONAL CRYPT() | | | 0X05 GLIBC2 | | | 0X06 FREEBSD CRYPT() | | | 0X07 OPENBSD CRYPT()\BCRYPT() | | | 0X08 A BRIEF VIEW INTO PASSWORD DATABASES | | | 0X09 UNDERSTANDING /ETC/SHADOW | | | 0X0A AIX | | | 0X0B MAC OSX | | | 0x0C CONCLUSION | | | 0X0D REFERENCES | | --------------------------------------------------------------------------------------------- 0x00 PREFACE I haven't seen a well written, thorough article on how passwords are stored within an operating system and how it all fits together (maybe, i haven't looked hard enough). While this isn't a complex topic, it is nonetheless important. I hope to provide a sturdy foundation for those that have not delved into how passwords are stored and how they "work". This will be a two part series with the second part's focus being on attacks, by using some tools that other slick gentlemen have unleashed upon us. 0x01 HOW PASSWORDS ARE STORED Passwords are stored in password databases. Really? yes. In Unix and unix-like operating systems, passwords are stored in a single text file. In a Windows operating system, passwords are stored in a binary file. It is unadvisable to store passwords in clear-text(unencrypted) form. If an individual obtains a clear- text password database, he will have your passwords. For this reason, passwords are stored cryptographically. All operating systems (ok, maybe not ALL) run their passwords through a hashing algorithm, the end result is a cryptographic hash, which is stored in the password database. This way, if someone obtains the database with the hashes, they will not be able to recover the passwords by merely looking at them. What is a hash? A hash, also called a digest, a checksum (depending on context), or message digest, is the cryptographic output of a hashing algorithm. A hashing algorithm provides a one-way transformation between clear-text and the cipher-text, in this case, the hash. A one-way function is a process that cannot be reversed, that is, I cannot take my hash and get the clear-text again by running it through the hashing algorithm. An unfixed amount of input through a hashing algorithm produces a fixed amount of output. In otherwords, it doesn't matter whether the input is a book's length of words, a video file, or one word such as "password". When ran through the algorithm, the end result (output/hash) will be of the same length. This is important in cryptography, for if they all have the same size, it becomes unfeasible to determine the type or length of the input given. A few popular hashing algorithms are as follows: MD5, SHA-1, SHA-2, RIPEMD-160 etc. Using the md5 program to generate the hash of the string 'yodude': md5 -s yodude MD5 ("yodude") = 0a2b20c712ba7bdfc97e27206cdbba8a Now for a full book in pdf form: md5 unixnetprogramming.pdf MD5 (unixnetprogramming.pdf) = c71e5ac19cddd21a3e09c10fffa75ff0 We used one of the many popular hashing algorithms: MD5 (Message Digest 5). An MD5 hash is a 128 bit (16 byte) hash that is generally considered (nowadays) to be weak due to hashing collisions. Its output is a 32 digit hexidecimal number (2 hex digits = 1 byte, 16 byte = 128 bit). A hash collision is where two different inputs produce two identical outputs, that is, two identical hashes. This isn't good from a defensive password cracking standpoint, this means that you now have two possible passwords to guess to gain entry to a system. More is possible if there are many collisions. The Secure Hashing Algorithm (SHA) with its various revisions and bit lengths are considered to be superior to MD5 from a cryptographic standpoint. SHA-2 is a group of hashing functions designed by the NSA and standardized by NIST. SHA-2 provides four types with various bit lengths: 224, 256, 386, and 512. Here's a sample of a SHA-256 hash using the sha256 (256 bits) program: sha256 -s yodude SHA256 ("yodude") = 5dc105b971c67645c0692c129af22e66c62136171c6af8cb570711f4428a66df And with that book: sha256 unixnetprogramming.pdf SHA256 (unixnetprogramming.pdf) = aa06d78290b9a298543d222b2b91f509fb8301883a41ea913bc3e6c57e5fc386 256/8 = 32, so the algorithm produces a 64 hex digit hash. right? cool. Hashing algorithms are used for checking the integrity of data(making sure your data hasn't been altered). One can check data by with the examples from above. If I copy that book to another persons machine and the hash calculated for that program differs after the transfer you can be sure that the data has been altered. Many software projects will produce a hash on their website to compare with a hash you generate after you download their software. This type of integrity checking is also used in public key cryptography with digital signanatures and with network protocols such as IPSEC. 0x02 PUTTING IT TOGETHER When you want to create a user account on a operating system, you will use the programs that the operating system provides. In Linux, we typically use the adduser or useradd programs. To create the user 'keister' we will use: # useradd keister The account will then be locked until a password is created. We use the passwd program to create a password: # passwd keister The passwd program runs your entered string through a hashing algorithm, the hash is then added to the /etc/shadow file. The crypt() programming function is used to generate the password (man 3 crypt). In older Unix systems the Data Encryption Standard (DES) was used to store the passwords. DES is s symmetric block cipher that was standarized and used by the U.S government in 1976. It is cryptographically weak and is now replaced by the Advanced Encryption Standard (AES) which uses the Rijndael cipher. While DES is not a hashing algorithm, it is used in the following way: "By taking the lowest 7 bits of each of the first eight characters of the key, a 56-bit key is obtained. This 56-bit key is used to encrypt repeatedly a constant string (usually a string consisting of all zeros). The returned value points to the encrypted password, a series of 13 printable ASCII characters (the first two characters represent the salt itself). The return value points to static data whose content is overwritten by each call. " The result (13 chars) is stored in /etc/shadow, and when you login via your operating systems login program the entered password is ran through the crypt() function and the resulting hash is compared to the one in /etc/shadow. If the hashes match you will be successfully authenticated and if not, succesfully denied. The basic form of the function is as follows: char *crypt(const char *key, const char *salt) We will discuss salting and a revised version of this function in the next sections. 0x03 SALTING Now that hashing is understood we will move onto salting. Salting consists of (pseudo)random bits that are used as one of the inputs to a key derivation function. The other input is usually a password or passphrase. We use salting to raise the level of entropy on our passwords, it provides "extra" protection. In older Unix systems e.g. System V that used DES encryption for passwords, there was also a 12 bit salt that was generated by the system. Two salt characters were cut down to 6 bits each, since this is a 12 bit salt. There are two inputs into the crypt function: crypt($salt, $key) If salt is 'aZ' and key is 'mypassword' then we have $salt + $pass: aZmypassword This is then hashed or in our case right now, encrypted with DES. The result is stored in the password database, /etc/shadow. Since the salt is a (pseudo)random value, that is used to determine the password, it must be stored somewhere so that it can be ran through the crypt function. What ends up happening is that the salt value is stored along with the encrypted password in the /etc/shadow file. When a user is trying to authenticate to a system, after their username and password is entered, the authenticating program will grab the salt value from the appropriate user's line in the shadow file. It will then take that value along with the password entered and run it through the crypt function. Depending on whether the information entered matches or doesn't match, determines whether you will be sitting with an interactive shell. What is the purpose? Salting tends to increase the burden on the attacker when using rainbow tables. A rainbow table is collection of generated hashes that are ran against a password hash in hope of a match. Instead of tasking the CPU by creating passwords and then running them through a hashing function(and then comparing), an attacker can save time by having them already in a hashed form. By spending his weekend computing hashes, later on, when he wants to, he can check for matches. This reduces the cpu load at a given time and thus enhances the ability of the attacker by reducing the time taken to complete the attack. "In time-memory tradeoff approach, the task of hash computing is done in advance with the results stored in files called "rainbow table". After that, hashes can be looked up from the rainbow tables whenever needed. The pre-computation process needs several times the effort of full key space brute force. But once the one time pre-computation is complete, the table lookup performance can be hundreds or thousands times faster than brute force." With salting, the generated hashes have to cover a much more broad spectrum, you can't just use dictionary words and hash them because of the salt value. For password 'mypassword', and a two byte salt we will need all the possible salt combinations plus the password: aamypassword abmypassword ... AZmypassword To be exhaustive, the attacker needs not only a few dictionary words, but all the possible salts for each dictionary word. Note: Rainbow tables are non-volatile memory expensive, they take up quite a bit of disk space. There are 500 GB tables floating around the net, and probably larger. Also, with salting, if two people have the same passwords, the encypted forms will be different because of the salt values. If Sally and Sammy have two identical passwords and they are stored in the same password database, that has been salted, me, having access to the database, will not be able to determine that the two passwords are identical. 0x04 TRADITIONAL CRYPT() "The first 8 bytes of the key are null-padded, and the low-order 7 bits of each character is used to form the 56-bit DES key. The setting is a 2-character array of the ASCII-encoded salt. Thus only 12 bits of salt are used. count is set to 25." The traditional DES-based crypt(3) hashes discard characters past 8. see below, john-users mailing list, excerpted dialogue between Solar Designer and a guy on the list. (question) "When i check the john.pot it gives me a result for my user_1 (e.g my_passw). But my real password for user_1 is not my_passw but my_passwd. So how can you use john for password longer as 8 char (using crypt/DES)." (response) The traditional DES-based crypt(3) hashes discard characters past 8. This means that your password really _is_ "my_passw" (using your example), even if you think that it is "my_passwd". The last "d" was discarded when you first set that password, and it is discarded each time you enter it on login (so you could as well not type that character, or type something different)." 0x05 GLIBC2 Most people don't want to rely on DES as a method of password encryption. The GNU C library(so has the BSD's with their crypt() function) takes care of the old crypt function that has been provided with older Unix systems: glibc2. With glibc2, which almost all Linux distrobutions use now, we have a larger and more "secure" amount of algorithms to choose from. "The glibc2 version of this function has the following additional features. If salt is a character string starting with the three characters "$1$" followed by at most eight characters, and optionally terminated by "$", then instead of using the DES machine, the glibc crypt function uses an MD5-based algorithm, and outputs up to 34 bytes, namely "$1$$", where "" stands for the up to 8 characters following "$1$" in the salt, followed by 22 bytes chosen from the set [a-zA-Z0-9./]. The entire key is significant here (instead of only the first 8 bytes)." "When the user enters their password for the first time, the salt should be set to a new string which is reasonably random. To verify a password against the result of a previous call to crypt, pass the result of the previous call as the salt. " The function now takes the form of: crypt($id, $salt, $key) Where id is one of the values below: 1 | MD5 2a | Blowfish (not in mainline glibc; added in some | Linux distributions) 5 | SHA-256 (since glibc 2.7) 6 | SHA-512 (since glibc 2.7) "So $5$salt$encrypted is an SHA-256 encoded password and $6$salt$encrypted is an SHA-512 encoded one." "salt" stands for the up to 16 characters following "$id$" in the salt. The encrypted part of the password string is the actual computed password. The size of this string is fixed: MD5 | 22 characters SHA-256 | 43 characters SHA-512 | 86 characters" 0x06 FREEBSD CRYPT FUNCTION BSD OS's have their own tools and their own way of doing things, so we will take a brief look at the FreeBSD crypt function, with its differences from the glibc crypt function(used in Linux). Quotes will suffice. "The crypt() function performs password hashing with additional code added to deter key search attempts. Different algorithms can be used to in the hash. Currently these include the NBS Data Encryption Standard (DES), MD5 hash, NT-Hash (compatible with Microsoft's NT scheme) and Blowfish. The algorithm used will depend upon the format of the Salt (following the Modular Crypt Format (MCF)), if DES and/or Blowfish is installed or not, and whether crypt_set_format() has been called to change the default." Notice how the implementation is slightly different from older Unix systems when it comes to the salt. "DES Extended Format: The key is divided into groups of 8 characters (the last group is null- padded) and the low-order 7 bits of each character (56 bits per group) are used to form the DES key as follows: the first group of 56 bits becomes the initial DES key. For each additional group, the XOR of the encryption of the current DES key with itself and the group bits becomes the next DES key. The salt is a 9-character array consisting of an underscore followed by 4 bytes of iteration count and 4 bytes of salt. These are encoded as printable characters, 6 bits per character, least significant character first. The values 0 to 63 are encoded as ``./0-9A-Za-z''. This allows 24 bits for both count and salt." And finally, the supported algorithms are: 1. MD5 2. Blowfish 3. NT-Hash Other crypt formats may be easily added. 0x07 OPENBSD CRYPT\BCRYPT FUNCTION The OpenBSD crypt function is very similar to the FreeBSD's function. Though, OpenBSD provides a few more functions that are used with crypt. When using blowfish, bcrypt() is used: man bcrypt Here's some Blowfish info since I didn't post it above: "The Blowfish version of crypt has 128 bits of salt in order to make building dictionaries of common passwords space consuming. The initial state of the Blowfish cipher is expanded using the salt and the password repeating the process a variable number of rounds, which is encoded in the password string. The maximum password length is 72. The final Blowfish password entry is created by encrypting the string ``OrpheanBeholderScryDoubt'' with the Blowfish state 64 times. The version number, the logarithm of the number of rounds and the concatenation of salt and hashed password are separated by the `$' character. An encoded `8' would specify 256 rounds. A valid Blowfish password looks like this: ``$2a$12$eIAq8PR8sIUnJ1HaohxX2O9x9Qlm2vK97LJ5dsXdmB.eXF42qjchC''. The whole Blowfish password string is passed as setting for interpretation." 0x08 A BRIEF VIEW INTO PASSWORD DATABASES Linux - password database: /etc/shadow /bin/login - login program Let's see what the shadow entry looks like for the account test: # grep test /etc/shadow test:$1$7gYVdbpz$lt3fVfMIxEqX8HeXBwos4/:15065:0:99999:7::: FreeBSD, OpenBSD - password database: /etc/master.passwd /bin/login - login program Let's see what the master.passwd entry looks like for the account test: # grep test /etc/master.passwd test:$1$AVITnyGr$Q3qXCb8RU17oivKTW1nio.:1002:1002::0:0:User &:/home/test:/bin/sh Windows XP - password database - SAM (Security Accounts Manager): /$WINDIR/system32/config/sam Let's see what the SAM entry for the account test looks like(Win XP): C:\> fgdump Test:1003:E52CAC67419A9A224A3B108F3FA6CB6D:8846F7EAEE8FB117AD06BDD830B7586C::: The ':' character is a field delimiter. The LM hash is E52CAC67419A9A224A3B108F3FA6CB6D and the NTLM hash is 8846F7EAEE8FB117AD06BDD830B7586C, both 32 characters, so a 32 byte hash(256 bits). Windows stores passwords in a binary format and it uses its own developed algorithms: LM, NTLM. I used a tool called fgdump to dump the hashes, www.foofus.net/~fizzgig/fgdump/ Both are much weaker than the algorithms available in Unix-like systems, they are also unsalted. LM (short for LAN Manager) is now only used for backwards compatibility between older windows machines e.g. NT and their domains. LM hashes are calculated like this: 1. The user's ASCII password is converted to uppercase. 2. This password is null-padded to 14 bytes.[Notes 1][3] 3. The "fixed-length" password is split into two 7-byte halves. 4. These values are used to create two DES keys, one from each 7-byte half, by converting the seven bytes into a bit stream, and inserting a null bit after every seven bits (so 1010100 becomes 01010100). This generates the 64 bits needed for a DES key. (A DES key ostensibly consists of 64 bits; however, only 56 of these are actually used by the algorithm. The null bits added in this step are later discarded.) 5. Each of the two keys is used to DES-encrypt the constant ASCII string "KGS!@#$%", resulting in two 8-byte ciphertext values. The DES CipherMode should be set to ECB, and PaddingMode should be set to NONE. 6. These two ciphertext values are concatenated to form a 16-byte value, which is the LM hash." As you can see this isn't a very safe way of doing things, LM hashes can be cracked in seconds. NTLM is only slightly better. A little NTLM info: "NTLM is still used in the following situations: The client is authenticating to a server using an IP address. The client is authenticating to a server that belongs to a different Active Directory forest that has a legacy NTLM trust instead of a transitive inter-forest trust The client is authenticating to a server that doesn't belong to a domain. No Active Directory domain exists (commonly referred to as "workgroup" or "peer-to-peer"). Where a firewall would otherwise restrict the ports required by Kerberos (of which there are quite a few) In Windows Vista and above, neither LM or NTLM are used by default. NTLM is still supported for inbound authentication, but for outbound authentication a newer version of NTLM, called NTLMv2, is sent by default instead. Prior versions of Windows (back as far as Windows NT 4.0 Service Pack 4) could be configured to behave this way, but it was not the default." 0x09 UNDERSTANDING /ETC/SHADOW test:$1$7gYVdbpz$lt3fVfMIxEqX8HeXBwos4/:15065:0:99999:7::: The $'s are the delimiters in the password field. The value between the first two $'s is an integer that represents the hashing algorithm(id): 1 stands for MD5, 2a for blowfish, 5 for SHA-256, 6 for SHA-512. If the id is absent, DES is used. The next string of characters located after the second $ and before the last $ is the salt value. The size of the salt depends on the algorithm chosen. The last set of characters is the password hash. The rest is account and password policy info in order of appearance: User name : login name ID/Salt/Password: It your encrypted (hashed) password. ^A blank entry (eg. ::) indicates a password is not required to log in and a * entry (eg. :*:) indicates the account has been disabled. Last password change: Days since Jan 1, 1970 that password was last changed Minimum: The minimum number of days required between password changes i.e. the number of days left before the user is allowed to change his/her password. Maximum: The maximum number of days the password is valid (after that user is forced to change his/her password) Warn : The number of days before password is to expire that user is warned that his/her password must be changed Inactive : The number of days after password expires that account is disabled Expire : days since Jan 1, 1970 that account is disabled i.e. an absolute date specifying when the login may no longer be used 0x0A AIX IBM's proprietary Unix OS, AIX, stores its password hashes in /etc/security/passwd Basic user information is still stored in /etc/passwd. The /etc/security/passwd file is very different from the other files we've looked at. It's comprised of stanzas with each statement on its own line. Example: smith: password = MGURSj.F056Dj lastupdate = 623078865 flags = ADMIN,NOCHECK AIX uses the old unix style crypt() function which uses DES, it has an 8 character limit. However, with AIX 5.3 and up, LPA's (Loadable Password Algorithm) are an option. Some algorithms available are: MD5, SHA-256, Blowfish. The LPA configuration file is /etc/security/pwdalg.cfg example of a /etc/security/pwdalg.cfg stanza: ssha256: lpa_module = /usr/lib/security/ssha lpa_options = algorithm=sha256 /etc/security/login.cfg is used to set the algorithm globally: usw: shells = /bin/sh,/bin/bsh,/bin/csh,/bin/ksh,/bin/tsh,/bin/ksh93 maxlogins = 32767 logintimeout = 60 maxroles = 8 auth_type = STD_AUTH pwd_algorithm = ssha256 0x0B MAC OSX OS X systems encrypt passwords with a salted SHA-1 hash. Each user has their own "shadow" file, these files are stored in /var/db/shadow/hash/. Each file in the directory will have the name of a user's GUID, Generated User ID. e.g /var/db/shadow/hash/A66BCB30-2413-422A-A574-DE03108F8AF2 OS X 10.4+ stores LM & NTLM hashes in the same file if the user has Windows Sharing on. 0x0C CONCLUSION I hope this has helped you understand things a little bit more. As I dig a around a bit more (which i plan to do) I will update this document accordingly. Email your suggestions, corrections, requests, and criticism to jonschipp [at] gmail.com. I tend to be wrong a lot, if you find something that doesn't make sense, do the honorable thing and let me know. 0x0D REFERENCES man 3 crypt (Arch linux) man 3 crypt (FreeBSD) man 3 crypt (OpenBSD) man 5 shadow (Arch Linux) man 5 master.passwd (FreeBSD) man 1 passwd (Arch Linux, FreeBSD) http://www.openwall.com/lists/john-users/2005/07/02/1 http://project-rainbowcrack.com/ http://linux.die.net/man/5/shadow http://stackoverflow.com/questions/420843/need-some-help-understanding-password-salt https://secure.wikimedia.org/wikipedia/en/wiki/NTLM (yes, wikipedia) https://secure.wikimedia.org/wikipedia/en/wiki/LM_hash (again) http://www.cyberciti.biz/faq/understanding-etcshadow-file/ http://www.foofus.net/~fizzgig/fgdump/ http://publib.boulder.ibm.com/infocenter/aix/v6r1/index.jsp?topic=/com.ibm.aix.files/doc/aixfiles/passwd_security.htm http://pentestmonkey.net/cheat-sheet/john-the-ripper-hash-formats http://openwall.info/wiki/john/sample-hashes http://macshadows.com/kb/index.php?title=Mac_OS_X_password_hashes http://www.defenceindepth.net/2009/12/cracking-os-x-passwords.html