МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ
им. Н.Э. БАУМАНА

РАСЧЕТНО-ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе

«ХЭШ-ФУКЦИИ.
КОЛЛИЗИИ АЛГОРИТМОВ SHA-256, MD5»

Дисциплина «Криптография»

Руководитель:
__________________Аносов В.Д.
Исполнитель:
студент группы ИУ 10-71 ___________Князев Б.А.

Москва
2008
 2

Оглавление
Введение ................................................................................................................... 3
Хэш-функции ........................................................................................................ 3
Бесключевые функции хэширования................................................................ 6
Применение хэш-функций в криптографии ................................................... 9
Ускорение поиска данных............................................................................... 10
Возможные атаки на функции хэширования .............................................. 10
SECURE HASH STANDARD ............................................................................... 13
Блок-схема алгоритма вычисления хэша ............................................................ 18
Блок-схема алгоритма подбора слова к хэшу .................................................... 21
Блок-схема алгоритма поиска коллизий простым перебором для SHA-256 .. 24
Алгоритм Властимила Клима по нахождению коллизии MD5 ........................ 25
Примеры 128 байтовых коллизий MD5 .............................................................. 33
Выводы ................................................................................................................... 35
Литература ............................................................................................................. 37
 3

ВВЕДЕНИЕ

Хэш-функции
Хэширование (англ. hashing) — преобразование входного массива
данных произвольной длины в выходную битовую строку фиксированной
длины, таким образом, чтобы изменение входных данных приводило к
непредсказуемому изменению выходных данных. Такие преобразования
также называются хэш-функциями или функциями свёртки, а их результаты
называют хэшем, хэш-кодом, свёрткой или дайджестом сообщения (англ.
message digest).
Обозначим через X множество, элементы которого будем называть
сообщениями. Обычно сообщения представляют собой последовательности
символов некоторого алфавита, как правило, двоичного. Пусть Y —
множество двоичных векторов фиксированной длины.
Хэш-функцией называется всякая функция h: X → Y, легко вычислимая
и такая, что для любого сообщения М значение h(M) = Н (свёртка) имеет
фиксированную битовую длину.
В общем случае однозначного соответствия между исходными данными
и хэш-кодом быть не может, так как число возможных сообщений
значительно превосходит число возможных значений сверток (рис. 1).Из-за
этого для каждого значения свертки имеется большое множество прообразов,
то есть сообщений с таким же значением свертки. Также существует
множество массивов данных, дающих одинаковые хэш-коды (так
называемые коллизии), и каждая хэш-функция должна оцениваться по
стойкости к возникновению коллизий.
Заметим, что при случайном и равновероятном выборе сообщений
условие равномерности распределения значений хэш-функции эквивалентно
наличию одинакового числа прообразов для каждого значения свертки.
 4

В общем случае для каждого хэша существует

| | | |
| | | | = прообразов (рис. 1).
| | | |

22 1
64

В случае алгоритма SHA-256: 256  22 1256  22 257 прообразов.

64 64

рис. 1.
Для криптографических хеш-функций также важно, чтобы при
малейшем изменении аргумента значение функции сильно изменялось. В
частности, значение хеша не должно давать утечки информации даже об
отдельных битах аргумента.
Среди множества существующих хэш-функций принято выделять
криптографически стойкие, применяемые в криптографии. Как правило,
криптографическая стойкость хэш-функции обеспечивается следующими
свойствами:
 Стойкость к коллизиям первого рода: для заданного сообщения
должно быть практически невозможно подобрать другое сообщение ,
имеющее такой же хэш. Это свойство также называется необратимостью
хэш-функции.
 5

 Стойкость к коллизиям второго рода: должно быть практически

невозможно подобрать пару сообщений , имеющих одинаковый хэш.
Согласно парадоксу о днях рождения, нахождение коллизии для хэш-
функции с длиной значений n бит требует в среднем перебора около 2n / 2

операций. Поэтому n-битная хэш-функция считается криптостойкой, если

вычислительная сложность нахождения коллизий для нее близка к 2n / 2 .

Как правило, хэш-функции строят на основе так называемых

одношаговых сжимающих функций у = f ( x 1 , x 2 ) двух переменных, где x 1 и у
— двоичные векторы длины т и п соответственно, причем п — длина
свертки. Для получения значения h ( M ) сообщение М сначала разбивается
на блоки длины т (при этом если длина сообщения не кратна т, то по-
следний блок неким специальным образом дополняется до полного), а затем
к полученным блокам М 1 , М 2 ,.., М N применяют следующую
последовательную процедуру вычисления свертки:
H0=v,
H 1 = f ( M i ,H i - 1 ) i =1,...,N, (1)
h(M) = HN.
Здесь v — некоторый фиксированный начальный вектор. Если функция
f зависит от ключа, то этот вектор можно положить равным нулевому
вектору. Если же функция f не зависит от ключа, то для исключения
возможности перебора коротких сообщений (при попытках обращения хэш-
функции) этот вектор можно составить из фрагментов, указывающих дату,
время, номер сообщения и т. п.
При таком подходе свойства хэш-функции h полностью определяются
свойствами одношаговой сжимающей функции f .
Особо выделяют два важных типа криптографических хэш-функций —
ключевые и бесключевые. Первые применяются в системах с симметричными
ключами. Ключевые хэш-функции называют кодами аутентификации
 6

сообщений (КАС) (message authentication code (MAC)). Они дают возмож-

ность без дополнительных средств гарантировать как правильность
источника данных, так и целостность данных в системах с доверяющими
друг другу пользователями.
Бесключевые хэш-функции называются кодами обнаружения ошибок
(modification detection code (MDC) или manipulation detection code, message
integrity code (MIC)). Они дают возможность с помощью дополнительных
средств (например, шифрования, использования защищенного канала или
цифровой подписи) гарантировать целостность данных. Эти хэш-функции
могут применяться в системах как с доверяющими, так и не доверяющими
друг другу пользователями. Так как все хэш-функции стандарта SHA
являются бесключевыми, то рассмотрим их более подробно.

Бесключевые функции хэширования

Обычно требуется, чтобы бесключевые хэш-функции обладали
следующими свойствами:
1) однонаправленность,
2 ) устойчивость к коллизиям,
3) устойчивость к нахождению второго прообраза,
означающими соответственно высокую сложность нахождения
сообщения с заданным значением свертки; пары сообщений с одинаковыми
значениями свертки; второго сообщения с тем же значением свертки для
заданного сообщения с известным значением свертки.
Например, хэш-функция CRC-32, представляющая собой контрольную
сумму, является линейным отображением и поэтому не удовлетворяет ни
одному из этих трех свойств.
Использование в качестве бесключевой хэш-функции, построенной на
основе алгоритма блочного шифрования в режиме выработки имитовставки,
также нецелесообразно, так как обратимость блочного шифрования
 7

позволяет подбирать входное сообщение для любого значения свертки при

фиксированном и общеизвестном ключе.
Для построения примера хэш-функции, удовлетворяющей свойству 1),
рассмотрим функцию, заданную формулой g k ( x ) = E k ( x ) ⨁ x , где E k —
алгоритм блочного шифрования. Такая функция является однонаправленной
по обоим аргументам. Поэтому на ее основе можно построить хэш-функцию
по правилу (1), определив одношаговую сжимающую функцию одной из
следующих формул:
f ( x , H ) = E H ( x ) ⨁ x или f ( x , H ) = E x ( H ) ⨁ H .
Первая из этих функций лежит в основе российского стандарта хэш-
функции, а вторая — в основе американского стандарта SHA.

Приведем без доказательства следующие утверждения:

 Если функция хэширования h построена на основе одношаговой

сжимающей функции f по правшу (1), то из устойчивости к коллизиям
функции f следует устойчивость к коллизиям функции h.

 Если хэш-функция устойчива к коллизиям, то она устойчива к

нахождению второго прообраза.

 Устойчивая к коллизиям хэш-функция не обязана быть

однонаправленной.

 Пусть h: X → Y — хэш-функция и | X | > 2|Y|. Тогда если существует

эффективный алгоритм обращения функции h, то существует
вероятностный алгоритм нахождения коллизии функции h с
вероятностью успеха, большей 1/2.
Заметим, что трудоемкость подбора прообраза для однонаправленной
функции или трудоемкость поиска второго прообраза оцениваются
величиной O(2n). В то же время трудоёмкость поиска коллизии оценивается
 8

величиной O(2n/2), так как в данной ситуации применима атака, основанная

на парадоксе "дней рождений".
Рассмотрим конкретные примеры хэш-функций, построенных на основе
некоторых алгоритмов преобразования блоков.
Пусть Еk — алгоритм блочного шифрования, п — размер блока, l —
размер ключа и G — некоторое отображение, ставящее в соответствие
вектору длины п вектор длины l. Рассмотрим следующие одношаговые
сжимающие функции, построенные на основе алгоритма Еk:

а) f ( x , H ) = E x ( H ) ⨁ H (Дэвис — Мейер);
б) f ( x , H ) = E G ( H ) ( x ) ⨁ x (Матиас — Мейер — Осеас);

в) f ( x , H ) = E G ( H ) ( x ) ⨁ x ⨁ Н (Миагучи — Принель).

Значением любой из хэш-функций, построенных по правилу (1) из

приведенных одношаговых сжимающих функций, является вектор длины n,
равной размеру блока. В случае если эта величина оказывается
недостаточной, ее можно увеличить, заменив одношаговую функцию f’ на
функцию f с удвоенной размерностью значений. Это можно сделать,
например, путем двукратного применения функции f с последующим
перемешиванием полублоков согласно формуле:
f ’ ( x ,H 1 , H 2 ) =  (f ( x , H l ) , f ( x ,H 2 ) ) ,
в которой  переставляет произвольные полублоки а, b, с, d по правилу
 ( ( a , b ) ,( c , d ) ) = (a,d , c , b ) . Такой подход, использующий схему (б),
реализован в конструкции одношаговой функции MDC-2.
Другие примеры бесключевых хэш-функций дают известные алгоритмы
MD-4, MD-5 и SHA. Они оперируют с блоками длины n, совпадающей с
длиной результирующего значения свертки, причем п = 128 для алгоритма
MD-4 и п = 160 для MD-5 и SHA. Указанные алгоритмы спроектированы
специально с учетом эффективной реализации на 32-разрядных ЭВМ.
 9

При их использовании исходное сообщение М разбивается на блоки

длиной m = 512 бит. Последний блок формируется путем дописывания к
концу сообщения комбинации 10...0 до получения блока размера 448 бит, к
которому затем добавляется комбинация из 64 бит, представляющая битовую
длину сообщения. Затем вычисляется значение свертки согласно процедуре
(1) с использованием одношаговой сжимающей функции, заданной
формулой f ( x , H ) = E x ( H ) ⨁ H , где х — блок сообщения длины т = 512 бит,
Н— блок из п бит, а Ех— некоторое преобразование множества блоков.
Значение начального вектора определяется в описании преобразования Ех.
В стандарте хэш-функции ГОСТ Р 34.11-94 приняты значения п = т =
512. Одношаговая сжимающая функция f(x,H), используемая для
вычисления последовательности значений Н i = f ( x i , H i - 1 ) , построена на базе
четырех параллельно работающих схем блочного шифрования (ГОСТ 28147-
89), каждая из которых имеет 256-битовый ключ и оперирует с блоками
размера 64 бита. Каждый из ключей вычисляется в соответствии с некоторой
линейной функцией от блока исходного сообщения xi и значения H i - 1 .
Значение H i является линейной функцией от результата шифрования, блока
исходного сообщения xi и значения H i - 1 . После вычисления значения H N для
последовательности блоков М 1 , М 2 ,.., М N применяют еще два шага
вычисления согласно формуле
H=h(M)= f ( Z ⨁ M N , f ( L, H N )), где Z — сумма по модулю два всех
блоков сообщения, а L — длина сообщения.

Применение хэш-функций в криптографии

1) Проверка целостности данных при их передаче или хранении
 с помощью ключевой хэш-функции
 с помощью бесключевой хэш-функции (аутентификация источника
данных)
 10

2) Проверка парольной фразы

В большинстве случаев парольные фразы не хранятся на целевых
объектах, хранятся лишь их хэш-значения.

3) Ускорение поиска данных

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

Хэш-функции имеют также разнообразные применения при проведении

статистических экспериментов, при тестировании логических устройств, при
построении алгоритмов быстрого поиска и проверки целостности записей в
базах данных.

Возможные атаки на функции хэширования

Простейшая атака с целью создания поддельного сообщения,
применимая к любой хэш-функции, состоит в следующем. Злоумышленник
может осуществить генерацию некоторого числа (r1) сообщений, вычислить
значения их сверток и сравнить получившиеся значения с известными
значениями сверток некоторого множества (из r2) переданных ранее со-
общений. Атака окажется успешной при получении хотя бы одного
 11

совпадения. Вероятность успеха Р можно оценить на основании парадокса

"дней рождений". Известно, что эта вероятность оценивается по формуле
r1r2

P  1 e 2n где п — длина свертки, е — основание натуральных
n
логарифмов. Наибольшей эта вероятность становится при r1  r2  2 . В этом 2

случае ее значение приблизительно равно 0,63. (В формуле возможна

r1r2

опечатка, возможно в [1] имелось ввиду P  1  e 22n , тогда вероятность равна
0,39).

0.9

0.8
Вероятность совпадения

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0
0 1024 4096 8192 16384
Количество операций перебора

рис. 2. Иллюстрация парадокса "дней рождений" для n=2^24

Ранее указывалось, что во многих случаях хэш-функции строятся на

основе одношаговых сжимающих функций. Поэтому имеется тесная связь
атак на хэш-функцию с атаками на соответствующую одношаговую
сжимающую функцию. В частности, последняя должна обладать практически
всеми теми же свойствами, которыми обладает и сама хэш-функция.
Итеративный способ построения хэш-функций позволяет иногда при ее
обращении или построении коллизий использовать метод "встречи
 12

посередине". Для защиты от этой опасности в конце сообщения обычно

дописывают блоки с контрольной суммой и длиной сообщения.
Возможны атаки, использующие слабости тех схем, на базе которых
построены хэш-функции. Например, для построения коллизий хэш-функций,
основанных на алгоритмах блочного шифрования, можно использовать
наличие слабых ключей или свойство дополнения (как это имеет место у
алгоритма DES), наличие неподвижных точек (для которых Ек( х ) = х ),
коллизии ключей (то есть пар различных ключей, для которых выполняется
равенство Еk ( х ) = Еk’ ( х ) ) и т. п.
В марте 2008 года индийские исследователи Сомитра Кумар Санадия и
Палаш Саркар опубликовали найденные ими коллизии для 22 итераций SHA-
256 и SHA-512. В сентябре того же года они представили метод
конструирования коллизий для усечённых вариантов SHA-2 (21 итерация).
Ввиду алгоритмической схожести SHA-2 с SHA-1 и наличия у последней
потенциальных уязвимостей ведутся поиски улучшенных альтернатив.
Новый стандарт будет назван SHA-3, он будет определен конкурсом,
проводимым Национальным институтом стандартов и технологий в 2008—
2012 гг.
 13

SECURE HASH STANDARD

Хеш-функции SHA (Secure Hash Algorithm – защищенный хэш алгоритм)

разработаны Агентством национальной безопасности США и
опубликованы Национальным институтом стандартов и технологий в
качестве Федерального стандарта обработки информации FIPS PUB 180-2
в 2002 году. В этот стандарт также была включена хеш-функция SHA-1,
разработанная ещё в 1995. В 2004 в FIPS PUB 180-2 была добавлена SHA-
224. Все эти хеш-функции запатентованы. Агентство национальной
безопасности от лица государства выпустило патент под лицензией Royalty
Free.
Этот стандарт включает 5 защищенных хэш алгоритмов: SHA-1, SHA-
224, SHA-256, SHA-384 и SHA-512. Каждый алгоритм состоит из двух
этапов: первичная обработка и вычисление хэша. Первичная обработка
заключается в “набивке” сообщения, разбиении его на блоки длиной m бит и
инициализации констант, начальных значений хэша.

рис. 3. Свойства SHA алгоритмов

 14

SHA-256 Функции и константы

SHRn ( x)  ( x >> n)

ROTRn ( x)  ( x >> n)  ( x  w  n)

Ch  x, y, z   ( x  y)  (x  z)

Maj  x, y, z   ( x  y)  ( x  z)  ( y  z)


{256}
0
( x)  ROTR 2 ( x)  ROTR13 ( x)  ROTR 22 ( x)


{256}
1
( x)  ROTR 6 ( x)  ROTR11 ( x)  ROTR 25 ( x)
 0{256}  ROTR 7 ( x)  ROTR18 ( x)  SHR 3 ( x)
 1{256}  ROTR17 ( x)  ROTR19 ( x)  SHR10 ( x)

SHA-256 использует последовательность 64-ёх 32-ых битных констант,

K {256}
0 , K1{256} ,..., K63
{256}
. Эти слова представляют собой первые 32 бита дробных
частей кубических корней первых 64 простых чисел.
428a2f98 71374491 b5c0fbcf e9b5dba5 3956c25b 59f111f1 923f82a4 ab1c5ed5
d807aa98 12835b01 243185be 550c7dc3 72be5d74 80deb1fe 9bdc06a7 c19bf174
e49b69c1 efbe4786 0fc19dc6 240ca1cc 2de92c6f 4a7484aa 5cb0a9dc 76f988da
983e5152 a831c66d b00327c8 bf597fc7 c6e00bf3 d5a79147 06ca6351 14292967
27b70a85 2e1b2138 4d2c6dfc 53380d13 650a7354 766a0abb 81c2c92e 92722c85
a2bfe8a1 a81a664b c24b8b70 c76c51a3 d192e819 d6990624 f40e3585 106aa070
19a4c116 1e376c08 2748774c 34b0bcb5 391c0cb3 4ed8aa4a 5b9cca4f 682e6ff3
748f82ee 78a5636f 84c87814 8cc70208 90befffa a4506ceb bef9a3f7 c67178f2

Начальный вектор - первые 32 бита дробных частей квадратных корней

первых 8-ми простых чисел.
H 0(0) = 6a09e667
H1(0) = bb67ae85
H 2(0) = 3c6ef372
H 3(0) = a54ff53a
H 4(0) = 510e527f
H 5(0) = 9b05688c
H 6(0) = 1f83d9ab
H 7(0) = 5be0cd19
 15

SHA-256 Вычисление хэша

Длина исходного сообщения l должна делиться на 512. В конце
сообщения всегда добавляется “1”, затем добавляется такое минимальное
число нулей k (k≥0), чтобы выполнялось равенство .
Последние 64 бита представляют собой длину сообщения.

M добавочная “1” последние 64 бита

10001001111101…. 1001010110000000….0101101….100110

n•512 бит k нулей

всего: (n+1) или (n+2) блоков (если бит)

рис. 4. Пример для сообщения “abc”

Таким образом, сообщение преобразуется, и далее его разбивают на N
512 битных блоков.

Алгоритм вычисления хэша

For i = 1 to N
{
1. Подготавливаем дополнительное сообщение, { Wt }:
M t(i ) 0  t  15
Wt =
 1{256} (Wt 2 )  Wt 7   0{256} (Wt 15 )  Wt 16 16  t  63
 16

2. Инициализация восьми переменных a, b, c, d, e, f, g, и h :

a  H 0(i 1)

b  H1(i 1)

c  H 2(i 1)

d  H 3(i 1)

e  H 4(i 1)

f  H 5(i 1)

g  H 6(i 1)

h  H 7(i 1)
3. For t = 0 to 63
{

T1  h  1
{256}
(a)  Ch(e, f , g )  Kt{256}  Wt

T2   0
{256}
(a)  Maj (a, b, c)

hg
g f
f e
e  d  T1
d c
cb
ba
a  T1  T2
}
4. Вычисляем промежуточный i-тый H(i):
 17

H 0(i )  a  H 0(i 1)

H1(i )  b  H1(i 1)
H 2(i )  c  H 2(i 1)
H 3(i )  d  H 3(i 1)
H 4(i )  e  H 4( i 1)
H 5(i )  f  H 5( i 1)
H 6(i )  g  H 6(i 1)
H 7(i )  h  H 7( i 1)
}
(N) (N) (N) (N) (N) (N) (N) (N)
Итоговый 256 битный хэш : H 0 || H1 || H 2 || H3 || H 4 || H5 || H 6 || H 7

Примеры из [2]:
1. "abc"
ba7816bf 8f01cfea 414140de 5dae2223 b00361a3 96177a9c b410ff61 f20015ad
2. "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"
248d6a61 d20638b8 e5c02693 0c3e6039 a33ce459 64ff2167 f6ecedd4 19db06c1
3. 1000000 букв “а”
cdc76e5c 9914fb92 81a1c7e2 84d73e67 f1809a48 a497200e 046d39cc c7112cd0
 18

БЛОК-СХЕМА АЛГОРИТМА ВЫЧИСЛЕНИЯ ХЭША

файл [Link] с начало

сообщением
инициализация начального вектора H0[8]

определение длины сообщения,

кол-ва блоков N

for i=1 to (N-2)

считывание 64
символов из файла

вычисление вектора W[64]

переменные a, b, c, d, e, f, g, h приравниваются вектору Hi-1 [8]

for t =0 to 63

ввод текущих значений a, b, c, d, e, f, g, h и W[64]

Блок Б1

вывод текущих значений a, b, c, d, e, f, g, h и W[64]

файл [Link] с
хэшэм вычисление промежуточного i-ого хэша Hi [8]

определение последних двух блоков сообщения

вычисление хэша последних двух блоков

запись вычисленного хэша в файл

конец
 19

Для удобства обозначим следующий блок как Б1

a b c d e f g h

T1 T2

рис. 5. Хэш слова “abc”

 20

рис. 6. Хэш слова

“abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq”

рис. 7. Хэш миллиона букв “a”

 21

БЛОК-СХЕМА АЛГОРИТМА ПОДБОРА СЛОВА К ХЭШУ

файл [Link] с начало

хэшэм
Выбор алфавита, кол-ва символов в пароле

считывание первых 32 битов хэша

пока не подберётся
весь хэш

пока не подберутся
первые 32 бита хэша

генерация случайного слова

вычисление хэша случайного слова

for j=1 to 7

считывание следующих 32 битов хэша

сравнение считанных 32 битов с соответствующими

32 битами только что вычисленного хэша
файл [Link] с нет
хэшэм все совпадают?

да
запись подобранного пароля в файл

конец
 22

рис. 8. Демонстрация подбора пароля из 4 букв к хэшу

рис. 9. Демонстрация подбора пароля из 6 букв к хэшу

 23

рис. 10. Демонстрация подбора пароля из 6 букв к хэшу ещё раз

Текущая вероятность подбора слова к хэшу вычисляется как отношение

кол-ва “проверенных” слов (то есть слов, хэши которых считались и
сравнивались с заданным) на данный момент к общему кол-ву слов из
заданного алфавита заданной длины. Так как генератор случайных чисел, а
значит и случайных слов, псевдослучайный, то распределение слов не
равномерно, то есть хэши некоторых слов вычисляются не 1 раз. Таким
образом, в данном случае значение текущей вероятности может быть любым
числом от 0 до n в зависимости от функции распределения генератора. В
результате многочисленных экспериментов было установлено, что n обычно
не больше 3…4.
 24

БЛОК-СХЕМА АЛГОРИТМА ПОИСКА КОЛЛИЗИЙ

ПРОСТЫМ ПЕРЕБОРОМ ДЛЯ SHA-256
начало

пока не совпадут
все биты 2-х хэшэй

while (flag) пока не совпадут

первые 32 бита хэшей

генерация случайного сообщения случайной длины

запоминание этого сообщения

вычисление его хэша

запоминание этого хэша

for j=0 to i

сравнение первых 32 битов только что вычисленного H[i] с 32

битами всех вычисленных хэшей до этого H[j]
да нет
flag = 0; совпадают?

i++

for j=1 to 7

сравнение следующих 32 битов только что вычисленного H[i] с

32 битами всех вычисленных хэшей до этого

нет
все совпадают?
да
конец
 25

АЛГОРИТМ ВЛАСТИМИЛА КЛИМА ПО НАХОЖДЕНИЮ

КОЛЛИЗИИ MD5
В [6] были введены так называемые sufficient conditions (достаточные
условия). Впоследствии эти условия были доработаны Liang J. и Lai X и
описаны в [7]. При успешном получении достаточных условий,
гарантируется нахождение коллизии по дифференциальной схеме [6]. В этом
описании используются именно эти условия.
Сообщения состоят из 2-х 512 битных блоков (M, N) и (HM, HN), где
MD5(M, N) = MD5(HM, HN). Первые блоки M и HM различаются
предопределённым постоянным вектором C1 (HM = M + C1), а вторые блоки
отличаются предопределённым постоянным вектором C2 (HN = N + C2).
Если имеются достаточные условия для блока M (блок 2), результат
хэширования блоков M и HM также отличается предопределённым
постоянным вектором С3 (блок 3). Когда мы переходим к хэшированию
второго бока (и достаточные условия для второго блока выполнены), разница
С3 становится нулевой и мы получаем коллизию (M,N) и (HM,HN). Действия
над первым и вторым блоками похожи, поэтому мы приведём описание для
первого блока.
Блок M состоит из 512 битов, которые получаются из 32 битных слов M =
(x[0], ..., x[15]) за 64 шага. Переменная Q[1] создаётся на первом шаге,
Q[2...64] на следующих шагах.
Переменные Q[-3] (= IV[0] = 0x67452301), Q[-2] (= IV[3] = 0x10325476),
Q[-1] (= IV[2] = 0x98badcfe) и Q[0] (= IV[1] = 0xefcdab89) определяются как
начальные значения, стандартные или выбираемые. После 64 шагов мы
добавляем начальные значения IV[0..3] к последним посчитанным
переменным Q[61...64], что создаёт промежуточный хэш IHV[0...3] от
хэширования первого блока (блок 1). IHV затем вводятся в хэширование
второго блока также, как и IV вводятся в хэширование первого блока.
 26
Q[ 1]=Q[ 0]+RL(F(Q[ 0],Q[-1],Q[-2])+Q[-3]+x[ 0]+0xd76aa478, 7); 0 c.
Q[ 2]=Q[ 1]+RL(F(Q[ 1],Q[ 0],Q[-1])+Q[-2]+x[ 1]+0xe8c7b756,12); 0 c.
Q[ 3]=Q[ 2]+RL(F(Q[ 2],Q[ 1],Q[ 0])+Q[-1]+x[ 2]+0x242070db,17); 17 c.
Q[ 4]=Q[ 3]+RL(F(Q[ 3],Q[ 2],Q[ 1])+Q[ 0]+x[ 3]+0xc1bdceee,22); 21 c.
Q[ 5]=Q[ 4]+RL(F(Q[ 4],Q[ 3],Q[ 2])+Q[ 1]+x[ 4]+0xf57c0faf, 7); 32 c.
Q[ 6]=Q[ 5]+RL(F(Q[ 5],Q[ 4],Q[ 3])+Q[ 2]+x[ 5]+0x4787c62a,12); 32 c.
Q[ 7]=Q[ 6]+RL(F(Q[ 6],Q[ 5],Q[ 4])+Q[ 3]+x[ 6]+0xa8304613,17); 32 c.
Q[ 8]=Q[ 7]+RL(F(Q[ 7],Q[ 6],Q[ 5])+Q[ 4]+x[ 7]+0xfd469501,22); 29 c.
Q[ 9]=Q[ 8]+RL(F(Q[ 8],Q[ 7],Q[ 6])+Q[ 5]+x[ 8]+0x698098d8, 7); 28 c.
Q[10]=Q[ 9]+RL(F(Q[ 9],Q[ 8],Q[ 7])+Q[ 6]+x[ 9]+0x8b44f7af,12); 18 c.
Q[11]=Q[10]+RL(F(Q[10],Q[ 9],Q[ 8])+Q[ 7]+x[10]+0xffff5bb1,17); 19 c.
Q[12]=Q[11]+RL(F(Q[11],Q[10],Q[ 9])+Q[ 8]+x[11]+0x895cd7be,22); 15 c.
Q[13]=Q[12]+RL(F(Q[12],Q[11],Q[10])+Q[ 9]+x[12]+0x6b901122, 7); 14 c.
Q[14]=Q[13]+RL(F(Q[13],Q[12],Q[11])+Q[10]+x[13]+0xfd987193,12); 15 c.
Q[15]=Q[14]+RL(F(Q[14],Q[13],Q[12])+Q[11]+x[14]+0xa679438e,17); 9 c.
Q[16]=Q[15]+RL(F(Q[15],Q[14],Q[13])+Q[12]+x[15]+0x49b40821,22); 6 c.
Q[17]=Q[16]+RL(G(Q[16],Q[15],Q[14])+Q[13]+x[ 1]+0xf61e2562, 5); 5 c.
Q[18]=Q[17]+RL(G(Q[17],Q[16],Q[15])+Q[14]+x[ 6]+0xc040b340, 9); 3 c.
Q[19]=Q[18]+RL(G(Q[18],Q[17],Q[16])+Q[15]+x[11]+0x265e5a51,14); 2 c.(+1s.)
Q[20]=Q[19]+RL(G(Q[19],Q[18],Q[17])+Q[16]+x[ 0]+0xe9b6c7aa,20); 1 c.(+1s.)
Q[21]=Q[20]+RL(G(Q[20],Q[19],Q[18])+Q[17]+x[ 5]+0xd62f105d, 5); 1 c.
Q[22]=Q[21]+RL(G(Q[21],Q[20],Q[19])+Q[18]+x[10]+0x02441453, 9); 1 c.
Q[23]=Q[22]+RL(G(Q[22],Q[21],Q[20])+Q[19]+x[15]+0xd8a1e681,14); 2 c.
Q[24]=Q[23]+RL(G(Q[23],Q[22],Q[21])+Q[20]+x[ 4]+0xe7d3fbc8,20); 1 c.
Q[25]=Q[24]+RL(G(Q[24],Q[23],Q[22])+Q[21]+x[ 9]+0x21e1cde6, 5);
Q[26]=Q[25]+RL(G(Q[25],Q[24],Q[23])+Q[22]+x[14]+0xc33707d6, 9);
Q[27]=Q[26]+RL(G(Q[26],Q[25],Q[24])+Q[23]+x[ 3]+0xf4d50d87,14);
Q[28]=Q[27]+RL(G(Q[27],Q[26],Q[25])+Q[24]+x[ 8]+0x455a14ed,20);
Q[29]=Q[28]+RL(G(Q[28],Q[27],Q[26])+Q[25]+x[13]+0xa9e3e905, 5);
Q[30]=Q[29]+RL(G(Q[29],Q[28],Q[27])+Q[26]+x[ 2]+0xfcefa3f8, 9);
Q[31]=Q[30]+RL(G(Q[30],Q[29],Q[28])+Q[27]+x[ 7]+0x676f02d9,14);
Q[32]=Q[31]+RL(G(Q[31],Q[30],Q[29])+Q[28]+x[12]+0x8d2a4c8a,20);
Q[33]=Q[32]+RL(H(Q[32],Q[31],Q[30])+Q[29]+x[ 5]+0xfffa3942, 4);
Q[34]=Q[33]+RL(H(Q[33],Q[32],Q[31])+Q[30]+x[ 8]+0x8771f681,11);
Q[35]=Q[34]+RL(H(Q[34],Q[33],Q[32])+Q[31]+x[11]+0x6d9d6122,16); 1 c.
Q[36]=Q[35]+RL(H(Q[35],Q[34],Q[33])+Q[32]+x[14]+0xfde5380c,23);
Q[37]=Q[36]+RL(H(Q[36],Q[35],Q[34])+Q[33]+x[ 1]+0xa4beea44, 4);
Q[38]=Q[37]+RL(H(Q[37],Q[36],Q[35])+Q[34]+x[ 4]+0x4bdecfa9,11);
Q[39]=Q[38]+RL(H(Q[38],Q[37],Q[36])+Q[35]+x[ 7]+0xf6bb4b60,16);
Q[40]=Q[39]+RL(H(Q[39],Q[38],Q[37])+Q[36]+x[10]+0xbebfbc70,23);
Q[41]=Q[40]+RL(H(Q[40],Q[39],Q[38])+Q[37]+x[13]+0x289b7ec6, 4);
Q[42]=Q[41]+RL(H(Q[41],Q[40],Q[39])+Q[38]+x[ 0]+0xeaa127fa,11);
Q[43]=Q[42]+RL(H(Q[42],Q[41],Q[40])+Q[39]+x[ 3]+0xd4ef3085,16);
Q[44]=Q[43]+RL(H(Q[43],Q[42],Q[41])+Q[40]+x[ 6]+0x04881d05,23);
Q[45]=Q[44]+RL(H(Q[44],Q[43],Q[42])+Q[41]+x[ 9]+0xd9d4d039, 4);
Q[46]=Q[45]+RL(H(Q[45],Q[44],Q[43])+Q[42]+x[12]+0xe6db99e5,11);
Q[47]=Q[46]+RL(H(Q[46],Q[45],Q[44])+Q[43]+x[15]+0x1fa27cf8,16);
Q[48]=Q[47]+RL(H(Q[47],Q[46],Q[45])+Q[44]+x[ 2]+0xc4ac5665,23); 1 c.
Q[49]=Q[48]+RL(I(Q[48],Q[47],Q[46])+Q[45]+x[ 0]+0xf4292244, 6); 1 c.
Q[50]=Q[49]+RL(I(Q[49],Q[48],Q[47])+Q[46]+x[ 7]+0x432aff97,10); 1 c.
Q[51]=Q[50]+RL(I(Q[50],Q[49],Q[48])+Q[47]+x[14]+0xab9423a7,15); 1 c.
Q[52]=Q[51]+RL(I(Q[51],Q[50],Q[49])+Q[48]+x[ 5]+0xfc93a039,21); 1 c.
Q[53]=Q[52]+RL(I(Q[52],Q[51],Q[50])+Q[49]+x[12]+0x655b59c3, 6); 1 c.
Q[54]=Q[53]+RL(I(Q[53],Q[52],Q[51])+Q[50]+x[ 3]+0x8f0ccc92,10); 1 c.
Q[55]=Q[54]+RL(I(Q[54],Q[53],Q[52])+Q[51]+x[10]+0xffeff47d,15); 1 c.
Q[56]=Q[55]+RL(I(Q[55],Q[54],Q[53])+Q[52]+x[ 1]+0x85845dd1,21); 1 c.
Q[57]=Q[56]+RL(I(Q[56],Q[55],Q[54])+Q[53]+x[ 8]+0x6fa87e4f, 6); 1 c.
Q[58]=Q[57]+RL(I(Q[57],Q[56],Q[55])+Q[54]+x[15]+0xfe2ce6e0,10); 1 c.
Q[59]=Q[58]+RL(I(Q[58],Q[57],Q[56])+Q[55]+x[ 6]+0xa3014314,15); 1 c.
Q[60]=Q[59]+RL(I(Q[59],Q[58],Q[57])+Q[56]+x[13]+0x4e0811a1,21); 2 c.
Q[61]=Q[60]+RL(I(Q[60],Q[59],Q[58])+Q[57]+x[ 4]+0xf7537e82, 6); 2 c.
Q[62]=Q[61]+RL(I(Q[61],Q[60],Q[59])+Q[58]+x[11]+0xbd3af235,10); 2 c.(+1s.)
 27
Q[63]=Q[62]+RL(I(Q[62],Q[61],Q[60])+Q[59]+x[ 2]+0x2ad7d2bb,15); 2 c.
Q[64]=Q[63]+RL(I(Q[63],Q[62],Q[61])+Q[60]+x[ 9]+0xeb86d391,21);
IHV[0] = IV[0]+Q[61];
IHV[3] = IV[3]+Q[62]; 1 c.
IHV[2] = IV[2]+Q[63]; 3 c.
IHV[1] = IV[1]+Q[64]; 4 c.
IV[0]=0x67452301; IV[1]=0xefcdab89; IV[2]=0x98badcfe; IV[3]=0x10325476;
Note: c. = (one-bit) sufficient condition, s. = "small sufficient condition"
(e.g. "five consequent bits are not all 1")
F(X,Y,Z) = XY or (not(X) Z)
G(X,Y,Z) = XZ or (Y not(Z))
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X or not(Z))
RL(x, n) = cyclic rotation by n bits to the left
RR(x, n) = ...to the right
Блок 1. Достаточные условия для первого блока MD5 [7]
Достаточные условия в первом блоке определяются отдельными битами
переменных IHV[0...3] и Q[1...64]. Эти переменные создаются нелинейными
преобразованиями функций F, G, H, I (блок 1) над словами x[0...15].
Достаточные условия (блок 2) показывают, что некоторые биты этих
переменных равны, некоторые из них различны, некоторые равны 1 или 0.
Оставшиеся биты могут быть любыми (блок 2).

bit position / 3332 2222 2222 2111 1111 111

\ 2109 8765 4321 0987 6543 2109 8765 4321
Q[ 1] = .... .... .... .... .... .... .... ....
Q[ 2] = .... .... .... .... .... .... .... ....
Q[ 3] = .... .... .vvv 0vvv vvvv 0vvv v0.. ....
Q[ 4] = 1... .... 0^^^ 1^^^ ^^^^ 1^^^ ^011 ....
Q[ 5] = 1000 100v 0100 0000 0000 0000 0010 v1v1
Q[ 6] = 0000 001^ 0111 1111 1011 1100 0100 ^0^1
Q[ 7] = 0000 0011 1111 1110 1111 1000 0010 0000
Q[ 8] = 0000 0001 1..1 0001 0.0v 0101 0100 0000
Q[ 9] = 1111 1011 ...1 0000 0.1^ 1111 0011 1101
Q[10] = 0111 .... 0001 1111 1v01 ...0 01.. ..00
Q[11] = 0010 .0v0 111. 0001 1^00 .0.0 11.. ..10
Q[12] = 000. ..^^ .... 1000 0001 ...1 0... ....
Q[13] = 01.. ..01 .... 1111 111. ...0 0... 1...
Q[14] = 000. ..00 .... 1011 111. ...1 1... 1...
Q[15] = v110 0001 ..V. .... 10.. .... .000 0000
Q[16] = ^010 00.. ..A. .... v... .... .000 v000
Q[17] = ^1v. .... .... ..0. ^... .... .... ^...
Q[18] = ^.^. .... .... ..1. .... .... .... ....
Q[19] = ^... .... .... ..0. .... .... .... ....
Q[20] = ^... .... .... ..v. .... .... .... ....
Q[21] = ^... .... .... ..^. .... .... .... ....
Q[22] = ^... .... .... .... .... .... .... ....
Q[23] = 0... .... .... .... .... .... .... ....
Q[24] = 1... .... .... .... .... .... .... ....

Note: ^ = a bit, equal to the bit above

v = a bit, equal to the bit below
V = a bit, equal to the negation of the bit below
A = a bit, equal to the negation of the bit above
 28
. = an arbitrary bit
0/1 = a bit, which is fixed to 0 or 1
Extra conditions are highlighted:
Tunnel Q4 = by this color
Tunnel Q9 = by this color
Tunnel Q10 = by this color
Tunnel Q14 = by this color
Блок 2. Достаточные условия и особые условия для первого блока
Достаточные условия первого и второго блока отличаются. В первом блоке
больше условий, так как они включают переменные Q и IHV. Поэтому мы
сконцентрируемся на (более сложном) первом блоке. Пусть мы имеем блоки
M = (x[0],..., x[15]) и HM = (Hx[0],...,Hx[15]), которые отличаются константой
C1 = (0,..., 0, 0x80000000, 0,..., 0, 0x00008000, 0,..., 0), т.е.
Hx[ 4] = x[ 4] + 0x80000000,
Hx[11] = x[11] + 0x0000800,
Hx[14] = x[14] + 0x80000000.
Переменные Q и IHV, и соответственно, HQ и HIHV создаются во время
хэширования первых блоков M и HM.
Если M удовлетворяет достаточным условиям из Q[1...64] и IHV[0...3], то
HQ[1...64] и HIHV[0...3] автоматически наследуют разностную часть в
соответствии с блоком 3.
HQ[ 1] - Q[ 1] = 0x00000000
HQ[ 2] - Q[ 2] = 0x00000000
HQ[ 3] - Q[ 3] = 0x00000000
HQ[ 4] - Q[ 4] = 0x00000000
HQ[ 5] - Q[ 5] = 0xFFFFFFC0
HQ[ 6] - Q[ 6] = 0x807FFFC0
HQ[ 7] - Q[ 7] = 0xF87FFFBF
HQ[ 8] - Q[ 8] = 0xFF7D8001
HQ[ 9] - Q[ 9] = 0x7FFFFFC1
HQ[10] - Q[10] = 0x80001000
HQ[11] - Q[11] = 0xC0000000
HQ[12] - Q[12] = 0x7FFFDF80
HQ[13] - Q[13] = 0x81000000
HQ[14] - Q[14] = 0x80000000
HQ[15] - Q[15] = 0x7FFF8008
HQ[16] - Q[16] = 0x60000000
HQ[17] - Q[17] = 0x80000000
HQ[18] - Q[18] = 0x80000000
HQ[19] - Q[19] = 0x80020000
HQ[20] - Q[20] = 0x80000000
HQ[21] - Q[21] = 0x80000000
HQ[22] - Q[22] = 0x80000000
HQ[23] - Q[23] = 0x00000000
.......the same differences
HQ[34] - Q[34] = 0x00000000
 29
HQ[35] - Q[35] = 0x80000000
.......the same differences
HQ[61] - Q[61] = 0x80000000
HQ[62] - Q[62] = 0x82000000
HQ[63] - Q[63] = 0x82000000
HQ[64] - Q[64] = 0x82000000
HIV[ 0]-IV[ 0] = 0x80000000
HIV[ 1]-IV[ 1] = 0x82000000
HIV[ 2]-IV[ 2] = 0x82000000
HIV[ 3]-IV[ 3] = 0x82000000
Блок 3. Разностная (дифференциальная) часть (X. Wang и H. Yu “How to
Break MD5 and Other Hash Functions”)
Недостатком достаточных условий является их большое количество и то,
что они начинают влиять на переменные Q и IHV достаточно поздно. Если
мы получили достаточные условия из Q[1...16], причем выбрали эти
переменные, то потом у нас нет свободы в выборе сообщениия x[0...15].
Поэтому значения Q[17...64] и IHV[0...3] полностью определены и их
достаточные условия получаются только случайно. Если мы не полностью
установим значения Q[1...16], то у нас будут проблемы с вычислением
Q[17..64] и IHV[0..3]. Они зависят от Q[1...16] нелинейным и сложным путём.
Метод модификации смешанных сообщений (multi-message modification
method) состоит в выборе сообщения x[] и изменении его от шага к шагу для
удовлетворения условиям над Q[1...64]. В разных статьях этот процесс
заканчивался на условиях над Q[18], потом над Q[19] например. В настоящее
время есть возможность получить почти все условия до Q[24], но этот метод
не был проверен экспериментально. Дальнейшие условия достаточно далеки
– над Q[35]. Было предложено много различных методов модификаций
смешанных сообщений в этих статьях. Для большей эффективности были
введены новые побитные условия (особые условия). Они похожи на
достаточные условия, но они не нуждаются в разностной части. Они только
ускоряют выбранный метод модификации смешанных сообщений. На
практике они состоят из от 10 до 20 дополнительных условий над
некоторыми битами Q[1…24]. Заметьте, что у нас есть около 250
достаточных условий.
 30

В любом случае методы модификаций смешанных сообщений

заканчивается над получением условия для Q[24]. В это время переменные
x[] были полностью определены и осталось только проверить, не существуют
ли других условий над Q[25...64] и IHV[0...3], полученных случайно. Если
условия не получены, метод генерирует другое сообщение x[] и так далее.
Точка, в которой осталось только проверить, не являются ли оставшиеся
случайные условия (здесь, Q[24) удовлетворительными, мы называем точкой
проверки (point of verification, POV). В случае MD5 существует 29
оставшихся условий, поэтому любой метод преобразования смешанных
сообщений требует создания 229 точек проверки. В идеальном случае метод
туннелирования состоит из поиска только одной POV. Используя туннели
возможно начать с этой точки и создать требуемое количество других POVs
(здесь 229). Конечно, мы можем получить точку проверки любым методом,
например, случайным с минимальной сложностью. В идеальном случае мы
можем полностью отменить фазу получения POVs. Это даст возможность
нам также отменить все дополнительные особые условия в
дифференциальной схеме.
Пример туннеля Q9.
Посмотрим на выражения Q[11] и Q[12]. Если i-ый бит Q[10] равен 0 и i-ый
бит Q[11] равен 1 (обозначим Q[10]i = 0 и Q[11]i = 1) и возможное изменение
i-ого бита Q[9] не повлияет на эти выражения. В этом случае значение
F(Q[10]i, Q[9]i, Q[8]i) не зависит от значения Q[9]i , в соответствии с
определением функции F.
Для тех битов , где Q[10]i = 0 и Q[11]i = 1 получается туннель.
На всех этих позициях мы можем менять значение Q[9]i , но при этом это не
будет влиять на значения Q[11] и Q[12]. В дальнейшем, возможные
изменения значений Q[10 и Q[13] мы скомпенсируем изменением слов x[8],
x[9] и x[12].
 31

Изменения не влияют на переменные до POV, поэтому достаточные условия

остаются удовлетворительными. Изменения появятся после POV. Все
переменные Q[25…64] изменятся сложным и случайным путём.
Чтобы получить хороший Q9 туннель, мы должны установить Q[10]i = 0 и
Q[11]i = 1 для стольких битов, насколько это возможно. Заметим, что эти
битовые условия не являются частью достаточных. Они только ускоряют
поиск коллизий. Поэтому мы называем их особые условия, подобно особым
условиям в случае методов модификации смешанных сообщений.
Дифференциальная схема ( разностная часть и достаточные условия вместе)
[6] содержит только 3 таких битовых позиции (i = 22, 23, 24). Поэтому это
туннель с мощностью 3. Используя туннель мы можем легко воспроизводить
из точки проверки 23 других точек. Было бы здорово, если совмещение двух
таких туннелей давало бы другой, более мощный. Но композиция Q9 с самим
собой даёт снова Q9.
 32

БЛОК-СХЕМА АЛГОРИТМА РАБОТЫ ПРОГРАММЫ,

ГЕНЕРИРУЮЩЕЙ КОЛЛИЗИИ

готовые переменные
из дифференциальных начало
схем
заданные типы генерация случайного числа X
туннелей Q4, Q9,
Q13, Q14, Q20. составление 1-го сообщения
x[0…31], основанного на X

создание переменных Q[0…63] из x[0…31] и случайных чисел

преобразование Q[0…63] таким образом,

чтобы выполнялись условия (достаточные и
специальные) над битами этих переменных

составление 2-го сообщения Hx[0…31],

основанного на X и x[0…31]

создание и преобразование HQ[0…63],

получение достаточных и специальных условий

x[0…31] и Hx[0…31] образуют коллизию

конец
 33

ПРИМЕРЫ 128 БАЙТОВЫХ КОЛЛИЗИЙ MD5

0x40,0x21,0x17,0xC6,0xE3,0x3D,0x04,0x10,0x7F,0xBD,0x2C,0x17,0x2E,0x9E,0xE0,0x6C,
0x6E,0x38,0x44,0x4A,0x2C,0xB7,0xF4,0x7D,0x5D,0x26,0x3A,0x98,0xB4,0x1A,0x62,0x15,
0x55,0x2D,0x34,0x06,0x01,0x82,0xD4,0x43,0x5F,0xA5,0xA0,0x78,0x1D,0x4F,0x31,0x14,
0x13,0xF7,0x52,0x41,0xCF,0x84,0xED,0x94,0x49,0x5A,0x03,0x73,0xFB,0x08,0xCA,0x33,
0x37,0x0C,0xF0,0x83,0x5C,0xF1,0xA3,0x33,0x77,0xC9,0x4D,0xD5,0x2A,0xF1,0x16,0xCB,
0x88,0xF1,0x68,0x15,0xCC,0xB2,0xC5,0x1C,0xEE,0xC4,0x30,0x38,0xCE,0x64,0x6D,0xFE,
0x69,0xD7,0x33,0x2E,0xB1,0x78,0x0B,0xA6,0x16,0x79,0x5D,0x2A,0x82,0x68,0xA5,0x9E,
0xCC,0x84,0x0F,0x02,0x93,0xCB,0x8B,0xFF,0x25,0xAC,0xA8,0x64,0x6A,0x96,0x55,0x30

0x40,0x21,0x17,0xC6,0xE3,0x3D,0x04,0x10,0x7F,0xBD,0x2C,0x17,0x2E,0x9E,0xE0,0x6C,
0x6E,0x38,0x44,0xCA,0x2C,0xB7,0xF4,0x7D,0x5D,0x26,0x3A,0x98,0xB4,0x1A,0x62,0x15,
0x55,0x2D,0x34,0x06,0x01,0x82,0xD4,0x43,0x5F,0xA5,0xA0,0x78,0x1D,0xCF,0x31,0x14,
0x13,0xF7,0x52,0x41,0xCF,0x84,0xED,0x94,0x49,0x5A,0x03,0xF3,0xFB,0x08,0xCA,0x33,
0x37,0x0C,0xF0,0x83,0x5C,0xF1,0xA3,0x33,0x77,0xC9,0x4D,0xD5,0x2A,0xF1,0x16,0xCB,
0x88,0xF1,0x68,0x95,0xCC,0xB2,0xC5,0x1C,0xEE,0xC4,0x30,0x38,0xCE,0x64,0x6D,0xFE,
0x69,0xD7,0x33,0x2E,0xB1,0x78,0x0B,0xA6,0x16,0x79,0x5D,0x2A,0x82,0xE8,0xA4,0x9E,
0xCC,0x84,0x0F,0x02,0x93,0xCB,0x8B,0xFF,0x25,0xAC,0xA8,0xE4,0x6A,0x96,0x55,0x30

@!˜Жг=˜˜˜Ѕ, ˜.ћаl @!˜Жг=˜˜˜Ѕ, ˜.ћаl

n8DJ,·ф}]&:˜ґ˜b˜ n8DК,·ф}]&:˜ґ˜b˜
U-4˜˜‚ФC_Ґ x˜O1˜ U-4˜˜‚ФC_Ґ x˜П1˜
˜чRAП„н”IZ˜sы˜К3 чRAП„н”IZ˜уы˜К3
7˜рѓ\сЈ3wЙMХ*с˜Л 7˜рѓ\сЈ3wЙMХ*с˜Л
€сh˜МІЕ˜оД08Оdmю €сh•МІЕ˜оД08Оdmю
iЧ3.±x˜¦˜y]*‚hҐћ iЧ3.±x˜¦˜y]*‚и¤ћ
М„˜˜“Л‹я%¬Ёdj–U0 М„˜˜“Л‹я%¬Ёдj–U0

MD5hash: 2436A325478189E4AA22B1C80997D613
 34

0x3A,0x38,0xF1,0x31,0x79,0xD5,0xE0,0xE0,0xF9,0xDD,0xCA,0xD6,0x36,0xD8,0xEC,0x50,
0xA7,0x3A,0x61,0x7F,0x1F,0xE2,0xC8,0x6D,0x43,0x08,0x68,0xA2,0xB1,0x3D,0x50,0x41,
0xD5,0x6C,0x34,0x06,0x0A,0x00,0x34,0xE2,0x7B,0x00,0xAD,0x83,0x23,0x9F,0x41,0x1D,
0xE8,0xC0,0xB6,0x0E,0xD7,0x1C,0x2C,0xE9,0xB7,0xE3,0xF9,0x11,0xFA,0xF4,0x0F,0x05,
0x8C,0xE8,0x60,0x76,0x7A,0xC0,0xB3,0x23,0x2C,0x91,0x39,0xDD,0x63,0x4E,0xEE,0xE3,
0x54,0x58,0x65,0xB7,0xCC,0x18,0x38,0xFD,0x0E,0xB9,0xEA,0x16,0x49,0xEC,0xCD,0xCE,
0xE5,0x17,0xF7,0x16,0x6C,0xB3,0xE7,0x65,0xA6,0xC2,0x29,0x2A,0x88,0x90,0x41,0x20,
0xB2,0xBC,0xD4,0x35,0xBB,0xE7,0x83,0x73,0x5C,0xB3,0x8A,0xD3,0x93,0x97,0x35,0x4D

0x3A,0x38,0xF1,0x31,0x79,0xD5,0xE0,0xE0,0xF9,0xDD,0xCA,0xD6,0x36,0xD8,0xEC,0x50,
0xA7,0x3A,0x61,0xFF,0x1F,0xE2,0xC8,0x6D,0x43,0x08,0x68,0xA2,0xB1,0x3D,0x50,0x41,
0xD5,0x6C,0x34,0x06,0x0A,0x00,0x34,0xE2,0x7B,0x00,0xAD,0x83,0x23,0x1F,0x42,0x1D,
0xE8,0xC0,0xB6,0x0E,0xD7,0x1C,0x2C,0xE9,0xB7,0xE3,0xF9,0x91,0xFA,0xF4,0x0F,0x05,
0x8C,0xE8,0x60,0x76,0x7A,0xC0,0xB3,0x23,0x2C,0x91,0x39,0xDD,0x63,0x4E,0xEE,0xE3,
0x54,0x58,0x65,0x37,0xCC,0x18,0x38,0xFD,0x0E,0xB9,0xEA,0x16,0x49,0xEC,0xCD,0xCE,
0xE5,0x17,0xF7,0x16,0x6C,0xB3,0xE7,0x65,0xA6,0xC2,0x29,0x2A,0x88,0x10,0x41,0x20,
0xB2,0xBC,0xD4,0x35,0xBB,0xE7,0x83,0x73,0x5C,0xB3,0x8A,0x53,0x93,0x97,0x35,0x4D

:8с1yХаащЭКЦ6ШмP :8с1yХаащЭКЦ6ШмP
§:a• ˜вИmC˜hў±=PA §:aя˜вИmC˜hў±=PA
Хl4˜ 4в{ ­ѓ#џA˜ Хl4˜ 4в{ ­ѓ#˜B˜
иА¶˜Ч˜,й·гщъф˜˜ иА¶˜Ч˜,й·гщ‘ъф˜˜
Њи`vzАі#,‘9ЭcNог Њи`vzАі#,‘9ЭcNог
TXe·М8э˜№к˜IмНО TXe7М8э˜№к˜IмНО
е˜ч˜lізe¦В)*€ђA е˜ч˜lізe¦В)*€˜A
ІјФ5»зѓs\іЉУ“—5M ІјФ5»зѓs\іЉS“—5M

MD5hash: E5B70FF80BAD93BF45C7162AF992B490
 35

ВЫВОДЫ

В курсовой работе были изучены хэш-функции в целом как класс

криптографических функций, более подробно изучены бесключевые хэш-
функции SHA, MD5. С помощью среды разработки Visual Studio 2008 были
реализованы алгоритм вычисления хэш-кода SHA-256, алгоритм подбора
сообщения к заданному хэш-коду, алгоритм поиска коллизий простым
перебором. Также был изучен алгоритм нахождения коллизий методом
туннелирования для алгоритма MD5, предложенный Властимилом Клима. В
результате на практике были подтверждены теоретические сведения:
однонаправленность хэш-функции, практическая невозможность найти
второй прообраз для заданного сообщения и его хэш-кода и пару сообщений,
имеющих одинаковый хэш (коллизию). Также отмечены следующие
особенности как SHA-256, так и MD5 алгоритмов. Быстрота вычисления
хэш-кода для сообщений любой длины (50мс для миллиона символов для
SHA-256 и значительно меньше для MD5), в силу этого достаточно быстрый
процесс подбора несложного пароля к хэш-коду, но трудоёмкость этого
процесса быстро растёт с ростом количества используемых символов (y = xn),
но ещё быстрее растёт с увеличением количества символов в пароле (y = nx).
Поэтому намного выгодней для повышения стойкости пароля увеличивать
его длину. Сложность поиска коллизий из-за ограничения вычислительных
ресурсов, самым главным из которых является время. Для решения этой
проблемы могут применяться либо аппаратное ускорение, либо
математичский подход, либо их комбинация. В качестве первого обычно
применяется распараллеливание процесса (в последнее время создаются
целые сетевые команды для этих целей), использование многоядерных
систем (сейчас часто применяют технологию программирования CUDA, с
помощью которой для вычислений используются ядра видеокарт GeForce 8 и
9 серий, что увеличивает процесс вычисления хэш-кода, например, для MD5
 36

с 50 до 500 миллиона хэшэй в секунду). В качестве второго применяются

дифференциальный метод, метод модификации смешанных сообщений и
основанный на них метод туннелирования. Ввиду схожести алгоритмов SHA
и MD5, к ним обоим применимы эти методы. Самым предпочтительным в
последнее время является метод туннелирования, с помощью которого на
домашнем компьютере за 30 секунд была получена пара сообщений длиной
128 байт с одинаковым хэш-кодом.
Математическая стойкость новых хэш-функций растёт, также как и
растут вычислительные способности компьютеров, также как и появляются
новые методы получения коллизий. Но следует отметить достаточно долгое
(по настоящее время) и повсеместное использование алгоритма MD5 (с 1991
года до 2005, когда были опубликованы первые коллизии [3]), чего скорее
всего не скажешь про алгоритмы SHA-2 (SHA-256 c 2002 года), к которому
из-за схожести с MD5 уже найдены усеченные коллизии [3]. Вследствие
этого сейчас ведутся поиски новых алгоритмов хэширования. Недавно создан
алгоритм MD6, который является кандидатом на включение в стандарт SHA-
3.
 37

ЛИТЕРАТУРА

1. А. П. Алфёров, А.Ю. Зубов, А.С. Кузьмин, А.В. Черёмушкин «Основы

Криптографии», 2-е издание – Москва, 2002.
2. Federal Information Processing Standards (FIPS) Publication 180-2, Secure
Hash Standard (SHS), U.S. DoC/NIST, August 1, 2002.
3. [Link]
4. [Link]
5. Tunnels in Hash Functions: MD5 Collisions Within a Minute (Extended
abstract) Vlastimil Klima. Prague, Czech Republic, Version 1 March 2006, version
2 April 2006
6. X. Wang and H. Yu: How to Break MD5 and Other Hash Functions.,
Eurocrypt’05, Springer-Verlag, LNCS, Vol. 3494, pp. 19–35. Springer, 2005.
7. Liang J. and Lai X.: Improved Collision Attack on Hash Function MD5,
Cryptology ePrint Archive: Report 425/2005, 23 Nov 2005