<?php // md5.php - Converts a word into md5 format echo("Please enter a string to hash: "); // ask for input $string = rtrim(fgets(STDIN)); // get input (remove carriage return) $md5 = md5($string); // convert to md5 echo("The hash value for $string is: $md5\r\n"); // echo hash and new line ?>

2. What are hashes used for?
Hashes are a common way of keeping personal and important data confidential. Most of the time when you register an account on a website somewhere and enter a password, the password you enter is first converted into a hash, and then the hash value is stored inside of a database. Next, when you go to login to the website, it takes the data you enter into the password form, converts it into the same hash format, and compares the two hashes for a match. There are a few reasons this is helpful, but the most common reason for this practice is for better security. For example, imagine if the hackthissite login database table was leaked, and that all of the passwords were in plain text format. This would allow anyone to login under your account very easily. However, if the data leaked was hashed, if someone tried to login with that information, the hash would be pushed through the formula and would return another completely different hash value, rendering the password invalid.

3. What are salts?
A salt is a way to keep simple user passwords more complex. (This will make more sense when you understand dictionary attacks)
What a salt will do is prepend or append certain characters to string input. For example let's assume we will use a prepended salt value of "0x9Abr". When a user gets ready to hash their password, say "bob", instead of simply hashing "bob", we will instead hash "0x9Abrbob", making the password more complex and therefor more secure. However, salts do not need to be static, there are many ways which we could generate a random hash for each individual user, but the salt would need to be stored alongside the user account with their hash value. An example of a random salt could be taking the current time, and sending it through a complex algorithm.

Code for hashing a string with a random salt value of 1-3
I recommend you enter the same string and notice how the hash differentiates with each appended salt.
CODE :

<?php // md5salt.php - Converts a string with an appended salt value of 1, 2, or 3 (for simplicity) $salt = rand(1,3); // random number 1, 2, or 3 echo("Please enter a string to hash: "); // ask for input $string = rtrim(fgets(STDIN)); // get input (remove carriage return) $md5 = md5($salt+$string); // hash the string with the salt appended echo("Hash value for string $string with salt value $salt is: $md5\r\n"); // echo the hash ?>

B. Dictionary Attacks

1. What are dictionary attacks?
A dictionary attack is a way of running an attack in an ATTEMPT to recover it's plain text value. With hashing having very complex formulas, it's usually not wise for some web developer to roll out their own "custom" hashing algorithm. The reason for this goes back to collision resistance, and security. Now, that you know that, you should also know that many web developers instead will use public hashing functions to secure sensitive data on their websites (which is a much wiser decision) However, this also allows use to take advantage of the hashing functions public use. For instance, we will explain a simple attack using the MD5 hashing function that we used previously. The goal is that we will take a list of words (Dictionary) and convert each word into MD5 format, and then compare that word to the hash we are looking for. If we get a match for two hash values, we know the word used to create that hash value is a plain text match for the hash.
Before we get started at taking a look at some example code, we first need to create a dictionary. So to do this, I have generated a small dictionary and posted it on pastebin at: http://pastebin.com/2gCwbxaL Just copy those words and paste it inside a new text file and name it dictionary.txt
Now, we will create some example code, in which we will hash each value and compare it to the hash value "4fded1464736e77865df232cbcb4cd19"

CODE :

<?php // dictionary.php - Dictionary attack on a hash value $hash = "4fded1464736e77865df232cbcb4cd19"; // hash value to find $fpath = "dictionary.txt"; // please have this file and the dictionary file in the same directory if(!file_exists($fpath)) echo("Invalid file path, please make sure you added the dictionary to the same directory and is named dictionary.txt\r\n"); else { // If dictionary is valid $file = fopen($fpath, "r+"); // open file with read access $found = false; // Set variable (determines if loop continues) while(!feof($file) && $found == false) { // while not at the end of file and the hash isn't found $word = rtrim(fgets($file)); // grab the current word on the line $md5 = md5($word); // hash that word if($md5 == $hash) { // compare it to the hash we are looking for echo("$word is a match for hash $hash\r\n"); // if found $found = true; // will terminate loop } } } ?>

2. The cons and pros
The bad part about dictionary attacks are that they are slow, and can take up a large amount of space with an increasing dictionary size. If a dictionary is too large, then a dictionary attack could take hours or longer to complete, which isn't very time efficient.
The good things about dictionary attacks, is that you can add salts and other replacements on the fly while comparing hashes. For example, substituting the string "too leet for you" into "+00 l337 4 '/0|_|" which may allow use to pick up some additional hash values.

Now, we know that one of problems with dictionary attacks, is that it can be slow (especially if you are anything like me and have a dictionary with over 1 billion strings to hash). So what can be done to increase the speed of this? One way is to use rainbow tables, or lookup tables. I will cover what exactly a lookup table is below.

C. Lookup Tables

1. What are lookup tables?
A lookup table is a file with pre-computed hashes stored alongside their plain text value. For example, in a lookup table a pre-computed hash could look similar to:
4fded1464736e77865df232cbcb4cd19:yolo
Which basically has the MD5 hash for the plain text word "yolo" followed by a colon and the word.

2. Why use lookup tables?
As said before, they will save computation time and will make running through a dictionary a lot less stressful on your cpu/gpu. The reason is that we no longer need to hash each string before we compare, we can simply search for the hash, if it's found, we display the value appended by the colon.

3. How to search
Personally, I have found that using grep to search a file for the hash will make things very easy, however this may be limited to *nix machines. It is still possible to have the PHP code search the code for the MD5 value and let you know if the hash was found or not. But for these examples we will use grep, mainly because it has been programmed to be very efficient, fast, and it uses a very nice sorting algorithm which also saves on computation time.

4. Create a lookup table
Below we will create a script which will convert a dictionary into a lookup table

CODE :

<?php // convert.php - convert a specific dictionary into a lookup table fwrite(STDOUT, "Please enter the path to your dictionary file: "); // asking the user to specify a dictionary file $dict = trim(fgets(STDIN)); // storing the dictionary to convert in $dict if(file_exists($dict)) { // if the dictionary file exists $dict = fopen($dict, "a+"); // open up the dictionary } else { // if the dictionary file does not exist echo "Sorry, the location of the dictionary was not found. Please check the path location and your syntax!\n"; // give error } fwrite(STDOUT, "Enter a name you wish to save the lookup table as: "); // asking what to save the filname as $file = trim(fgets(STDIN)); // grabbing a name from user to save the rainbow table as $file = fopen($file, "a+"); // open up the rainbow table with write privileges echo "Would you like to print the hashes to the terminal as they are converted?\n"; // would the user like to see the conversion as it happens? echo "Choosing no will save time (Recommended for large files), while choosing yes will allow you to see the conversion in progress [y/n] "; // more details $show = trim(fgets(STDIN)); // storing the user's answer in $show if($show == "y") { // if the user does want to show the hashes as they are converted while(!feof($dict)) { // while not at the end of the dictionary $word = fgets($dict); // get the word on the current line $word = rtrim($word); // remove trailing white space from that word $hash = md5($word); // convert that word into md5 format fwrite($file, $hash . ":" . $word . "\n"); // write the word on the current line of our dictionary to the lookup table echo "MD5 value: $hash successfully stored inside your rainbow table!\n"; // display the hash that was converted and added to the file } } else { // if the user did not want to show the hashes as they are converted while(!feof($dict)) { // while not at the end of the dictionary $word = fgets($dict); // get the word on the current line $word = rtrim($word); // remove trailing white space from that word $hash = md5($word); // convert that word into md5 format fwrite($file, $hash . ":" . $word . "\n"); // write the word to our lookup table } } fclose($dict); // close the dictionary file fclose($file); // close the rainbow file ?>

D. Lookup Attack

1. Code
Below we will demonstrate a simple lookup attack. Now, you will not notice any changes in speed efficiency on such a small scale (only 25 words in a dictionary), however if you used a much larger dictionary, you would notice drastic changes in time and computation.

CODE :

<?php // lookup.php - Search MD5 hash values from lookup table exec("touch temp.txt"); // creating a temp file, to ensure there is a copy to delete exec("rm temp.txt"); // removing temp file if it exists echo("Enter the hash to lookup: "); // Asking for a hash to lookup $hash = trim(fgets(STDIN)); // Grabbing the hash to lookup fwrite(STDOUT, "Please enter the location of the lookup table: "); // Asking for the lookup table location $look = trim(fgets(STDIN)); // Storing the filename in $look $lookup = fopen($look, "r"); // opening the filename in $lookup $temp = fopen("temp.txt", "a+"); // opening the temp file to write the found hashes to if($lookup) { // if the lookup table exists exec("grep -m1 '$hash' '$look' >> temp.txt"); // grep the hash and store the output into the temp file } while(!feof($temp)) { // while not at the end of the lookup table $word = trim(fgets($temp)); // grab the word on the current line of the lookup table $word = substr($word, 33); // remove the hash and colon from the word, leaving the value if(strlen($word) >= 1) { // if the word is not a carriage return echo "The value for hash: " . $hash . " is: ".$word."\n"; } } echo "Done looking up the hashes, if a word was not displayed, it was not located!\n"; echo "The found hashes are stored in temp.txt\n"; fwrite(STDOUT, "Would you like me to remove the file now, or would you like it to be deleted later (good if you want to review hashes) [y/n] "); $choice = trim(fgets(STDIN)); // storing the user's choice switch($choice) { // creating a switch for the choice instead of if/elseif/else case 'y': // if the user chose y exec("rm temp.txt"); echo "The file has been removed!\n"; break; case 'n': // if the user chose n echo "You have chosen not to remove the file, thanks for using the program!\n"; break; default: // if the user did not choose y nor n echo "The command you entered was not recognized, terminating the program!\n"; break; } ?>

2. The cons
We know that the pros are time and computation efficiency, but where are the cons? It's basically the reverse of dictionary attacks. With prec-omputed hash values, you can not append/prepend salt values or use substitution on the fly. Another similar con for lookup tables is also storage space, adding more bits to the file will rack up on storage space.

3. Make it faster
mShred and I a while back ran some tests with computation time, using an extremely large dictionary. The result was that is was slow as fuck, so long in fact that I decided to terminate the program. Luckily someone had a great idea, which was the way we had been storing our hashes. At first we had everything jumbled together into one giant lookup table, however this was proving time consuming. So what we did was take it a bit further, and stored each hash with it's value inside a file specific to the first 3 characters of it's hash. (I did this only for MD5) Since MD5 is all hexadecimal values, we have 16 beginning letter choices, A-F or 0-9. So by placing each hash depending on it's first three hash values, we came out with 4096 separate lookup tables. As an example, hash "150468c0a7cc25db1f5e604833d84713" would be stored in a lookup table called 150.txt while a hash like "10d0dafff7cc25db1f5e604833d8c012" would be stored inside a tabled called 10d.txt, etc. Now when you lookup the hash, you target the table with the first three characters of said hash.

Donate

Challenges

Get Informed

Get Involved

Communicate

About HTS

Partners