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

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

Хэш функции

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

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

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

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

Пример

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

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

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

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

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

MD5

The Functions

Обозначения

Замечание

Secure Hash Algorithm (SHA)

Алгоритм SHA

Функции

SHA-256, SHA-384, and SHA-512

Different Message Expansions MD / RIPEMD roundwise permu-tations of the Mi

Step Operation SHA-0/1:

Обзор MD4-Family

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

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

Attack Methods

Взлом поиском коллизий Найти 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

Dobbertin‘s Attack on MD4, MD5, RIPEMD

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

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

Атака на MD5 Главные шаги в атаке: Выбор  Нахождение 2 внутренних коллизий Связать внутренние коллизии Связать IV and первую внутреннюю коллизию Как это сделать ? Решая системы уравнений

Литература [ 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