Password Cracking Basics: Exhaustive Search vs Time-memory Tradeoff

Panggi Libersa J.A

Published in

prismapp

5 min readNov 14, 2016

In this article i try to explain how password-cracking works in two different basic ways.

Limitations:

Password algorithm to test: MD5
Two password-cracking algorithms to compare: Exhaustive Search and Time-memory Tradeoff.
This tutorial will use Ruby programming language to make it easy to understand.
Password combination: numeric from 1–15,000,000.
No concurrency or parallelism only serial programming.

Introduction

Password storing generally works like this:

Let say you register to a website using username: “myusername” and password: “qwerty”, it’s going to look like this in in their database:

So, what happens right there? your password is being transformed to one-way hash form, in this case using MD5 algorithm so that in case of there is a system breach and the database is being stolen, the thief will not get the correct plain text.

What does a one-way hash algorithm do? let me give you a few examples:

From the examples above, we can see that:

Different length of plain texts produce the same length of hashed text. That is how one-way hash algorithm works, after the plain text is hashed, there is no mathematical way to reverse it to the origin plain text form.

How is this algorithm can be implemented in password storing mechanism? let see another example:

Stored credentials:

username: “myusername”
password: “qwerty”

Database record:

Let say you forgot the password and login using:

username: “myusername”
password: “qwerty1234”

The flow will be like this:

Look at the “users” table where username equals to “myusername”
If there is a record with that username, hash the password using MD5 function, in this case md5(“qwerty1234”) = “ec4e2d27630b3859bda056931ae79fbf”
Match the record with the generated hash “ec4e2d27630b3859bda056931ae79fbf” == “d8578edf8458ce06fbc5bb76a58c5ca4” and the result is not matched.
Because of the generated hash and stored hash is not matched, the permission is not granted and vice versa.

Feel secure already by using non-reverseable algorithm to secure you password? wait a minute, let me show you how to crack it using lookup techniques.

What is lookup technique? in finding plain text of a hashed text all you have to do is :

generating the hashed text from a known plain text and compare the generated hashed text with the target hashed text, if the hashed text matched then we know the origin plain text of it.

Password-Cracking

Exhaustive Search

This is a brute force way that is basically trying all the combinations to find the correct plain text from hash text.

Algorithm:

Given the hash “eccbc87e4b5ce2fe28308fd9f2a7baf3”
Do a loop from first character, in this case “1” to infinite and stop until the plain text is found.

1st iteration = md5(1) = “c4ca4238a0b923820dcc509a6f75849b” == “eccbc87e4b5ce2fe28308fd9f2a7baf3” ? not matched
2nd iteration = md5(2) = “c81e728d9d4c2f636f067f89cc14862c” == “eccbc87e4b5ce2fe28308fd9f2a7baf3” ? not matched
3rd iteration = md5(3) = “eccbc87e4b5ce2fe28308fd9f2a7baf3” == “eccbc87e4b5ce2fe28308fd9f2a7baf3” ? matched
The plain text of “eccbc87e4b5ce2fe28308fd9f2a7baf3” is “3”

Let’s implement them in Ruby:

Run the script

So, that’s it we cracked the hashed text in 0.008171 second!

Let’s try again with larger number such as “10000000”

Cracked in 14.8 seconds just by using interpreted language with no optimization like concurrency and parallelism!

What is the drawback of using this method? in each iteration we need to do calculation and matching procedure and this is not efficient. That’s why we will tweak the lookup a bit by using the technique called “Time-memory tradeoff”.

Time-memory tradeoff

“Time-memory tradeoff” or “Space-time tradeoff” in this case is basically by using pre-calculated lookup table so we don’t need to do calculation and just searching when doing password cracking.

There is a great implementation of this method called “RainbowCrack” that is using lookup table called “Rainbow Tables”. In this article we will create lookup table that is loosely inspired by how rainbow tables work.

Lets jump in to the algorithm:

Preprocessing

Set the range for combination generation. e.g (1..10,000,000)
Create all the hash possibilities and store it with the plain text in a file with this structure:

Slice the cipher to 8 characters and sort them by cipher:

Plain text searching process:

Load the sorted table to the memory and structure them in key-value type.

{“0cc175b9” => “1”, “4a8a08f0” => “3”, “92eb5ffe” => “2”}

Slice the target hash to 8 characters (eg: “4a8a08f09d37b73795649038408b5f33” become “4a8a08f0”).
Search “4a8a08f0” in the memory.
If the record is found, calculate the md5 of the value (eg: md5(3))
If the calculated hash is matched with the target hash, the plain text is found
If the calculated hash is not matched with the target hash, continue the searching.

Now let see the code:

The first one is the code to generate the table, simply run the code using ruby generate_table.rb and it will generate the table in tables directory.

After the table is generated, let’s run the password-cracker

Let see how it performs:

In 5.5 seconds it cracked the password, faster than the exhautive search one that cracked it in 14.8 seconds.

The drawback of using Time-memory tradeoff is that the table generation takes time and for this implementation it needs to load the table to memory which takes a lot of time as well, but once it’s loaded it can search for multiple hashed text until you tipe “stop”.