Презентация 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