В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 3. Введение в криптографию ожидать повторения ключа, вы можете построить таблицу ключей, которые выбрали сами. Давайте вернемся к предыдущему примеру о системе финансовых тран- закций, в которой для каждой транзакции используется новый 64-битовый ключ. Используя двустороннюю атаку, злоумышленник может еще более про- двинуться во взломе системы. Для этого он случайным образом выбирает 2 32 различных 64-битовых ключа. По каждому из них он подсчитывает зна- чение MAC для сообщения: “Готовы ли вы принять транзакцию?” Получен- ное значение MAC вместе с соответствующим ключом помещается в таблицу. Затем злоумышленник прослушивает каждую транзакцию и проверяет, не окажется ли значение MAC первого сообщения этой транзакции в его табли- це. Если такая транзакция находится, значит, с высокой долей вероятности ее ключом аутентификации является тот самый ключ, который был сгене- рирован злоумышленником и помещен в таблицу вместе с соответствующим значением MAC. Теперь, когда злоумышленник обладает ключом аутентифи- кации транзакции, он может вставлять в нее собственные сообщения с лю- бым нужным ему текстом. (Напомним, что предыдущий тип атаки позволял злоумышленнику вставлять только сообщения, взятые из более старой тран- закции.) Сколько транзакций придется прослушать злоумышленнику? Он подсчи- тал значения MAC для 2 32 из всех возможных ключей. По этой причине каж- дый раз, когда система выбирает ключ, он с вероятностью 1 к 2 32 окажется в таблице злоумышленника, а следовательно, после 2 32 транзакций злоумыш- ленник может ожидать появление транзакции, использующей ключ из его таблицы. Таким образом, злоумышленнику придется проделать 2 32 предва- рительных подсчета и прослушать 2 32 транзакции. Это намного меньше, чем перебирать все 2 64 возможных ключа. Различие между атакой, в основе которой лежит парадокс задачи о днях рождения, и двусторонней атакой состоит в следующем. В первом случае мы ждем, когда одно и то же значение появится дважды в одном множестве элементов. В двусторонней атаке у нас есть два множества элементов, и мы ждем, когда эти множества пересекутся. И в том и в другом случае ожидать первого результата можно примерно через одинаковое количество элементов. Двусторонняя атака является более гибкой, чем атака, в основе которой лежит парадокс задачи о днях рождения. Давайте рассмотрим суть двусто- ронней атаки в более абстрактной форме. Предположим, что элементы обоих множеств могут принимать N возможных значений. Пусть в первом множе- стве содержится P элементов, а во втором — Q элементов. Из них можно обра- зовать P Q различных пар, в которых один элемент будет принадлежать пер- вому множеству, а другой — второму множеству. Для каждой пары вероят- ность того, что значения ее элементов совпадут, равна 1 /N . Мы можем ожи- 3.7. Уровень безопасности 55 дать возникновения коллизии, когда значение P Q/N приближается к еди- нице. В этом случае наиболее эффективным выбором будет P ≈ Q ≈ √ N . Как видите, мы вновь получили оценку парадокса задачи о днях рождения. Отметим, что двусторонняя атака обладает определенной гибкостью в отно- шении выбора P и Q . Иногда элементы одного множества легче получить, чем элементы второго, поэтому размер множеств может быть и неодинаков. Единственным требованием является соблюдение условия P Q ≈ N . Мы мо- жем выбрать P ≈ N 1 / 3 , а Q ≈ N 2 / 3 . В приведенном выше примере злоумыш- ленник может составить таблицу из 2 40 значений MAC и ожидать первого совпадения уже после 2 24 прослушанных транзакций. Проводя теоретический анализ того, насколько легко взломать систему, мы часто принимаем размер обоих множеств равным √ N , поскольку это минимизирует количество шагов, которые должен предпринять злоумыш- ленник. На практике необходимо анализировать, насколько элементы одного множества труднее получить, чем элементы другого. Проводя двустороннюю атаку в реальной жизни, величины P и Q следует выбирать таким образом, чтобы удовлетворить условие P Q ≈ N при наименьших возможных затратах. 3.6.8 Другие типы атак До сих пор в основном речь шла об атаках на функции шифрования. Ана- логичным образом можно определить атаки на другие криптографические функции, такие, как аутентификация, цифровые подписи и т.п. Они будут рассматриваться по мере необходимости. 3.7 Уровень безопасности Теоретически, приложив достаточно усилий, злоумышленник может взло- мать любую криптографическую систему. Вопрос заключается в том, сколько работы ему необходимо проделать. Чтобы получить количественную оценку нагрузки на злоумышленника, атаку можно сравнить с поиском, выполняе- мым путем полного перебора вариантов. Если для осуществления атаки необ- ходимо проделать 2 235 шагов, это эквивалентно полному перебору вариантов для 235-битового значения. Много раз отмечая, что злоумышленнику необходимо проделать опреде- ленное количество шагов, мы до сих пор не уточнили, что же такое шаг. Это продиктовано не только свойственной нам — чего греха таить — ленью, но и стремлением упростить анализ. Если речь идет о попытке взлома функции шифрования, одним шагом можно считать одну процедуру шифрования за- данного сообщения с заданным ключом. Иногда шаг атаки включает в себя всего лишь одно обращение к таблице. Все зависит от конкретной ситуации. |