SHARE
TWEET

inc/HashCrach.class.php

a guest Sep 2nd, 2011 663 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
Top