MD5 — контроль честности
Что такое MD5?
Алгоритм MD5, разработанный в 1991 году профессором Рональдом Л. Ривестом, часто называют алгоритмом шифрования, но на самом деле это неверно. MD5 — это хэш-функция, главным преимуществом которой является то, что обработанные с ее помощью данные восстановить нельзя. Давайте остановимся на этом подробнее.
Предположим, имеется некоторый набор данных. Для простоты будем рассматривать натуральные числа от 1 до 106. И пусть есть некоторая функция, в которой один параметр — натуральное число от 1 до 106, а возвращаемое значение — натуральное число от 1 до 1000. При этом здесь не важно, что именно делает эта функция, важно то, что она каждому натуральному числу от 1 до 106 ставит в соответствие другое натуральное число от 1 до 1000. Для примера рассмотрим одну из самых простых функций, выполняющих это действие:
int hash(long int x){
if (x%1000==0) return 1000;
return (x % 1000);
}
function hash(x:longint):longint;
begin
if (x mod 1000=0) then hash:=1000 else
hash:=x mod 1000;
end;
Это и есть простая хэш-функция. Если мы знаем параметр функции, то однозначно можем сказать, какой будет результат. А если нам известен результат, то можем ли мы узнать однозначно параметр? Конечно, нет. Для числа 234 параметр может быть 234,1234, 2234,3234… Поэтому однозначно восстановить параметр не получится.
Зачем нужен MD5?
Предположим, имеется некоторый набор данных. Для простоты будем рассматривать натуральные числа от 1 до 106. И пусть есть некоторая функция, в которой один параметр — натуральное число от 1 до 106, а возвращаемое значение — натуральное число от 1 до 1000. При этом здесь не важно, что именно делает эта функция, важно то, что она каждому натуральному числу от 1 до 106 ставит в соответствие другое натуральное число от 1 до 1000. Для примера рассмотрим одну из самых простых функций, выполняющих это действие:
int hash(long int x){
if (x%1000==0) return 1000;
return (x % 1000);
}
function hash(x:longint):longint;
begin
if (x mod 1000=0) then hash:=1000 else
hash:=x mod 1000;
end;
Это и есть простая хэш-функция. Если мы знаем параметр функции, то однозначно можем сказать, какой будет результат. А если нам известен результат, то можем ли мы узнать однозначно параметр? Конечно, нет. Для числа 234 параметр может быть 234,1234, 2234,3234… Поэтому однозначно восстановить параметр не получится.
Зачем нужен MD5?
Для функции из примера, если известен результат, можно легко найти параметр, для которого будет такой же результат. А вот для функции MD5 это сделать не так-то просто. Т.е. если у нас есть только результат функции MD5, то мы не сможем найти параметр, для которого функция выдаст этот же результат (речь даже не идет об однозначном восстановлении параметра). В частности, MD5 используют для хранения паролей. После того, как пользователь введет свой пароль, от пароля вычисляется хэш-функция MD5. Результат сравнивается со значением, хранящимся в базе. Если значения равны, то пароль верен. Еще MD5 можно использовать в качестве контрольной суммы. Предположим, необходимо куда-то скопировать файл. Причем нет никаких гарантий, что файл будет доставлен без повреждений. Перед отправкой можно посчитать MD5 от содержимого файла и передать результат вместе с файлом. Затем посчитать MD5 от принятого файла и сравнить два результата. Если результаты различные, то это означает, что файл или результат был испорчен при передаче.
Как работает MD5?
Теперь посмотрим, как именно работает MD5. Для обработки MD5 получает некоторую строку. Эта строка преобразуется в последовательность из нулей и единиц. Как это делается? У каждого символа есть свой номер. Эти номера можно записать в двоичной системе счисления. Получается, каждый символ можно записать как последовательность нулей и единиц. Если этим воспользоваться, получим из строки последовательность из нулей и единиц. Пусть q будет длина получившейся последовательности (ровно 64 бита, возможно, с незначащими нулями). К получившейся последовательности приписывается 1. В результате длина последовательности увеличивается на 1. Затем к последовательности приписываются нули, пока длина не станет по модулю 512 равна 448 (length mod 512=448). Далее к последовательности дописываются младшие 32 бита числа q, а затем — старшие. Длина последовательности становится кратной 512. Полученную последовательность назовем S. Для подсчета результата используются четыре двойных слова (32 бита). Эти двойные слова инициализируются следующими шестнадцатеричными значениями, где первым следует самый младший байт:
A: 01 23 45 67
B: 89 ab cd ef
C: fe dc ba 98
D: 76 54 32 10
Также для подсчета результата используются следующие функции:
F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))
X,Y,Z — это двойные слова. Результаты функций — также двойные слова. Для подсчета используется еще одна функция (назовем ее W). Она хитро обрабатывает данные и возвращает результат (подробно ее описывать не будем, т.к. она выполняет серию простых преобразований). Обработка данных происходит с использованием функций F, G, H, I.
На рисунке схематически изображена функция. Слева — входные данные, справа — выходные.
Теперь рассмотрим, как происходит просчет результата:
1. Запоминаем первые 512 бит последовательности S.
2. Удаляем первые 512 бит последовательности S (можно обойтись и без удаления, но тогда на первом шаге надо брать не первые 512, а следующие 512 бит).
3. Вызываем функцию W. Параметры A,B,C,D — это текущие значения соответствующих двойных слов. Параметр T — это запомненные 512 бит.
4. Прибавляем к A A0.
5. B=B+B0.
6. C=C+C0.
7. D=D+D0.
8. Если длина последовательности 0, выходим.
9. Переходим к шагу 1.
После выполнения этого алгоритма A,B,C,D — это результат (его длина будет 128 бит). Часто можно видеть результат MD5 как последовательность из 32 символов 0..f. Это — то же самое, только результат записан не в двоичной системе счисления, а в шестнадцатеричной.
Можно ли взломать MD5?
В Интернете можно найти много программ, которые обещают найти строку, для которой алгоритм MD5 выдаст заданный результат. Эти программы действительно работают. Ранее отмечалось, что восстановить параметр невозможно. Как же работают эти программы? Они перебирают все возможные строки, применяют к ним алгоритм MD5, а затем сравнивают с образцом. Если значения совпали, это означает, что программа нашла необходимую строку. Однако, у этих программ есть существенный недостаток. Предположим, известно, что программе придется перебрать все слова длиной в 8 символов, состоящих из маленьких и больших латинских букв. Сколько времени это займет? Сколько всего таких слов? На первом месте может стоять любой из 26*2=52 символов. На 2, 3, 4, 5, 6, 7 и 8 — тоже 52. Значит, всего таких слов будет: 52*52*52*52*52*52*52*52=528=53*1012. А если используются не только латинские буквы? То это еще больше. Перебор всех вариантов даже на суперкомпьютере займет годы.
Таким образом, реальный взлом MD5, применяемого онлайн казино, в игре black jack, рулетке, покере, в любом виртуальном игровом автомате и других азартных играх, на практике осуществить невозможно. Будьте осторожны, не попадитесь в лапы мошенников!
