ХЕШ-ФУНКЦИИ
• Свойства, назначение и основы построения хеш-функций.
• Построение хеш-функций на основе блочных шифров.
• Самостоятельные хеш – алгоритмы.
СОДЕРЖАНИЕ:
Свойства, назначение и основы построения хеш-функций. 2
Алгоритм применения хэш-функции. 2
Обобщенная схема хэш – функции. 3
ПРИМЕР ХЭШИРОВАНИЯ.. 4
Гипотеза о существовании односторонних функций. 8
Свойства односторонних хэш-функций. 9
Длины однонаправленных хэш-функций. 9
Коллизии и реверс. 9
Методы построения криптографических хэш-функций. 10
Назначение криптографических хэш-функций. 10
Методы криптоанализа хэш-функций. 10
Построение хеш-функций на основе блочных шифров. 12
Схемы, в которых длина хэш-значения равна длине блока. 13
Модификация схемы Davies-Меуеr 14
Тандемная (Таndеm) и одновременная (Abreast) схемы Davies-Meyer. 15
MDC.. 17
Схема алгоритма выработки MDC.. 18
МDС-2 и МDС-4. 18
Хэш-функция АR.. 20
Хэш-функция ГОСТ. 20
Самостоятельные хэш – алгоритмы. 21
Краткое описание наиболее распространенных алгоритмов. 21
Алгоритм MD2. 21
Алгоритм МD3. 22
Алгоритм MD4. 22
Алгоритм MD5. 23
Описание МD5. 23
Отличия MD5 от MD4. 25
ПОЛНЫЙ ПРИМЕР MD5. 25
SECURE HASH ALGORITHM (SHA) 27
RIPE-МD.. 29
HAVAL.. 29
Snefru. 29
Криптоанализ Snefru. 30
Tiger 30
Выбор хэш-функции. 30
Эвристические принципы, сформулированные Ривестом.. 31
Основные требования к алгоритму с точки зрения пользователя. 31
Свойства, назначение и основы построения хеш-функций.
• Хэш-функция — это процедура обработки сообщения, в результате действия которой формируется строка символов (дайджест сообщения) фиксированного размера. Малейшие изменения в тексте сообщения приводят к изменению дайджеста при обработке сообщения хэш-функцией. Таким образом, любые искажения, внесенные в текст сообщения, отразятся в дайджесте.
Простейшим примером хеш-функции, преобразующей любую последовательность байтов в один байт, является следующая:
y=(a AND NOT e AND NOT u) OR (NOT a AND NOT e AND u) OR (NOT a AND e AND NOT u),
где:
a, e, u- аргументы,
OR - дизъюнкции,
AND - конъюнкции.
Эта функция равна единице только тогда, когда один из ее аргументов равен единице. Пусть задана битовая последовательность. которая состоит из трех байтов. Она для удобства использования записана в три строки:
10 100 100
01 100 011
01 010 110
Определяя поразрядно функцию "y", получаем байт:
10 010 001.
Хеш-функция позволяет преобразовывать код ключа базы данных в ее адрес. Это дает возможность так размещать элементы данных в памяти, что их затем несложно будет найти. Хеш-функции также широко используются при шифровании.
Алгоритм применения хэш-функции:
• перед отправлением сообщение обрабатывается при помощи хэш-функции. В результате получается его сжатый вариант (дайджест). Само сообщение при этом не изменяется и для передачи по каналам связи нуждается в шифровании описанными выше методами;
• полученный дайджест шифруется закрытым ключом отправителя (подписывается ЭЦП) и пересылается получателю вместе с сообщением;
• получатель расшифровывает дайджест сообщения открытым ключом отправителя;
• получатель обрабатывает сообщение той же хэш-функцией, что и отправитель и получает его дайджест. Если дайджест, присланный отправителем, и дайджест, полученный в результате обработки сообщения получателем, совпадают, значит, в сообщение не было внесено искажений.
Обобщенная схема хэш – функции
Первым шагом при выработке хэш-свертки является разбиение входных данных на последовательность битовых блоков определенной длины.
Дополнения до блока требуемой длины возможно: нулями, пробелами, иными символами, вычисленными по определенным правилам значениями.
При программировании в среде.NET справочную информацию по способам построения блоков требуемой длины можно получить в справке к
System.Security.Cryptography. PaddingMode (режимы дополнения).
При использовании в программах данного пространства имен можно добиться автоматического дополнения входных блоков данных до требуемой длины.
Каждый полученный битовый блок в свою очередь разбивается на стандартные блоки меньшей длины в соответствии с размером входных данных для обеспечения работы основной части алгоритма хэширования.
На каждом шаге алгоритма получаются некоторые промежуточные выходные данные: также в виде битовых блоков. Это так называемая хэш-свертка блока. Она получается в общем случае применением алгоритма хэширования к входным данным, к которым каким-либо образом присоеденена, сконкатенирована свертка с предыдущего шага алгоритма.
Таким образом, происходит последовательная обработка входных блоков данных.
Выход основного алгоритма на последнем шаге (при этом на входе был последний блок данных) определяет блоки для получения результирующей хэш-свертки.
Пример получения хэш-свертки для текста произвольной длины:
ПРИМЕР ХЭШИРОВАНИЯ
Остановимся подробнее на алгоритме хэширования.
Пусть мы хотим найти хэш сообщения длиной b бит.
b - неотрицательное число (т.е. возможно 0), не обязательно кратное 8.
Примем за исходные данные сообщение:
«Одно из побочных применений хеширования состоит в том, что оно создает своего рода слепок, «отпечаток пальца» для сообщения, текстовой строки, области памяти и т. п. Такой «отпечаток пальца» может стремиться как к «уникальности», так и к «похожести» Яркий пример слепка — контрольная сумма.»
Длина строки сообщения больше 192 байт. Для получения битовой последовательности из сообщения используем ASCII – коды символов строки в двоичном представлении.
На рисунке использовано шестнадцатеричное представление символов сообщения.
12*16+2 = 194 байт = 1552 бита = (512 * 3 +16) бит.
Сообщение выравнивается до длины 448 по модулю 512. Выравнивание
производится всегда, даже если длина сообщения и так равна 448. Выравнивание
производится так: к сообщению добавляется один бит со значением <1>. Далее
добавляются столько битов со значением <0>, сколько необходимо для того,
чтобы длина стала равна 448. Вообще, добавляется минимум один, максимум 512
бит.
Таким образом, дополняем последний /четвертый/ блок до длины 448 бит:
16 бит + 12 + 431*02
Примечание: 16+1+431 = 448
Последний / четвертый/ блок, дополненный описанным выше способом будет выглядеть следующим образом:
Далее к сообщению добавляется 64х-битовая длина оригинального сообщения. В
маловероятном случае, если длина сообщения больше 2^64, добавляются только
младшие 64 бита. Биты добавляются как два 32х битовых слова, младшее идет
первым (всего 8 байт = 2слова по 4 байта).
Длина исходного сообщения 194байта = 1552 бита = 61016 = 210 +29+24.
110000100002
09876543210
61016 = 2*162+6*161+2*160.
Записываем в первое 4 байтовое слово. Второе слово заполняем двоичными нулями.
После этого шага сообщение имеет длину, кратную 512 битам. Разделим каждый его блок на 16 блоков длиной по 32 бита.
Получаем 4 * (16блоков*32бита) = 2048бит.
Алгоритм на каждом шаге хэширования получает на вход блок длиной 32 бита.
Приведенное выше описание дополнения сообщения до требуемой длины справедливо для большинства используемых сейчас алгоритмов хэширования, в частности для MD5.
Далее в действие вступает собственно алгоритм хэширования:
Для примера получения хэш-свертки можно рассмотреть самую элементарную функцию, при этом должно быть ясно, что криптостойкости подобная функция обеспечить не способна.
Описание:
Пусть на выходе мы должны получить хэш-свертку длиной 32 бита = 4 байта.
Пусть на вход функции получаем:
1. 32 -х битный блок данных /4 байта/;
2. 1 и 3 –й байты 32-х битного выхода алгоритма на предыдущем шаге.
Действия алгоритма:
1. Двоичное сложение 1 и 3, 2 и 4 байтов входного блока сообщения. При сложении перенос разряда не учитывается, т.е. берется младший байт результата каждого сложения.
2. Построение 4 байтового слова из полученных сумм и 1-го и 3-го байтов выхода с прошлого шага алгоритма: чередование как показано на рисунке.
3. Циклический сдвиг битов в слове влево на S бит, где S – сумма двоичных единиц в слове. Таким образом, если в слове 32 бита, то сдвиг может быть осуществлен на 0 – 32 бита влево.
4. Полученное в результате 4 байтное слово будет выходом алгоритма на каждом конкретном шаге.
На первом шаге алгоритма в качестве замены для байтов с предыдущего шага будем использовать значения следующего вида: 110011002 – замена первого байта выхода, 101010102 – замена третьего байта выхода.
На последнем шаге алгоритма на выходе получаем требуемое 32 битное значение хэш-свёртки нашего сообщения. При этом можно изменить байтовую последовательность выхода например с 1234 на 1432.
Для исходного текста, представленного в примере:
CE E4 ED EE – первый блок на входе
1: 11001110
2: 11100100
3: 11101101
4: 11101110
1+3: 110111011
|76543210 – разряды.
Оставляем последний байт: 10111011.
2+4: 111010010
|76543210 – разряды.
Оставляем последний байт: 11010010.
Т.к. мы находимся на первом шаге алгоритма, то в качестве дополнения берем
1доп: 110011002
2доп: 101010102.
10111011_11001100_11010010_10101010 - 32 – разрядное слово.
Подсчитываем количество единиц в слове: 18 единиц.
Осуществляем циклический сдвиг влево на 18 битов:
01001010101010101110111100110011
Разбиваем слово на байты:
01001010_10101010_11101111_00110011
1 2 3 4
Шаг не является последним, поэтому продолжаем выполнение алгоритма.
Выбираем в соответствии с алгоритмом 1 и 3 байты для использования на последующем шаге алгоритма:
1доп: 010010102
2доп: 111011112
Второй шаг алгоритма:
20 E8 E7 20 – следующие 4 байта в последовательности символов сообщения:
1: 001000002
2: 111010002
3: 111001112
4: 001000002
1+3: 100001000
|76543210 – разряды.
Оставляем последний байт: 10002
2+4: 100000111
|76543210 – разряды.
Оставляем последний байт: 1112
Составляем 32 – разрядное слово:
00001000_01001010_00000111_11101111
Подсчитываем количество единиц в слове: 14 единиц.
Осуществляем циклический сдвиг влево на 14 битов:
10000001111110111100001000010010
Разбиваем слово на байты:
10000001_11111011_11000010_00010010 – хэш – свертка на шаге 2.
1 2 3 4
Шаг не последний, выбираем 1 и 3 байты для использования на последующем шаге алгоритма:
1доп: 100000012
2доп: 110000102
… последующие шаги выполняются аналогично. На последнем шаге при получении результирующей хэш-свертки изменим битовую последовательность выхода на: 1432.
