Guest User

inc/HashCrach.class.php

a guest
Sep 2nd, 2011
884
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. <?php
  2. /*
  3. Binary search in a 2 big separated files .hash and .pass
  4.  
  5. (c) HarpyWar, 2011 (harpywar@gmail.com)
  6. http://harpywar.com
  7. */
  8.  
  9. class HashCrack
  10. {
  11.     public $hash_length; // длина хеша в одной записи файла
  12.     public $hash_compressed; // сжат ли хеш в файле (т.к. хекс, то может быть сжат в 2 раза)
  13.     public $pass_length; // длина пароля в одной записи файла
  14.     public $pass_compressed; // сжат ли пароль в файле (в 2 раза, для цифр)
  15.     public $meta1_length = 2; // длина метаданных (начальная позиция считывания паролей)
  16.     public $meta2_length = 4; // длина метаданных (количество считываемых паролей)
  17.        
  18.    
  19.    
  20.     private $filename; // процессируемый файл (без расширения - должен быть файла .hsh и .pass (если файлы паролей отдельно) )
  21.     private $find_original; // искомый хеш в оригинале
  22.     private $find; // обрезанный искомый хеш
  23.     private $row_length; // длина одной записи в файле
  24.  
  25.     private $process = true;
  26.     private $avg = 0; // средняя позиция в срезе
  27.     private $avg_prev = 0; // предыдущая средняя позиция в срезе
  28.     private $pos1 = 0; // первая позиция в файле, для среза
  29.     private $pos2 = 0; // вторая позиция в файле, для среза
  30.    
  31.     private $db_steps = 0; // количество шагов, пройденных для поиска хеша
  32.     private $db_size = 0; // размер файла в байтах
  33.     private $db_elapsed = 0; // затраченное время на поиск в секундах
  34.     private $db_bytes_read = 0; // количество считанных байтов
  35.    
  36.     function __construct($filename, $hash_length = 3, $hash_compressed = true, $pass_length = 8, $pass_compressed = false, $meta1_length = 2, $meta2_length = 4)
  37.     {
  38.         $this->filename = $filename;
  39.         if ( !is_readable($this->filename . '.hash') )
  40.             die ("can't read " . $this->filename . '.hash');
  41.    
  42.         $this->hash_length = $hash_length;
  43.         $this->hash_compressed = $hash_compressed;
  44.         $this->pass_length = $pass_length;
  45.         $this->pass_compressed = $pass_compressed;
  46.         $this->meta1_length = $meta1_length;
  47.         $this->meta2_length = $meta2_length;
  48.         $this->row_length = $this->hash_length + $meta1_length + $meta2_length;
  49.  
  50.     }
  51.  
  52.     public function Search($find)
  53.     {
  54.         if ( !HashHelper::validate($find) )
  55.             return false;
  56.    
  57.         $timer = new Timer();
  58.         $timer->Start();
  59.    
  60.         $this->find_original = $find;
  61.         $this->find = HashHelper::Crop($find, ($this->hash_compressed) ? $this->hash_length * 2 : $this->hash_length);
  62.    
  63.        
  64.         $this->db_size = filesize($this->filename . '.hash');
  65.         $fp = fopen($this->filename . '.hash', 'rb');
  66.    
  67.         $this->pos2 = $this->db_size;
  68.         $prev_pos1 = 0;
  69.         $prev_pos2 = 0;
  70.         $output = false;
  71.         while ($this->process)
  72.         {
  73.             // FIXME: $pos 2 всегда > $pos1, поэтому следующее условине ненужно:
  74.             // ($this->pos1 > $this->pos2) ? ($this->pos1 - $this->pos2) / 2 + $this->avg_prev :
  75.             $this->avg = ($this->pos2 - $this->pos1) / 2 + $this->avg_prev;
  76.             $this->avg = ceil($this->avg);
  77.  
  78.             // коррекция позиции
  79.             $pos_read = $this->avg - ($this->avg % $this->row_length);
  80.            
  81.             $hash = $this->readHash($fp, $pos_read);
  82.  
  83.    
  84.             //var_dump( $hash, $this->db_steps);
  85.            
  86.             // debug
  87.             #echo var_dump($this->pos1, $this->pos2, $this->avg, $pos_read, $hash, HashHelper::CompareHashes($this->find, $hash), $this->find);
  88.             #echo "<br>";
  89.  
  90.             // если хеш найден
  91.             if ($hash == $this->find)
  92.             {
  93.                 // считать все предыдущие и последующие совпадающие хеши от данной позиции
  94.                 // т.к. в файле хранятся только начала хешей, то они могут быть одинаковыми
  95.                 // но они отсортированы, и если их попадется несколько, нужно восстановить
  96.                 // эти хеши из паролей и затем сравнить каждый из них с тем, который ищется
  97.                
  98.                 list($pass_count, $pass_startline) = $this->readHashMetaData($fp, $pos_read);
  99.                 #var_dump($pass_count, $pass_startline * $this->pass_length);
  100.  
  101.                 // считать пароли из файла паролей
  102.                 if ( $passwords = $this->loadPasswords($pass_startline, $pass_count) )
  103.                     $output = $passwords;
  104.                
  105.                 $this->process = false;
  106.                 break;
  107.             }
  108.            
  109.             // если искомый хеш выше текущего
  110.             if ( HashHelper::CompareHashes($this->find, $hash) )
  111.             {
  112.                 $this->pos1 = $pos_read;
  113.                 $this->avg_prev = $this->avg;
  114.             }
  115.             // если ниже
  116.             else
  117.             {
  118.                 $this->pos2 = $pos_read;
  119.                 $this->avg_prev = $this->pos1;
  120.             }
  121.             // FIXME: HashHelper::CompareHashes возвращает null = конец файла,
  122.             //        но до него не дойдет - можно не обрабатывать,
  123.             //        т.к. если хеши равные, то это обработается раньше
  124.  
  125.             // конец файла, хеш не найден
  126.             if ($this->avg <= 1 or $this->avg >= $this->db_size)
  127.                 $this->process = false;
  128.            
  129.             // не конец и не начало, но где-то на середине данного хеше не найдено
  130.             if ($prev_pos1 == $this->pos1 && $prev_pos2 == $this->pos2)
  131.                 $this->process = false;
  132.            
  133.             $prev_pos1 = $this->pos1;
  134.             $prev_pos2 = $this->pos2;
  135.            
  136.             // DEBUG: force stop
  137.             $this->db_steps++;
  138.             #if ($db_steps > 10)
  139.             #   $this->process = false;
  140.         }
  141.         // debug
  142.         #var_dump($this->steps);
  143.        
  144.         $this->db_elapsed = $timer->Stop();
  145.         fclose($fp);
  146.        
  147.         return $output;    
  148.     }
  149.    
  150.     public function GetDbSize()
  151.     {
  152.         return $this->db_size;
  153.     }
  154.     public function GetDbSteps()
  155.     {
  156.         return $this->db_steps;
  157.     }
  158.     public function GetDbRows()
  159.     {
  160.         $rows = $this->db_size / $this->row_length;
  161.         return $rows;
  162.     }
  163.     public function GetDbElapsed()
  164.     {
  165.         return $this->db_elapsed;
  166.     }
  167.     public function GetDbBytesRead()
  168.     {
  169.         return $this->db_bytes_read;
  170.     }
  171.    
  172.    
  173.  
  174.     // возвращает массив паролей, соответствующих найденному обрезку хеша
  175.     // загружает пароли из файла .pass, начиная со $startLine (позиция * длина_пароля), до $count * длина_пароля
  176.     //  предполагается, что файл .pass определенной структуры, и если доходит до этой функции, то хотя бы один пароль обязательно должен
  177.     //  находиться в данном интервале
  178.     private function loadPasswords($startLine, $count)
  179.     {
  180.         $cur_pos = $read_pos = $startLine * $this->pass_length; // читаемая позиция в байтах
  181.         $PHP_INT_MAX_32 = 2147483647; // на 32 бит
  182.         $file_num = 0; // номер текущего читаемого файла паролей
  183.        
  184.         // если начальная позиция чтения больше макс. int
  185.         if ($cur_pos > $PHP_INT_MAX_32)
  186.         {
  187.             // изменяем номер файла
  188.             $file_num = floor( $cur_pos / $PHP_INT_MAX_32 );
  189.         }
  190.         //$passwords_in_file = floor($PHP_INT_MAX_32 / $this->pass_length) * $this->pass_length; // макс. количество паролей в файле паролей
  191.        
  192.         if ( !is_readable($this->filename . $file_num . '.pass') )
  193.             die ("can't read " . $this->filename . $file_num . '.pass');
  194.            
  195.         $fp_pass = fopen($this->filename . $file_num . '.pass', 'rb');
  196.         $filesize = filesize($this->filename . '0.pass'); // размер нулевого файла, т.к. он всегда самый большой
  197.         #$this->db_size += $filesize;
  198.         $passwords = array();
  199.        
  200.         for ($pos = $cur_pos;
  201.                 $pos <  $cur_pos + ($count * $this->pass_length);
  202.                 $pos += $this->pass_length)
  203.             {
  204.            
  205.                 $read_pos = ( ($pos >= $filesize) && ($file_num > 0) )
  206.                                 ? $pos - ($file_num * $filesize)  // FIXME
  207.                                 : $pos;
  208.                                
  209.                 // если позиция чтения = концу текущего файла
  210.                 if ( $read_pos == $filesize )
  211.                 {
  212.                     // закрываем предыдущий файл паролей и открываем следующий
  213.                     fclose($fp_pass);
  214.                     $fp_pass = fopen($this->filename . ++$file_num . '.pass', 'rb');
  215.                     #$this->db_size += filesize($this->filename);
  216.                     $read_pos = 0;
  217.                 }  
  218.        
  219.                 //2147483646 - 4294967292
  220.                
  221.                 // debug - прибавить это к $passwords[] и вывести в индексе дампом
  222.                 #. " - " . $read_pos . " - " . $pos . " - " .$file_num
  223.                
  224.                 $passwords[] = $this->readPassword($fp_pass, $read_pos);
  225.             }  
  226.        
  227.         fclose($fp_pass);
  228.        
  229.         return $passwords;
  230.     }
  231.    
  232.    
  233.     // возвращает запись длиной $length) с заданной позиции $pos, либо false
  234.     private function readRow($fp, $pos, $length)
  235.     {
  236.         if ( fseek($fp, $pos) == -1 )
  237.             return false;
  238.        
  239.         $this->db_bytes_read += $length;
  240.        
  241.         // читаем данные
  242.         if ( !$row = fread($fp, $length) )
  243.             return false;
  244.        
  245.    
  246.         //var_dump($row, $pos);
  247.  
  248.         return $row;
  249.     }
  250.    
  251.  
  252.     // возвращает хеш с данной позиции файла
  253.     private function readHash($fp, $pos)
  254.     {
  255.         $hash = $this->readRow($fp, $pos, $this->hash_length);
  256.         $hash = HashHelper::parseHash($hash, $this->hash_compressed);
  257.        
  258.         return $hash;
  259.     }
  260.     private function readPassword($fp_pass, $pos)
  261.     {
  262.         $pass_bin = $this->readRow($fp_pass, $pos, $this->pass_length);
  263.         $pass = HashHelper::parsePassword($pass_bin, $this->pass_compressed); // парсим пароль, на случай если он сжат
  264.         return $pass;
  265.     }
  266.     // читаем мета данные хеша, по которым обращаемся к файлу пароля
  267.     // возвращает массив из 2х элементов
  268.     private function readHashMetaData($fp, $pos)
  269.     {
  270.         $meta1 = $this->readRow($fp, $pos + $this->hash_length,  $this->meta1_length);
  271.         $meta2 = $this->readRow($fp, $pos + $this->hash_length + $this->meta1_length, $this->meta2_length);
  272.            
  273.         $meta = array();
  274.         $meta[0] = HashHelper::parseMetaData($meta1);
  275.         $meta[1] = HashHelper::parseMetaData($meta2);
  276.        
  277.         return $meta;
  278.     }
  279.  
  280. }
  281.  
  282.  
  283. class HashHelper
  284. {
  285.     /*
  286.         $hash1="4a9f67";
  287.         $hash2="8009ce";
  288.         $h = new HashHelper();
  289.         echo $h->CompareHashes($hash1, $hash2);
  290.     */
  291.     // сравнение 2х хешей ("0698af", "f9c0bb")
  292.     //  если $hash1 > $hash2, то true
  293.     //  если $hash1 < $hash2, то false,
  294.     public static function CompareHashes($hash1, $hash2)
  295.     {
  296.         $bool = null;
  297.         for ($i = 0; $i < strlen($hash1); $i++)
  298.         {
  299.             // сравниваем последовательно dec у каждого байта
  300.             if ($hash1[$i] != $hash2[$i])
  301.                 $bool = ( ord($hash1[$i]) > ord($hash2[$i]) ) ? true : false;
  302.            
  303.             if ($bool !== null)
  304.                 break;
  305.         }
  306.         return $bool;
  307.     }
  308.  
  309.    
  310.     /*
  311.         $tmp = array(chr(0xC0), chr(0xFF), chr(0xBE));
  312.         $hash_bin = implode("", $tmp);
  313.         $h = new HashHelper();
  314.         echo $h->BinToString($hash_bin);
  315.     */
  316.     // конвертирует бинарный хеш в строку из hex от каждого символа (строка удваивается)
  317.     public static function BinToString($str)
  318.     {
  319.         $hex = "";
  320.         for ($i = 0; $i < strlen($str); $i++)
  321.         {
  322.             $s = ord($str[$i]);
  323.             $s = dechex($s);
  324.             $s = str_pad($s, 2, "0", STR_PAD_LEFT);
  325.             $hex .= $s;
  326.         }
  327.        
  328.         return $hex;
  329.     }
  330.  
  331.     // обрезать хеш c начала строки
  332.     public static function Crop($hash, $length = 6)
  333.     {
  334.         return substr($hash, 0, $length);
  335.     }
  336.  
  337.     /*
  338.         $hash = "test".chr(0x00);
  339.         $h = new HashHelper();
  340.         var_dump ( $hash );
  341.         var_dump ( $h->Trim($hash) );
  342.     */
  343.     // удалить нулевые байты справа (для пароля - у него 8 символов всегда)
  344.     public static function Trim($str, $char = false )
  345.     {      
  346.         if (!$char)
  347.             $char = chr(0x00);
  348.  
  349.         return rtrim($str, $char);
  350.     }
  351.    
  352.     // возвращает читаемый хеш
  353.     public static function parseHash($hash, $compressed = false)
  354.     {
  355.         if ($compressed)
  356.             $hash = self::BinToString($hash);
  357.            
  358.         return $hash;
  359.     }
  360.     // возвращает читаемый пароль
  361.     public static function parsePassword($pass, $compressed = false)
  362.     {
  363.         if ($compressed)
  364.         {
  365.             $pass = self::BinToString($pass); // символ F - заглушка в сжатом пароле из цифр
  366.             $pass = self::Trim($pass, 'f');
  367.         }
  368.         else
  369.             $pass = self::Trim($pass);
  370.            
  371.         return $pass;
  372.     }
  373.     // возвращает распакованные метаданные хеша (число)
  374.     public static function parseMetaData($data)
  375.     {
  376.         $data = self::BinToString($data); // символ F - заглушка для данных из цифр
  377.  
  378.         $data = self::Trim($data, 'f');
  379.         return $data;
  380.     }
  381.    
  382.     public static function validate($hash)
  383.     {
  384.         // pvpgn hash всегда состоит из 40 символов!
  385.         if (!preg_match("/^[0-9abcdef]{40}$/", $hash))
  386.             return false;
  387.        
  388.         return true;
  389.     }
  390.    
  391. }
  392.  
  393.  
  394.  
  395. class Timer {
  396.  
  397.     private $time1 = 0;
  398.     private $time_m1 = 0;
  399.  
  400.  
  401.     public function __construct() {}
  402.  
  403.     public function Start()
  404.     {
  405.         //таймер для определения времени генерации страницы
  406.         $this->time1 = time();
  407.         $this->time_m1 = microtime();
  408.     }
  409.  
  410.     public function Stop()
  411.     {
  412.         //таймер для определения времени генерации страницы
  413.         $time2 = time();
  414.         $mtime = abs ($time2 - $this->time1);
  415.         $time_m2 = microtime();
  416.         $mtime_m = abs ($time_m2 - $this->time_m1);
  417.         $mtime_m = substr($mtime_m, 2, 3);
  418.         $mtime .= "." ."$mtime_m";
  419.         return $mtime;
  420.  
  421.     }
  422.  
  423.  
  424. }
RAW Paste Data