PHP Lookup Table - Finding Hashes

For the discussion of Perl, Python, Ruby, and PHP and other interpreted languages.

PHP Lookup Table - Finding Hashes

Post by -Ninjex- on Sat Jun 22, 2013 6:15 am
([msg=76215]see PHP Lookup Table - Finding Hashes[/msg])

I was going to add this to my other post on dictionary attacking, but since it never really kicked off and has a couple thousand lines of words, I decided to talk about this in a separate post.

So if you read my former post: viewtopic.php?f=104&t=10315

You understand the methodology for dictionary attacks.
In a nutshell it's basically like this:

Material Needed:
1. Word List - Just a file with words separated by carriage returns [enter]
2. Common Sense
3. A Program

How it works:
1. You are given a hash and need to find the value of the hash.
2. Convert the word on the current line of the dictionary into the hash type
3. Compare the hash of the word in the word list to the hash's value you are trying to find
4. If they match, the word which was converted to find the match is the value of the hash
5. If the hash did not match, repeat process from #2

Alright, so let's talk about a way to optimize it.
So what is the key to speeding this up... Let's think about it. We have to do the following
word ---> convert into hash type ---> compare converted hash to the hash you are looking for

Well, what if you just converted everything into the hash before hand? Let's say MD5. If you do this, you kind of run into a small issue. Every word in the new dictionary is now only the MD5 value of that word. So if you compared each md5 value and you did return a match, you no longer know where to find the original value to that hash (unless you note the line number the hash was found, and then echo the data of that line number from the original un-hashed dictionary -- which is what I did in the post before using a bash script)

So what's the next option, we can take the word, convert it into md5 and then add it to the dictionary with the value of it following it with a semicolon. For example:
Code: Select all
ae3115832ad28aaf5d8a99c9e2ec962d:5werkeloz
43292e6d5c250b0ba6f9aa94b3f3aad1:5werkeloze
7edea232d55f2802dc056c6df55b0dbe:5werkelozen
8edc2d08417ef35cc3dcaa992f22ea2f:5werkelozenkas
94ba544e12efaec425bd4acde0055ef9:5werkelozenkases
a6902355330b61da1005c7d55f8054c4:5werkelozens
5c1c9e96c381a698dedcb94d1306b2dc:5werkelozenste
68ef6eba51bca40b4c7fec81248c5408:5werkelozensteun
f14f57fb88fe59a86bebbc38dc1e81ee:5werkelozes
fc3a116683c743e7ae7fe50678a4ab1d:5werkelt


Now, we place the md5 hash in front of it's value for a reason here, instead of placing it as value:md5
We did this because we will be using grep to search through our word list for the word, since it's extremely fast compared to other methods of searching for a word. We can make use of greps "." option which basically means any character in that position. So if we want to add a word (ninjex) in the future, we can see if it exists with grep like:
Code: Select all
grep -m1 '^.................................ninjex$' dictionary.dic


^ meaning to start at the beginning of the line, and then we move and pass up the hash and colon (33 characters so 33 .'s) and specify our word followed by "$" which is an anchor telling it to stop there, so we don't pull values like ninjexor, ninjex1, etc if they exist in the dictionary.

Now, the great thing about hashes it that there are always an infinite number of collisions so if we search for a hash and get multiple values for it, we could use either value and still authenticate well with the hash.

So here is a php script that will convert a dictionary file into md5:value for those interested.

Code: Select all
<?php

/*///---------------------------------------------------------------------------------------------------------------------------------------------------------
   convert.php
        Created by: Ninjex
   This is a php script that will convert a specific dictionary file into pre-converted hashes.
*///----------------------------------------------------------------------------------------------------------------------------------------------------------

fwrite(STDOUT, "Please enter the full path to your dictionary file: ");
$dict = trim(fgets(STDIN)); // storing location 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";
}

//------------------------------------------------------------------------------------------------------------------------------------------------------------

    fwrite(STDOUT, "Enter a name you wish to save the new file 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 privs
    echo "Would you like to print the hashes to the terminal as they are converted?\n";
    echo "Choosing no will save time (Recommended for large files), while choosing yes will allow you to see the conversion in progress [y/n] ";
    $show = trim(fgets(STDIN)); // does the user want to show the hashes as they are converted?

//-------------------------------------------------------------------------------------------------------------------------------------------------------------

    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 to our file with a carriage return \n
           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 rainbow table with a carriage return \n
            }
    }

//-------------------------------------------------------------------------------------------------------------------------------------------------------------

    fclose($dict); // close the dictionary file
    fclose($file); // close the rainbow file

?>


So you can take this and run it on your dictionary (it will not erase that dictionary) and choose to save a new dictionary that has the md5 hashes prefigured in front of the values.

For those of you who are curious about all the hash types you can use, it's basically limitless, however here is a list I made:

Code: Select all
$md5 = md5($word);
$md5_2 = md5($md5);
$md5_3 = md5($md5_2);
$md5_4 = md5($md5_3);
$md5_5 = md5($md5_4);
$sha1 = hash('sha1', $word);
$sha1_2 = hash('sha1', $sha1);
$sha1_3 = hash('sha1', $sha1_2);
$sha256 = hash('sha256', $word);
$sha384 = hash('sha384', $word);
$sha512 = hash('sha512', $word);
$ripemd160 = hash('ripemd160', $word);
$md5_sha1 = md5(sha1($word));
$sha1_md5 = sha1(md5($word));


Alright, so how are we going to search for this now, let's talk about it...
If we wanted to search for the md5 value: "28128605a42f04917238713f71545f43", we simply need to run a command like:

Code: Select all
grep -m1 '28128605a42f04917238713f71545f43' newrockyou.txt


Now, this is good but we have two issues we want to solve and that is:
1.) It displays via STDOUT to the console terminal, and doesn't store anywhere
2.) It still has the value appended like "28128605a42f04917238713f71545f43:ninjex"

To prevent the first issue, we can simply edit our grep command to append the word into a file like so:

Code: Select all
grep -m1 '28128605a42f04917238713f71545f43' newrockyou.txt >> temp.txt


To fix the second issue, we will use a php script and strip out the hash, so that only the value is returned.
I configured a script to do both of these for use at one, so let's take a look at it!

Code: Select all
                <?php
                fwrite(STDOUT, "Please enter the hash to search!\n");
                $hash = trim(fgets(STDIN));
                fwrite(STDOUT, "Please enter the full path to your dictionary!\n");
                $dictionary = trim(fgets(STDIN));
                exec("grep '$hash' '$dictionary' >> tempt.txt");
                $file = fopen("tempt.txt", "a+");
                $count = 0;
                 while(!feof($file)) {
                    $word = fgets($file);
                    $word = substr($word, 33);
                    if(strlen($word) >= 1) {
                        fwrite(STDOUT, "The value of the hash is: ".$word."\n");
                    }
                     $count++;
                 }
                    if($count <= 1) {
                        fwrite(STDOUT, "The value of the hash is not located in the dictionary...");
                    }
                     exec("rm tempt.txt");  // execute this if you do not want to keep the temp file
?>


There you have it, using grep to search the file for the hash, and store it in a temp file, which php then opens up, removes the hash and colon from, and echo's back that hashes value.

As a note, I can run through around 150 million words in ~2 minutes this way.


I hope you guys can learn something from this,

- Ninjex
Last edited by -Ninjex- on Sat Jun 22, 2013 11:27 pm, edited 1 time in total.
If you're not willing to learn, no one can help you. If you're determined to learn, no one can stop you.⠠⠵
The absence of evidence is not evidence of absence.
I can explain it for you, but I can't understand it for you.
User avatar
-Ninjex-
Addict
Addict
 
Posts: 1236
Joined: Sun Sep 02, 2012 8:02 pm
Blog: View Blog (0)


Re: PHP Lookup Table - Finding Hashes

Post by caracarn001 on Sat Jun 22, 2013 9:59 am
([msg=76216]see Re: PHP Lookup Table - Finding Hashes[/msg])

Why are you using a text file? Wouldn't using a database with a single table be better for searching because it's indexed?

eg:
+------------------------------------+
|word|md5|sha1|whatever|... |
+------------------------------------+
User avatar
caracarn001
New User
New User
 
Posts: 42
Joined: Thu Nov 04, 2010 5:23 am
Blog: View Blog (0)


Re: PHP Lookup Table - Finding Hashes

Post by -Ninjex- on Sat Jun 22, 2013 11:32 pm
([msg=76224]see Re: PHP Lookup Table - Finding Hashes[/msg])

caracarn001 wrote:Why are you using a text file? Wouldn't using a database with a single table be better for searching because it's indexed?

eg:
+------------------------------------+
|word|md5|sha1|whatever|... |
+------------------------------------+



The reason I am using a text file is because this is for education, and is basically an addition to my former post. I am going to be running tests with the hashes in a db in IRC soon. I wanted to create scripts which users can easily pick up off of this post and follow and analyze them to understand the methodology of the attack, opposed to optimization. Creating a linked array list of the words is another option instead of using a db. We have several ways to optimize this, which I plan on posting as time goes on and I have the time to do so.
If you're not willing to learn, no one can help you. If you're determined to learn, no one can stop you.⠠⠵
The absence of evidence is not evidence of absence.
I can explain it for you, but I can't understand it for you.
User avatar
-Ninjex-
Addict
Addict
 
Posts: 1236
Joined: Sun Sep 02, 2012 8:02 pm
Blog: View Blog (0)


Re: PHP Lookup Table - Finding Hashes

Post by mShred on Sat Jun 29, 2013 4:10 pm
([msg=76269]see Re: PHP Lookup Table - Finding Hashes[/msg])

Me and Ninjex were both actually on this. He was using text files while I was incorporating a db. The problem was our wordlist is over 500 million records, so inserting and indexing that many records would take a shit ton of time. And then it still wouldn't prove as efficient.
Someone in IRC actually popped in and had the idea to store the hashes in tables that were split up for the first letter of each hash. So take this hash, 5d41402abc4b2a76b9719d911017c592. It could be stored in the table `5`. Since md5 utilizes hex chars, that would mean there would be 16 tables. But me and Ninjex both being the kinda guys we are decided to take it a little further. Break the tables by the first three chars of the hash. So in our case, 5d41402abc4b2a76b9719d911017c592 would be stored in the table `5d4`. Do a little math and you'll realize that's 4096 (16^3) tables (or files). And with half a billion records to enter, each table would have, on average, less than 200,000 records.
/mindfuck
Using the above method, both the database and the file tree structures both work with ridiculous efficiency. Our bots can crawl through the wordlist and find the corresponding value for a hash within milliseconds.
Image

For those about to rock.
User avatar
mShred
Administrator
Administrator
 
Posts: 1686
Joined: Tue Jun 22, 2010 4:22 pm
Blog: View Blog (2)


Re: PHP Lookup Table - Finding Hashes

Post by -Ninjex- on Sun Jun 30, 2013 8:00 pm
([msg=76292]see Re: PHP Lookup Table - Finding Hashes[/msg])

Very well said, mShred. I probably should have posted here faster, but I have been a bit busy lately.
The next thing we plan on doing is to add in other hash types to the dictionary, such as sha and more; and see how efficient it will still prove to be. However, if we do this, we could easily create a new database to hold those values, to keep the efficiency at it's max. We are also looking into extending our dictionaries a lot more, hopefully as big as possible.
If you're not willing to learn, no one can help you. If you're determined to learn, no one can stop you.⠠⠵
The absence of evidence is not evidence of absence.
I can explain it for you, but I can't understand it for you.
User avatar
-Ninjex-
Addict
Addict
 
Posts: 1236
Joined: Sun Sep 02, 2012 8:02 pm
Blog: View Blog (0)



Return to Interpreted Languages

Who is online

Users browsing this forum: No registered users and 0 guests