Атаки на хэш-функции и коды аутентичности.

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

Этот тип атаки, основан на том факте, что одинаковые значения, называемые также коллизиями (collisions), появляются намного быстрее, чем можно было ожидать. В системе финансовых транзакций, в которой для обеспечения безопасности каждой транзакции применяется новый 64-битовый ключ аутентификации. (Для простоты предполагается, что шифрование не используется.) Существует 2⁶⁴ возможных значения ключа (это больше, чем 18·10¹⁸, т.е. 18 миллиардов миллиардов). Отследив около 2³² транзакций, злоумышленник может предположить, что две из них используют один и тот же ключ. Предположим, что сообщение-заголовок, передаваемый в ходе каждой транзакции, всегда одинаково. Если две транзакции используют один и тот же ключ аутентификации, тогда значения MAC первых сообщений этих транзакций будут совпадать, что легко отследит злоумышленник. Зная, что обе транзакции используют один и тот же ключ аутентификации, он сможет вставлять сообщения из более старой транзакции в более новую транзакцию во время выполнения последней. Поскольку ложные сообщения успешно пройдут аутентификацию, они будут приняты, что является очевидным взломом системы финансовых транзакций.

В общем случае, если элемент может принимать N различных значений, ожидать первой коллизии можно после случайного выбора приблизительно элементов. В большинстве случаев мы будем говорят об n-битовых значениях. Поскольку n-битовый элемент может иметь 2ⁿ возможных значения, необходимо извлечь = 2^n/2 элементов множества, чтобы надеяться на возникновение коллизии. Назовем это оценкой 2^n/2 или оценкой парадокса задачи о днях рождения (birthday bound).

Двусторонняя атака

Является разновидностью атак, в основе которых лежит парадокс задачи о днях рождения, носит также название атаки "встреча на середине" (meet-in-the-middle attacks). (В совокупности оба типа атак называются атаками на основе коллизий (collision attacks).) Этот тип атак более распространен и более результативен.

В системе финансовых транзакций, в которой для каждой транзакции используется новый 64-битовый ключ, используя двустороннюю атаку, злоумышленник может еще более продвинуться во взломе системы. Для этого он случайным образом выбирает 2³² различных 64-битовых ключа. По каждому из них он подсчитывает значение MAC для сообщения-заголовка. Полученное значение MAC вместе с соответствующим ключом помещается в таблицу. Затем злоумышленник прослушивает каждую транзакцию и проверяет, не окажется ли значение MAC первого сообщения этой транзакции в его таблице. Если такая транзакция находится, значит, с высокой долей вероятности ее ключом аутентификации является тот самый ключ, который был сгенерирован злоумышленником и помещен в таблицу вместе с соответствующим значением MAC. Теперь, когда злоумышленник обладает ключом аутентификации транзакции, он может вставлять в нее собственные сообщения с любым нужным ему текстом. (Предыдущий тип атаки позволял злоумышленнику вставлять только сообщения, взятые из более старой транзакции.)

После 2³² транзакций злоумышленник может ожидать появление транзакции, использующей ключ из его таблицы. Таким образом, злоумышленнику придется проделать 2³² предварительных подсчета и прослушать 2³² транзакции. Это намного меньше, чем перебирать все 2⁶⁴ возможных ключа.

Различие между атакой, в основе которой лежит парадокс задачи о днях рождения, и двусторонней атакой состоит в следующем. В первом случае мы ждем, когда одно и то же значение появится дважды в одном множестве элементов. В двусторонней атаке у нас есть два множества элементов, и мы ждем, когда эти множества пересекутся. И в том и в другом случае ожидать первого результата можно примерно через одинаковое количество элементов.

Двусторонняя атака является более гибкой, чем атака, в основе которой лежит парадокс задачи о днях рождения. Предположим, что элементы обоих множеств могут принимать JV возможных значений. Пусть в первом множестве содержится Р элементов, а во втором - Q элементов. Из них можно образовать PQ различных пар, в которых один элемент будет принадлежать первому множеству, а другой — второму множеству. Для каждой пары вероятность того, что значения ее элементов совпадут, равна 1/N. Мы можем ожидать возникновения коллизии, когда значение PQ/N приближается к единице. В этом случае наиболее эффективным выбором будет Р @ Q @ N. Отметим, что двусторонняя атака обладает определенной гибкостью в отношении выбора Р и Q. Иногда элементы одного множества легче получить, чем элементы второго, поэтому размер множеств может быть и неодинаков. Единственным требованием является соблюдение условия PQ @ N. Мы можем выбрать Р @ N¹/³, a Q @ N²/³. В приведенном выше примере злоумышленник может составить таблицу из 2⁴⁰ значений MAC и ожидать первого совпадения уже после 2²⁴ прослушанных транзакций.