Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > md5

Автор: mmvds 14.4.2008, 20:56

Возник такой вопрос, возможно ли зная входной вектор хэша md5 получить первоначальные данные (или коллизию к ним), точнее строку. Почти разобрался как это сделать, но появилась пара вопросов: например для хэша 79054025255fb1a26e4bc422aef54eb4, берем его уже известный (вычисленный/подобранный) входной вектор Код d1  31  dd  02  c5  e6  ee  c4  69  3d  9a  06  98  af  f9  5c 2f  ca  b5  87  12  46  7e  ab  40  04  58  3e  b8  fb  7f  89 55  ad  34  06  09  f4  b3  02  83  e4  88  83  25  71  41  5a 08  51  25  e8  f7  cd  c9  9f  d9  1d  bd  f2  80  37  3c  5b d8  82  3e  31  56  34  8f  5b  ae  6d  ac  d4  36  c9  19  c6 dd  53  e2  b4  87  da  03  fd  02  39  63  06  d2  48  cd  a0 e9  9f  33  42  0f  57  7e  e8  ce  54  b6  70  80  a8  0d  1e c6  98  21  bc  b6  a8  83  93  96  f9  65  2b  6f  f7  2a  70 128 байт (1024 бита) кратен 512 битам, все ок. переводим в bin Код 11010001 00110001 11011101 00000010 11000101 11100110 11101110 11000100  01101001 00111101 10011010 00000110 10011000 10101111 11111001 01011100  00101111 11001010 10110101 10000111 00010010 01000110 01111110 10101011  01000000 00000100 01011000 00111110 10111000 11111011 01111111 10001001  01010101 10101101 00110100 00000110 00001001 11110100 10110011 00000010  10000011 11100100 10001000 10000011 00100101 01110001 01000001 01011010  00001000 01010001 00100101 11101000 11110111 11001101 11001001 10011111  11011001 00011101 10111101 11110010 10000000 00110111 00111100 01011011  11011000 10000010 00111110 00110001 01010110 00110100 10001111 01011011  10101110 01101101 10101100 11010100 00110110 11001001 00011001 11000110  11011101 01010011 11100010 10110100 10000111 11011010 00000011 11111101  00000010 00111001 01100011 00000110 11010010 01001000 11001101 10100000  11101001 10011111 00110011 01000010 00001111 01010111 01111110 11101000  11001110 01010100 10110110 01110000 10000000 10101000 00001101 00011110  11000110 10011000 00100001 10111100 10110110 10101000 10000011 10010011  10010110 11111001 01100101 00101011 01101111 11110111 00101010 01110000  Из описания по созданию вектора: Код Шаг 1: выравнивание потока. Входной поток выравнивается так, что бы его длина стала конгруэнтной (сравнимой) с 448 по модулю 512. Выравнивание происходит следующим образом: к потоку добавляется один бит '1', а затем биты '0' до тех пор, пока длина потока не будет сравнима с 448 по модулю 512. Выравнивание происходит всегда, даже если длина потока была уже сравнима с 448 по модулю 512. Таким образом к потоку добавляется минимум 1 бит, максимум - 512. Шаг 2: добавление длины. 64 битное представление длины входного потока (длины потока до выравниваия) добавляется к результату предыдущего шага. Если длина потока превосходит 2^64, то добавляются младшие 64 бит. Эти биты добавляются как 2 32-битных слова, младшее слово добавляется первым. Таким образом на этом шаге длина потока становится кратной 512 битам или 16 32-битным словам. Далее будем рассматривать входной поток как массив M[0 ... N-1] слов длиной N. т.е. идем с конца, сначала необходимо вычесть младшие 64 бита входного потока, тут как раз и проблемы: (1) не совсем понятно, куда добавляются в начало или в конец? Или 32 бита в начало, 32 в конец? Цитата Эти биты добавляются как 2 32-битных слова, младшее слово добавляется первым (2) какое из слов считается младшим?  Хотя, это не так важно, главное выяснить с каго конца убирать 64 бита Затем идем к 1 шагу тут опять тот же вопрос Цитата Выравнивание происходит следующим образом: к потоку добавляется один бит '1', а затем биты '0' до тех пор, пока длина потока не будет сравнима с 448 по модулю 512 (3)куда дописываем нули и единичку в начало или конец? (4) Ну и наконец, когда получим входной поток, в какой последовательности располагаются ASCII номера символов строки?

Автор: mmvds 16.4.2008, 08:37

Дожал я его, к сожалению преобразовать в строку любой вектор не получится :( Необходимо сразу несколько условий: 1) чтобы входной поток был строкой необходима его кратность 8 битам (байту), смотрим пример выше:  а) убираем последние 64 бита,  б) последний байт 10010011, убираем 1, нулей с конца больше нет, получаем входной поток размером 959 бит, не кратен 8 :( Т.е. необходимо, чтоб 120-ый байт имел вид 10000000 (0x80) Программа md5coll строит коллизии (точнее находит 2 разных входных вектора с одним хэшем) и у ее входных векторов 120-ый байт как раз 1000000, но даже это не поможет построить строку-коллизию, т.к. из-за стандарта ASCIIZ: 2) будет необходимо, чтобы 119-ый байт был нулевым (окончание строки) и третье условие: 3) до 119-ого байта не должно быть нулевых байтов, по той же причине В общем вероятность возможности преобразования входного вектора, а точнее самого входного потока в строку близка к 0.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)