1. PHP / Говнокод #25945

    0

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    38. 38
    39. 39
    40. 40
    41. 41
    42. 42
    43. 43
    44. 44
    45. 45
    46. 46
    47. 47
    48. 48
    49. 49
    50. 50
    51. 51
    52. 52
    53. 53
    54. 54
    55. 55
    56. 56
    57. 57
    58. 58
    59. 59
    60. 60
    61. 61
    62. 62
    63. 63
    64. 64
    65. 65
    66. 66
    67. 67
    68. 68
    69. 69
    70. 70
    71. 71
    72. 72
    73. 73
    74. 74
    75. 75
    76. 76
    77. 77
    78. 78
    79. 79
    80. 80
    81. 81
    82. 82
    83. 83
    84. 84
    85. 85
    86. 86
    87. 87
    88. 88
    89. 89
    90. 90
    91. 91
    92. 92
    93. 93
    94. 94
    <?php
    
    function word_by_index($index, $dicts) {
        $sizes = array_map(function($val){return count($val);}, $dicts); // получаем размеры каждого словаря
        $result = '';
        foreach($sizes as $key=>$size) {
            $result .= $dicts[$key][$index % $size]; // сцепляем слово из частей
            $index = floor($index / $size);
        }
        return $result;
    }
    
    function R($hash, $dicts, $total) {
        $index = gmp_intval(gmp_mod(gmp_init($hash, 16), $total));
        return word_by_index($index, $dicts); 
    }
    
    function make_chain($start, $length, $dicts, $total) {
        $chain['start'] = $start;
        for($i = 0; $i < $length; ++$i) {
            $hash = md5($start);                    // <-- сюда вставьте нужную хэш-функцию
            // echo ">>> $hash : $start\n";            // диагностическое сообщение
            $start = R($hash, $dicts, $total);
        }
        $chain['end'] = $hash;
        echo "Chain from ${chain['start']} to ${chain['end']} is ready.\n"; // диагностическое сообщение
        return $chain;
    }
    
    function make_chains($count, $length, $dicts) {
        $sizes = array_map(function($val){return count($val);}, $dicts); // получаем размеры каждого словаря
        $total = array_reduce($sizes, function($carry,$item){return $carry*$item;}, 1); // произведение размеров словарей
        $chains = [];
        mt_srand();
        for($i = 0; $i < $count; ++$i) {
            $word = word_by_index(mt_rand(0, $total - 1), $dicts);  // начинаем цепочку с псевдослучайного слова
            $chain = make_chain($word, $length, $dicts, $total);
            $hash = $chain['end'];                               // используем конец найденной цепочки как индекс для быстрого поиска
            if(!isset($chains[$hash])) $chains[$hash] = [];      // если такого хэша не было в корзине, инициализируем её
            if(!in_array($chain['start'], $chains[$hash])) {     // проверяем на дубли
                $chains[$hash][] = $chain['start'];              // добавляем начало цепочки в корзину
            }
        }
        return $chains;
    }
    
    function find_hash_in_basket($needle, $haystack_start, $haystack_end, $dicts, $total) {
        echo "Роемся в цепочке от $haystack_start до $haystack_end.\n";       // диагностическое сообщение
        $current_word = $haystack_start;
        do {
            $current_hash = md5($current_word);         // <-- сюда вставьте нужную хэш-функцию
            if($current_hash === $needle) {
                 return $current_word;                  // нашли слово, хэш от которого равен заданному
            }
            $current_word = R($current_hash, $dicts, $total);  // роем в глубину
        } while($current_hash !== $haystack_end);
        return false; // не нашли
    }
    
    function search_hash($hash, $dicts, $chains, $length) {
        $sizes = array_map(function($val){return count($val);}, $dicts); // получаем размеры каждого словаря
        $total = array_reduce($sizes, function($carry,$item){return $carry*$item;}, 1); // произведение размеров словарей
        $current_hash = $hash;
        for($i = 0; $i < $length; ++$i) {
              if(isset($chains[$current_hash])) {                // нашли хэш в одной из корзин
                  echo "Лезем в корзину $current_hash.\n";       // диагностическое сообщение
                  foreach($chains[$current_hash] as $start) {    // роемся в корзине
                      $result = find_hash_in_basket($hash, $start, $current_hash, $dicts, $total); // пытаемся найти в каждой из цепочек корзины
                      if($result) {
                          return $result;                        // конец поиска
                      }
                  }
              }
              $next_word = R($current_hash, $dicts, $total);             // копаем в глубину
              $current_hash = md5($next_word);
        }
        return false; // не нашли
    }
    
    ///////////////////// ПРИМЕР //////////////////////////////////
    
    $dicts= array(
          array('свино',  'овце', 'тигро', 'косатко', 'зубро', 'волко', 'кото'),
          array('собака', 'бык',  'лев',   'дельфин', 'бизон')
    );
    
    $chains = make_chains(15, 15, $dicts);
    echo "Радужные таблицы готовы.\n";
    var_dump($chains);
    
    $hash = '360629d3cf05cee0240a23e1251c58a0';
    echo "Пытаемся обратить $hash.\n";
    $word = search_hash($hash, $dicts, $chains, 15);
    echo "$hash is reversed to $word.\n";

    По просьбам трудящихся.

    Выхлоп на Ideone:
    http://ideone.com/otdCDg

    Запостил: ropuJIJIa, 13 Октября 2019

    Комментарии (25) RSS

    • SEO-пост.

      #hybrid_rainbow_table
      #proof_of_concept
      Ответить
    • На ideone не очень красиво получилось: хэш нашёлся в конце цепочки. Если перезапустить с другими размерами цепочек, то он может найтись и в середине цепочки:
      Пытаемся обратить 360629d3cf05cee0240a23e1251c58a0.
      Лезем в корзину 34015e916ea500c831c8e75aa515db92.
      Роемся в цепочке от котобык до 34015e916ea500c831c8e75aa515db92.
      360629d3cf05cee0240a23e1251c58a0 is reversed to свинособака.
      Ответить
    • Сделаем R более непредсказуемой:
      function R($hash, $dicts, $total) {
          $seed = crc32(pack('h*', $hash));               // результат должен быть детерминированным
          mt_srand($seed);                                // mt_srand и mt_rand используем просто как сжимающее отображение
          return word_by_index(mt_rand(0, $total - 1), $dicts); 
      }


      Выхлоп:
      Пытаемся обратить 360629d3cf05cee0240a23e1251c58a0.
      Лезем в корзину 1f7ad860b089c0e1141de02ac1e6e3ef.
      Роемся в цепочке от волкособака до 1f7ad860b089c0e1141de02ac1e6e3ef.
      Лезем в корзину c368c543126e4acd98419c9e64a7fc5a.
      Роемся в цепочке от котолев до c368c543126e4acd98419c9e64a7fc5a.
      Лезем в корзину 4378025c69e2e7d8d8e44a5f075024a7.
      Роемся в цепочке от свинособака до 4378025c69e2e7d8d8e44a5f075024a7.
      360629d3cf05cee0240a23e1251c58a0 is reversed to свинособака.
      Ответить
    • echo "Лезем в корзину $current_hash.\n";       // диагностическое сообщение

      Давно программируешь?

      У тебя сложность поиска какая-то хуевая получается. У тебя нету ни одной операции собственно поиска, в хешмепе или двоичного. В чем профит по сравнению с брутом? Для простоты можешь сделать не гибридные а обычные таблицы.
      Ответить
      • >> У тебя нету ни одной операции собственно поиска, в хешмепе или двоичного.
        Есть: $chains[$current_hash]
        $chains — это хешмеп.

        По сути построение таблиц и есть брут.

        Сложность тут и будет больше, чем у поиска по нерадужной таблице.

        Профит в размере: от каждой цепочки храним только первое и последнее значение. Промежуточные звенья восстанавливаем итерациями во время поиска.

        Просто считай, что радужные таблицы — это архиватор: там тоже тратится время на распаковку, зато требуется меньше места для хранения.
        Ответить
        • А, ну да. Тогда чем больше цепочек - тем эффективнее таблицы?

          >построение таблиц и есть брут.
          В курсе.
          Ответить
          • Чем цепочка длиннее, тем сильнее она экономит память (мы же храним не целиком её, а только начало и конец). Но при очень длинных цепочках замедляется поиск, потому что нужно восстанавливать кучу звеньев.

            Количество же цепочек подбирается таким образом, чтобы звеньями покрыть максимальную часть области значений пароля или хэша. Проблема в том, что трудно проверить, всё мы покрыли или нет, поэтому пользуются априорными оценками (например, если произведение количества цепочек на длину каждой в три раза превышает количество возможных значений пароля, то покрытие будем считать удовлетворительным). А не всё мы можем покрыть из-за того, что в цепочках встречаются одинаковые фрагменты, поэтому в априорной оценке и стоит коэффициент запаса.
            Ответить
    • описал блять код поисковой системы яндекса! заебись
      Ответить
      • Мудло, ты оставил хоть один осмысленный коммент?
        Ответить
    • показать все, что скрыто> По просьбам трудящихся.
      Понемногу уже рядовых ватников отлавливают

      Шести участникам петербургского отделения проправительственного движения "Молодая гвардия" закрыли въезд в шенгенскую зону на 10 лет. По их мнению, причиной стало их участие в акции "Бессмертный полк" в Таллинне минувшей весной.

      Активистка "Молодой гвардии "Единой России" Анастасия Ковеза узнала о введении запрета на пограничном пункте: "Меня остановили на границе с Финляндией и там стали разбираться. Причину не объяснили. Сказали, что все страны Шенгена попадают под этот запрет, хотя претензии есть только у одной страны".

      Ковеза предположила, что запрет появился из-за сотрудничества МГЕР с эстонской организацией "Российские соотечественники в Европе". Организация пригласила мгеровцев поучаствовать в эстонской акции "Бессмертный полк" 9 мая 2019 года. Ковеза утверждает, что сама она на шествие тогда не поехала. Теперь она рассчитывает на поддержку государства: "Мы обратились в МИД и надеемся на их помощь".

      Еще двое коллег Анастасии узнали о запрете на въезд в немецком аэропорту.

      Сергей Христенко написал в соцсетях, что считает запрет "абсолютно политическим решением" и отметил, что акция "Бессмертный полк" в Таллинне была согласована властями эстонского города.
      Ответить
    • gmp_intval(gmp_mod(gmp_init
      Ответить
    • Короче теперь я понял принцип радужных таблиц. Осталось только понять почему они радужные, а также разрешение того что ты писал раньше (циклы/неподвижные точки)
      Ответить
    • Кстати есть тут те кто RSA ломали/дискретный логарифм искали?
      Ответить

    Добавить комментарий