В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 3. Введение в криптографию вают ключ шифрования, однако позволяют расшифровать другое сообщение. Кроме того, есть атаки, которые не восстанавливают сообщение, но позволя- ют получить некоторую информацию о нем. Вообще говоря, с каждым днем в мире появляется так много разнообразных типов атак, что перечислить их все на страницах этой книги невозможно. Так с чем же нам следует бороться? Чтобы лучше понять эту проблему, введем понятие различающей ата- ки. Различающая атака (distinguishing attack) — это любой нетривиальный метод, позволяющий обнаружить различие между идеальным и реальным шифром. Данное понятие охватывает все рассмотренные нами типы атак, а также атаки, которые появятся в будущем. Разумеется, нам также понадо- бится определить, что следует считать идеальным шифром. Не слишком ли это определение искусственно, скажете вы? Вовсе нет. Опыт подсказывает, что каждый компонент криптографической системы дол- жен быть как можно более совершенным. Некоторые функции шифрования имеют определенные недостатки, что теоретически позволяет взломать их посредством различающей атаки. Во всем остальном, однако, они являются абсолютно удовлетворительными функциями шифрования. Используя такие функции, необходимо всякий раз проверять, не приводят ли эти недостатки к каким-либо проблемам безопасности. В системе, состоящей из множества компонентов, необходимо также проверять, не приводят ли к проблемам без- опасности все возможные комбинации недостатков ее компонентов. На прак- тике реализовать данное требование почти невозможно, в результате чего на рынке появляются системы, обладающие массой слабых мест из-за известно- го несовершенства их компонентов. 3.6.6 Атаки, в основе которых лежит парадокс задачи о днях рождения Такие атаки получили свое название в честь парадокса задачи о днях рождения, суть которого такова: если в комнате находятся 23 человека, ве- роятность того, что два из них родились в один и тот же день, превышает 50%. Это на удивление высокая вероятность, учитывая то, что в году может быть 365 разных дней рождения. Итак, что же такое атака, в основе которой лежит парадокс задачи о днях рождения (birthday attack)? Это тип атаки, основанный на том факте, что одинаковые значения, называемые также коллизиями (collisions) , появляют- ся намного быстрее, чем можно было ожидать. Представьте себе систему финансовых транзакций, в которой для обеспечения безопасности каждой транзакции применяется новый 64-битовый ключ аутентификации. (Для про- стоты будем предполагать, что шифрование не используется.) Существует 2 64 возможных значения ключа (это больше, чем 18 · 10 18 , т.е. 18 миллиардов 3.6. Типы атак 53 миллиардов), поэтому взломать такую систему на первый взгляд довольно сложно, не правда ли? Отнюдь нет! Отследив около 2 32 транзакций, зло- умышленник может предположить, что две из них используют один и тот же ключ. Предположим, что первое сообщение, передаваемое в ходе каж- дой транзакции, всегда одно и то же: “Готовы ли вы принять транзакцию?” Если две транзакции используют один и тот же ключ аутентификации, то- гда значения MAC первых сообщений этих транзакций будут совпадать, что легко отследит злоумышленник. Зная, что обе транзакции используют один и тот же ключ аутентификации, он сможет вставлять сообщения из более старой транзакции в более новую транзакцию во время выполнения послед- ней. Поскольку ложные сообщения успешно пройдут аутентификацию, они будут приняты, что является очевидным взломом системы финансовых тран- закций. В общем случае, если элемент может принимать N различных значений, ожидать первой коллизии можно после случайного выбора приблизительно √ N элементов. Не вдаваясь в подробности, можно сказать, что значение √ N достаточно близко к истинному. Для парадокса задачи о днях рождения N = 365 и √ N ≈ 19 . На самом деле количество людей, при котором ве- роятность совпадения дней рождения превышает 50%, равно 23, однако для наших целей вполне достаточно и приближения √ N . Для большей наглядно- сти рассмотрим следующее. Если случайным образом выбрать k элементов из N , они могут образовать k ( k − 1) / 2 различных пар. Вероятность того, что элементы одной пары совпадут, равна 1 /N . Следовательно, вероятность того, что хотя бы два элемента из k совпадут, равна k ( k − 1) / 2 N . Если k ≈ √ N , эта вероятность приближается к 50% 2 . В большинстве случаев мы будем говорить об n -битовых значениях. По- скольку n -битовый элемент может иметь 2 n возможных значения, необходимо извлечь √ 2 n = 2 n/ 2 элементов множества, чтобы надеяться на возникнове- ние коллизии. Назовем это оценкой 2 n/ 2 или оценкой парадокса задачи о днях рождения (birthday bound) . 3.6.7 Двусторонняя атака Другой разновидностью атак, в основе которых лежит парадокс задачи о днях рождения, являются так называемые двусторонние атаки или атаки “встреча на середине” (meet-in-the-middle attacks) . (В совокупности оба типа атак называются атаками на основе коллизий (collision attacks) .) Этот тип атак более распространен и более результативен. Вместо того чтобы пассивно 2 В действительности это лишь приближенные значения, однако для наших целей их вполне достаточно. |