Атака, основанная на парадоксе задачи о днях рождения

Атака: подпись нелигитимного сообщения. Атакующийсоздает 2k/2лигитимных сообщения Xи столько женелигитимныхY. С вероятностью >1/2 найдется паралигитимное-нелигитимное сообщения, с совпадающимихэш-кодами. Лигитимное сообщение отсылается наподпись. Центр подписывает сообщение и шифруетподпись. Атакующий присоединяет зашифрованнуюподпись к парному нелигитимному сообщению. Подписькорректна

22. Сильные хэш-функции. MD4. MD5. SHA-1. ГОСТ Р34.11-94 . Cравнение.

Сильные хэш-функции.

MD4

Операции, использующиеся в алгоритмах типа MD4:

• bitwise Boolean operations,• addition modulo 232

• cyclicshifts.

Эти операции выбраны в силу быстроты выполнения на на 32-разрядном процессоре.

MD4 (MessageDigest 4) — хеш-функция, разработанная профессором Массачусетскогоуниверситета Рональдом Ривестом в 1990 году. Для произвольного входного сообщенияфункция генерирует 128-разрядное хеш-значение, называемое дайджестом сообщения.

Алгоритм MD4Предполагается, что на вход подано сообщение, состоящее из бит, хеш которого нампредстоит вычислить. Здесь — произвольное неотрицательное целое число. Запишемсообщение побитово, в виде:

Ниже приведены 5 шагов, используемые для вычисления хеша сообщения.

Шаг 1. Добавление недостающих битов.

Сообщение расширяется так, чтобы его длина в битах по модулю 512 равнялась 448.

Таким образом, в результате расширения, сообщению недостает 64 бита до длины,

кратной 512 битам. Расширение производится всегда, даже если сообщение изначальноимеет нужную длину.

Расширение производится следующим образом: один бит, равный 1, добавляется ксообщению, а затем добавляются биты, равные 0, до тех пор, пока длина сообщения нестанет равной 448 по модулю 512. В итоге, к сообщению добавляется как минимум 1 бит,и как максимум 512.

Шаг 2. Добавление длины сообщения.

64-битное представление (длины сообщения перед добавлением набивочных битов)добавляется к результату предыдущего шага. В случае, когда больше, чем 264,используются только 64 младших бита.

В результате получается сообщение длиной кратной 512 битам (512 бит = 16 * 32-битныхслов). Каждое 32-битное слово содержит четыре 8-битных, но следуют они не подряд, а наоборот (например, из восьми 8-битных слов (abcdefgh) мы получаем два 32-битныхслова (dcbahgfe)). Пусть означает массив слов получившегосясообщения (здесь N кратно 16).

Шаг 3. Инициализация MD-буфера.

Для вычисления хеша сообщения используется буфер, состоящий из 4 слов (32-битныхрегистров): . Эти регистры инициализируются следующимишестнадцатеричными числами (младшие байты сначала):

word A: 67 45 23 01

word B: ef cd ab 89

word C: 98 ba dc fe

word D: 10 32 54 76

Шаг 4. Обработка сообщения блоками по 16 слов.

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

На каждую битовую позицию F действует как условное выражение: если X, то Y; иначе Z.

G действует на каждую битовую позицию как функция максимального значения: если покрайней мере в двух словах из X,Y,Z соответствующие биты равны 1, то G выдаст 1 в этомбите, а иначе G выдаст бит, равный 0.

Функция H реализует побитовыйxor.

Выровненные данные разбиваются на блоки (слова) по 32 бита, и каждый блок проходит 4раунда из 16 операторов.

Шаг 5. Формирование хеша.

Результат (хеш-функция) получается как ABCD. То есть, мы выписываем 128 бит,начиная с младшего бита A, и заканчивая старшим битом D.

MD5 — 128-битный алгоритм хеширования, разработанный профессором Рональдом Л.Ривестом из Массачусетского технологического в 1991 году.Предназначен для создания«отпечатков» или «дайджестов» сообщений произвольной длины. Является улучшенной вплане безопасности версией MD4. Зная MD5-образ (называемый также MD5-хеш илиMD5-дайджест), невозможно восстановить входное сообщение, так как одному MD5-образу могут соответствовать разные сообщения. Используется для проверкиподлинности опубликованных сообщений путѐм сравнения дайджеста сообщения сопубликованным.

Алгоритм MD5Операции, использующиеся в алгоритмах типа MD4:• bitwiseBooleanoperations,

• addition modulo 232,

• cyclicshifts.

На вход алгоритма поступает входной поток данных, хеш которого необходимо найти.

Длина сообщения может быть любой (в том числе нулевой). Запишем длину сообщения вL. Это число целое и неотрицательное. После поступления данных идѐт процессподготовки потока к вычислениям.

Шаг 1. Выравнивание потокаСначала дописывают единичный бит в конец потока, затем необходимое число нулевыхбит. Входные данные выравниваются так, чтобы их новый размер L' был сравним с 448 помодулю 512 (L’ = 512 × N + 448). Выравнивание происходит, даже если длина ужесравнима с 448.

Шаг 2. Добавление длины сообщенияВ оставшиеся 64 бита дописывают 64-битное представление длины данных (количествобит в сообщении) до выравнивания. Сначала записывают младшие 4 байта. Если длинапревосходит 264 − 1, то дописывают только младшие биты. После этого длина потокастанет кратной 512. Вычисления будут основываться на представлении этого потокаданных в виде массива слов по 512 бит.Шаг 3. Инициализация буфераДля вычислений инициализируются 4 переменных размером по 32 бита и задаютсяначальные значения шестнадцатеричными числами (шестнадцатеричное представление,сначала младший байт):

А = 01 23 45 67;

В = 89 ABCDEF;

С = FEDCBA 98;

D = 76 54 32 10.

В этих переменных будут храниться результаты промежуточных вычислений. Начальноесостояние ABCD называется инициализирующим вектором.

Определим ещѐ функции и константы, которые нам понадобятся для вычислений.

Потребуются 4 функции для четырѐх раундов. Введѐм функции от трѐх параметров —слов, результатом также будет слово.

Определим таблицу констант T[1..64] — 64-элементная таблица данных,построенная следующим образом:

T[i] = int(232* | sin(i) | ).

Выровненные данные разбиваются на блоки (слова) по 32 бита, и каждый блокпроходит 4 раунда из 16 операторов. Все операторы однотипны и имеют вид:

[abcdksi],определяемый какa = b + ((a + Fun(b,c,d) + X[k] + T[i]) <<<s),где X — блок данных. X[k] = M [n * 16 + k], где k — номер 32-битного слова из n-го512-битного блока сообщения, и s — циклический сдвиг влево на s бит полученного32-битного аргумента.

Шаг 4. Вычисление в циклеЗаносим в блок данных элемент n из массива. Сохраняются значения A, B, C и D,оставшиеся после операций над предыдущими блоками (или их начальные значения, еслиблок первый).

AA = A

BB = B

CC = C

DD = D

Шаг 5. Результат вычисленийРезультат вычислений находится в буфере ABCD, это и есть хеш. Если выводитьпобайтово начиная с младшего байта A и закончив старшим байтом D, то мы получимMD5 хеш.

ГОСТ Р34.11-94 — российский криптографический стандарт вычисления хэш-функции.

 Дата введения: 23 мая 1994 г.

 Размерхэша: 256 бит

 Размер блока входных данных: 256 бит

 Разработчик: ГУБС ФАПСИ и ВНИИС

Стандарт определяет алгоритм и процедуру вычисления хэш-функции дляпоследовательности символов. Этот стандарт является обязательным для применения вкачестве алгоритма хэширования в государственных организациях РФ и рядекоммерческих организаций.ЦБ РФ требует использовать ГОСТ Р 34.11-94 для электронной подписи предоставляемыхему документов.Вводные обозначенияДля описания алгоритма хэширования будем использовать следующие обозначения:

{0}^j — блок длиной j бит заполненный нулями.

|M| — длина блока M в битах по модулю 2^256

|| — слияние (конкатенация) двух блоков в один.

+ — сложение двух блоков длиной 256 бит по модулю 2^256

XOP — побитное сложение (XOR) двух блоков одинаковой длины.

Далее будем считать, что младший (нулевой) бит в блоке находится справа, старшийслева.

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

Дополнение последнего блока

Входное сообщение M разделяется на блоки mn,mn − 1,mn − 2,...,m1по 256 бит. В случае еслиразмер последнего блока mnменьше 256 бит, то к нему приписываются слева нули длядостижения заданной длины блока.

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

Значение H1можно выбрать произвольным.

Конечное значение хэш-функцииПосле вычисления Hn + 1конечное значение хэш-функции получают следующим образом:

Hn+2=f(Hn+1,L) , где L — Длина сообщения M в битах по модулю 2H=f(Hn+2,K) , где K — Контрольная сумма сообщения M: m1 + m2 + m3 + ... + mn

h — значение хэш-функции сообщения M

Алгоритм

1. Инициализация:

h:=H1— Начальное значение хэш-функции. Т.е. – 256битовый IV вектор, определяется пользователем.

E:=0 — Контрольная сумма

L:=0 — Длина сообщения

2. Функция сжатия внутренних итераций: для i = 1 … n — 1

выполняем следующее (пока | M | > 256):

h:=f(h,m) - итерация метода последовательногохэшированияL:=L+256 - итерация вычисления длины сообщенияE:=E+mi - итерация вычисления контрольнойсуммы

3. Функция сжатия финальной итерации:

L:=L+|mn| - вычисление полной длины сообщения

Mn:=0^(256-|mn|)||mn - набивка последнего блока

E:=E+mn - вычисление контрольной суммысообщения

h:=f(h,mn)

h:=f(h,L) - MD - усиление

h:=f(h,E)

4. Выход. Значением хэш-функции является h,

SHA-1

SecureHashAlgorithm 1 — алгоритм криптографического хеширования. Для входногосообщения произвольной длины (максимум 264− 1 бит) алгоритм генерирует 160-битноехеш-значение, называемое также дайджестом сообщения. Используется во многихкриптографических приложениях и протоколах. 1995 год.

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

Выход представляет собой значение всех хеш-блоков до этого момента. Иными словамихеш блока Miравенhi = f(Mi,hi − 1). Хеш-значением всего сообщения является выходпоследнего блока.

Дополнение

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

ИнициализацияИнициализируются пять 32-битовых переменных.

A = a = 67452301

B = b = EFCDAB89

C = c = 98BADCFE

D = d = 10325476

E = e = C3D2E1F0

Определяются четыре нелинейные операции и четыре константы.

= 5A827999 0≤t≤19

= 6ED9EBA1 20≤t≤39

= 8F1BBCDC 40≤t≤59

= CA62C1D6 60≤t≤79

Главный цикл

Главный цикл итеративно обрабатывает каждый 512-битный блок. Итерация состоит изчетырех этапов по двадцать операций в каждом. Блок сообщения преобразуется из 16 32-битовых слов Miв 80 32-битовых слов WjПосле этого a, b, c, d, e прибавляются к A, B, C , D , E соответственно. Начинаетсяследующая итерация.

Итоговым значением будет объединение пяти 32-битовых слов в одно 160-битное хеш-значение.

Сравнение

И MD5, и SHA-1 являются, по сути, улучшенными продолжениями MD4.

Сходства:

1. Четыре этапа.

2. Каждое действие прибавляется к ранее полученному результату.

3. Размер блока обработки равный 512 бит.

4. Оба алгоритма выполняют сложение по модулю 232

, они рассчитаны на 32-битнуюархитектуру.

Различия:

1. В SHA-1 на четвертом этапе используется та же функция f, что и на втором этапе.

2. В MD5 в каждом действии используется уникальная прибавляемая константа. ВSHA-1 константы используются повторно для каждой из четырех групп.

3. В SHA-1 добавлена пятая переменная.

4. SHA-1 использует циклический код исправления ошибок.

5. В MD5 четыре сдвига, используемые на каждом этапе отличаются от значений,используемых на предыдущих этапах. В SHA на каждом этапе используетсяпостоянное значение сдвига.

6. В MD5 четыре различных элементарных логических функции, в SHA-1 — три.

7. В MD5 длина дайджеста составляет 128 бит, в SHA-1 — 160 бит.

8. SHA-1 содержит больше раундов (80 вместо 64) и выполняется на 160-битном

буфере по сравнению со 128-битным буфером MD5. Таким образом, SHA-1 должен

выполняться приблизительно на 25 % медленнее, чем MD5 на той же аппаратуре.

Сравнение с ГОСТ Р 34.11-94

Ряд отличительных особенностей ГОСТ Р 34.11-94:

1. При обработке блоков используются преобразования по алгоритму ГОСТ 28147—89;

2. Обрабатывается блок длиной 256 бит, и выходное значение тоже имеет длину 256бит.

3. Применены меры борьбы против поиска коллизий, основанном на неполнотепоследнего блока.

4. Обработка блоков происходит по алгоритму шифрования ГОСТ 28147—89,который содержит преобразования на S — боксах, что существенно осложняетприменение метода дифференциального криптоанализа к поиску коллизийалгоритма ГОСТ Р 34.11-94. Это существенный плюс по сравнению с SHA-1.

5. Теоретическая криптостойкость ГОСТ Р 34.11-94 равна 2 128, что во много разпревосходит 280для SHA-1.

6. Скорость обработки данных для SHA-1 — 48.462*220

байт/с, а для ГОСТ Р 34.11-94 — 9.977*220байт/с.

23. Коды аутентичности. DAC. ГОСТ 28147-89 режим выработки имитовставки.

Коды аутентичности сообщений.

Пусть известна пара X,MAC(X). Атака – подбор сообщения y скодом аутентичности MFC(X). Можно перебрать ключи ( можетпотребоваться несколько пар, но количество возможных ключейбыстро снижается с каждой атакой).

Можно попытаться найти MAC, не перебирая всех ключей.

Тогда нужно создать около 2**n сообщений.

Усилия оцениваются величиной) 2 , 2 min(k n, где k-длина ключа,n – длина кода.

Код аутентичности на основе DES (DAC)

Алгоритм определяется как шифрование DES в режиме сцепленияблоков шифротекста с нулевым вектором инициализации.

ГОСТ28147-89можетиспользоватьсявкачествеодногоизметодовповычислениюкодоваутентификациисообщений. ДляГОСТ28147-89режимвыработкиимитовставкивыглядитследующимобразом:ИсходныйтекстделитсянаблокиTiдлинойв64бита.

Блоки Ti последовательно подвергаются преобразованию,соответствующему первым 16 раундам работы ГОСТ в режимепростойзамены.

После16 раундов полученное 64-разрядное число прибавляется помодулю2кследующемублокуTi+1ипроцедураповторяется.

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

Из получившегося в конце работы конечного 64-битного числавыбирается отрезок в p бит, где p —выбранная длинаимитовставки.

24. HMAC. Алгоритм, цели разработки алгоритма.

HMAC (сокращение от англ. hash-basedmessageauthenticationcode, хеш-кодидентификации сообщений). Наличие способа проверить целостностьинформации, передаваемой или хранящийся в ненадежной среде являетсянеотъемлемой и необходимой частью мира открытых вычислений икоммуникаций. Механизмы, которые предоставляют такие проверки целостностина основе секретного ключа обычно называют кодом аутентичностисообщения(MAC). Как правило, МАС используется между двумя сторонами,которые разделяют секретный ключ для проверки подлинности информации ,передаваемой между этими сторонами. Этот стандарт определяет MAC.

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

Основная цель:

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

уже есть в программном продукте, и их код уже доступен.

 Чтобы сохранить первоначальное исполнение хэш-функции,без каких нибудь значительных ухудшении

 Использовать и обрабатывать ключи более простым способом.

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

Длина хэш-кода равна L.

Если длина ключа К = b, то K0= K . Переходим сразу к шагу 4.

1. Если длина ключа K > b, то применяем H к ключу K дляполучения L-байтовой строки. Добавить нули к левой частиэтой строки для создания b-байтовой строки K0

.Переходимсразу к шагу 4.

2. Если длина ключа K < b то добавляем нули к левой части Kдля создания b-байтовой строки K0(например, если К имеетдлину 20 байтов и b = 64, то к левой части К будет добавлено44 нулевых байта 0x00).

3. K0ipad — (xorпобитовое исключающее ИЛИ) для полученияb-байтового блока S I .

4. Сложить М с S I . (конкатенация)5. Применить Н к потоку, созданному на шаге 5.

6. K0opad для получения b-байтового блока So.

7. Сложить результат хеширования на шаге 6 с So.(конкатенация)

8. Применить Н к потоку, созданному на шаге 8 и вывести

результат.

25. Атаки на функции хэширования и коды аутентичности.