В более общем случае, если имеется некое соответствие между n входами (людьми, сообщениями и т. д.) и k возможными выходами (днями рождения, профилями сообщений и т. д.), мы имеем
входных пар. Если
то вероятность
того, что будет хотя бы одно совпадение выхода при различных входах, довольно велика. Таким образом, вероятность существования двух сообщений с одинаковыми профилями велика уже при
Это означает, что 64-разрядный профиль сообще
ния можно с большой вероятностью взломать (то есть найти два различных сообщения с одинаковым профилем), перебрав 232 сообщений.
Рассмотрим практический пример. На кафедре компьютерных наук Государственного университета появились вакансия и два кандидата на эту должность, Том и Дик. Том работает на факультете на два года дольше Дика, поэтому его кандидатура будет рассматриваться первой. Если он получит эту должность, значит, Дику не повезло. Том знает, что заведующая кафедрой Мэрилин высоко ценит его работу, поэтому он просит ее написать для него рекомендательное письмо декану факультета, который будет решать дело Тома. После отправки все письма становятся конфиденциальными.
Мэрилин просит написать это письмо декану своего секретаря Элен, подчеркивая, что она хотела бы видеть в этом письме. Когда письмо готово, Мэрилин просматривает его, вычисляет и подписывает 64-разрядный профиль письма и посылает этот подписанный профиль декану. Позднее Элен может послать само письмо электронной почтой.
К несчастью для Тома, у Элен роман с Диком, и она хочет обмануть Тома. Поэтому она пишет следующее письмо с 32 вариантами в квадратных скобках.
Уважаемый господин декан,
Это [письмо | обращение] отражает мое [искреннее | откровенное] мнение о проф. Томе Уилсоне, являющемся [кандидатом | претендентом] на профессорскую должность [в настоящее время | в этом году]. Я [знакома | работала] с проф. Уилсоном в течение [почти | около] шести лет. Он является [выдающимся | блестящим] исследователем, обладающим [большим талантом | большими возможностями] и известным
[во всем мире | не только в нашей стране] своим [серьезным | созидательным] подходом к [большому числу I широкому спектру] [сложных | перспективных] вопросов.
Он также является [высоко | весьма] [уважаемым | ценимым] [преподавателем | педагогом]. Его студенты дают его [занятиям | лекциям] [самые высокие | высочайшие] оценки. Он самый [популярный | любимый] [преподаватель | учитель] [нашей кафедры I нашего Университета].
[Кроме I Помимо] того, [гранты | контракты] проф. Уилсона [существенно | значительно] пополнили [фонды | финансовые запасы] нашей кафедры. Эти [денежные | финансовые] средства [позволили нам | дали возможность] [выполнить | осуществить] [много |ряд] [важных | специальных] программ, [такихкак | среди которых], государственная программа 2000 года. Без этих средств было бы невозможным продолжение этой программы, такой [важной | значительной] для нас. Я настойчиво рекомендую вам предоставить ему эту должность.
К несчастью для Тома, закончив печатать это письмо, Элен тут же принимается за второе:
Уважаемый господин декан,
Это [письмо | обращение] отражает мое [искреннее | откровенное] [мнение | суждение] о проф. Томе Уилсоне, являющемся [кандидатом | претендентом] на профессорскую должность в [настоящее время | этом году]. Я [знакома |работала] с проф. Уилсоном в течение [почти | около] шести лет. Он является [слабым | недостаточно талантливым] [исследователем | ученым], почти не известным в той области науки, которой он занимается. В его работах практически не заметно понимания [ключевых | главных] [проблем | вопросов] современности.
[Более | Кроме] того, он также не является сколько-нибудь [уважаемым | ценимым] [преподавателем | педагогом]. Его студенты дают его [занятиям | лекциям] [самые низкие | негативные] оценки. Он самый непопулярный [преподаватель | учитель] нашей кафедры, [славящийся | печально известный] своей [привычкой | склонностью] [высмеивать | ставить в неудобное положение] студентов, осмелившихся задавать вопросы на его [лекциях | занятиях].
[Кроме | Помимо] того, [гранты | контракты] проф. Уилсона [почти | практически] не пополняют [фондов | финансовых запасов] нашей кафедры. Если не удастся быстро найти новый источник финансирования, [мы будем вынуждены | нам придется] [закрыть | прекратить] [много |ряд] [важных | специальных] программ, [такихкак | среди которых] государственная программа 2000 года. К сожалению, при таких [условиях | обстоятельствах] я не могу [предлагать | рекомендовать] его вам на эту должность.
Затем Элен заставляет свой компьютер сосчитать 232 профиля сообщения для каждого варианта обоих писем, что занимает всю ночь. Есть шансы, что один профиль первого письма совпадет с одним из профилей второго письма. Если нет, она может добавить еще несколько вариантов слов и выражений в каждое письмо и попытаться еще раз за выходные. Предположим, что ей удалось найти такое совпадение. Назовем положительный отзыв письмом A, а отрицательный — письмом B.
Элен отправляет письмо A электронной почтой Мэрилин на утверждение. Мэрилин, конечно, утверждает письмо, вычисляет 64-разрядный профиль сообщения, подписывает профиль и посылает по почте подписанный профиль декану. Независимо Элен посылает декану письмо B (вместо письма A, которое следует отправить на самом деле).
Получив письмо и подписанный профиль, декан запускает алгоритм вычисления профиля сообщений для письма B, видит, что его профиль совпадает с тем, что ему прислала Мэрилин, и увольняет Тома. Он даже не может себе представить, что Элен удалось создать два письма с одинаковыми профилями сообщений и отправить ему совсем не тот вариант, который читала и подписала Мэрилин. (Вариант с хэппи-эндом: Элен сообщает Дику о своих проделках. Потрясенный, Дик порывает с ней. Элен в ярости бежит сознаваться во всем Мэрилин. Мэрилин звонит декану. В конце концов, Том получает профессуру.) При использовании алгоритма SHA-1 подобная атака шифра является достаточно трудной для исполнения, так как даже если компьютер сможет вычислять по 1 трлн профилей в секунду, потребуется более 32 00 лет, чтобы перебрать по 280 варианта для обоих писем, что все равно не даст 100%-й гарантии совпадения. Конечно, если заставить параллельно работать 1 млн, вместо 32 000 лет потребуется 2 недели.
8.5. Управление открытыми ключами
Криптография с использованием открытых ключей позволяет передавать секретные данные, не обладая общим ключом заранее, а также создавать электронные подписи сообщений без необходимости привлечения третьей, доверительной стороны. Наконец, подписанные профили сообщений позволяют получателю легко и надежно проверять целостность и аутентичность полученных данных.
Однако мы как-то слишком ловко обошли один вопрос: если Алиса и Боб друг друга не знают, как они смогут обменяться открытыми ключами перед началом общения? Вот, казалось бы, очевидное решение: выложить открытый ключ на веб-сайте. Однако так делать нельзя, и вот почему: представим себе, что Алиса хочет найти открытый ключ Боба на его веб-сайте. Каким образом она это делает? Набирает URL сайта. Браузер ищет DNS-адрес домашней страницы Боба и посылает запрос GET, как показано на рис. 8.20. К сожалению, Труди в этот момент перехватывает запрос и посылает Алисе фальшивую страницу. В качестве таковой может выступать, к примеру, копия страницы Боба, на которой вместо его открытого ключа выложен открытый ключ Труди. После того как Алиса зашифрует свое первое сообщение с помощью ET, Труди расшифрует его, прочтет, зашифрует с помощью открытого ключа Боба и перешлет сообщение Бобу, который даже не подозревает обо всех этих перипетиях. Но гораздо хуже то, что Труди может изменять сообщения перед повторным шифрованием и отправкой Бобу. Очевидно, нужен некий механизм секретного обмена открытыми ключами.
