Лабораторная работа №4
Реализация и исследование свойств алгоритмов хэширования
Введение
Функция хэширования – это функция, которая принимает на вход строку битов (или байтов) произвольной длины и выдаёт результат фиксированной длины. Результат работы хэш-функции называется хэш-кодом (или просто хэшем) сообщения. Хэш-функции находят широкое применение в теории кодирования, передачи информации, в разработке программного обеспечения. Примером простейших хэш-функций являются контрольные суммы и CRC-коды. Основное их назначение – обнаружение случайных повреждений данных. В криптографических приложениях к хэш-функциям предъявляются более жёсткие требования. Функции, отвечающие этим требованиям, называются криптографическими хэш-функциями. Наиболее известными алгоритмами хэширования являются алгоритмы семейств MD и SHA. Кроме того, можно построить хэш-функцию на основе блочного симметричного шифра. Ниже приведены основные области применения криптографических хэш-функций.
· Проверка целостности сообщения.
· Электронная цифровая подпись.
· Получение значения фиксированной длины.
· Генерация псевдослучайных чисел.
· Хранение и проверка паролей.
Свойства криптографических хэш-функций
Пусть M – сообщение, H – функция хэширования, h = H (M) – хэш-код.
Криптографическая хэш-функция должна обладать следующими свойствами:
1. Зная M, легко вычислить h.
2. Зная h, трудно найти M, для которого h = H (M).
3. Зная M, трудно найти M¢ такое, что H (M) = H (M¢).
4. Трудно найти два разных сообщения M и M¢, для которых H (M) = H (M¢).
5. Хэш-коды близких по содержимому сообщений должны сильно различаться.
6. Все значения хэш-функции равновероятны.
Свойство 1 требует, чтобы алгоритм вычисления хэш-кода являлся эффективным. Обычно в таких алгоритмах широко используются поразрядные операции над машинными словами.
Свойство 2 называется односторонностью. В контексте данного свойства сообщение M = H -1(h) называют прообразом, а сам хэш-код h – образом. Таких прообразов будет бесконечное множество, однако на практике все они эквивалентны. Для хорошей криптографической функции хэширования не должно существовать обратного преобразования H -1(h), а единственным методом нахождения прообраза должен являться метод прямого перебора. Если хэш-код имеет длину n битов, то в среднем необходимо будет перебрать 2 n сообщений.
Два сообщения M и M¢, для которых H (M) = H (M¢), называются коллизией. Задача поиска коллизий является более простой, чем поиск прообраза: согласно парадоксу «дней рождения» для нахождения коллизии достаточно перебрать в среднем 2n/2 различных сообщений.
Свойство 5 утверждает, что два сообщения, отличающиеся всего одним битом, должны иметь сильно различающиеся хэш-коды. Данное свойство часто называют «лавинным » эффектом.
Свойство 6 требует, чтобы хэш-функция была близка к случайному отображению, то есть значение хэш-функции можно рассматривать как псевдослучайное число.
Описание алгоритма хэширования MD4
Алгоритм MD4 генерирует 128-битный хэш-код для произвольного входного сообщения. Входное сообщение представляет собой поток битов (или байтов), и может иметь произвольную битовую длину (в том числе нулевую), которую обозначим буквой b.
Словом будем называть 32-разрядное целое значение (unsigned int в языках C/C++). Последовательность байтов сообщения можно рассматривать как последовательность 32-битных слов. Группа из четырёх байтов рассматривается как слово, в котором младший байт является первым байтом группы. Например, группе из четырёх байтов (0x6F, 0x02, 0xE5, 0x8C) соответствует слово 0x8CE5026F (префикс 0x обозначает число в 16-ричной системе счисления). Обратное преобразования слова в последовательность байтов выполняется аналогично. Блоком будем называть последовательность из 512 битов. Блок можно представить в виде массива из 16-ти 32-битных слов.
Таким образом, исходное сообщение разбивается на блоки длиной 512 битов, каждый из которых последовательно подвергается процедуре хэширования. Результат хэширования предыдущего блока используется при вычислении хэша следующего блока.
Перед хэшированием сообщение расширяется так, чтобы его длина была кратной 512. Расширение сообщения состоит из двух этапов.
На первом этапе к сообщению добавляется единичный бит «1». После этого к нему добавляется необходимое число нулевых битов, чтобы длина сообщения была равна 448 по модулю 512. Единичный бит добавляется всегда, даже если длина сообщения уже равна 448 по модулю 512.
На втором этапе к сообщению добавляется 64-битное представление числа b (длины исходного сообщения). Отметим, что первое 32-битное слово содержит младшую часть b, а второе слово – старшую (второе слово равно нулю, если длина сообщения не превосходит 224). При записи этих 32-битных слов порядок байтов также обращается. В итоге длина расширенного сообщения будет кратной 512.
Для вычисления хэш-кода сообщения используется буфер, состоящий из 4-х слов: A, B, C, D. Вначале им присваиваются следующие шестнадцатеричные значения: A = 0x67452301, B = 0xefcdab89, C = 0x98badcfe, D = 0x10325476.
Представим блок в виде массива X, состоящего из 16 слов (X[0]…X[15]). Для каждого такого блока выполняются 3 раунда преобразований. Введём следующие обозначения.
Для первого раунда выражение [abcd k s] обозначает операцию
a = (a + F(b, c, d) + X[k]) <<< s.
Для второго раунда выражение [abcd k s] обозначает операцию
a = (a + G(b, c, d) + X[k] + 0x5A827999) <<< s.
Для третьего раунда выражение[abcd k s] обозначает операцию
a = (a + H(b, c, d) + X[k] + 0x6ED9EBA1) <<< s.
Операция X <<< s обозначает циклический сдвиг влево на s бит. При циклическом сдвиге влево на один бит все биты числа X сдвигаются влево, при этом старший бит записывается в младший разряд. Например, (01000111 <<< 2) = 00011101.
Вспомогательные функции F, G, H имеют следующий вид:
В этих функциях используются поразрядные операции: xy обозначает поразрядное логическое умножение (конъюнкция, операция &), x ˅ y обозначает поразрядное логическое сложение (дизъюнкция, операция |), x̅ обозначает поразрядное логическое отрицание (инверсия, операция ~), x Å y обозначает поразрядное сложение по модулю 2 (исключающее или, операция ^).
Пусть расширенное сообщение представлено в виде массива B, составленного из N блоков. Тогда алгоритм вычисления хэш-кода можно записать в виде следующего псевдокода.
for i = 0 to N do
X = B[i]
// сохранение начальных значений
AA = A
BB = B
CC = C
DD = D
// 1-й раунд (порядок выполнения слева направо, сверху вниз)
[ABCD 0 3] [DABC 1 7] [CDAB 2 11] [BCDA 3 19]
[ABCD 4 3] [DABC 5 7] [CDAB 6 11] [BCDA 7 19]
[ABCD 8 3] [DABC 9 7] [CDAB 10 11] [BCDA 11 19]
[ABCD 12 3] [DABC 13 7] [CDAB 14 11] [BCDA 15 19]
// 2-й раунд
[ABCD 0 3] [DABC 4 5] [CDAB 8 9] [BCDA 12 13]
[ABCD 1 3] [DABC 5 5] [CDAB 9 9] [BCDA 13 13]
[ABCD 2 3] [DABC 6 5] [CDAB 10 9] [BCDA 14 13]
[ABCD 3 3] [DABC 7 5] [CDAB 11 9] [BCDA 15 13]
// 3-й раунд
[ABCD 0 3] [DABC 8 9] [CDAB 4 11] [BCDA 12 15]
[ABCD 2 3] [DABC 10 9] [CDAB 6 11] [BCDA 14 15]
[ABCD 1 3] [DABC 9 9] [CDAB 5 11] [BCDA 13 15]
[ABCD 3 3] [DABC 11 9] [CDAB 7 11] [BCDA 15 15]
A = A + AA
B = B + BB
C = C + CC
D = D + DD
end
После обработки последнего блока значение хэш-функции будет содержаться в переменных A, B, C, D. Обычно хэш-код выводится в виде 16 байтов: от младшего байта A до старшего байта D.
Примеры хэш-кодов для разных строк:
MD4("") = 31d6cfe0d16ae931b73c59d7e0c089c0
MD4("abc") = a448017aaf21d8525fc10ae87aa6729d
MD4("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") =
043f8582f241db351ce627e153e7f0e4
Практическое задание
Задание 1. Программно реализовать алгоритм MD4 хэширования символьной строки. Хэш-код представить в виде 16-ричного числа.
Задание 2. Убедиться в наличии лавинного эффекта. Для этого в исходной символьной строке M изменить один произвольный бит и получить строку M¢. Вычислить и сравнить хэш-коды h = H (M) и h¢ = H (M¢). Определить, какое количество битов в h’ изменилось, по сравнению с h. Для этого можно использовать сложение по модулю |2|. Число различных битов в h и h’ будет равно числу единичных разрядов в h Å h¢.
Задание 3. Программно реализовать процедуру поиска коллизий алгоритма MD4 для хэш-кода различной длины n. Для сокращения количества операций (~ 2 n) до разумного количества использовать не весь хэш-код, а лишь его часть. Пусть алгоритм MD4 возвращает хэш-код в виде четырёх слов A, B, C, D. Тогда в качестве хэш-кода будем использовать только младшие k битов слова A (т.е. k не должно превышать 32). Поиск коллизии производить следующим образом. Последовательно генерировать псевдослучайные строки фиксированной длины L и вычислять их хэш-коды. Для хранения результатов этих операций использовать 2 массива: в один массив записываются сгенерированные строки, а во второй – соответствующие им хэш-коды. Указанные действия продолжать до обнаружения двух одинаковых элементов в массиве хэш-кодов. Вывести на экран соответствующие строки – обнаруженную коллизию, а также количество сгенерированных при её поиске строк.
Задание 4. Программно реализовать поиск прообраза для заданного хэш-кода некоторой строки. В качестве хэш-кода также использовать только часть реального хэш-кода (см. Задание 3). Исходным сообщением является парольная фраза, для которой вычисляется частичный хэш-код длиной k младших бит слова A. Путем формирования псевдослучайных строк найти строку, дающую тот же самый частичный хэш. Вывести найденную строку и количество потребовавшихся итераций. В задании 4 для генерации строк использовать только печатные символы.