Коллизии MD5

Понятие коллизии. Парадокс дней рождения. Сравнение длины кода аутентификации сообщения (имитоставки) и длины блочного шифра.

Аутентификация и целостность

Неумышленные нарушения целостности

Обеспечение целостности данных с использованием шифрации и MAC

По сравнению с предыдущим случаем в канал посылается сообщение следующего вида: E _k(x || h _k1(x)). Такая схема обеспечения целостности имеет преимущество над предыдущей схемой с MDC: если шифр будет взломан, MAC все равно будет обеспечивать целостность данных. Недостатком является то, что используется два различных ключа, для криптоалгоритма и для MAC. При использовании подобной схемы, следует быть уверенным, что какие-либо зависимости между алгоритмом MAC и алгоритмом шифрации не приведут к уязвимости системы. Рекомендуется, чтобы эти два алгоритма были независимыми (например, такой недостаток системы может проявляться, когда в качестве алгоритма MAC используется CBC-MAC, и в качестве схемы шифрования CBC).

Вообще говоря, шифрация всего сообщения при использовании кодов аутентификации сообщений не обязательно с точки зрения обеспечения целостности данных, поэтому в простейших случаях в схеме может не происходить шифрация сообщения (x || h _k(x)).

С точки зрения криптографии основной интерес представляют задачи обеспечения целостности данных, в которых осуществляются их умышленные изменения. Однако методы обеспечения проверки случайных изменений тоже применяются. К таким методам относят использование кодов обнаружения и исправления ошибок. К таковым, например, относятся: коды Хемминга, коды CRC, коды БЧХ и прочие.

Проблема целостности данных плотно связанно и с проблемой аутентификации данных, то есть установлением источника данных. Эти проблемы не могут быть отделены одна от другой. Данные, которые были изменены, имеют фактически новый источник. Также если не известен источник данных, то вопрос об их изменении не может быть разрешен (без ссылки на источник). Таким образом, механизмы проверки целостности данных обеспечивают аутентификацию данных, и наоборот.

Коллизия хеш-функции — это получение одинакового значения функции для разных сообщений и идентичного начального буфера. В отличие от коллизий, псевдоколлизии определяются как равные значения хеша для разных значений начального буфера, причём сами сообщения могут совпадать или отличаться. В 1996 году Ганс Доббертин нашёл псевдоколлизии в MD5, используя определённые инициализирующие векторы, отличные от стандартных. Оказалось, что можно для известного сообщения построить второе, такое, что оно будет иметь такой же хеш, как и исходное. C точки зрения математики это означает: MD5(IV,L1) = MD5(IV,L2), где IV — начальное значение буфера, а L1 и L2 — различные сообщения.

Парадо́кс дней рожде́ния — это кажущееся парадоксальным утверждение, что вероятность совпадения дней рождения (числа и месяца) хотя бы у двух членов группы из 23 и более человек, превышает 50 %. С практической точки зрения это означает, что если, например, в вашем классе более 22 учеников, то более вероятно, что у кого-то из одноклассников дни рождения придутся на один день, чем что у каждого будет свой собственный день рождения.

Для 60 и более человек вероятность такого совпадения превышает 99 %, хотя 100 % она достигает, согласно принципу Дирихле, только когда в группе не менее 367 человек (с учётом високосных лет).

Такое утверждение может показаться неочевидным, так как вероятность совпадения дней рождения двух человек в любой день года (1/365 = 0,27 %), помноженная на число человек в группе из 23, даёт лишь 23/365 = 6,3 %. Это рассуждение неверно, так как число возможных пар (253) значительно превышает число человек в группе. Таким образом, утверждение не является парадоксом в строгом научном смысле — логического противоречия в нём нет, а парадокс заключается лишь в различиях между интуитивным восприятием ситуации человеком и результатами математического расчёта.

В криптоанализе под атакой «дней рождения» понимают метод взлома шифров или поиска коллизий хеш-функций на основе парадокса дней рождения.

Дата добавления: 2015-04-24