Md5 crack

From Dionyziz

The MD5 algorithm is often used for one-way password encryption to store on web sites. Although it provides sufficiently adequate protection against mass password cracking, individual password cracking is achievable, providing the passwords are simple enough.

PHP is not a fast language, hence it is inappropriate for CPU-intensive operations such as password cracking. However, it is good enough for small passwords, and for showcasing. In real-world applications, one would more often use C++ for this purpose.

This document aims to demystify how cracking algorithms work, illustrating how a brute force and a dictionary attack work respectively. The code provided in this section is for educational purposes only.

Two simple programs in PHP follow, that are designed to crack MD5-encrypted passwords. The first uses a brute force attack, while the second uses a Dictionary attack.

[edit] Brute Force Attack

A simple md5 brute forcing script in PHP. "MAXLEN" specifies the maximum number of characters in the password (inclusive), "CRACK" specifies the target hash, and $chars is an array of available characters (in the example, lower-case Latin characters and numbers).

<?php
    // Brute force md5 password crack
    $startts = microtime( true );
    
    define( 'MAXLEN' , 6 );
    define( 'CRACK' , '098f6bcd4621d373cade4e832627b4f6' );
    
    $chars = array_merge( 
                range( 0, 9 ), // 10
                range( 'a', 'z' ) // 26
            );
    $diglen = count( $chars );
    
    function inc( &$array, $pos ) {
        global $diglen;
        global $chars;
        
        if ( $pos >= count( $array ) ) {
            return false;
        }
        
        if ( ++$array[ $pos ] >= $diglen ) {
            $array[ $pos ] = 0;
            return inc( $array, $pos + 1 );
        }
        return true;
    }
    
    function timeme() {
        global $startts;
        
        echo "\n";
        $endts = microtime( true );
        $ts = $endts - $startts;
        ?>Operation took <?php
        echo $ts;
        ?> seconds.<?php
    }
    
    for ( $numchars = 0; $numchars <= MAXLEN; ++$numchars ) {
        echo "Testing $numchars-digits passwords...\n";
        if ( $numchars == 0 ) {
            $mm = array();
        }
        else {
            $mm = array_fill( 0, $numchars, 0 );
        }
        do {
            $ll = '';
            for ( $j = 0; $j < count( $mm ); ++$j ){
                $ll .= $chars[ $mm[ $j ] ];
            }
            if ( md5( $ll ) == CRACK ) {
                echo 'Password: ' . $ll . "\n";
                timeme();
                exit();
            }
        } while ( inc( $mm, 0 ) );
    }
    
    echo pow( $diglen, MAXLEN );
    ?> passwords tested, password not found.<?php
    timeme();
?>

[edit] Dictionary Attack

A dictionary attack is often faster and simpler, but not as rigorous. Again 'CRACK' refers to the hash in question, while 'DICT' is the location is a dictionary file, having one word per line, in Windows format.

A dictionary with common English words is available.

<?php
    // dictionary md5 password crack
    $startts = microtime( true );
    
    define( 'CRACK' , '098f6bcd4621d373cade4e832627b4f6' );
    define( 'DICT' , 'English.txt' );
    
    $lines = explode( "\r\n", file_get_contents( DICT ) );
    
    function timeme() {
        global $startts;
        
        echo "\n";
        $endts = microtime( true );
        $ts = $endts - $startts;
        ?>Operation took <?php
        echo $ts;
        ?> seconds.<?php
    }
    
    foreach ( $lines as $line ) {
        if ( md5( $line ) == CRACK ) {
            echo 'Password: ' . $line . "\n";
            timeme();
            exit();
        }
    }
    
    echo count( $lines );
    ?> passwords tested, password not found.<?php
    timeme();
?>

[edit] Running

Here are the example runs of both cracking mechanisms:

dionyziz@Jupiter ~ $ php crack2.php
 Password: test
 
 Operation took 1.31975698471 seconds.
 
dionyziz@Jupiter ~ $ php crack.php
 Testing 0-digits passwords...
 Testing 1-digits passwords...
 Testing 2-digits passwords...
 Testing 3-digits passwords...
 Testing 4-digits passwords...
 Password: test
 
 Operation took 87.2039868832 seconds.

©2010 dionyziz