Компьютерные сети. 6-е изд.

8.7. Цифровые подписи

Подлинность документов (юридических, финансовых и др.) определяется наличием или отсутствием авторизованной собственноручной подписи (фотокопии не в счет). Чтобы компьютерные системы обмена сообщениями могли заменить пересылку бумажных документов, необходимо решить проблему подписи, исключив возможность подделки.

Задача разработки замены для подписи от руки довольно сложна. По сути, требуется система, с помощью которой одна сторона может отправить другой стороне подписанное сообщение, при этом:

1. Получатель может проверить заявленную личность отправителя.

2. Позднее отправитель не может отрицать содержание отправленного сообщения.

3. Получатель не имеет возможности изменить сообщение.

Первое требование имеет большое значение, к примеру, для финансовых систем. Когда компьютер клиента передает компьютеру банка заказ на покупку тонны золота, тот должен быть уверен, что устройство, с которого пришел запрос, действительно принадлежит данному клиенту, прежде чем снимать деньги с его счета. Другими словами, банк должен аутентифицировать клиента (и наоборот).

Соблюдение второго условия требуется для защиты банка от мошенничества. Предположим, что банк покупает заказанную тонну золота, после чего цена на этот металл резко падает. Недобросовестный клиент может подать на банк в суд, заявляя, что никогда не заказывал покупку. Банк может предъявить суду письмо с заказом, но клиент будет отрицать его подлинность. Свойство, при котором стороны не могут отрицать факт подписания контракта, называется неотказуемостью (nonrepudiation). Схемы цифровых подписей, которые мы изучим далее, помогают ее обеспечить.

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

8.7.1. Подписи с симметричным ключом

Один из методов реализации цифровых подписей состоит в создании центрального авторитетного органа, которому все доверяют, назовем его Большим Братом (Big Brother, BB). Каждый пользователь выбирает секретный ключ и лично относит его в его офис. Таким образом, к примеру, секретный ключ Алисы KA известен только ей самой и BB. Если вы забудете, что значит какой-либо символ или подстрочный индекс, вы всегда можете свериться с илл. 8.20. Здесь описаны самые важные обозначения, используемые в этом и последующих разделах.

Обозначение

Описание

A

Алиса (отправитель)

B

Банковский менеджер Боб (получатель)

P

Открытый текст сообщения, которое хочет отправить Алиса

BB

Большой Брат (авторитетный центральный орган)

t

Временная метка (для подтверждения новизны)

RA

Случайное число, выбранное Алисой

Симметричный ключ

KA

Секретный ключ Алисы (аналогично и в случае KB, KBB и т.д.)

KA(M)

Сообщение M шифруется/дешифруется с помощью секретного ключа Алисы

Асимметричные ключи

DA

Закрытый ключ Алисы (аналогично и в случае DB и т.д.)

EA

Открытый ключ Алисы (аналогично и в случае EB и т.д.)

DA(M)

Сообщение M шифруется/дешифруется с помощью закрытого ключа Алисы

EA(M)

Сообщение M шифруется/дешифруется с помощью открытого ключа Алисы

Профиль сообщения

MD(P)

Профиль сообщения для открытого текста P

Илл. 8.20. Алиса хочет отправить сообщение своему банковскому менеджеру: расшифровка ключей и символов

Чтобы отправить своему банковскому менеджеру Бобу подписанное незашифрованное сообщение P, Алиса формирует сообщение KA(B, RA, t, P), зашифрованное ее ключом KA (B — идентификатор Боба, RA — случайное число, выбранное Алисой, t — временная метка для подтверждения новизны сообщения). Затем она отсылает его BB (илл. 8.21). BB видит, что это сообщение от Алисы, расшифровывает его и передает Бобу. Сообщение для Боба содержит открытый текст сообщения Алисы KBB(A, t, P) и подпись BB. Получив его, Боб может выполнять заказ Алисы.

Илл. 8.21. Цифровая подпись BB

Что случится, если позже Алиса будет отрицать отправку этого сообщения? Прежде всего, все подают друг на друга в суд (по крайней мере, в США). В суде Алиса решительно утверждает, что она не отправляла Бобу спорное сообщение. Судья спрашивает Боба, почему он уверен, что данное сообщение пришло именно от Алисы, а не от Труди. Сначала Боб заявляет, что BB не принял бы сообщение от Алисы, если бы оно не было зашифровано ее ключом KA. У Труди просто нет возможности отправить фальшивое сообщение от имени Алисы — Боб сразу бы это обнаружил.

Затем Боб театрально демонстрирует суду вещественное доказательство A: KBB(A, t, P). Боб говорит, что это сообщение подписано BB, а значит, Алиса является источником сообщения P. Судья просит BB (которому все доверяют) проверить подпись под этим сообщением. Когда BB подтверждает, что Боб говорит правду, судья решает дело в пользу Боба. Дело закрыто.

Теоретически проблема с протоколом цифровых подписей, показанным на илл. 8.21, может возникнуть, если Труди повторно воспроизведет любое из сообщений. Чтобы свести к минимуму такую вероятность, используются временные метки. Кроме того, Боб может просмотреть все недавние письма и проверить, не встречалось ли в них такое же RA. При повторе RA сообщение считается дубликатом и отбрасывается. Очень старые (исходя из временной метки) письма также игнорируются. Для защиты от атаки мгновенного повторного воспроизведения Боб просто проверяет значение числа RA в каждом входящем сообщении, сверяя его со всеми RA, полученными за последний час. Если в течение часа такое значение не приходило, Боб может быть уверен, что полученное сообщение является новым запросом.

8.7.2. Подписи с открытым ключом

Главная проблема создания цифровых подписей с помощью шифрования с симметричным ключом — все должны согласиться доверять BB. Помимо этого, BB получает возможность читать подписываемые им сообщения. Самыми логичными кандидатами на управление сервером BB являются правительство, банки или нотариальные бюро. Однако им доверяют не все граждане. Было бы здорово, если бы для получения подписи на электронном документе не требовался какой-либо доверенный полномочный орган.

К счастью, здесь нам поможет шифрование с открытым ключом. Предположим, такие алгоритмы шифрования и дешифрования, помимо обычного свойства D(E(P)) = P, обладают свойством E(D(P)) = P. Например, оно есть у алгоритма RSA, так что это предположение вполне обоснованно. В этом случае Алиса может отправить Бобу подписанное открытое сообщение P, переслав ему EB(DA(P)). Обратите внимание, что она знает свой собственный (закрытый) ключ дешифрования DA, так же как и открытый ключ Боба EB, поэтому сформировать такое сообщение ей по силам.

Приняв сообщение, Боб расшифровывает его как обычно, используя свой закрытый ключ DB, что в результате дает DA(P), как показано на илл. 8.22. Он сохраняет зашифрованный текст в надежном месте, после чего декодирует его открытым ключом шифрования Алисы EA, получая открытый текст.

Чтобы понять, как в данном случае работает цифровая подпись, предположим, что впоследствии Алиса отрицает отправку Бобу сообщения P. Когда дело доходит до суда, Боб предъявляет P и DA(P). Судья легко может убедиться, что у Боба есть подлинное сообщение, зашифрованное ключом DA, просто применив к нему ключ EA. Боб не знает закрытого ключа Алисы, следовательно, получить зашифрованное этим ключом сообщение он мог только от нее. Сидя в тюрьме за лжесвидетельство и мошенничество, Алиса сможет заняться разработкой новых интересных алгоритмов с открытым ключом.

Илл. 8.22. Цифровая подпись, полученная при помощи шифрования с открытым ключом

Хотя схема шифрования с открытым ключом довольно элегантна, у нее есть серьезные недостатки. Правда, они скорее связаны не с самим алгоритмом, а со средой, в которой он работает. Прежде всего, Боб может доказать, что сообщение было отправлено Алисой, только пока ключ DA хранится в тайне. Если Алиса раскроет свой секретный ключ, этот аргумент потеряет актуальность, так как в этом случае нельзя определить источник сообщения (им может быть кто угодно, включая самого Боба).

Например, проблема может возникнуть, если Боб является биржевым брокером Алисы. Она заказывает ему покупку определенных акций. Сразу после этого их цена резко падает. Чтобы отречься от своего запроса, Алиса сообщает в полицию, что ее дом был обворован, и в том числе украден компьютер вместе с секретным ключом. В зависимости от законов ее страны или штата Алиса может понести (или нет) юридическую ответственность, особенно если она заявляет, что обнаружила проникновение в квартиру, только вернувшись с работы, — через несколько часов после того, как это якобы произошло.

Другая проблема этой схемы цифровой подписи возникает, если Алиса поменяет свой ключ. Это абсолютно законно, более того, рекомендуется периодически менять ключ, чтобы гарантировать его высокую надежность. В этом случае, если дело дойдет до судебного разбирательства, судья попытается применить к подписи DA(P) текущий ключ EA и обнаружит, что в результате сообщение P не получается. При этом Боб будет выглядеть довольно глупо.

В принципе, для цифровых подписей можно использовать любой алгоритм с открытым ключом. Стандартом фактически является RSA. Он применяется во многих программах, предназначенных для обеспечения безопасности. Однако в 1991 году NIST предложил использовать для нового Стандарта цифровой подписи (Digital Signature Standard, DSS) вариант алгоритма с открытым ключом Эль-Гамаля. Он основан не на трудности факторизации больших чисел, а на сложности вычисления дискретных логарифмов.

Как обычно, попытка правительства навязать новые криптографические стандарты вызвала много шума. Стандарт DSS критиковали за то, что он:

1) слишком засекречен (протокол, использующий алгоритм Эль-Гамаля, разрабатывался АНБ);

2) слишком медленный (при проверке подписей он работает в 10–40 раз медленнее алгоритма RSA);

3) слишком новый (алгоритм Эль-Гамаля еще не был тщательно проанализирован);

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 года. Без этих средств было бы невозможным продолжение этой программы, такой [важной | значительной] для нас. Я настойчиво рекомендую вам предоставить ему эту должность.

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

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

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

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

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

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

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

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