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

Сентябрь 7, 2022

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

Содержание

2. Mussiraliyeva -- Hash Functions Обрабатывает сообщения произвольной длины. Выдает результат фиксированной длины Хэш функции
3. Mussiraliyeva -- Hash Functions Применение в схемах электронных подписей Подпись верна? ? = h h
4. Mussiraliyeva -- Hash Functions Свойства криптографических хэш функций Зная сообщение M, довольно просто вычислить h=H(M), где
5. Mussiraliyeva -- Hash Functions ? = Алиса, подпиши, пожалуйста, этот контракт! Боб, Алиса подписала этот контракт!
6. Mussiraliyeva -- Hash Functions Устойчивость к коллизиям В некоторых приложениях свойства однонаправленности функции недостаточно, необходимо выполнение
7. Mussiraliyeva -- Hash Functions Пример 1. Алиса подготавливает две версии контракта: одну приемлемую для Боба, а
8. Mussiraliyeva -- Hash Functions Продолжение примера 4. Используя протокол, в котором требуется подписывать только значение хэш-функции,
9. Mussiraliyeva -- Hash Functions Хэш функции семейства MD4
10. MD4-Family Hash Functions Хэш функции представляющие практический интерес: Хэш функции основанные на блочном шифровании: Matyas-Meyer-Oseas, Davies-Meyer,
11. Mussiraliyeva -- Hash Functions Общая структура Итерационные сжимающие функции
12. Mussiraliyeva -- Hash Functions Общая структура сжимающих функций
13. Mussiraliyeva -- Hash Functions MD5 Алгоритм разработан Роном Ривестом. Алгоритм обрабатывает входной текст блоками размером 512
14. Mussiraliyeva -- Hash Functions При этом инициализируются четыре переменные A = 0x01234567; B = 0x89ABCDEF; C
15. Mussiraliyeva -- Hash Functions The Functions Раунд 1: f (b, c, d) = (b ∧ c)
16. Mussiraliyeva -- Hash Functions Обозначения ⊕ - операция XOR ¬ - операция NOT ∧ - операция
17. Mussiraliyeva -- Hash Functions Замечание Для многих приложений длина в 128 бит хэш функции MD5 недостаточна.
18. Mussiraliyeva -- Hash Functions Secure Hash Algorithm (SHA) NIST совместно с АНБ разработали алгоритм SHA-1 для
19. Mussiraliyeva -- Hash Functions Алгоритм SHA Вначале сообщение дополняется так, чтобы размер был на 64 разряда
20. Mussiraliyeva -- Hash Functions Функции Главный цикл состоит из 4 раундов, каждый из которых включает 20
21. Mussiraliyeva -- Hash Functions В алгоритме используются следующие 4 константы. : k0 = 0x5A827999; k1 =
22. Mussiraliyeva -- Hash Functions SHA-256, SHA-384, and SHA-512 В период с 2002-2004 NIST опубликовала стандарт содержащий
23. Mussiraliyeva -- Hash Functions Different Message Expansions MD / RIPEMD roundwise permu-tations of the Mi SHA
24. Mussiraliyeva -- Hash Functions Step Operation SHA-0/1: MD5: Only 1 register changed per step Mixture of
25. Mussiraliyeva -- Hash Functions SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512) (NIST, ’02/04) SHA-0 (NIST, ’93) Обзор MD4-Family
26. Новый стандарт! SHA-3 2 октября 2012 года Национальный институт стандартов и технологий США (NIST) выбрал победителя
27. Keccak Основой функции сжатия алгоритма является функция f(), выполняющая перемешивание внутреннего состояния алгоритма. Состояние (обозначим его
28. Mussiraliyeva -- Hash Functions Attack Methods
29. Mussiraliyeva -- Hash Functions Найти M‘≠M с тем, чтобы h(M‘)=h(M)“ Существует три вида(успешных) атак: Dobbertin (1995/96)
30. Mussiraliyeva -- Hash Functions Dobbertin‘s Attack on MD4, MD5, RIPEMD
31. Mussiraliyeva -- Hash Functions Попытаемся найти M ≠M’ такие, что H(M)=H(M’) Здесь M=(M1,M2,…..,M16) M‘=M+Δ Каждое Mi
32. Mussiraliyeva -- Hash Functions Атака на MD5 Вычисления производятся параллельно до появления Δi ≠ 0 Специальное
33. Mussiraliyeva -- Hash Functions Главные шаги в атаке: Выбор Δ Нахождение 2 внутренних коллизий Связать внутренние
35. Скачать презентацию

Слайд 2

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

Слайд 3

Mussiraliyeva -- Hash Functions
Применение в схемах электронных подписей
Подпись верна?
?
=
h
h

Слайд 4

Mussiraliyeva -- Hash Functions
Свойства криптографических хэш функций
Зная сообщение M, довольно просто

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

Слайд 5

Mussiraliyeva -- Hash Functions
?
=
Алиса, подпиши, пожалуйста, этот контракт!
Боб, Алиса подписала этот

контракт!

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

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

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

Коллизия!

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

Слайд 6

Mussiraliyeva -- Hash Functions
Устойчивость к коллизиям
В некоторых приложениях свойства однонаправленности функции

недостаточно, необходимо выполнение выполнение строгого требования, называемого устойчивостью к коллизиям:
Трудно найти два случайных сообщения
M и M’, для которых H(M) = H(M’)
Следующий пример иллюстрирует необходимость последнего требования.

Слайд 7

Mussiraliyeva -- Hash Functions
Пример
1. Алиса подготавливает две версии контракта: одну приемлемую

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

Слайд 8

Mussiraliyeva -- Hash Functions
Продолжение примера
4. Используя протокол, в котором требуется подписывать

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

Слайд 9

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

Слайд 10

MD4-Family
Hash Functions
Хэш функции представляющие практический интерес:
Хэш функции основанные на блочном шифровании:
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
Whirlpool
Новый стандарт SHA-3 : Keccak

Слайд 11

Mussiraliyeva -- Hash Functions
Общая структура
Итерационные сжимающие функции

Слайд 12

Mussiraliyeva -- Hash Functions
Общая структура сжимающих функций

Слайд 13

Mussiraliyeva -- Hash Functions
MD5
Алгоритм разработан Роном Ривестом. Алгоритм обрабатывает входной текст

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

Слайд 14

Mussiraliyeva -- Hash Functions
При этом инициализируются четыре переменные
A = 0x01234567; B

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

Слайд 15

Mussiraliyeva -- Hash Functions
The Functions
Раунд 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)

Слайд 16

Mussiraliyeva -- Hash Functions
Обозначения
⊕ - операция XOR
<<< - циклический сдвиг влево
¬

- операция NOT
∧ - операция AND
∨ - операция OR

Слайд 17

Mussiraliyeva -- Hash Functions
Замечание
Для многих приложений длина в 128 бит хэш

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

Слайд 18

Mussiraliyeva -- Hash Functions
Secure Hash Algorithm (SHA)
NIST совместно с АНБ разработали

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

Слайд 19

Mussiraliyeva -- Hash Functions
Алгоритм SHA
Вначале сообщение дополняется так, чтобы размер был

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

Слайд 20

Mussiraliyeva -- Hash Functions
Функции
Главный цикл состоит из 4 раундов, каждый из

которых включает 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

Слайд 21

Mussiraliyeva -- Hash Functions
В алгоритме используются следующие 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

Слайд 22

Mussiraliyeva -- Hash Functions
SHA-256, SHA-384, and SHA-512
В период с 2002-2004 NIST

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

Слайд 23

Mussiraliyeva -- Hash Functions
Different Message Expansions
MD / RIPEMD
roundwise permu-tations of the

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

Слайд 24

Mussiraliyeva -- Hash Functions
Step Operation
SHA-0/1:
MD5:
Only 1 register changed per step
Mixture of

different kinds of operations

Слайд 25

Mussiraliyeva -- Hash Functions
SHA-2
(SHA-224, SHA-256, SHA-384, SHA-512) (NIST, ’02/04)
SHA-0 (NIST, ’93)
Обзор

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 и др.)

Слайд 26

Новый стандарт! SHA-3
2 октября 2012 года Национальный институт стандартов и

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

Слайд 27

Keccak
Основой функции сжатия алгоритма является функция f(), выполняющая перемешивание внутреннего состояния

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

Mussiraliyeva -- Hash Functions

Слайд 28

Mussiraliyeva -- Hash Functions
Attack Methods

Слайд 29

Mussiraliyeva -- Hash Functions
Найти 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

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

Слайд 30

Mussiraliyeva -- Hash Functions
Dobbertin‘s Attack on MD4, MD5, RIPEMD

Слайд 31

Mussiraliyeva -- Hash Functions
Попытаемся найти M ≠M’ такие,
что H(M)=H(M’)
Здесь

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

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

Слайд 32

Mussiraliyeva -- Hash Functions
Атака на MD5
Вычисления производятся параллельно до появления Δi

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

Слайд 33

Mussiraliyeva -- Hash Functions
Главные шаги в атаке:
Выбор Δ
Нахождение 2 внутренних

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

Атака на MD5

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

Содержание

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

Mussiraliyeva -- Hash FunctionsПрименение в схемах электронных подписейПодпись верна??=hh

Mussiraliyeva -- Hash FunctionsСвойства криптографических хэш функцийЗная сообщение M, довольно просто

Mussiraliyeva -- Hash Functions?=Алиса, подпиши, пожалуйста, этот контракт!Боб, Алиса подписала этот

Mussiraliyeva -- Hash FunctionsУстойчивость к коллизиямВ некоторых приложениях свойства однонаправленности функции

Mussiraliyeva -- Hash FunctionsПример1. Алиса подготавливает две версии контракта: одну приемлемую

Mussiraliyeva -- Hash FunctionsПродолжение примера4. Используя протокол, в котором требуется подписывать

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

MD4-FamilyHash FunctionsХэш функции представляющие практический интерес:Хэш функции основанные на блочном шифровании:Matyas-Meyer-Oseas,

Mussiraliyeva -- Hash FunctionsОбщая структура Итерационные сжимающие функции

Mussiraliyeva -- Hash FunctionsОбщая структура сжимающих функций

Mussiraliyeva -- Hash FunctionsMD5Алгоритм разработан Роном Ривестом. Алгоритм обрабатывает входной текст

Mussiraliyeva -- Hash FunctionsПри этом инициализируются четыре переменныеA = 0x01234567; B

Mussiraliyeva -- Hash FunctionsThe FunctionsРаунд 1:f (b, c, d) = (b

Mussiraliyeva -- Hash FunctionsОбозначения⊕ - операция XOR<<< - циклический сдвиг влево¬

Mussiraliyeva -- Hash FunctionsЗамечаниеДля многих приложений длина в 128 бит хэш

Mussiraliyeva -- Hash FunctionsSecure Hash Algorithm (SHA)NIST совместно с АНБ разработали

Mussiraliyeva -- Hash FunctionsАлгоритм SHAВначале сообщение дополняется так, чтобы размер был

Mussiraliyeva -- Hash FunctionsФункцииГлавный цикл состоит из 4 раундов, каждый из

Mussiraliyeva -- Hash FunctionsВ алгоритме используются следующие 4 константы. :k0 =

Mussiraliyeva -- Hash FunctionsSHA-256, SHA-384, and SHA-512В период с 2002-2004 NIST

Mussiraliyeva -- Hash FunctionsDifferent Message ExpansionsMD / RIPEMDroundwise permu-tations of the

Mussiraliyeva -- Hash FunctionsStep OperationSHA-0/1:MD5:Only 1 register changed per stepMixture of

Mussiraliyeva -- Hash FunctionsSHA-2(SHA-224, SHA-256, SHA-384, SHA-512) (NIST, ’02/04)SHA-0 (NIST, ’93)Обзор

Новый стандарт! SHA-3 2 октября 2012 года Национальный институт стандартов и

KeccakОсновой функции сжатия алгоритма является функция f(), выполняющая перемешивание внутреннего состояния

Mussiraliyeva -- Hash FunctionsAttack Methods

Mussiraliyeva -- Hash FunctionsНайти M‘≠M с тем, чтобы h(M‘)=h(M)“Существует три вида(успешных)

Mussiraliyeva -- Hash FunctionsDobbertin‘s Attack on MD4, MD5, RIPEMD

Mussiraliyeva -- Hash FunctionsПопытаемся найти M ≠M’ такие, что H(M)=H(M’) Здесь

Mussiraliyeva -- Hash FunctionsАтака на MD5Вычисления производятся параллельно до появления Δi

Mussiraliyeva -- Hash FunctionsГлавные шаги в атаке:Выбор Δ Нахождение 2 внутренних

Похожие презентации