Virus Experts : MD5 Shadow Passwords

MD5 Shadow Passwords

Posted 2004.06.26 17:59 UTC | Updated 2004.07.15 16:28 UTC

Amir Malik (amir@virusexperts.com) Webmaster

Introduction

All modern Unix-like operating systems provide a method for storing users' passwords in a database of some sort. Some provide a truly despicable way of storing them in a plain-text file that is world- readable. Sensible operating systems store passwords as one-way encrypted hashes. A hashing algorithm, such as SHA-1, MD4, or MD5, takes a piece of data (the plain-text password in this case), and performs some mathematical operations on the data. The algorithm produces a unique number representing that particular piece of data.

That number is considered to be unique to that piece of data, and it is practically impossible to have that algorithm produce the same number for another piece of data. By "practically impossible," it is meant that the probability of two pieces of data having the same unique number (hash) as a result is highly unlikely, although this depends completely on the hasing algorithm used. For example, MD5 is a 128-bit hashing algorithm, and it can produce at most 2¹²⁸ unique hashes for any given pieces of data. Even though that is a large number, what if we feed the algorithm 2¹²⁸ + 1 different pieces of data? Surely we will find that at least two hashes will be the same. However, the time it would take to check every single piece of data, is far too great, even with modern supercomputers.

Shadow Passwords

On most Unix-like operating systems, shadow passwords can be stored in two formats. The older format, is based on the Data Encryption Standard (DES), which was cracked in the late 1990's. The problem with DES is that it is a 56-bit algorithm, and thus can produce a maximum of 2⁵⁶ unique hashes. It does not take long to figure out that this is indeed a weak algorithm in terms of strength.

The newer shadow format uses MD5 as the hashing algorithm.

Generating MD5 Shadow Passwords

The best way to learn is usually be example. Reading an RFC can be enjoyable, but when a quick solution is needed, valuable time spent reading an RFC could be spent on debugging some code. We begin by taking a look at our own /etc/shadow file.

root:$1$e8aD.GAJ$RVs8vl4KaXt/hr2pLAHjc.:12515:0:99999:7:::

But then again, you may see a shorter line for the same password.

root:Ep6mckrOLChF.:12515:0:99999:7:::

So what? Well, if you know your shadow file fields, you'll know that the first field is the login name of the user. The next field is a hash of the user's password. The rest of the fields deal with password aging and expiry. Take a close look at the second field. In the first snippet, we have a long hash -- yes, this is indeed an MD5 hash of the password. The latter snippet is a vanilla DES-based hash. As a programmer, how do we differentiate between these two types of hashes? Historically, the DES hash uses the Unix system call crypt() to create the hash from a password and a random seed value (referred to as a salt). This random seed value is usually composed of two characters (letters, numbers, or both) and is chosen randomly. The rest of the field (minus the salt) consists of the hashed password.

Now let's take a look at the first snippet again. You will notice it begins with $1$. This indicates that this is a password hashed using the MD5 algorithm. The 8 characters following the second dollar sign compose the salt. Note that this is much larger than the two characters allocated for a plain DES-based hash. Obviously, this allows for a more random hash value. Following the salt, is the actual hash of the password.

Now that you know the format of the field, you'll surely want to generate some hashed MD5 passwords. To create an MD5 shadow password, you will need to:

generate a seed (many fun ways to do this)
hash the password with that seed; the md5-aware crypt() function accomplishes this
put the results in standard form: $1$SEED$HASHPASS

What follows is some proof-of-concept code in Perl to generate an MD5 shadow password with the help of the Crypt::PasswdMD5 module. All this module does is provide the unix_md5_crypt() function. The seed should be 8 characters length. Picking a truly random seed value can be tricky. An elegant salt/seed generation solution should incorporate lots of random data (gathered from keyboard, mouse movement, reading /dev/random, /dev/urandom, local time, GMT offset, number of packets received over eth0 divided by 7, etc.).

The Code

The following Perl code requires the Crypt::PasswdMD5 module, which is readily available from CPAN.

use Crypt::PasswdMD5;

chomp(my $password = <STDIN>);
chomp(my $salt = <STDIN>);

$crypted = unix_md5_crypt($password, $salt);

print "$crypted\n";

MD5 Shadow Passwords

Introduction

Shadow Passwords

Generating MD5 Shadow Passwords

The Code

Projects

Documentation