Понятие коллизии и причины ее существования. Парадокс дней рождения. Длина кода аутентификации сообщения (имитовставки)

 

Коллизия – это ситуация, когда разные блоки исходного текста имеют одинаковый хэш.

( но ).

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

Парадо́кс дней рожде́ния — это кажущееся парадоксальным утверждение, что вероятность совпадения дней рождения (числа и месяца) хотя бы у двух членов группы из 23 и более человек, превышает 50 %. С практической точки зрения это означает, что если, например, в вашем классе более 22 учеников, то более вероятно, что у кого-то из одноклассников дни рождения придутся на один день, чем что у каждого будет свой собственный день рождения.

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

 

39. Алгоритм хеширования MD5: параметры, алгоритм забивки, алгоритм изменения переменных сцепления, раунды и операции, функции раундов. Стойкость к поиску коллизий.

 

Параметры:

1. Длина хэша: 128 бит.
2. Количество раундов: 4(по 16 проходов каждый).
3. Длина хэшируемого сообщения: произвольная (L).
4. Размер блока хэшируемого сообщения: 512 бит

 

Алгоритм забивки:

1. Сначала дописывают единичный бит в конец потока (байт 0x80), затем необходимое число нулевых бит. Входные данные выравниваются так, чтобы их новый размер был сравним с 448 по модулю 512 (). Выравнивание происходит, даже если длина уже сравнима с 448.

 

1. В оставшиеся 64 бита дописывают 64-битное представление длины данных (количество бит в сообщении) до выравнивания. Сначала записывают младшие 4 байта. Если длина превосходит , то дописывают только младшие биты. После этого длина потока станет кратной 512. Вычисления будут основываться на представлении этого потока данных в виде массива слов по 512 бит.

 

Алгоритм изменения переменных сцепления:

1. Начальное значение переменных задается, как

А = 01 23 45 67;

В = 89 AB CD EF;

С = FE DC BA 98;

D = 76 54 32 10.

1. Задается таблица констант — 64-элементная таблица данных, построенная следующим образом
2. Выровненные данные разбиваются на блоки по 512 бит, которые в свою очередь делятся на слова по 32 бита (16 штук). Каждый блок проходит через 4 раунда по 16 операторов в каждом Результаты A,B,C,D для каждого блока суммируются. При этом сумма с предыдущего этапа обрабатывается новым этапом(т. е. начальные значения задаются только для первого блока. Перед каждым последующим содержимое регистров запоминается, дальше оно же обрабатывается со следующим блоком и потом к результату обработки добавляется запомненное.)
3. Всего операторов 64. На каждом операторе(см. схему ниже) выбирается T[i], где i – номер оператора от 1 до 64.
4. X_k – одно из 16 32-битовых слов текущего блока. На каждом раунде обрабатываются все 16 слов(по одному на оператор) в разном порядке.
5. s принимает одно из 4 значений циклически каждый оператор в одном раунде. У разных раундов разных четверки значений s
6. Функция F определяется номером раунда

 

 

Схема оператора:

 

 

Ф-ции раундов:

1 раунд .

2 раунд .

3 раунд .

4 раунд .

 

Коллизии MD5

В 2004 году китайские исследователи Ван Сяоюнь (Wang Xiaoyun), Фэн Дэнго (Feng Dengguo), Лай Сюэцзя (Lai Xuejia) и Юй Хунбо (Yu Hongbo) объявили об обнаруженной ими уязвимости в алгоритме, позволяющей за небольшое время (1 час на кластере IBM p690) находить коллизии.

В 2005 году Ван Сяоюнь и Юй Хунбо из университета Шаньдуна в Китае опубликовали алгоритм, который может найти две различные последовательности в 128 байт, которые дают одинаковый MD5-хеш.

Таким образом, на данный момент MD5 официально неустойчив к поиску коллизий.

 

 

40. Алгоритм хеширования MD4 как средство решения задачи безопасного хранения паролей в ОС Windows: NT hash.

Задача безопасного хранения паролей подразумевает, что даже если криптоаналитик получил доступ к ОС и таблице хранимых проверочных значений паролей, он не может восстановить по ней настоящие «секретные» пароли. Одни из решений этой задачи является использования хэшей в качестве проверочных значений паролей, поскольку по хэшу невозможно восстановить секретный пароль. Однако, в таком случае остается возможно атаки на алгоритм хэширования с целью подобрать входное значение имеющее заданный хэш(проверочное значение искомого пароля). Эта атака в частности может быть осуществлена полным перебором.

NT хэш:

1. Пароль пользователя переводится в Unicod
2. Пароль хэшируется MD4
3. По логину пользователя извлекается его уникальный идентификатор SID
4. Из SID выбирается RID – часть идентификатора уникальная для пользователей в пределах компьютера(а вторая часть уникальная для разных компьютеров, но общая в пределах одного отбрасывается)
5. MD4 хэш шифруется DES с использованием RID в качестве ключа
6. Полученный результат является NT хэшем.

 

 

41. Алгоритм хеширования MD4 как средство решения задачи безопасного хранения паролей в ОС Windows: LM hash.

LM-хеш вычисляется следующим образом:

1. Пароль пользователя как OEM-строка приводится к верхнему регистру.
2. Пароль дополняется нулями или обрезается до 14 байтов
3. Получившийся пароль разделяется на две половинки по 7 байтов.
4. Эти значения используются для создания двух ключей DES, по одному для каждой 7-байтовой половинки, рассматривая 7 байтов как битовый поток и вставляя ноль после каждых 7 битов. Так создаются 64 бита, необходимые для ключа DES.
5. Каждый из этих ключей используется для DES-шифрования ASCII-строки «KGS!@#$%», получая два 8-байтовых шифрованных значения.
6. Данные шифрованные значения соединяются в 16-байтовое значение, являющееся LM-хешем.

 

Несмотря на то что LM-хеш основан на качественном блочном шифре DES, он может быть легко атакован для подбора пароля из-за двух уязвимостей в его реализации. Во-первых, пароли длиннее 7 символов разделяются на две части и каждая часть хешируется отдельно. Во-вторых, все символы нижнего регистра приводятся к верхнему до хеширования пароля. Первая уязвимость позволяет атаковать каждую часть пароля по отдельности. Хотя и существует различных паролей составленных из видимых ASCII-символов, но можно составить только различных 7-байтовых частей пароля используя одну кодовую таблицу. Ограничение набора символов из-за преобразования к верхнему регистру также сокращает количество вариантов до . Применив brute force атаку отдельно к каждой половине, современные персональные компьютеры могут подобрать буквенно-цифровой LM-хеш за несколько часов.

42. Решение задачи безопасного хранения паролей в ОС UNIX/Linux, понятие «соли», используемые алгоритмы хеширования.

В системе UNIX каждый пользователь имеет свой пароль и его знает только пользователь. Для защиты паролей используется хеширование. Предполагалось, что получить настоящий пароль можно только полным перебором. При появлении UNIX единственным способом хеширования был DES (Data Encryption Standard), но им могли пользоваться только жители США, потому что исходные коды DES нельзя было вывозить из страны. Во FreeBSD решили эту проблему. Пользователи США могли использовать библиотеку DES, а остальные пользователи имеют метод, разрешённый для экспорта. Поэтому в FreeBSD стали использовать MD5 по умолчанию. Некоторые Linux-системы также используют MD5 для хранения паролей.

Соль – уникальное значение для каждого пользователя, использующееся для того, чтобы при одинаковых паролях их хэши не совпадали.

Таблицы паролей хранятся либо в /etc/shadow, либо в /etc/master.password

Формат записей в таблице: login:salt$hash

Кроме упомянутых выше MD5 и DES для хэширования также иногда применяется SHA.

 

43. Алгоритм хеширования SHA-1: параметры, алгоритм забивки, алгоритм изменения переменных сцепления, раунды и операции, функции раундов.

 

Параметры:

1. Длина хэша: 160 бит.
2. Количество раундов: 80 (4 по 20).
3. Длина хэшируемого сообщения: произвольная (L).
4. Размер блока хэшируемого сообщения: 512 бит

 

Алгоритм забивки(идентичен алгоритму забивки MD5):

1. Сначала дописывают единичный бит в конец потока (байт 0x80), затем необходимое число нулевых бит. Входные данные выравниваются так, чтобы их новый размер был сравним с 448 по модулю 512 (). Выравнивание происходит, даже если длина уже сравнима с 448.

 

1. В оставшиеся 64 бита дописывают 64-битное представление длины данных (количество бит в сообщении) до выравнивания. Сначала записывают младшие 4 байта. Если длина превосходит , то дописывают только младшие биты. После этого длина потока станет кратной 512. Вычисления будут основываться на представлении этого потока данных в виде массива слов по 512 бит.

 

Алгоритм изменения переменных сцепления:

1. Начальное значение переменных задается, как

A = a = 0x67452301

B = b = 0xEFCDAB89

C = c = 0x98BADCFE

D = d = 0x10325476

E = e = 0xC3D2E1F0

1. Выбирается 512-битный блок из входного потока. Он преобразуется из 15 32-битных слов в массив из 80 32-битных слов:

1. Проходят 4 раунда по 20 проход, согласно схеме. Функция и константа K меняется каждый раунд согласно таблице. Значение W меняется каждый проход(от 0 до 79)/

 

	= 0x5A827999	1 раунд
	= 0x6ED9EBA1	2 раунд
	= 0x8F1BBCDC	3 раунд
	= 0xCA62C1D6	4 раунд

 

Схема раунда:

 

 

 

1. Отдельно хранится сумма результатов всех итераций (один 512-битный блок обрабатывается в рамках 1 итерации) для каждого из пяти регистров. Когда все блоки обработаны – эти 5 32-битных сумм вместе составят 160-битный хэш.

44. Антивирусное ПО: сигнатурные базы и алгоритмы хеширования. Утверждение Cohen о невозможности создать идеальный антивирус и проблема остановки в теории вычислимости.

 

45. Функции хеширования, основанные на симметричных шифрах. Алгоритм ГОСТ Р34.11-94: параметры, сжимающая функция и ее результат (имитовставка), генерация ключей, шифрующее преобразование, перемешивающее преобразование.

 

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

Основным недостатком хеш-функций, спроектированных на основе блочных алгоритмов, является низкая скорость работы.

 

Алгоритм ГОСТ Р34.11-94:

 

Параметры:

1. Длина хэша: 256 бит.
2. Количество раундов: 1
3. Длина хэшируемого сообщения: произвольная (L).
4. Размер блока хэшируемого сообщения: 256 бит
5. Для алгоритма должны указываться 8 S-блоков для шифрующего преобразования ГОСТ 28147-89

 

Основой описываемой хеш-функции является шаговая функция хеширования где , , — блоки длины 256 бит.

Основной алгоритм

1. Входное сообщение разделяется на блоки по 256 бит. В случае если размер последнего блока меньше 256 бит, то к нему приписываются слева нули для достижения заданной длины блока.
2. Каждый блок сообщения, начиная с первого, подаётся на шаговую функцию для вычисления промежуточного значения хеш-функции:
   
   Значение можно выбрать произвольным.
3. После вычисления конечное значение хеш-функции получают следующим образом:

, где L — Длина сообщения M в битах по модулю

,

где K — Контрольная сумма сообщения M:

 

 

 

Шаговая функция хэширования – сжимающая функция: преобразует два 256-битных значения в одно 256-битное значение состоит из трех частей:

1. Генерирование ключей
2. Шифрующее преобразование — шифрование с использованием ключей
3. Перемешивающее преобразование результата шифрования

 

Генерация ключей:

Алгоритм:

1.

2. Для j = 2,3,4 выполняем следующее:

 

Где:

C2 = 0

C3 = 0xff00ffff000000ffff0000ff00ffff0000ff00ff00ff00ffff00ff00ff00ff00

C4 = 0

Преобразование , где — подблоки блока Y длины 64 бит.

Преобразование , где , а — подблоки блока Y длины 8 бит.

 

 

Шифрующее преобразование:

После генерирования ключей происходит шифрование по ГОСТ 28147—89 в режиме простой замены на ключах (для ), процедуру шифрования обозначим через E (Примечание: функция шифрования E по ГОСТ 28147 шифрует 64 битные данные 256 битным ключом). Для шифрования разделяют на четыре блока по 64 бита: и зашифровывают каждый из блоков:

1. 
2. 
3. 
4. 

После чего блоки собирают в 256 битный блок:

 

Перемешивающее преобразование:

 

 

:

 

46. Алгоритм хеширования Keccak: параметры, алгоритм забивки, sponge-конструкция и фазы работы алгоритма, функция псевдослучайной перестановки. Использование алгоритма Keccak в качестве поточного шифра.