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

1. Вопросы

Department of
Informational
Systems
• Хэш функции: Свойства и применения
• Семейство хэш функций MD4
– Принципы построения
– Исторический обзор криптоанализа
• Методы криптоанализа
– Атака Доббертина на MD4, MD5 and RIPEMD
• Улучшенный метод Доббертина
– Атаки Chabaud/Joux and Biham/Chen на SHA-0/1
– Атаки Wang et al. на MD4, MD5 HAVAL and RIPEMD
• Заключение
Mussiraliyeva -- Hash Functions

2. Хэш функции

Обрабатывает сообщения произвольной
длины.
Выдает результат фиксированной длины
message
Hash function
Mussiraliyeva -- Hash Functions

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

Department of
Informational
Systems
Bob
Alice
h
h
?
=
Mussiraliyeva -- Hash Functions
Подпись
верна?

4. Свойства криптографических хэш функций

Department of
Informational
Systems
Свойства
криптографических хэш функций
• Зная сообщение M, довольно просто вычислить h=H(M),
где H однонаправленная хэш-функция
• Зная h, трудно определить M, для которого H(M) = h
• Зная M, трудно определить другое сообщение M’, для
которого H(M) = H(M’)
Mussiraliyeva -- Hash Functions

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

Alice
Department of
Informational
Systems
Подпись
Алиса
Okay, Я подпишу
подписала
верна !
этот контракт
на
конракт на
сумму €10k
.
сумму
€50k.
h
€ 10k
€ 10k
h
Bob
?
=
€ 50k
h
h
€ 50k
Коллизия!
Алиса, подпиши,
пожалуйста, этот
контракт!
Eve
Mussiraliyeva -- Hash Functions
Боб, Алиса
подписала этот
контракт!

6. Устойчивость к коллизиям

Department of
Informational
Systems
В некоторых приложениях свойства однонаправленности
функции
недостаточно,
необходимо
выполнение
выполнение
строгого
требования,
называемого
устойчивостью к коллизиям:
•Трудно найти два случайных сообщения
M и M’, для которых H(M) = H(M’)
Следующий пример иллюстрирует
последнего требования.
Mussiraliyeva -- Hash Functions
необходимость

7. Пример

Department of
Informational
Systems
1. Алиса подготавливает две версии контракта: одну
приемлемую для Боба, а вторую нет.
2. Алиса вносит несколько несущественных модификаций
в каждый документ и вычисляет их хэш-функции.
(например, пробел, ввод)
3. Алиса сравнивает значения хэш-функции, рассчитанного
в каждом из двух документов, разыскивая пару, для
которой эти значения совпадают.
Mussiraliyeva -- Hash Functions

8. Продолжение примера

Department of
Informational
Systems
Продолжение примера
4. Используя протокол, в котором требуется подписывать
только значение хэш-функции, Алиса получает подписанную
Бобом выгодную для него версию контракта.
5. Алиса заменяет подписанный Бобом контракт другим.
Совет 1: Всегда вносите мелкие исправления в документ перед
его подписанием.
Совет 2: Следует использовать хэш-функцию с достаточно
длинным выходом.
Mussiraliyeva -- Hash Functions

9. Хэш функции семейства MD4

Department of
Informational
Systems
Хэш функции
семейства MD4
Mussiraliyeva -- Hash Functions

10. Hash Functions

Department of
Informational
Systems
• Хэш функции представляющие практический интерес:
– Хэш функции основанные на блочном шифровании:
• Matyas-Meyer-Oseas, 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
MD4Family
• Whirlpool
Новый стандарт SHA-3 : Keccak

11. Общая структура

Department of
Informational
Systems
• Итерационные сжимающие функции
collision-resistance of the
compression function
collision-resistance
of the hash function
Mussiraliyeva -- Hash Functions

12. Общая структура сжимающих функций

Message
Expansion
Mussiraliyeva -- Hash Functions
Department of
Informational
Systems

13. MD5

Department of
Informational
Systems
Алгоритм
разработан
Роном
Ривестом.
Алгоритм
обрабатывает входной текст блоками размером 512
разрядов. Выходным результатом функции является 128
разрядное значение.
Вначале сообщение дополняется так, чтобы размер был на
64 разряда меньше числа, кратного 512. Это дополнение
включает единицу, за которой, вплоть до конца сообщения,
помещаются нули. Затем к результату добавляется 64разрядное представление размера сообщения.
Mussiraliyeva -- Hash Functions

14.

Department of
Informational
Systems
При этом инициализируются четыре переменные
A = 0x01234567; B = 0x89ABCDEF;
C = 0xFEDCBA98; D = 0x76543210
MD5 использует 4 раунда. На каждом раунде
выполняется 16 различных операций.
Каждая
операция
состоит
в
вычислении
нелинейной функции над тремя переменными b, c
и d.
a = A; b = B; c = C; d = D;
Mussiraliyeva -- Hash Functions

15. The Functions

Department of
Informational
Systems
Раунд 1:
f (b, c, d) = (b 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)
Mussiraliyeva -- Hash Functions

16. Обозначения

- операция XOR
<<< - циклический сдвиг влево
- операция NOT
- операция AND
- операция OR
Mussiraliyeva -- Hash Functions
Department of
Informational
Systems

17. Замечание

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

18. Secure Hash Algorithm (SHA)

Department of
Informational
Systems
Secure Hash Algorithm (SHA)
NIST совместно с АНБ разработали алгоритм
SHA-1 для его использования вместе со
стандартом цифровых подписей DSS. SHA-1
обычно называют просто SHA.
Алгоритм обрабатывает блоки сообщения
длиной 512 бит и выдает 160 битовое значение
хэш функции.
Mussiraliyeva -- Hash Functions

19. Алгоритм SHA

Department of
Informational
Systems
Вначале сообщение дополняется так, чтобы размер был на
64 разряда меньше числа, кратного 512. Это дополнение
включает единицу, за которой, вплоть до конца
сообщения, помещаются нули.
Затем к результату
добавляется
64-разрядное
представление
размера
сообщения.
448 bits + 64 bits = 512 bits
Инициализируется пять переменных. :
A = 0x67452301; B = 0xEFCDAB89: C = 0x98BADCFE;
D = 0x10325476; E = 0xC3D2E1F0;
Mussiraliyeva -- Hash Functions

20. Функции

Department of
Informational
Systems
Главный цикл состоит из 4 раундов, каждый из
которых включает 20 операций. В алгоритме
SHA
используется
следующий
набор
нелинейных функций.
ft (x, y,
t=0..19
ft (x, y,
ft (x, y,
t=40..59
ft (x, y,
z) = (x y) (( x)
z),
z) = (x y z), t=20..39
z) = (x y) (x z) (y z),
z) = (x y z), t=60..79
Mussiraliyeva -- Hash Functions

21.

Department of
Informational
Systems
В
алгоритме
константы. :
используются
следующие
4
k0 = 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
Mussiraliyeva -- Hash Functions

22. SHA-256, SHA-384, and SHA-512

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

23. Different Message Expansions

Department of
Informational
Systems
Different Message Expansions
MD / RIPEMD
• roundwise permutations of the Mi
SHA
• recursive
definition
Wi=Mi, i=1,…,k
Wi=f(Wi-k,…,Wi-1)
i>k
SHA-1
Wi=(Wi-3 Wi-8 Wi-14
Wi-16)<<<1
Mussiraliyeva -- Hash Functions

24. Step Operation

MD5:
Step Operation
Department of
Informational
Systems
SHA-0/1:
• Only 1 register changed per step
• Mixture of different kinds of operations
Mussiraliyeva -- Hash Functions

25. Обзор MD4-Family

Wang/Feng/
Dobbertin
‚’95/96
Lai/Yu‚
2004
(RIPE, ‘92)
SHA-0
(Rivest ‚‘90)
(Rivest ‚‘90)
RIPEMD-0
Joux‚ 2004‘98
Chabaud/Joux‚
MD4
Ext. MD4
Department of
Informational
Systems
(NIST, ’93)
van
Kasselman/
Rompay/
Preneel/???‚
Penzhorn‚ 2000
2003
MD5
HAVAL
(Rivest ‚‘92)
(Zheng, Pieprzyk,
Seberry ‚‘93)
RIPEMD-128
RIPEMD-160
RIPEMD-256
RIPEMD-320
MD6
(Dobbertin, Bosselaers,
Preneel ‘96)
(Rivest,2008)
Mussiraliyeva -- Hash Functions
Biham/Chen‚
2004
SHA-1
(NIST, ’95)
,
Каньер, Рехберг 2006
SHA-2
(SHA-224, SHA-256,
SHA-384, SHA-512)
(NIST, ’02/04)
Кумар,Саркар,2008
SHA-3: Keccak( J.
Daemen и др.)

26. Новый стандарт! SHA-3

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

27. Keccak

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

28. Attack Methods

Department of
Informational
Systems
Attack Methods
Mussiraliyeva -- Hash Functions

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

Найти M‘ M с тем, чтобы h(M‘)=h(M)“
Существует три вида(успешных) атак:
– Dobbertin (1995/96)
– Chabaud/Joux (1998),
Biham/Chen(2004),
Joux(2004)
– Wang/Feng/Lai/Yu (2004)
Все атаки используют некоторую начальную разность
– input differential output differential
– modular differentials XOR differentials
Mussiraliyeva -- Hash Functions
Department of
Computational
Mathematics

30. Dobbertin‘s Attack on MD4, MD5, RIPEMD

Department of
Computational
Mathematics
Dobbertin‘s Attack
on MD4, MD5,
RIPEMD
Mussiraliyeva -- Hash Functions

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

Department of
Computational
Mathematics
• Попытаемся найти M M’ такие,
что H(M)=H(M’)
Здесь M=(M1,M2,…..,M16)
M‘=M+
• Каждое Mi используется в точности в 4
строках вычислений
– Выберем 15=1 и i=0 для всех i
Вычисления для M и M‘ отличаются
только 4 строках вычислений
Mussiraliyeva -- Hash Functions

32. Атака на MD5

i=0
15 0
15 0
i=0
15 0
Department of
Computational
Mathematics
• Вычисления производятся
параллельно до появления
i 0
• Специальное построение:
Требование Внутренних
Коллизий(Inner Collisions)
• Дальнейшие вычисления
также производятся
параллельно
15 0
i=0
Mussiraliyeva -- Hash Functions

33. Атака на MD5

i=0
15 0
15 0
i=0
15 0
Department of
Computational
Mathematics
Главные шаги в атаке:
• Выбор
• Нахождение 2 внутренних
коллизий
• Связать внутренние
коллизии
• Связать IV and первую
внутреннюю коллизию
Как это сделать ?
► Решая системы уравнений
15 0
i=0
Mussiraliyeva -- Hash Functions

34. Литература

• [ 1]Magnus Daum. Cryptoanalysis of
Hash Functions of the MD4-Family.
Dissertation. 2005
• [ 2]
http://www.cs.colorado.edu/~jrblack/
papers/md5e-full.pdf
• [3] http://ru.wikipedia.org/wiki/MD5
Mussiraliyeva -- Hash Functions