Атака «дней рождения»

Атака «дней рождения»

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

Поиск коллизий хеш-функций

Для заданной хеш-функции f целью атаки является поиск коллизии второго рода. Для этого вычисляются значения f для случайно выбранных блоков входных данных до тех пор, пока не будут найдены два блока, имеющие один и тот же хеш. Таким образом, если f имеет N различных равновероятных выходных значений, и N является достаточно большим, то из парадокса о днях рождения следует, что, в среднем, после перебора 1,25 \cdot \sqrt N различных входных значений, будет найдена искомая коллизия.

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

В частности, требуется в два раза большая длина хеша, чтобы обеспечить вычислительную сложность, сравнимую со сложностью полного перебора. Другими словами, если с помощью полного перебора злоумышленник может вычислить 2^n хэш-значений, то он начнёт находить хэш-коллизии для всех хэшей длиной менее 2n бит.

Примеры

Предположим, что для атаки на 64-битный блочный шифр злоумышленнику нужно получить две пары открытого/шифрованного текста, которые отличаются только в наименее значимом бите. Интерпретация этой задачи в терминах парадокса дней рождения приводит к выводу, что пространство из всего лишь 2^{32} известных открытых текстов с высокой вероятностью будет содержать необходимую пару.

В качестве другого примера рассмотрим цикл 64-битового Фейстелева шифра. Предположим, что в шифре использована случайная функция F (32 в 32 бита). Нападающий может захотеть узнать, как много ему необходимо получить открытых текстов для получения коллизии функции F. Согласно парадоксу дней рождения, для этого придётся перебрать около 2^{16} открытых текстов.

Одним из следствий парадокса дней рождения является то, что для n-битового блочного шифра повторяемые появления блока шифротекста могут ожидаться с вероятностью около 0,63 при наличии лишь 2^{n/2} случайных открытых текстов, зашифрованных на одном ключе (независимо от размера ключа). Для ECB режима при совпадении двух блоков шифротекста соответствующие открытые тексты обязаны также совпадать. Это означает, что в атаке с известным шифротекстом информация об открытых текстах может раскрываться из шифртекстовых блоков.




Wikimedia Foundation. 2010.

Нужна помощь с курсовой?

Полезное


Смотреть что такое "Атака «дней рождения»" в других словарях:

  • криптоанализ на основе парадокса дней рождения — Атака "по дню рождения"; частный случай лобовой атаки для выявления коллизий. Получила свое название от того парадокса, что в группе из 23 человек вероятность совпадения двух или нескольких дней рождений больше чем 50 %.… …   Справочник технического переводчика

  • Атака нахождения прообраза — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете …   Википедия

  • Криптографическая атака — Криптоанализ (от греч. κρυπτός скрытый и анализ) наука о методах получения исходного значения зашифрованной информации, не имея доступа к секретной информации (ключу), необходимой для этого. В большинстве случаев под этим подразумевается… …   Википедия

  • Человек посередине — Атака «человек посередине», MITM атака (англ. Man in the middle)  термин в криптографии, обозначающий ситуацию, когда криптоаналитик (атакующий) способен читать и видоизменять по своей воле сообщения, которыми обмениваются… …   Википедия

  • Tiger (хэш-функция) — Tiger  хеш функция, разработанная Росом Андерсоном и Эли Бихамом в 1995 году. Tiger был предназначен для особенно быстрого выполнения на 64 разрядных компьютерах. Tiger не имеет патентных ограничений, может использоваться свободно как с… …   Википедия

  • Криптоанализ — (от др. греч. κρυπτός  скрытый и анализ)  наука о методах расшифровки зашифрованной информации без предназначенного для такой расшифровки ключа. Термин был введён американским криптографом Уильямом Ф. Фридманом в 1920 году. Неформально… …   Википедия

  • HMAC — (сокращение от англ. hash based message authentication code, хеш код аутентификации сообщений). Наличие способа проверить целостность информации, передаваемой или хранящийся в ненадежной среде является неотъемлемой и необходимой частью мира… …   Википедия

  • Коллизия хэш-функции — Коллизией хеш функции H называется два различных входных блока данных x и y таких, что H(x) = H(y). Коллизии существуют для большинства хеш функций, но для «хороших» хеш функций частота их возникновения близка к теоретическому минимуму. В… …   Википедия

  • Коллизия хеш-функции — Коллизией хеш функции называется два различных входных блока данных и таких, что Коллизии существуют для большинства хеш функций, но для «хороших» хеш функций частота их возникновения близка к теоретическому минимуму. В некоторых частных случаях …   Википедия

  • Коллизия хэш функции — Коллизией хеш функции H называется два различных входных блока данных x и y таких, что H(x) = H(y). Коллизии существуют для большинства хеш функций, но для «хороших» хеш функций частота их возникновения близка к теоретическому минимуму. В… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»