inc/HashCrach.class.php

<?php
/*
Binary search in a 2 big separated files .hash and .pass

(c) HarpyWar, 2011 (harpywar@gmail.com)
http://harpywar.com
*/

class HashCrack
{
    public $hash_length; // длина хеша в одной записи файла
    public $hash_compressed; // сжат ли хеш в файле (т.к. хекс, то может быть сжат в 2 раза)
    public $pass_length; // длина пароля в одной записи файла
    public $pass_compressed; // сжат ли пароль в файле (в 2 раза, для цифр)
    public $meta1_length = 2; // длина метаданных (начальная позиция считывания паролей)
    public $meta2_length = 4; // длина метаданных (количество считываемых паролей)



    private $filename; // процессируемый файл (без расширения - должен быть файла .hsh и .pass (если файлы паролей отдельно) )
    private $find_original; // искомый хеш в оригинале
    private $find; // обрезанный искомый хеш
    private $row_length; // длина одной записи в файле

    private $process = true;
    private $avg = 0; // средняя позиция в срезе
    private $avg_prev = 0; // предыдущая средняя позиция в срезе
    private $pos1 = 0; // первая позиция в файле, для среза
    private $pos2 = 0; // вторая позиция в файле, для среза

    private $db_steps = 0; // количество шагов, пройденных для поиска хеша
    private $db_size = 0; // размер файла в байтах
    private $db_elapsed = 0; // затраченное время на поиск в секундах
    private $db_bytes_read = 0; // количество считанных байтов

    function __construct($filename, $hash_length = 3, $hash_compressed = true, $pass_length = 8, $pass_compressed = false, $meta1_length = 2, $meta2_length = 4)
    {
        $this->filename = $filename;
        if ( !is_readable($this->filename . '.hash') )
            die ("can't read " . $this->filename . '.hash');

        $this->hash_length = $hash_length;
        $this->hash_compressed = $hash_compressed;
        $this->pass_length = $pass_length;
        $this->pass_compressed = $pass_compressed;
        $this->meta1_length = $meta1_length;
        $this->meta2_length = $meta2_length;
        $this->row_length = $this->hash_length + $meta1_length + $meta2_length;

    }

    public function Search($find)
    {
        if ( !HashHelper::validate($find) )
            return false;

        $timer = new Timer();
        $timer->Start();

        $this->find_original = $find;
        $this->find = HashHelper::Crop($find, ($this->hash_compressed) ? $this->hash_length * 2 : $this->hash_length);


        $this->db_size = filesize($this->filename . '.hash');
        $fp = fopen($this->filename . '.hash', 'rb');

        $this->pos2 = $this->db_size;
        $prev_pos1 = 0;
        $prev_pos2 = 0;
        $output = false;
        while ($this->process)
        {
            // FIXME: $pos 2 всегда > $pos1, поэтому следующее условине ненужно:
            // ($this->pos1 > $this->pos2) ? ($this->pos1 - $this->pos2) / 2 + $this->avg_prev :
            $this->avg = ($this->pos2 - $this->pos1) / 2 + $this->avg_prev;
            $this->avg = ceil($this->avg);

            // коррекция позиции
            $pos_read = $this->avg - ($this->avg % $this->row_length);

            $hash = $this->readHash($fp, $pos_read);


            //var_dump( $hash, $this->db_steps);

            // debug
            #echo var_dump($this->pos1, $this->pos2, $this->avg, $pos_read, $hash, HashHelper::CompareHashes($this->find, $hash), $this->find);
            #echo "<br>";

            // если хеш найден
            if ($hash == $this->find)
            {
                // считать все предыдущие и последующие совпадающие хеши от данной позиции
                // т.к. в файле хранятся только начала хешей, то они могут быть одинаковыми
                // но они отсортированы, и если их попадется несколько, нужно восстановить
                // эти хеши из паролей и затем сравнить каждый из них с тем, который ищется

                list($pass_count, $pass_startline) = $this->readHashMetaData($fp, $pos_read);
                #var_dump($pass_count, $pass_startline * $this->pass_length);

                // считать пароли из файла паролей
                if ( $passwords = $this->loadPasswords($pass_startline, $pass_count) )
                    $output = $passwords;

                $this->process = false;
                break;
            }

            // если искомый хеш выше текущего
            if ( HashHelper::CompareHashes($this->find, $hash) )
            {
                $this->pos1 = $pos_read;
                $this->avg_prev = $this->avg;
            }
            // если ниже
            else
            {
                $this->pos2 = $pos_read;
                $this->avg_prev = $this->pos1;
            }
            // FIXME: HashHelper::CompareHashes возвращает null = конец файла,
            //        но до него не дойдет - можно не обрабатывать,
            //        т.к. если хеши равные, то это обработается раньше

            // конец файла, хеш не найден
            if ($this->avg <= 1 or $this->avg >= $this->db_size)
                $this->process = false;

            // не конец и не начало, но где-то на середине данного хеше не найдено
            if ($prev_pos1 == $this->pos1 && $prev_pos2 == $this->pos2)
                $this->process = false;

            $prev_pos1 = $this->pos1;
            $prev_pos2 = $this->pos2;

            // DEBUG: force stop
            $this->db_steps++;
            #if ($db_steps > 10)
            #   $this->process = false;
        }
        // debug
        #var_dump($this->steps);

        $this->db_elapsed = $timer->Stop();
        fclose($fp);

        return $output;
    }

    public function GetDbSize()
    {
        return $this->db_size;
    }
    public function GetDbSteps()
    {
        return $this->db_steps;
    }
    public function GetDbRows()
    {
        $rows = $this->db_size / $this->row_length;
        return $rows;
    }
    public function GetDbElapsed()
    {
        return $this->db_elapsed;
    }
    public function GetDbBytesRead()
    {
        return $this->db_bytes_read;
    }



    // возвращает массив паролей, соответствующих найденному обрезку хеша
    // загружает пароли из файла .pass, начиная со $startLine (позиция * длина_пароля), до $count * длина_пароля
    //  предполагается, что файл .pass определенной структуры, и если доходит до этой функции, то хотя бы один пароль обязательно должен
    //  находиться в данном интервале
    private function loadPasswords($startLine, $count)
    {
        $cur_pos = $read_pos = $startLine * $this->pass_length; // читаемая позиция в байтах
        $PHP_INT_MAX_32 = 2147483647; // на 32 бит
        $file_num = 0; // номер текущего читаемого файла паролей

        // если начальная позиция чтения больше макс. int
        if ($cur_pos > $PHP_INT_MAX_32)
        {
            // изменяем номер файла
            $file_num = floor( $cur_pos / $PHP_INT_MAX_32 );
        }
        //$passwords_in_file = floor($PHP_INT_MAX_32 / $this->pass_length) * $this->pass_length; // макс. количество паролей в файле паролей

        if ( !is_readable($this->filename . $file_num . '.pass') )
            die ("can't read " . $this->filename . $file_num . '.pass');

        $fp_pass = fopen($this->filename . $file_num . '.pass', 'rb');
        $filesize = filesize($this->filename . '0.pass'); // размер нулевого файла, т.к. он всегда самый большой
        #$this->db_size += $filesize;
        $passwords = array();

        for ($pos = $cur_pos;
                $pos <  $cur_pos + ($count * $this->pass_length);
                $pos += $this->pass_length)
            {

                $read_pos = ( ($pos >= $filesize) && ($file_num > 0) )
                                ? $pos - ($file_num * $filesize)  // FIXME
                                : $pos;

                // если позиция чтения = концу текущего файла
                if ( $read_pos == $filesize )
                {
                    // закрываем предыдущий файл паролей и открываем следующий
                    fclose($fp_pass);
                    $fp_pass = fopen($this->filename . ++$file_num . '.pass', 'rb');
                    #$this->db_size += filesize($this->filename);
                    $read_pos = 0;
                }

                //2147483646 - 4294967292

                // debug - прибавить это к $passwords[] и вывести в индексе дампом
                #. " - " . $read_pos . " - " . $pos . " - " .$file_num

                $passwords[] = $this->readPassword($fp_pass, $read_pos);
            }

        fclose($fp_pass);

        return $passwords;
    }


    // возвращает запись длиной $length) с заданной позиции $pos, либо false
    private function readRow($fp, $pos, $length)
    {
        if ( fseek($fp, $pos) == -1 )
            return false;

        $this->db_bytes_read += $length;

        // читаем данные
        if ( !$row = fread($fp, $length) )
            return false;


        //var_dump($row, $pos);

        return $row;
    }


    // возвращает хеш с данной позиции файла
    private function readHash($fp, $pos)
    {
        $hash = $this->readRow($fp, $pos, $this->hash_length);
        $hash = HashHelper::parseHash($hash, $this->hash_compressed);

        return $hash;
    }
    private function readPassword($fp_pass, $pos)
    {
        $pass_bin = $this->readRow($fp_pass, $pos, $this->pass_length);
        $pass = HashHelper::parsePassword($pass_bin, $this->pass_compressed); // парсим пароль, на случай если он сжат
        return $pass;
    }
    // читаем мета данные хеша, по которым обращаемся к файлу пароля
    // возвращает массив из 2х элементов
    private function readHashMetaData($fp, $pos)
    {
        $meta1 = $this->readRow($fp, $pos + $this->hash_length,  $this->meta1_length);
        $meta2 = $this->readRow($fp, $pos + $this->hash_length + $this->meta1_length, $this->meta2_length);

        $meta = array();
        $meta[0] = HashHelper::parseMetaData($meta1);
        $meta[1] = HashHelper::parseMetaData($meta2);

        return $meta;
    }

}


class HashHelper
{
    /*
        $hash1="4a9f67";
        $hash2="8009ce";
        $h = new HashHelper();
        echo $h->CompareHashes($hash1, $hash2);
    */
    // сравнение 2х хешей ("0698af", "f9c0bb")
    //  если $hash1 > $hash2, то true
    //  если $hash1 < $hash2, то false,
    public static function CompareHashes($hash1, $hash2)
    {
        $bool = null;
        for ($i = 0; $i < strlen($hash1); $i++)
        {
            // сравниваем последовательно dec у каждого байта
            if ($hash1[$i] != $hash2[$i])
                $bool = ( ord($hash1[$i]) > ord($hash2[$i]) ) ? true : false;

            if ($bool !== null)
                break;
        }
        return $bool;
    }


    /*
        $tmp = array(chr(0xC0), chr(0xFF), chr(0xBE));
        $hash_bin = implode("", $tmp);
        $h = new HashHelper();
        echo $h->BinToString($hash_bin);
    */
    // конвертирует бинарный хеш в строку из hex от каждого символа (строка удваивается)
    public static function BinToString($str)
    {
        $hex = "";
        for ($i = 0; $i < strlen($str); $i++)
        {
            $s = ord($str[$i]);
            $s = dechex($s);
            $s = str_pad($s, 2, "0", STR_PAD_LEFT);
            $hex .= $s;
        }

        return $hex;
    }

    // обрезать хеш c начала строки
    public static function Crop($hash, $length = 6)
    {
        return substr($hash, 0, $length);
    }

    /*
        $hash = "test".chr(0x00);
        $h = new HashHelper();
        var_dump ( $hash );
        var_dump ( $h->Trim($hash) );
    */
    // удалить нулевые байты справа (для пароля - у него 8 символов всегда)
    public static function Trim($str, $char = false )
    {
        if (!$char)
            $char = chr(0x00);

        return rtrim($str, $char);
    }

    // возвращает читаемый хеш
    public static function parseHash($hash, $compressed = false)
    {
        if ($compressed)
            $hash = self::BinToString($hash);

        return $hash;
    }
    // возвращает читаемый пароль
    public static function parsePassword($pass, $compressed = false)
    {
        if ($compressed)
        {
            $pass = self::BinToString($pass); // символ F - заглушка в сжатом пароле из цифр
            $pass = self::Trim($pass, 'f');
        }
        else
            $pass = self::Trim($pass);

        return $pass;
    }
    // возвращает распакованные метаданные хеша (число)
    public static function parseMetaData($data)
    {
        $data = self::BinToString($data); // символ F - заглушка для данных из цифр

        $data = self::Trim($data, 'f');
        return $data;
    }

    public static function validate($hash)
    {
        // pvpgn hash всегда состоит из 40 символов!
        if (!preg_match("/^[0-9abcdef]{40}$/", $hash))
            return false;

        return true;
    }

}



class Timer {

    private $time1 = 0;
    private $time_m1 = 0;


    public function __construct() {}

    public function Start()
    {
        //таймер для определения времени генерации страницы
        $this->time1 = time();
        $this->time_m1 = microtime();
    }

    public function Stop()
    {
        //таймер для определения времени генерации страницы
        $time2 = time();
        $mtime = abs ($time2 - $this->time1);
        $time_m2 = microtime();
        $mtime_m = abs ($time_m2 - $this->time_m1);
        $mtime_m = substr($mtime_m, 2, 3);
        $mtime .= "." ."$mtime_m";
        return $mtime;

    }


}