MD5 Decryption
After seeing lots and lots of people on various IRC-channels and newsgroups requesting ways of decrypting a MD5-checksum, I decided to write this little article describing why you most likely do not want to decrypt a MD5-checksum while still being able to use the algorithm for e.g. storing passwords in a database table.
I will also give a few examples of how actually to get the text which is stored in the MD5-checksum. But before you start reading remember that these methods is only suitable for very small strings, you are never going to create a 650mb ISO-file from a MD5-checksum. If you do, I will buy you a beer.
"MD5 is an algorithm that is used to verify data integrity through the creation of a 128-bit message digest from data input (which may be a message of any length) that is claimed to be as unique to that specific data as a fingerprint is to the specific individual. MD5, which was developed by Professor Ronald L. Rivest of MIT, is intended for use with digital signature applications, which require that large files must be compressed by a secure method before being encrypted with a secret key, under a public key cryptosystem. MD5 is currently a standard, Internet Engineering Task Force (IETF) Request for Comments (RFC) 1321. According to the standard, it is "computationally infeasible" that any two messages that have been input to the MD5 algorithm could have as the output the same message digest, or that a false message could be created through apprehension of the message digest. MD5 is the third message digest algorithm created by Rivest. All three (the others are MD2 and MD4) have similar structures, but MD2 was optimized for 8-bit machines, in comparison with the two later formulas, which are optimized for 32-bit machines. The MD5 algorithm is an extension of MD4, which the critical review found to be fast, but possibly not absolutely secure. In comparison, MD5 is not quite as fast as the MD4 algorithm, but offers much more assurance of data security."
taken from searchSecurity.com
Bruteforce algorithm
As soon as I get the time to look through some of my old backup CDs I will post some of my old bruteforce algorithm implementations.
Combinations
+--------------------+-----------------------------+ | Character set | # of combinations | +--------------------+-----------------------------+ | alphabet lowercase | 25^n | | [a-z] | 25^6 = 244140625 | +--------------------+-----------------------------+ | alphabet lowercase | 50^n | | and uppercase | 50^6 = 15625000000 | | [a-zA-Z] | | +--------------------+-----------------------------+ | [a-zA-Z] + numbers | 60^n | | [a-zA-Z0-9] | 60^6 = 46656000000 | +--------------------+-----------------------------+ | above + | 128^n | | special characters | 128^6 = 4398046511104 | | [a-zA-Z0-9!"#@|<>] | | +--------------------+-----------------------------+
Dictionary attack
A dictionary attack is an ofter much faster approach for retrieving a password, but depends solely on the scope of the word list. Large word lists can be found at various sites on the web e.g. ftp://ftp.cerias.purdue.edu/pub/dict/wordlists/ and used instead of having to create all cases to test against.
This will allow you to quickly run through a large amount of possible matches with out much effort. It is though unlikely that any of the words will match, since the password is hopefully not a normal word.
Dictionary attack - dictattack.php - example code
#!env php -q
<?php
// If no arguments given present usage info
if ($_SERVER["argc"] < 2) {
print "Usage: dictattack.php <MD5 checksum> [ <Dictionary file> ]\n";
exit;
}
// Get MD5 checksum from command line
$md5sum = $_SERVER["argv"][1];
// Open word list - either the one from the command line
// or use the default list
if (isset($_SERVER["argv"][2]) && is_file($_SERVER["argv"][2])) {
$words = file($_SERVER["argv"][2]);
} else {
$words = file("/usr/share/dict/words");
}
// Loop through all words
foreach ($words as $word) {
$word = rtrim($word);
if (md5($word) == $md5sum) {
print "Match found! $word = $md5sum\n";
exit;
}
}
print "No matches found!\n";
?>
Extended dictionary attack
An extended dictionary attack combines the benefits from both dictionary and bruteforce attacks.
Users often choose passwords like john16 or baby82, this knowledge is what can be used for creating a more powerfull attack.
For this attack, we would like to append a two character string, containing lower- and uppercase alphabet characters and numbers, to all our words in the word list.
Change the foreach loop in the above code to the code below, and the dictionary attack should work as simple extended dictionary attack.
Extended Dictionary attack - exdictattack.php - example code
<?php
// Charset to append characters from
$charset = "abcdefghijkmnopqrstuvwxyzABCDEFGHJIKLMNPQRSTUVWXYZ0123456789";
// Loop through all words
foreach ($words as $word) {
$word = rtrim($word);
if (md5($word) == $md5sum) {
print "Match found! $word = $md5sum\n";
exit;
}
// Since the word didnt match we will try to append strings to the word
for ($i=0; $i<strlen($charset); $i++) {
for ($j=0; $j<strlen($charset); $j++) {
$word2 = $word.charset[$i].$charset[$j];
if (md5($word2) == $md5sum) {
print "Match found! $word2 = $md5sum\n";
exit;
}
}
}
}
?>
But how can I then use it?
Even though you can not decrypt a MD5 checksum, you can still use it to validate password entered by a user during a login process up against a checksum stored in a database.
Pseduo code
IF (MD5("entered password") == stored_md5_sum) THEN
USER LOGIN SUCCESED.
SQL Query
SELECT 1 FROM users WHERE username="john" AND password=MD5("secret password");