Department of Informational Systems. Хэш функции, свойства и применения. Семейство хэш функций MD4. (Лекция 8) презентация

построения
Исторический обзор криптоанализа
Методы криптоанализа
Атака Доббертина на MD4, MD5 and RIPEMD
Улучшенный метод Доббертина
Атаки Chabaud/Joux and Biham/Chen на SHA-0/1
Атаки Wang et al. на MD4, MD5 HAVAL and RIPEMD
Заключение

Вопросы

вычислить h=H(M), где H однонаправленная хэш-функция

Зная h, трудно определить M, для которого H(M) = h

Зная M, трудно определить другое сообщение M’, для которого H(M) = H(M’)

контракт!

h

Okay, Я подпишу этот контракт на сумму €10k.

Алиса подписала конракт на сумму €50k.

Подпись верна !

Коллизия!

Применение в схемах электронных подписей

недостаточно, необходимо выполнение выполнение строгого требования, называемого устойчивостью к коллизиям:

Трудно найти два случайных сообщения
M и M’, для которых H(M) = H(M’)

Следующий пример иллюстрирует необходимость последнего требования.

для Боба, а вторую нет.

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

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

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

5. Алиса заменяет подписанный Бобом контракт другим.

Совет 1: Всегда вносите мелкие исправления в документ перед его подписанием.

Совет 2: Следует использовать хэш-функцию с достаточно длинным выходом.

Davies-Meyer, Miyaguchi-Preneel
MDC-2, MDC-4
Специализированные хэш функции:
MD4, MD5
RIPEMD-{0,128,160,256,320}
SHA-{0,1,224,256,384,512}
HAVAL
Tiger
Whirlpool
Новый стандарт SHA-3 : Keccak

блоками размером 512 разрядов. Выходным результатом функции является 128 разрядное значение.

Вначале сообщение дополняется так, чтобы размер был на 64 разряда меньше числа, кратного 512. Это дополнение включает единицу, за которой, вплоть до конца сообщения, помещаются нули. Затем к результату добавляется 64-разрядное представление размера сообщения.

= 0x89ABCDEF;
C = 0xFEDCBA98; D = 0x76543210

MD5 использует 4 раунда. На каждом раунде выполняется 16 различных операций.
Каждая операция состоит в вычислении нелинейной функции над тремя переменными b, c и d.
a = A; b = B; c = C; d = D;

∧ c) ∨ (¬ b ∧ d)

Раунд 2:
f (b, c, d) = (b ∧ c) ∨ (b ∧ ¬ d)

Раунд 3:
f (b, c, d) = (b ⊕ c ⊕ d)

Раунд 4:
f (b, c, d) = c ⊕ (b ∨ ¬ d)

- операция NOT

∧ - операция AND

∨ - операция OR

функции MD5 недостаточна. Используя атаку «дней рождений» можно определить MD5 коллизию за 264 вычислений значений хэш-функции. Что не обеспечит защиту в современных системах.
Наш совет: Не используйте MD5, если вы нуждаетесь в действенной защите .

алгоритм SHA-1 для его использования вместе со стандартом цифровых подписей DSS. SHA-1 обычно называют просто SHA.

Алгоритм обрабатывает блоки сообщения длиной 512 бит и выдает 160 битовое значение хэш функции.

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

448 bits + 64 bits = 512 bits

Инициализируется пять переменных. :

A = 0x67452301; B = 0xEFCDAB89: C = 0x98BADCFE;
D = 0x10325476; E = 0xC3D2E1F0;

которых включает 20 операций. В алгоритме SHA используется следующий набор нелинейных функций.
ft (x, y, z) = (x ∧ y) ∨ ((¬ x) ∧ z), t=0..19
ft (x, y, z) = (x ⊕ y ⊕ z), t=20..39
ft (x, y, z) = (x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z), t=40..59
ft (x, y, z) = (x ⊕ y ⊕ z), t=60..79

0x5A827999; k1 = 0x6ED9EBA1;
k2 = 0x8F1BBCDC; k3 = 0xCA62C!D6;

Блок сообщения преобразуется из 16 слов размером в 32 разряда в 80 слов размером 32 разряда.

wi = mi for i = 0 ... 15
wi = (wi-3 ⊕ wi-8 ⊕ wi-14 ⊕ wi-16) <<< 1
for i = 16 ... 79

опубликовала стандарт содержащий три хэш функции. (см. http://csrc.nist.gov/encryption/shs/dfips-180-2.pdf. [страница 89])
Выходными значениями данных функций являются соответственно 256-, 384-, and 512-битовые значения. Используются ключи AES размером 128, 196, и 256 бит. Структура алгоритма подобна SHA-1.

Mi

SHA
recursive definition

Wi=Mi, i=1,…,k

Wi=f(Wi-k,…,Wi-1)

i>k

Wi=(Wi-3⊕Wi-8 ⊕ Wi-14 ⊕ Wi-16)<<<1

SHA-1

different kinds of operations

MD4-Family

MD4 (Rivest ‚‘90)

Ext. MD4 (Rivest ‚‘90)

RIPEMD-0 (RIPE, ‘92)

MD5 (Rivest ‚‘92)

RIPEMD-128
RIPEMD-160
RIPEMD-256
RIPEMD-320
(Dobbertin, Bosselaers, Preneel ‘96)

SHA-1 (NIST, ’95)

HAVAL (Zheng, Pieprzyk, Seberry ‚‘93)

Dobbertin ‚’95/96

Kasselman/ Penzhorn‚ 2000

Chabaud/Joux‚ ‘98

van Rompay/ Preneel/???‚ 2003

Biham/Chen‚ 2004

Joux‚ 2004

Wang/Feng/ Lai/Yu‚ 2004

MD6
(Rivest,2008)

Каньер, Рехберг,2006

Кумар,Саркар,2008

SHA-3: Keccak( J. Daemen и др.)

технологий США (NIST) выбрал победителя в конкурсе криптографических хэш-алгоритмов для стандарта SHA-3. В нём участвовало 64 претендента. Пять финалистов конкурса определились почти два года назад. Победителем стал алгоритм Keccak (читается «кэтчэк» или «кетчак» — устоявшегося варианта русского написания и произношения пока нет), созданный командой криптологов из Италии и Бельгии.  Хотя алгоритм SHA-2 пока не взломан, принятие нового стандарта уже сейчас готовит «запасной аэродром» на случай компрометации старого. Конкурс на новый алгоритм был объявлен в 2007 году после того, как был скомпрометирован алгоритм SHA-1. Это внушило опасения, что и родственное ему семейство SHA-2 не устоит. По словам специалистов NIST, алгоритм Keccak выбран из-за простого и элегантного дизайна и гораздо лучшей, чем у большинства конкурентов, производительности и лёгкости реализации на разных типах устройств. Алгоритм принципиально отличается от SHA-2, а значит уязвимости, которые могут быть найдены в старом стандарте, скорее всего не затронут новый.

алгоритма. Состояние (обозначим его A) представляется в виде массива 5 X 5, элементами которого являются 64-битные слова, инициализированные нулевыми битами (то есть размер состояния составляет 1600 битов). Функция f() выполняет 18 раундов
Возможные размеры хэш-значений — 224, 256, 384 и 512 бит.

Mussiraliyeva -- Hash Functions

атак:
Dobbertin (1995/96)
Chabaud/Joux (1998), Biham/Chen(2004), Joux(2004)
Wang/Feng/Lai/Yu (2004)
Все атаки используют некоторую начальную разность
input differential ? output differential
modular differentials ?? XOR differentials

Взлом поиском коллизий

Здесь M=(M1,M2,…..,M16)
M‘=M+Δ
Каждое Mi используется в точности в 4 строках вычислений
Выберем Δ15=1 и Δi=0 для всех i
Вычисления для M и M‘ отличаются только 4 строках вычислений

Пример: Атака на MD5

≠ 0
Специальное построение: Требование Внутренних Коллизий(Inner Collisions)
Дальнейшие вычисления также производятся параллельно

коллизий
Связать внутренние коллизии
Связать IV and первую внутреннюю коллизию
Как это сделать ?
Решая системы уравнений

Атака на MD5

the MD4-Family. Dissertation. 2005
[ 2] http://www.cs.colorado.edu/~jrblack/papers/md5e-full.pdf
[3] http://ru.wikipedia.org/wiki/MD5