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

В мире криптографии ничто не является тем, чем кажется. К примеру, можно предположить, что для взлома профиля сообщения, состоящего из m разрядов, потребуется порядка 2m операций. На самом деле часто достаточно 2m/2 операций, если использовать атаку «дней рождения» (birthday attack). Впервые она была описана в уже ставшей классикой работе Юваля (Yuval, «How to Swindle Rabin», 1979).

Как уже упоминалось в разделе, посвященном службе DNS, атака «дней рождения» основана на том, что если имеется отображение n входных значений (людей, сообщений и т.д.) на k возможных выходных значений (дней рождения, профилей сообщения и т.д.), то имеется n(n – 1)/2 входных пар. Если n(n – 1)/2 > k, то довольно высока вероятность получения хотя бы одного совпадения. Таким образом, вероятность существования двух сообщений с одинаковыми профилями велика уже при n > √k. Это означает, что 64-разрядный профиль сообщения вполне возможно взломать, перебрав 232 сообщений и отыскав два разных сообщения с одинаковым профилем.

Разберем практический пример. На кафедре вычислительной техники государственного университета появилась вакансия. На нее претендуют два кандидата, Том и Дик. Том работает в университете на два года дольше Дика, поэтому его кандидатура рассматривается первой. Если он получит эту должность, значит, Дику не повезло. Том знает, что заведующая кафедрой Мэрилин высоко ценит его работу, поэтому просит ее написать для него рекомендательное письмо декану факультета, который будет принимать решение. После отправки все письма становятся конфиденциальными.

Мэрилин просит своего секретаря Элен написать это письмо и дает ей примерное содержание. Когда письмо готово, Мэрилин просматривает его, вычисляет и подписывает его 64-разрядный профиль и отсылает этот подписанный профиль декану. Позже Элен должна отправить само письмо электронной почтой.

К несчастью для Тома, у Элен роман с Диком, и она хочет подставить Тома. Поэтому она пишет следующее письмо с 32 вариантами в квадратных скобках.

Уважаемый господин декан,

Это [письмо | обращение] отражает мое [искреннее | откровенное] мнение о проф. Томе Уилсоне, являющемся [кандидатом | претендентом] на профессорскую должность [в настоящее время | в этом году]. Я [знакома | работала] с проф. Уилсоном в течение [почти | около] шести лет. Он является [выдающимся | блестящим] исследователем, обладающим [большим талантом | большими возможностями] и известным [во всем мире | не только в нашей стране] своим [серьезным | созидательным] подходом к [большому числу | широкому спектру] [сложных | перспективных] вопросов.

Он также является [высоко | весьма] [уважаемым | ценимым] [преподавателем | педагогом]. Его студенты дают его [занятиям | лекциям] [самые высокие | высочайшие] оценки. Он самый [популярный | любимый] [преподаватель | учитель] [нашей кафедры | нашего университета].

[Кроме | Помимо] того, [гранты | контракты] проф. Уилсона [существенно | значительно] пополнили [фонды | финансовые запасы] нашей кафедры. Эти [денежные | финансовые] средства [позволили нам | дали возможность] [выполнить | осуществить] [много | ряд] [важных | специальных] программ, [таких как | среди которых] государственная программа 2025 года. Без этих средств было бы невозможным продолжение этой программы, такой [важной | значительной] для нас. Я настойчиво рекомендую вам предоставить ему эту должность.

К несчастью для Тома, закончив печатать это письмо, Элен тут же принимается за второе:

Уважаемый господин декан,

Это [письмо | обращение] отражает мое [искреннее | откровенное] [мнение | суждение] о проф. Томе Уилсоне, являющемся [кандидатом | претендентом] на профессорскую должность в [настоящее время | этом году]. Я [знакома | работала] с проф. Уилсоном в течение [почти | около] шести лет. Он является [слабым | недостаточно талантливым] [исследователем | ученым], почти неизвестным в той области науки, которой он занимается. В его работах практически не заметно понимания [ключевых | главных] [проблем | вопросов] современности.

[Более | Кроме] того, он также не является сколько-нибудь [уважаемым | ценимым] [преподавателем | педагогом]. Его студенты дают его [занятиям | лекциям] [самые низкие | негативные] оценки. Он самый непопулярный [преподаватель | учитель] нашей кафедры, [славящийся | печально известный] своей [привычкой | склонностью] [высмеивать | ставить в неудобное положение] студентов, осмелившихся задавать вопросы на его [лекциях | занятиях].

[Кроме | Помимо] того, [гранты | контракты] проф. Уилсона [почти | практически] не пополняют [фондов | финансовых запасов] нашей кафедры. Если не удастся быстро найти новый источник финансирования, [мы будем вынуждены | нам придется] [закрыть | прекратить] [много | ряд] [важных | специальных] программ, [таких как | среди которых] государственная программа 2025 года. К сожалению, при таких [условиях | обстоятельствах] я не могу [предлагать | рекомендовать] его вам на эту должность.

Затем Элен программирует свой компьютер на подсчет 232 профилей сообщения для каждого варианта обоих писем; вычисления занимают всю ночь. Есть шанс, что один профиль первого письма совпадет с одним из профилей второго письма. В противном случае Элен может добавить еще несколько вариантов слов и выражений в каждое письмо и попытаться еще раз вычислить профили за выходные. Предположим, она нашла совпадение. Назовем положительный отзыв письмом A, а отрицательный — письмом B.

Элен отправляет письмо A по электронной почте Мэрилин на утверждение. Содержание письма B она сохраняет в тайне, никому его не показывая. Естественно, Мэрилин утверждает письмо, вычисляет 64-разрядный профиль сообщения, подписывает профиль и отсылает его декану. Независимо от нее, Элен отправляет декану письмо B (вместо письма A, которое нужно отправить на самом деле).

Получив письмо и подписанный профиль, декан запускает алгоритм вычисления профиля сообщений для письма B, видит, что его профиль совпадает с тем, что ему прислала Мэрилин, и увольняет Тома. Он не догадывается, что Элен удалось создать два письма с одинаковыми профилями сообщений и отправить ему совсем не тот вариант, который читала и подписала Мэрилин. (Вариант с хэппи-эндом: Элен сообщает Дику о своих проделках. Потрясенный, Дик порывает с ней. Элен в ярости бежит сознаваться во всем Мэрилин. Мэрилин звонит декану. Том получает должность.) При использовании алгоритма SHA-2 подобную атаку шифра достаточно сложно выполнить. Даже если компьютер сможет вычислять по 1 трлн профилей в секунду, потребуется более 32 000 лет, чтобы перебрать по 280 вариантов для обоих писем, и это все равно не даст стопроцентной гарантии совпадения. Конечно, если параллельно запустить 1 млн процессоров, то вместо 32 000 лет потребуется 2 недели.

8.8. Управление открытыми ключами

Криптография с использованием открытых ключей позволяет передавать секретные данные, не обладая открытым ключом заранее, а также создавать электронные подписи сообщений без необходимости в привлечении третьей, доверительной стороны. Наконец, подписанные профили