4) слишком ненадежен (фиксированная длина ключа — 512 бит).
При последующей переработке четвертый пункт утратил значение, так как было разрешено применять ключи длиной до 1024 бит. Однако первые два пункта актуальны и по сей день.
8.7.3. Профили сообщений
Многие методы цифровых подписей критикуют за то, что в них совмещаются две разные функции: аутентификация и секретность. Чаще всего требуется лишь первая функция. К тому же получить лицензию на экспорт обычно проще, если система обеспечивает только аутентификацию. Ниже описана схема аутентификации, не требующая шифрования всего сообщения.
Она основана на идее необратимой хеш-функции, которая принимает на входе участок открытого текста произвольной длины и по нему вычисляет строку битов фиксированной длины. Эта хеш-функция, которую часто называют профилем сообщения (message digest, MD), обладает четырьмя важными свойствами:
1. На основе заданного сообщения P можно легко вычислить MD(P).
2. На основе MD(P) практически невозможно определить P.
3. Для заданного сообщения P невозможно подобрать сообщение P', для которого будет выполняться равенство MD(Pʹ) = MD(P).
4. Изменение даже одного бита входной последовательности приводит к совершенно другому результату.
Чтобы удовлетворять требованию 3, результат хеш-функции должен обладать длиной по крайней мере 128 бит (а желательно больше). Чтобы соответствовать требованию 4, хеш-функция должна очень сильно искажать входные значения, как и алгоритмы шифрования с симметричным ключом, рассмотренные выше.
Вычислить профиль сообщения по фрагменту открытого текста гораздо быстрее, чем зашифровать все сообщение с помощью алгоритма с открытым ключом. Поэтому профили сообщений могут использоваться для ускорения работы алгоритмов цифровых подписей. Чтобы понять, как это работает, мы вновь обратимся к протоколу цифровой подписи на илл. 8.21. Вместо передачи открытого текста P вместе с KBB(A, t, P) теперь BB вычисляет профиль сообщения MD(P), применяя функцию хеширования MD к открытому тексту P. Затем он помещает KBB(A, t, MD(P)) как пятый элемент в список, зашифрованный ключом KB, и отправляет его Бобу вместо KBB(A, t, P).
В случае возникновения спора Боб может предъявить на суде как открытый текст P, так и KBB(A, t, MD(P)). По просьбе судьи BB расшифровывает KBB(A, t, MD(P)). В результате суду также предъявляется цифровая подпись MD(P), подлинность которой гарантируется BB, и сам открытый текст P, подлинность которого суд должен выяснить. Поскольку создать другой открытый текст, соответствующий данной цифровой подписи, практически невозможно, суд убеждается в том, что Боб говорит правду. Использование профиля сообщения экономит время шифрования и затраты на транспортировку и хранение.
Профиль сообщения также применяется в системах шифрования с открытым ключом (илл. 8.23). Сначала Алиса вычисляет профиль сообщения для своего открытого текста. Затем она подписывает его и отправляет Бобу вместе с открытым текстом. Если во время передачи Труди подменит открытый текст P, Боб обнаружит это, вычислив MD(P).
Илл. 8.23. Цифровая подпись с использованием профиля сообщения
SHA-1, SHA-2 и SHA-3
Для вычисления профиля сообщения было предложено несколько вариантов функций. Долгое время в качестве такой функции широко использовался алгоритм SHA-1 (Secure Hash Algorithm 1 — защищенный алгоритм хеширования 1) (NIST, 1993). Прежде всего стоит отметить, что он был взломан в 2017 году и теперь постепенно выводится из эксплуатации в большинстве систем, о чем будет подробно рассказано чуть позже. Как и все профили сообщения, этот алгоритм достаточно сложным образом перемешивает входные биты, и в результате каждый выходной бит зависит от каждого входного. Алгоритм SHA-1 был разработан АНБ и получил благословение NIST (в виде федерального стандарта FIPS 180-1). Он обрабатывает входные данные блоками по 512 бит и формирует профиль сообщения длиной 160 бит. Типичный случай отправки Алисой несекретного, но подписанного сообщения Бобу показан на илл. 8.24. Открытый текст обрабатывается алгоритмом SHA-1, на выходе получается 160-битный хеш SHA-1. Затем Алиса подписывает его закрытым ключом RSA и отправляет вместе с открытым текстом Бобу.
Илл. 8.24. Применение SHA-1 и RSA для создания подписей несекретных сообщений
При получении сообщения Боб сам вычисляет хеш-функцию с помощью SHA-1 и применяет открытый ключ Алисы к подписанному хешу, чтобы получить исходный хеш H. Если они совпадают, сообщение считается корректным. Поскольку Труди не может перехватить сообщение и изменить его так, чтобы значение H совпадало с контрольным, Боб легко узнает обо всех подменах, которые она совершила. Для сообщений, чья целостность важна, а секретность не имеет значения, часто применяется схема, показанная на илл. 8.24. При относительно небольших вычислительных затратах она гарантирует, что все изменения, внесенные на пути следования сообщения, будут с высокой степенью вероятности выявлены.
В настоящее время идет работа над новыми версиями SHA-1 с 224-, 256-, 384- и 512-разрядными значениями хеш-функций. Вместе они называются SHA-2. Помимо увеличения длины хешей, в этих версиях также была изменена функция для вычисления профиля, что позволило избавиться от потенциальных уязвимостей версии SHA-1 (а они были достаточно серьезными). В 2017 году SHA-1 был взломан специалистами Google и амстердамского исследовательского центра CWI. Точнее, им удалось сгенерировать коллизии хеш-функций (hash collisions), что нивелирует защиту алгоритма SHA-1. Как и следовало ожидать, результатом этой атаки стало существенное возрастание интереса к SHA-2.
В 2006 году NIST организовал конкурс с целью создания нового стандарта хеш-функции, теперь известного как SHA-3. Это соревнование было завершено в 2012 году, а три года спустя был опубликован новый стандарт SHA-3 («Keccak»). Что интересно, NIST не предлагает сразу же отказаться от алгоритма SHA-2 в пользу SHA-3, поскольку случаев успешного взлома SHA-2 еще не зафиксировано. Но даже несмотря на это, полезно на всякий случай иметь под рукой запасной вариант.
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 года. Без этих средств было бы невозможным продолжение этой программы, такой [важной | значительной] для нас. Я настойчиво рекомендую вам предоставить ему эту должность.
К несчастью для Тома, закончив печатать это письмо, Элен тут же принимается за второе:
Уважаемый господин декан,
Это [письмо | обращение] отражает мое [искреннее | откровенное] [мнение | суждение] о проф. Томе Уилсоне, являющемся [кандидатом | претендентом] на профессорскую должность в [настоящее время | этом году]. Я [знакома | работала] с проф. Уилсоном в течение [почти | около] шести лет. Он является [слабым | недостаточно талантливым] [исследователем | ученым], почти неизвестным в той области науки, которой он занимается. В его работах практически не заметно понимания [ключевых | главных] [проблем | вопросов] современности.