Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С

• Название: Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
• Дата: 29.04.2022
• Размер: 3.25 Mb.
• Имя файла: Shnayer_Prikladnaya-kriptografiya.352928.pdf
• Тип: Протокол; #504484
• страница: 8 из 78

Боба и Алисы и шифруется ключом, общим для Трента и Алисы. Второе состоит из имени Алисы, сл у- чайного сеансового ключа и шифруется ключом, общим для Трента и Боба. Трент посылает оба сообщ е- ния Алисе:
E
A
(B, K, R
A
, R
B
), E
B
(A, K)
(4) Алиса расшифровывает первое сообщение, извлекает K и убеждается, что R
A
совпадает со значением, от- правленным на этапе (1). Алиса посылает Бобу два сообщения. Одним является сообщение Трента, за- шифрованное ключом Боба. Второе - это R
B
, зашифрованное сеансовым ключом.
E
B
(A, K), E
K
(R
B
),
(5) Боб расшифровывает первое сообщение, извлекает K и убеждается, что R
B
совпадает с отправленным на этапе (2).
В результате Алиса и Боб убеждены, что они общаются именно друг с другом, а не с третьей стороной . Но- вовведение состоит в том, что именно Боб первым обращается к Тренту, который только посылает одно соо б- щение Алисе.
Needham-Schroeder
В этом протоколе, изобретенном Роджером Неедхэмом (Roger Needham) и Майклом Шредером (Michael
Schroeder) [1159], также используются симметричная криптография и Трент .
(1) Алиса посылает Тренту сообщение, содержащее ее имя, имя Боба и случайное число.
A, B, R
A
(2) Трент генерирует случайный сеансовый ключ. Он шифрует сообщение, содержащее случайный сеансовый ключ и имя Алисы, секретным ключом, общим для него и Боба. Затем он шифрует случайное число Ал и- сы, имя Боба, ключ, и шифрованное сообщение секретным ключом, общим для него и Алисы. Наконец, он отправляет шифрованное сообщение Алисе:
E
A
(R
A
, B, K, E
B
(K, A))
(3) Алиса расшифровывает сообщение и извлекает K. Она убеждается, что R
A
совпадает со значением, от- правленным Тренту на этапе (1). Затем она посылает Бобу сообщение, зашифрованное Трентом ключом
Боба.
E
B
(K, A)
(4) Боб расшифровывает сообщение и извлекает K. Затем он генерирует другое случайное число, R
B
. Он шифрует это число ключом K и отправляет его Алисе.
E
K
(R
B
)

(5) Алиса расшифровывает сообщение с помощью ключа K. Она создает число R
B
-1 и шифрует это число ключом K. Затем она посылает это сообщение обратно Бобу.
E
K
(R
B
-1)
(6) Боб расшифровывает сообщение с помощью ключа K и проверяет значение R
B
-1.
Вся эта возня с R
A
, R
B
, и R
B
-1 служит для предотвращения вскрытия с повторной передачей. При таком способе вскрытия Мэллори может записать старые сообщения и впоследствии использовать их при попытке взломать протокол. Присутствие R
A
на этапе (2) убеждает Алису, что сообщение Трента достоверно и не являе т- ся повторной передачей отклика, использованного при одном из предыдущих применений протокола . Когда
Алиса успешно расшифрует R
B
и передает Бобу R
B
-1 на этапе (5), Боб убеждается, что сообщения Алисы не я в- ляется повторной передачей сообщений, использованных при одном из предыдущих применений протокола .
Главной прорехой этого протокола является важность использованных сеансовых ключей . Если Мэллори получит доступ к старому K, он сможет предпринять успешное вскрытие [461]. Ему нужно только записать со- общения Алисы Бобу на этапе (3). Тогда, имея K, он может выдать себя за Алису:
(1) Мэллори посылает Бобу следующее сообщение:
E
B
(K, A)
(2) Боб извлекает K, генерирует R
B
и отправляет Алисе:
E
K
(R
B
)
(3) Мэллори перехватывает сообщение, расшифровывает его с помощью ключа K и посылает Бобу:
E
K
(R
B
-1)
(4) Боб убеждается, что сообщение "Алисы" состоит из R
B
-1.
Теперь Мэллори убедил Боб, что он и есть "Алиса". Более защищенный протокол, использующий метки времени, может противостоять этому вскрытию [461,456]. Метки времени добавляются к сообщению Трента на этапе (2) и шифруются ключом Боба: E
B
(K, A, T). Метки времени требуют надежной и точной системы единого времени, что само по себе нетривиальная проблема .
Если ключ, общий для Трента и Алисы будет скомпрометирован, последствия будут драматичны . Мэллори сможет использовать его, для получения сеансовых ключей для обмена сообщениями с Бобом (или с кем-нибудь еще). Даже хуже, Мэллори продолжать подобные действия даже после замены ключа Алисы [90].
Неедхэм и Шредер пытались исправить эти проблемы в модифицированной версии своего протокола [1160].
Их новый протокол по существу совпадает с протоколом Отуэя- Риса (Otway-Rees), опубликованном в том же выпуске того же журнала.
Otway-Rees
Этот протокол также использует симметричную криптографию [1224].
(1) Алиса создает сообщение, состоящее из порядкового номера, ее имени, имени Боба и случайного числа.
Сообщение шифруется ключом, общим для Алисы и Трента. Она посылает это сообщение Бобу вместе с порядковым номером, ее и его именами:
I, A, B, E
A
(R
A
, I, A, B)
(2) Боб создает сообщение, состоящее из нового случайного числа, порядкового номера, имени Алисы и им е- ни Боба. Сообщение шифруется ключом, общим для Алисы и Боба. Он посылает это сообщение Тренту вместе шифрованным сообщением Алисы, порядк овым номером, ее и его именами:
I, A, B, E
A
(R
A
, I, A, B), E
B
(R
B
, I, A, B)
(3) Трент генерирует случайный сеансовый ключ. Затем он создает два сообщения. Одно, состоящее из сл у- чайного числа Алисы и сеансового ключа, шифруется ключом, общим для него и Алисы. Другое, состо я- щее из случайного числа Боба и сеансового ключа, шифруется ключом, общим для него и Боба. Он о т- правляет два этих сообщения вместе с порядковым номером Бобу:
I, E
A
(R
A
, K), E
B
(R
B
, K)
(4) Боб отправляет Алисе сообщение, шифрованное ее ключом, и порядковый номер:
I, E
A
(R
A
, K)
(5) Алиса расшифровывает сообщение, получая свои ключ и случайное число. Алиса убеждается, что при в ы- полнении протокола они не изменились Боб отправляет Алисе сообщение, шифрованное ее ключом, и п о-

рядковый номер.
Если все случайные числа правильны, а порядковый номер не изменился при выполнении протокола, Алиса и Боб убеждаются в подлинности друг друга и получают секретный ключ для обмена сообщениями .
Kerberos
Kerberos - вариант протокола Needham-Schroeder - подробно обсуждается в разделе 24.5. В базовом прото- коле Kerberos Version 5 у Алисы и Боба общие ключи с Трентом. Алиса хочет генерировать сеансовый ключ для сеанса связи с Бобом.
(1) Алиса посылает Тренту сообщение со своим именем и именем Боба:
A, B
(2) Трент создает сообщение, состоящее из метки времени, время жизни, L, случайного сеансового ключа и имени Алисы. Он шифрует сообщение ключом, общим для него и Боба. Затем он объединяет метку вр е- мени, время жизни, сеансовый ключ, имя Боба, и шифрует полученное сообщение ключом, общим для н е- го и Алисы. Оба шифрованных сообщения он отправляет Алисе.
E
A
(T, L, K, B), E
B
(T, L, K, A)
(3) Алиса создает сообщение, состоящее из ее имени и метки времени, шифрует его ключом K и отправляет
Бобу. Алиса также посылает Бобу сообщение от Трента, шифрованное ключом Боба:
E
A
(A, T), E
B
(T, L, K, A)
(4) Боб создает сообщение, состоящее из метки времени плюс единица, шифрует его ключом K и отправляет
Алисе:
E
K
(T+1)
Этот протокол работает, но только если часы каждого пользователя синхронизированы с часами Трента . На практике эффект достигается синхронизацией с надежным сервером времени с точностью в несколько минут и обнаружением повторной передачи в течение определенного интервала времени .
Neuman-Stubblebine
Из-за недостатков системы или саботажа синхронизация часов может быть нарушена . Если часы сбиваются,
против большинства протоколов может быть использован определенный способ вскрытия [644]. Если часы от- правителя опережают часы получателя, Мэллори может перехватить сообщение отправителя и повторно и с- пользовать его позднее, когда метка времени станет текущей в месте нахождения получателя . Этот способ, на- зывающийся вскрытием с подавлением повторной передачи, может привести к неприятным последствиям .
Этот протокол, впервые опубликованный в [820] и исправлен в [1162], пытается противостоять вскрытию с подавлением повторной передачи. Этот отличный протокол является улучшением Yahalom.
(1) Алиса объединяет свое имя и случайное число, и отправляет созданное сообщение Бобу.
A, R
A
(2) Боб объединяет имя Алисы, ее случайное число и метку времени, шифрует созданное сообщение общим с
Трентом ключом и посылает его Тренту, добавляя свое имя и новое случайное число:
B, R
B
, E
B
(A, R
A
, T
B
)
(3) Трент генерирует случайный сеансовый ключ. Затем он создает два сообщения. Первое включает имя Б о- ба, случайное число Алисы, случайный сеансовый ключ, метку времени и шифруется ключом, общим для
Трента и Алисы. Второе состоит из имени Алисы, сеансового ключа, метки времени и шифруется ключом,
общим для Трента и Боба. Трент посылает оба сообщения Алисе вместе со случайным числом Боба:
E
A
(B, R
A
, K, T
B
), E
B
(A, K, T
B
), R
B
(4) Алиса расшифровывает сообщение, зашифрованное ее ключом, извлекает K и убеждается, что R
A
совпа- дает со значением, отправленным на этапе (1). Алиса посылает Бобу два сообщения. Одним является с о- общение Трента, зашифрованное ключом Боба. Второе - это R
B
, зашифрованное сеансовым ключом.
E
B
(A, K), E
K
(R
B
),
(5) Боб расшифровывает сообщение, зашифрованное его ключом, извлекает K и убеждается, что значения T
B
и R
B
те же, что и отправленные на этапе (2).
Если оба случайных числа и метка времени совпадают , Алиса и Боб убеждаются в подлинности дуг друга и получают секретный ключ. Синхронизация часов не требуется, так как метка времени определяется только по

часам Боба, и только Боб проверяет созданную им метку времени .
У этого протокола есть еще одно полезное свойство - Алиса может использовать полученное от Трента с о- общение для последующей проверки подлинности Боба в пределах некоторого времени . Предположим, что
Алиса и Боб выполнили приведенный выше протокол, провели и завершили сеанс связи . Алиса и Боб могут повторно проверить подлинность друг друга, не обращаясь к Тренту .
(1) Алиса посылает Бобу сообщение, присланное ей Трентом на этапе (3) и новое случайное число.
E
B
(A, K, T
B
), R'
A
(2) Боб посылает Алисе другое новое случайное число и случайное число, присланное Алисой, шифруя их с е- ансовым ключом связи.
R'
B
, E
K
(R'
A
)
(3) Алиса посылает Бобу его новое случайное число, шифруя его сеансовым ключом связи.
E
K
(R'
B
)
Новые случайные числа защищают от вскрытия с повторно передачей .
DASS
Протоколы Распределенной служба безопасности и проверки подлинности ( Distributed Authentication Secu- rity Service, DASS), созданные в Digital Equipment Corporation, также обеспечивают обоюдную проверку по д- линности и обмен ключами [604, 1519, 1518]. В отличие от предыдущего протокола DASS использует как крип- тографию с открытыми ключами, так и симметричную криптографию . И у Алисы, и у Боба есть свой закрытый ключ. Трент подписывает копии их открытых кл ючей.
(1) Алиса посылает Тренту сообщение, состоящее из имени Боба.
В
(2) Трент посылает Алисе открытый ключ Боба, K
B
, подписанный закрытым ключом Трента, T. Подписанное сообщение содержит имя Боба.
S
T
(B, K
B
)
(3) Алиса проверяет подпись Трента, убеждаясь, что она действительно получила открытый ключ Боба. Она генерирует случайный сеансовый ключ, K, и случайную пару ключей открытый/закрытый, K
p
. Она шиф- рует метку времени ключом K, а затем подписывает время жизни, L, свое имя и своим закрытым ключом,
K
A
. Наконец, она зашифровывает K открытым ключом Боба и подписывает его с помощью K
p
. Все это она отправляет Бобу.
E
K
(T
A
),
S
K
A
(L, A, K
p
),
S
K
p
(
E
K
B
(K))
(4) Боб посылает Тренту (это может быть другой Трент) сообщение, состоящее из имени Алисы.
А
(5) Трент посылает Бобу открытый ключ Алисы, K
А
, подписанный закрытым ключом Трента. Подписанное сообщение содержит имя Алисы.
S
T
(А, K
А
)
(6) Боб проверяет подпись Трента, убеждаясь, что он действительно получила открытый ключ Алисы. Затем он проверяет подпись Алисы и извлекает K
p
. Боб использует свой закрытый ключ, извлекая K. Затем он расшифровывает T
A
, проверяя, что это сообщение - текущее.
(7) Если требуется обоюдная проверка подлинности, Боб шифрует новую метку времени ключом K и посыла- ет ее Алисе.
E
K
(T
В
)
(8) Алиса расшифровывает T
В
ключом K, проверяя, что это сообщение - текущее.
SPX, продукт DEC, основан на DASS. Дополнительную информацию можно найти в [34].
Denning-Sacco
В этом протоколе также используется криптография с открытыми ключами [461]. Трент ведет базу данных,
хранящую открытые ключи всех пользователей .

(1) Алиса посылает Тренту сообщение, состоящее из ее имени и имени Боба.
А, В
(2) Трент посылает Алисе открытый ключ Боба, K
B
, подписанный закрытым ключом Трента, T. Трент также посылает Алисе ее собственный открытый ключ, K
А
, подписанный закрытым ключом Трента.
S
T
(B, K
B
), S
T
(А, K
А
)
(3) Алиса посылает Бобу случайный сеансовый ключ и метку времени, подписав их своим закрытым ключом и зашифровав открытым ключом Боба, вместе с обоими подписанными ключами.
Е
В
(S
А
(K, Т
А
)), S
T
(А, K
А
), S
T
(В, K
В
)
(4) Боб расшифровывает сообщение Алисы с помощью своего закрытого ключа и проверяет подпись Алисы с помощью ее открытого ключа. Он также убеждается, что метка времени правильна.
С этого момента Алиса и Боб получили K и могут провести безопасный сеанс связи. Это выгляди красиво,
но есть одна тонкость - выполнив протокол с Алисой, Боб сможет выдать себя за Алису [5]. Смотрите:
(1) Боб посылает Тренту свое имя и имя Кэрол.
В, С
(2) Трент посылает Бобу подписанные открытые ключи Боба и Кэрол.
S
T
(B, K
B
), S
T
(С, K
С
)
(3) Боб посылает Кэрол подписанный случайный сеансовый ключ и метку времени, ранее полученные от
Алисы, зашифровав их открытым ключом Кэрол, вместе с подтверждением Алисы и подтверждением К э- рол.
Е
С
(S
А
(K, Т
А
)), S
T
(А, K
А
), S
T
(С, K
С
)
(4) Кэрол расшифровывает сообщение Алисы с помощью своего закрытого ключа и проверяет подпись Ал и- сы с помощью ее открытого ключа. Он также убеждается, что метка времени правильна.
Теперь Кэрол считает, что она соединилась с Алисой, Боб успешно одурачил ее . Действительно, Боб сможет дурачить любого пользователя сети, пока не закончится срок действия метки времени . Но это легко можно ис- править. Просто вставьте имена в шифрованное сообщение на этапе (3) :
Е
В
(S
А
(А, В, K, Т
А
)), S
T
(А, K
А
), S
T
(В, K
В
)
Теперь Боб не сможет повторно послать Кэрол старое сообщение, потому что оно явно предназначено для сеанса связи между Алисой и Бобом.
Woo-Lam
В этом протоколе также используется криптография с открытыми ключами [1610, 1611]:
(1) Алиса посылает Тренту сообщение, состоящее из ее имени и имени Боба.
А, В
(2) Трент посылает Алисе открытый ключ Боба, K
B
, подписанный закрытым ключом Трента, T.
S
T
(K
B
)
(3) Алиса проверяет подпись Трента. Затем она посылает Бобу свое имя и случайное число, шифрованное о т- крытым ключом Боба.
А, Е
В
(R
В
)
(4) Боб посылает Тренту свое имя, имя Алисы и случайное число Алисы, шифрованное открытым ключом
Трента, K
Т
А, В,
E
K
T
(R
A
)
(5) Трент посылает Бобу открытый ключ Алисы, K
А
, подписанный закрытым ключом Трента. Он также п о- сылает Бобу случайное число Алисы, случайный сеансовый ключ, имена Алисы и Боба, подписав все это закрытым ключом Трента и зашифровав открытым кл ючом Боба.
S
Т
(K
А
),
E
K
B
(S
Т
(R
A
, К, А, В))
(6) Боб проверяет подписи Трента. Затем он посылает Алисе вторую часть сообщения Трента, полученного на этапе (5), и новое случайное число, зашифровав все открытым ключом Алисы.

E
K
A
(S
Т
(R
A
, К, А, В), R
В
)
(7) Алиса проверяет подпись Трента и свое случайное число. Затем она посылает Бобу второе случайное чи с- ло, шифрованное сеансовым ключом.
Е
К
(R
В
)
(8) Боб расшифровывает свое случайное число и проверяет, что оно не изменилось.
Другие протоколы
В литературе описано множество протоколов . Протоколы X.509 рассматриваются в разделе 24.9, Kryp- toKnight - в разделе 24.6, а Шифрованный обмен ключами (Encrypted Key Exchange) - в разделе 22.5.
Другим новым протоколом с открытыми ключами является Kuperee [694]. Ведется работа на протоколами,
использующими маяки - заслуживающие доверия узлы сети, которые непрерывно и широковещательно пер е- дают достоверные метки времени [783].
Выводы
Из приведенных протоколов, как из тех, которые вскрываются, так и из надежных, можно извлечь ряд ва ж- ных уроков:
— Многие протоколы терпят неудачу, так как их разработчики пытались быть слишком умными. Они опт и- мизировали протоколы, убирая важные элементы - имена, случайные числа и т.п. - и пытаясь сделать протоколы как можно более прозрачными [43, 44].
— Оптимизация - эта манящая ловушка - сильно зависит от сделанных предположений. Пример: наличие достоверного времени позволяет вам реализовать многие вещи, невозможные в проти вном случае.
— Выбираемый протокол зависит от архитектуры используемых средств связи. Хотите ли вы минимизир о- вать размер сообщений или их количество? Могут ли сторона взаимодействовать каждый с каждым или круг их общения будет ограничен?
Именно подобные вопросы и привели к созданию формальных методов анализа протоколов .
3.4 Формальный анализ протоколов проверки подлинности и обмена ключами
Проблема выделения безопасного сеансового ключа для пары компьютеров (или людей) в сети настолько фундаментальна, что стала причиной многих исследований . Некоторые исследования заключались в разработке протоколов, подобных рассматриваемым в разделах 3.1, 3.2 и 3.3. Это, в свою очередь, привело к появлению более важной и интересной задачи: формальному анализу протоколов проверки подлинности и обмена ключами. Иногда прорехи в протоколах, кажущихся вполне надежными, обнаруживались спустя много лет п о- сле их разработки, и разработчикам потребовались средства, позволяющие сразу же проверять безопасность протокола. Хотя большая часть этого инструментария применима и к более общим криптографическим прот о- колам, особое внимание уделялось проверке подлинности и обмену ключами . Существует четыре основных подхода к анализу криптографических протоколов [1045]:
1. Моделирование и проверка работы протокола с использованием языков описания и средств проверки,
не разработанных специально для анализа криптографических протоколов.
2. Создание экспертных систем, позволяющих конструктору протокола разрабатывать и исследовать различные сценарии.
3. Выработка требований к семейству протоколов, используя некую логику для анализа понятий "знание" и "доверие".
4. Разработка формальных методов, основанных на записи свойств криптографических систем в алге б- раическом виде.
Полное описание этих четырех подходов и связанных с ними исследований выходит за рамки данной книги.
Хорошее введение в эту тему дано в [1047, 1355], я же собираюсь коснуться только основных вопросов .
Первый из подходов пытается доказать правильность протокола, рассматривая его как обычную компьюте р- ную программу. Ряд исследователей представляют протокол как конечный автомат [1449, 1565], другие исполь- зуют расширения методов исчисления предиката первого порядка [822], а третьи для анализа протоколов ис- пользуют языки описания [1566]. Однако, доказательство правильности отнюдь не является доказательством безопасности, и этот подход потерпел неудачу при анализе многих "дырявых" протоколов . И хотя его примене- ние поначалу широко изучалось, с ростом популярности третьего из подходов работы в этой области были п е- реориентированы.

Во втором подходе для определения того, может ли протокол перейти в нежелательное состояние (например,
потеря ключа), используются экспертные системы . Хотя этот подход дает лучшие результаты при поиске "дыр",
он не гарантирует безопасности и не предоставляет методик разработки вскрытий . Он хорош для проверки того,
содержит ли протокол конкретную "дыру", но вряд ли способен обнаружить неизвестные "дыры" в протоколе .
Примеры такого подхода можно найти в [987,1521], а в [1092] обсуждается экспертная система, разработанная армией США и названная Следователем ( Interrogator).
Третий подход гораздо популярнее. Он был впервые введен Майклом Бэрроузом ( Michael Burrows), Марти- ном Абэди (Martin Abadi) и Роджером Неедхэмом. Они разработали формальную логическую модель для ан а- лиза знания и доверия, названную БАН-логикой [283, 284]. БАН-логика является наиболее широко распр о- странена при анализе протоколов проверки подлинности . Она рассматривает подлинность как функцию от ц е- лостности и новизны, используя логические правила для отслеживания состояния этих атрибутов на протяжении всего протокола. Хотя были предложены различные варианты и расширения, большинство разработчиков пр о- токолов до сих пор обращаются к оригинальной работе.
БАН-логика не предоставляет доказательство безопасности , она может только рассуждать о проверке под- линности. Она является простой, прямолинейной логикой, легкой в применении и полезной при поиске "дыр" .
Вот некоторые предложения БАН-логики:
Алиса считает X. (Алиса действует, как если бы X являлось истиной.)
Алиса видит X. (Кто-то послал сообщение, содержащее X, Алисе, которая может прочитать и снова передать X - возмож- но после дешифрирования.)
Алиса сказала X. (В некоторый момент времени Алиса послала сообщение, которое содержит предложение X. Не извест- но, как давно было послано сообщение, и было ли оно послано в течении текущего выполнения протокола . Известно, что
Алиса считала X, когда говорила X.)
X ново. (X никогда не было послано в сообщении до текущего выполнения протокола .)
И так далее. БАН-логика также предоставляет правила для рассуждения о доверии протоколу . Для доказа- тельства чего-либо в протоколе или для ответа на какие-то вопросы к логическим предложениям о протоколе можно применить эти правила. Например, одним из правил является правило о значении сообщения :
ЕСЛИ Алиса считает, что у Алисы и Боба общий секретный ключ, K, и Алиса видит Х, шифрованное K, и Алиса не шиф- ровала X с помощью K, ТО Алиса считает, что Боб сказал X.
Другим является правило подтверждения метки времени :
ЕСЛИ Алиса считает, что X могло быть сказано только недавно, и, что Боб X когда-то сказал X, ТО Алиса считает, что
Боб считает X.
БАН-анализ делится на четыре этапа:
(1) Преобразуйте протокол к идеальной форме, используя описанные выше предложения.
(2) Добавьте все предположения о начальном состоянии протокола.
(3) Присоедините логические формулы к предложениям, получая утверждения о состоянии системы после каждого предложения.
(4) Примените логические постулаты к утверждениям и предположениям, чтобы раскрыть состояние доверия участников протокола.
Авторы БАН-логики "рассматривают идеализированные протоколы как более ясные и полные описания, чем традиционные, найденные в литературе..." [283, 284]. Другие исследователи не так оптимистичны и подвергают это действие критике, так как при этом реальный протокол может быть искажен [1161, 1612]. Дальнейшие спо- ры отражены в [221, 1557]. Ряд критиков пытается показать, что БАН-логика может и получить очевидно н е- правильные характеристики протоколов [1161] - см. контрдоводы в [285, 1509] - и что БАН-логика занимается только доверием, а не безопасностью [1509]. Подробное обсуждение приведено в [1488, 706, 1002].
Несмотря на эту критику БАН-логика достигла определенных успехов . Ей удалось обнаружить "дыры" в не- скольких протоколах, включая Needham-Schroeder и раннюю черновую версию протокола CCITT X.509 [303].
Она обнаружила избыточность во многих протоколах, включая Yahalom, Needham-Schroeder и Kerberos. Во многих опубликованных работах БАН-логика используется для заявления претензии о безопасности описыва е- мых протоколов [40, 1162, 73].
Были опубликованы и другие логические системы, некоторые из них разрабатывались как расширения БАН- логики [645, 586, 1556, 828], а другие основывались на БАН-логике для исправления ощутимых слабостей
[1488, 1002]. Из них наиболее успешной оказалась CNY [645], хотя у нее есть ряд изъянов [40]. В [292,474] к
БАН-логике с переменным успехом были добавлены вероятностные доверия . Другие формальные логики опи- саны в [156, 798,288]. [1514] пытается объединить черты нескольких логик . А в [1124, 1511] представлены ло- гики, в которых доверия изменяются со временем .
Четвертый подход к анализу криптографических протоколов предлагает моделировать протокол как алге б- раическую систему, выразить состояние знания участников о протоколе и затем проанализировать достиж и-

мость определенных состояний. Этот подход пока не привлек столько внимания, как формальная логика, но состояние дел меняется. Он впервые был использован Майклом Мерриттом [1076], который показал, что для анализа криптографических протоколов можно использовать алгебраическую модель . Другие подходы рассмот- рены в [473, 1508, 1530, 1531, 1532, 1510, 1612].
Анализатор протоколов Исследовательской лаборатория ВМС ( Navy Research Laboratory, NRL), возможно,
является наиболее успешным применением этих методов [1512, 823, 1046, 1513]. Он был использован для поис- ка как новых, так и известных "дыр" во множестве протоколов [1044, 1045, 1047]. Анализатор протоколов оп- ределяет следующие действия:
— Принять (Боб, Алиса, M, N). (Боб принимает сообщение M как пришедшее от Алисы в течение локальн о- го раунда Боба N.)
— Узнать (Ева, M). (Ева узнает M.)
— Послать (Алиса, Боб, Q, M). (Алиса посылает M Бобу в ответ на запрос, Q.)
— Запросить (Боб, Алиса, Q, N). (Боб посылает Q Алисе в течение локального раунда Боба N.)
Используя эти действия, можно задать требования . Например:
— Если Боб принял сообщение M от Алисы в какой-то прошедший момент времени, то Ева не знает M в ка- кой-то прошедший момент времени.
— Если Боб принял сообщение M от Алисы в течение локального раунда Боба N, то Алиса послала M Бобу в ответ на запрос Боба в локальном раунде Боба N.
Для анализа Анализатором протоколов NRL исследуемый протокол должен быть описан с помощью прив е- денных конструкций. Затем выполняются четыре фазы анализа : определение правил перехода для честных уч а- стников, описание операций, возможных и для полностью честных, и для нечестных участников , описание базо- вых блоков протокола и описание правил преобразования . Смысл всего этого в том, чтобы показать, что да н- ный протокол удовлетворяет необходимым требованиями . Использование инструментов, подобных Анализат о- ру протоколов NRL, в итоге могло бы привести к созданию протокола, который был бы обоснованно признан безопасным.
Хотя формальные методы в основном применяются к уже существующим протоколам, сегодня есть тенде н- ция использовать их и при проектировании протоколов . Ряд предварительных шагов в этом направлении сделан в [711]. Это же пытается сделать и анализатор протоколов NRL [1512, 222, 1513].
Применение формальных методов к криптографическим протоколам представляет собой качественно новую идею, и трудно обрисовать, к чему может привести ее реализация . С этой точки зрения слабейшим звеном к а- жется процесс формализации.
3.5 Криптография с несколькими открытыми ключами
Обычная криптография с открытыми ключами использует два ключа. Сообщение, зашифрованное одним ключом, может быть расшифровано другим . Обычно один ключ является закрытым, а другой - открытым .
Пусть, один ключ находится у Алисы, а другой - у Боба. Мы хотим реализовать следующую схему: Алиса м о- жет зашифровать сообщение так, что только Боб сможет расшифровать его, а Боб может зашифровать сообщ е- ние так, что только Алиса сможет прочитать его.
Эта концепция была обобщены Конном Бойдом ( Conn Boyd) [217]. Представьте себе вариант криптографии с открытыми ключами, использующий три ключа : K
A
, K
B
и K
C
, распределение которых показано в 1-й.
Алиса может зашифровать сообщение ключом K
A
так, что Эллен может расшифровать его, используя ключи
K
B
и Kc. То же самое, сговорившись, могут сделать Боб и Кэрол . Боб может зашифровать сообщение так, что
Фрэнк сможет прочесть его а Кэрол сможет зашифровать сообщение так, что его сможет прочесть Дэйв. Дэйв может зашифровать сообщение ключом K
A
так, что Эллен сможет прочесть его, ключом K
B
так, что его сможет прочесть Фрэнк, или обоими ключами, K
A
и K
B
, так, что сообщение сможет прочесть Кэрол. Аналогично, Эллен может зашифровать сообщение так, что Алиса, или Дэйв, или Фрэнк сможет прочесть его. Все возможные ко м- бинации показаны в , других не существует.
Табл. 3-2.
Распределение ключей в трехключевой системе.
Алиса
K
A
Боб
K
B

Кэрол
K
С
Дэйв
K
A
и K
B
Эллен
K
B
и Kc
Франк
K
С
и K
A
Такая схема может быть расширена на n ключей. Если для шифрования сообщения используется заданное подмножество ключей, то для дешифрирования сообщения потребуются оставшиеся ключи .
Широковещательная передача сообщения
Представьте, что в некоей операции занято 100 ваших тайных агентов . Вы хотите иметь возможность посы- лать сообщения группам агентов, но вы не знаете заранее состав групп . Можно либо шифровать сообщение от- дельно для каждого корреспондента, либо распределить ключи для всех возможных комбинаций агентов . Для реализации первого способа потребуется множество сообщений, для второго - множество ключей .
Криптография с несколькими ключами позволяет решить эту задачу намного проще. Мы будем использовать трех агентов: Алису, Боба и Кэрол. Вы выдадите Алисе ключ K
A
и K
B
, Бобу - K
B
и K
С
, Кэрол - K
С
и K
A
. Теперь вы сможете говорить с любым нужным подмножеством агентов. Если вы хотите, чтобы сообщение могла пр о- читать только Алиса, зашифруйте его ключом K
С
. Когда Алиса получит сообщение, она расшифрует его, посл е- довательно используя ключи K
A
и K
B
. Если вы хотите послать сообщение только Бобу, зашифруйте его ключом
K
A
, а сообщение для Кэрол - ключом K
B
. Если вы хотите, чтобы посланное сообщение могли прочитать Алиса и
Боб, зашифруйте его ключами K
A
и K
С
Для трех агентов это не слишком впечатляет, но для 100 преимущество достаточно ощутимо. Индивидуал ь- ные сообщения означают использование отдельного ключа для каждого агента (всего 100 ключей) и каждого сообщения. Передача сообщений всем возможным подмножествам означает использование 2 100
-2 различных ключей (исключены случаи сообщения всем агентам и никому из них) . Для схемы, использующий криптогра- фию с несколькими открытыми ключами, нужно только одно шифрованное сообщение и сто различных ключей .
Недостатком этой схемы является то, что вам также придется широковещательно передавать, какое подмнож е- ство агентов может читать сообщение, иначе каждому их них придется перебирать все возможные комбинации ключей в поисках подходящей. Даже только перечисление имен получателей может быть весьма внушительным. Кроме того, каждому агенту придется хранить немаленький объем информации о ключах, по крайней мере при прямолинейной реализации этой схемы .
Существуют и другие способы широковещательной передачи , ряд из них позволяет избежать описанной проблемы. Эти способы обсуждаются в разделе 22.7.
Табл. 3-3.
Шифрование сообщения в трехключевой системе.
Шифруется ключами
Должно быть расшифровано ключами
K
A
K
B
и Kc
K
B
K
A
и K
С
K
С
K
A
и K
B
K
A
и K
B
K
С
K
A
и K
С
K
B
K
B
и KcK
A
3.6 Разделение секрета
Вообразите, что вы изобрели новый, сверхлипкую, сверхсладкую сливочную тянучку или соус для гамбург е- ров, который еще безвкуснее, чем у ваших конкурентов. Это очень важно, и вы хотите сохранить изобретение в секрете. Только самым надежным работникам вы можете сообщить точный состав ингредиентов , но вдруг и кто-то из них подкуплен конкурентами? Секрет выкрадут, и немного погодя каждый в квартале будет делать гамбургеры с таким же безвкусным соусом, как ваш.
Предлагаемая схема называется разделением секрета. Есть способы взять сообщение и разделить его на части [551]. Каждая часть сама по себе ничего не значит, но сложите их - и вы получите сообщение . Если это

рецепт, и у каждого работника находится только его часть, то лишь собравшись все вместе ваши служащие см о- гут сделать соус. Если кто-нибудь из работников уволится, прихватив с собой свою часть рецепта, раскрытая информация по себе будет бесполезной.
По простейшей схеме сообщение делится между двумя людьми. Вот протокол, используя который Трент д е- лит сообщение между Алисой и Бобом:
(1) Трент генерирует строку случайных битов, R, такой же длины, что и сообщение, M.
(2) Трент выполняет "исключающее или" (XOR) над M и R, создавая S.
R ? M = S
(3) Трент передает Алисе R, а Бобу - S.
Чтобы получить сообщение, Алисе и Бобу нужно выполнить единственное действие:
(4)
Алиса и Боб выполняют операцию над имеющимися у них частями, восстанавливая сообщение.
R ? S = M
Этот метод при правильном выполнении абсолютно безопасен. Каждая часть в отдельности абсолютно бе с- смысленна. Что существенно, Трент шифрует сообщение одноразовым блокнотом и дает шифротекст одному человеку, а блокнот - другому. Одноразовые блокноты, обладающие абсолютной безопасностью, обсуждаются в разделе 1.5. Никакие вычислительные средства не смогут восстановить сообщение только по одной его части .
Эту схему легко расширить на большее число людей . Чтобы разделить сообщение между более чем двумя людьми, выполните операцию XOR с большим числом строк случайных битов . В следующем примере Трент делит сообщение на четыре части:
(1) Трент генерирует три строки случайных битов, R, S и T, такой же длины, что и сообщение, M.
(2) Трент выполняет "исключающее или" (XOR) над M и созданными тремя строками, создавая U.
M ? R ? S ? T = U
(3) Трент передает Алисе R, Бобу - S, Кэрол - T, а Дэйву - U.
Вместе Алиса, Боб, Кэрол и Дэйв могут восстановить сообщение :
(4)
Алиса, Боб, Кэрол и Дэйв собираются вместе и вычисляют:
R ? S ? T ? U = M
Это арбитражный протокол. Трент обладает абсолютной властью и может делать все, что он хочет . Он мо- жет раздать чепуху и утверждать, что это настоящие части секретной информации, никто не сможет это пров е- рить, пока, собравшись вместе, участники протокола не попробуют прочитать письмо . Он может выдать части секрета Алисе, Бобу, Кэрол и Дэйву и позже заявить всем, что только Алиса, Кэрол и Дэйв нужны для восст а- новления секрета, застрелив при этом Боба . Но это не является проблемой, так как делимый секрет принадл е- жит Тренту.
Однако, одна проблема у этого протокола существует. Если любая из частей будет потеряна, а Трента не б у- дет поблизости, пропадет и все сообщение . Если Кэрол, обладая частью рецепта соуса, перейдет работать к ко н- куренту, оставив свою часть секрета у себя, значит, остальным не повезло. Она не сможет восстановить рецепт,
но не смогут, собравшись, и Алиса, Боб и Дэйв . Ее часть также критична для восстановления сообщения, как и любая другая. Все, что известно Алисе, Бобу и Дэйву - это длина сообщения, и ничего больше . Это истинно, так как у R, S, T, U и M одинаковая длина, следовательно, каждому из участников известна длина M. Помните, со- общение M делится не в обычном смысле этого слова, а подвергается операции XOR со случайными величина- ми.
3.7 Совместное использование секрета
Вы вводите программу запуска ядерной ракеты и хотите быть уверенным, что никакой псих в одиночку не сможет вызвать пуск. Вы хотите быть уверенным, что и два психа не смогут вызвать пуск . Вы хотите, чтобы пуск произошел только, если не меньше трех из пяти офицеров будут психами .
Эта проблема легко может быть решена. Сделайте механическое устройство контроля запуска . Выдайте ключ каждому из пяти офицеров и потребуйте, чтобы по меньше мере три офицера вставили свои ключи в соо т- ветствующие гнезда, прежде чем вы разрешите им взорвать того, кого мы взрываем на этой неделе . (Если вы действительно волнуетесь, сделайте гнезда подальше друг от друга и потребуйте, чтобы офицеры вставляли ключи одновременно - вы ведь не хотели бы, чтобы офицер, выкравший недостающую пару ключей, смог бы испепелить Толедо.)

Можно сделать еще сложнее. Пусть только генерал у и паре полковников разрешено запустить ракету, но е с- ли генерал занят игрой в гольф, то запустить ракету имеют право только пять полковников . Сделайте контроль- ное устройство с пятью ключами. Выдайте генералу три ключа, а полковникам по одному. Генерал вместе с двумя полковниками или пять полковников смогут запустить ракету. Однако ни генерал в одиночку, ни четыре полковника не смогут этого сделать.
Более сложная схема совместного использования, называемая пороговой схемой, может решить и эти зада- чи, и более сложные - математически. На ее простейшем уровне вы можете взять любое сообщение (секретный рецепт, коды запуска, ваш список для прачечной и т.п.) и разделить его на n частей, называемых тенями или долями, так, что по любым m из них можно восстановить сообщение. Более точно, это называется
(m,n)-пороговой схемой.
Используя (3,4)-пороговую схему, Трент может разделить свой секретный рецепт между Алисой, Бобом, К э- рол и Дэйвом так, что любые трое из них могут сложить свои тени вместе и восстановить сообщение. Если Кэ- рол в отпуске, то Алиса, Боб и Дэйв смогут восстановить сообщение. Если Боб попал под автобус, то сообщение смогут восстановить Алиса, Кэрол и Дэйв. Но если Боб попал под автобус, а Кэрол в отпуске, то Алиса и Дэйв самостоятельно не смогут восстановить сообщение .
Вообще, пороговые схемы могут быть еще более гибкими. Можно отмоделировать любые сценарии совм е- стного использования, которые вы только сможете вообразить. Можно разделить сообщение между людьми в вашем здании так, что для его восстановления, если нет никого с третьего этажа, потребуется семь человек с первого этажа и пять со второго, в противном случае достаточно представителя третьего этажа вместе с тремя человеками с первого этажа и двумя со второго. Если же есть кто-то с четвертого этажа, то для восстановления сообщения достаточно этого человека и одного с третьего этажа или этого человека вместе с двумя с первого этажа и одного со второго. Если же ... ну вы уловили идею .
Эта идея была независимо выдвинута Ади Шамиром [1414] и Джорджем Блэкли (George Blakley) [182] и интенсивно была изучена Гусом Симмонсом ( Gus Simmons) [1466]. Множество различных алгоритмов обсуж- дается в разделе 23.2.
Совместное использование с мошенниками
Существует множество способов обмануть пороговую схему. Вот только несколько из них. Сценарий 1 : Пол- ковники Алиса, Боб и Кэрол сидят в изолированном бункере где-то глубоко под землей. Однажды они получают закодированное сообщение от президента : "Запустить ракеты. Мы собираемся стереть с лица Земли любые сл е- ды исследований противника в области нейронных сетей ". Алиса, Боб и Кэрол открывают свои тени, но Кэрол вводит случайное число. Он на самом деле пацифист и не хочет, чтобы ракеты были запущены . Поскольку
Кэрол не ввела правильное тени, секретная информация, которую они хотели получить, оказалась неправильной. Ракеты остались в своих шахтах. И самое плохое, никто не знает почему. Даже объединившись
Алиса и Боб не смогут доказать, что тень Кэрол неправильна.
Сценарий 2: Полковники Алиса и Боб сидят в бункере вместе с Мэллори. Мэллори ложно выдает себя за полковника. От президента приходит то же самое сообщение и все открывают свои тени . "Ха-ха-ха!" кричит
Мэллори. "Я подделал это сообщение президента. Теперь я знаю обе ваших доли." Он убегает вверх по лестни- це и исчезает прежде, чем его успеют поймать .
Сценарий 3: Полковники Алиса, Боб и Кэрол сидят в бункере вместе с Мэллори, который снова замаскиро- вался. (Помните, у Мэллори нет правильной тени.) От президента приходит то же самое сообщение и все о т- крывают свои тени. Мэллори открывает свою тень, только услышав все остальные . Так как для восстановления секрета требуется только три тени, он может быстро создать правильную тень и открыть ее. Итак, он не только заполучил секрет, но и никто не догадался, что он не является частью этой системы . Некоторые протоколы, ко- торые позволяют бороться с подобными мошенниками, рассматриваются в разделе 23.2.
Совместное использование секрета без Трента
Банк хочет, чтобы его подвал могли открыть трое из пяти офицеров, введя свои ключи . Это выглядит как типичная (3,5)-пороговая схема, но с одной тонкостью. Никто не знает секрета целиком. Трента, которые делит секрет на пять частей, нет. Существуют протоколы, используя которые пять офицеров могут создать секрет и поделить его на части так, что никто из офицеров не узнает секрета, пока он не будет восстановлен . В этой кни- ге я не рассматриваю эти протоколы, подробности см. в [756].
Совместное использование секрета без раскрытия долей
У этих схем есть одна проблема. Когда участники протокола собираются, чтобы восстановить секрет, они открывают свои части. Но раскрытие секрета не всегда желательно . Если разделяемый секрет является закры- тым ключом (например, к цифровой подписи), то каждый из n участников может выполнить частичную подпись

документа. После n-ой частичной подписи документ оказывается подписан совместно используемым закрытым ключом, а ни один из участников не может узнать содержания части, используемой другим участником . Смысл в том, что вы можете повторно использовать секрет, и для работы с ним вам не понадобится надежный посре д- ник. Дальнейшее развитие эта идея получила в работах Иво Десмедта (Yvo Desmedt) и Йера Френкеля (Yair
Frankel) [483, 484].
Подтверждаемое совместное использование секрета
Трент передает Алисе, Бобу, Кэрол и Дэйву часть секрета (или, по крайней мере, заявляет, что он это делает). Единственный способ убедиться, что их части правильны - это попытаться восстановить секрет . Может быть Трент послал Бобу поддельную часть, или часть Боба случайно испортилась при передаче по линиям связи. Подтверждаемое совместное использование секрета позволяет каждому из участников лично убедиться,
что их часть правильна, без необходимости восстанавливать секрет [558, 1235].
Схемы совместного использования секрета с мерами предохранения
Секрет делится среди 50 человек так, чтобы любые 10 могли собраться вместе и восстановить секрет . Это нетрудно. Но, можем ли мы реализовать ту же схему совместного использования секрета, добавив требование,
чтобы 20 человек могли собраться вместе и помешать остальным, независимо от их числа, восстановить секрет? Оказывается, что да [153].
Математика достаточно сложна, но основная идея в том, что каждый получает две части : часть "да" и часть "нет". Когда приходит время восстановить секрет, люди предоставляют одну из своих частей . Какую конкретно зависит от того, хотят ли они, чтобы секрет был раскрыт. Если предоставлено m или больше долей "да" и мень- ше чем n долей "нет", то секрет может быть восстановлен. В противном случае, это невозможно.
Конечно же, ничего не мешает достаточному числу людей "да" отойти в уголок, уединившись от людей "нет"
(если они знают, кто есть кто) и восстановить секрет. Но при условии, что все передают свои части в централ ь- ный компьютер эта схема будет работать .
Совместное использование секрета с вычеркиванием из списка
Вы создали систему совместного использования секрета и теперь хотите застрелить одного из владельцев части секрета. Вы могли бы создать новую схему, исключив этого несчастного, но время поджимает. Для п о- добной системы существуют способы копирования . Они позволяют активизировать новую схему совместного использования секрета сразу же после того, как вы перестали доверять одному из участников [1004].
3.8 Криптографическая защита баз данных
База данных членов организации - это весьма важная вещь. С одной стороны вы хотите предоставить к не доступ всем членам, желая, чтобы они общались друг с другом, обменивались идеями и делились друг с другом бутербродами. С другой стороны, если вы пустите в вашу базу данных кого угодно, сведения обязательно поп а- дут в руки надоедливых страховых агентов и докучливых поставщиков всякого хлама по почте .
Криптография может облегчить эту проблему . Можно зашифровать базу данных так, чтобы получить адрес одного человека было легко, а извлечь список почтовых адресов всех членов - трудно .
Схема, предложенная в [550, 549], прямолинейна. Выберите однонаправленную хэш-функцию и симметри ч- ный алгоритм шифрования. У каждой записи в базе данных два поля. Индексным полем является фамилия чл е- на, и именно оно обрабатывается однонаправленной хэш-функцией . Поле данных, в котором хранится полное имя и адрес члена, шифруется с помощью используемой в качестве ключа фамилии . Если вы не знаете фами- лии, вы никогда не сможете расшифровать поле данных .
Поиск по конкретной фамилии прост. Сначала хэшируется фамилия, и выполняется поиск значения хэш- функции в базе данных. Наличие нескольких совпадений означает, что база данных содержит информацию о нескольких людях с такой фамилией.
В [550] авторы используют эту систему для защиты словаря из 6000 испанских слов. Они сообщают о том,
что потеря производительности, вызванная шифрованием, минимальна . В более сложной схеме [549] использу- ется поиск по нескольким индексам, но идея остается той же . Основная проблема, связанная с этой системой,
состоит в том, что вы не сможете найти человека, не зная, как пишется его фамилия . Можно попробовать не- сколько вариантов, пока не будет найден правильный, но неудобно перебирать всех, чьи фамилии начинаются на "Sch" при поиске "Schneier."
Эта защита несовершенна. Очень назойливый страховой агент восстановит базу данных членов организации с помощью грубого взлома, перебирая все возможные фамилии . Если у него есть телефонная база данных, он может использовать имеющийся в ней список фамилий . Это пережевывание номеров может занять несколько

недель, но дело будет сделано. Тем не менее такая схема усложнит работу взломщика ( в мире продаже всякой чепухи по почте "усложнит" быстро превращается в "сделает слишком дорогой". Другой подход, предложенный в [185], предлагает набирать статистику по шифрованным данным .

Глава 4
Промежуточные протоколы
4.1 Службы меток времени
Во многих ситуациях людям нужно убедиться, что определенный документ уже существовал в определенный момент времени. Примером является спор об авторских правах или патенте. Дело выигрывает сторона, которая представит более раннюю копию спорной работы . Бумажные документы заверяются нотариусами и хранятся у юристов. Если возникает спор, нотариус или юрист свидетельствует, что письмо существовало в определенный момент времени.
В цифровом мире все гораздо сложнее. Нет способов обнаружить признаки подделки электронного докуме н- та. Его можно бесконечно копировать и изменять, не оставляя никаких следов . Несложно и изменить время соз- дания компьютерного файла. Никто не может взглянуть на документ и с полной уверенностью сказать: "Да, этот документ был создан раньше 4 ноября 1952 года "
Этой проблемой задались Стюарт Хабер ( Stuart Haber) и В. Скотт Сторнетта (W. Scott Stornetta) из
Bellcore
[682, 683, 92]. Им потребовался протокол цифровых меток времени со следующими свойствами :
— Метка времени должна существовать сама по себе, независя от физической среды, используемой для ее хранения.
— Должно быть невозможно тайно изменить ни единого бита документа.
— Должно быть невозможно задать для документа метку времени, отличного от текущего.
Решение с посредником
В этом протоколе участвуют Трент, обладающий надежной службой меток времени, и Алиса, которая хочет задать метку времени для документа.
(1) Алиса передает копию документа Тренту.
(2) Трент записывает время и дату получения документа, оставляя у себя копию для безопасного хранения.
Теперь, если кто-нибудь усомнится в заявленном Алисой времени создания документа, то Алисе просто нужно обратиться к Тренту. Он предоставит свою копию документа и подтвердит, что он получил документ в указанный день и час.
Этот протокол работает, но есть ряд очевидных проблем. Во первых, невозможно сохранить тайну - Алиса должна предоставить копию документа Тренту. Кто-то, подслушивающий линию связи, сможет прочесть док у- мент. Она может зашифровать документ при передаче, но ведь он должен будет храниться в базе данных Тре н- та. Насколько эта база безопасна?
Во вторых, самой базе данных придется быть очень большой . Велики будут требования и к пропускной сп о- собности линии связи.
Третья проблема связана с возможными ошибками. Ошибки при передаче или электромагнитная бомба,
взорванная где-то в центральном компьютере Трента могут полностью свести на нет заявление Алисы о метке времени.
И в четвертых, может оказаться невозможным найти такого честного Трента для ведения службы меток времени. Может быть, Алиса использует метку времени Боба . Ничто не остановит Алису и Боба от сговора и пометки документа тем временем, которое им нужно .
Улучшенное решение с посредником
Большинство этих проблем легко снимаются при использовании однонаправленной хэш-функции и цифр о- вых подписей:
(1) Алиса вычисляет значение однонаправленной хэш-функции для документа.
(2) Алиса передает это значение Тренту.
(3) Трент добавляет время и дату получения этого значения и затем подписывает результат цифровой подп и- сью.
(4) Трент отправляет подписанное значение хэш-функции вместе с меткой времени Алисе.
Это решает все проблемы, кроме последней. Алисе больше не нужно беспокоиться о раскрытии содержания

документа, использование значения хэш-функции вполне достаточно . Тренту больше не нужно хранить копии документов (и даже значения хэш-функции), поэтому снимаются проблемы безопасности и объема сохраняемых данных (помните, у однонаправленных хэш-функций нет ключа ). Алиса может немедленно проверить подп и- санную метку времени, полученную на этапе (4), и немедленно обнаружить любые ошибки передачи . Единст- венной оставшейся проблемой остается сговор Алисы и Трента с целью создания поддельной метки времени .
Протокол связи
Одним из путей решения этой проблемы является установление связи между меткой времени Алисы и ме т- ками времени, ранее созданными Трентом . Весьма вероятно, что эти метки были созданы не для Алисы, а для других людей. Так как порядок, в котором Трент получает различные запросы о метках времени не может быть известен заранее, перед меткой времени для Алисы должна была появиться другая метка времени. И так как запрос, пришедший позже, связан с меткой времени Алисы, то ее метка должна была появиться раньше . Эти две метки содержат между собой запрос Алисы как будто в сэндвиче .
Если А - это имя Алисы, H
n
- значение хэш-функции, для которого Алиса хочет зафиксировать время, а T
n-1
- предыдущая метка времени, то протокол имеет следующий вид :
(1) Алиса посылает Тренту H
n и А.
(2) Трент посылает Алисе обратно:
T
n
=S
K
(n,A,H
n
,T
n
,I
n-1
,H
n-1
,T
n-1
,L
n
)
где состоит L
n
- это информация о следующей хэшированной связи:
L
n
=H(I
n-1
,H
n-1
,T
n-1
,L
n-1
)
S
K
указывает, что сообщение подписано открытым ключом Трента. Имя Алисы определяет ее как отпр а- вителя запроса. Параметр n указывает последовательность запросов. Это n-ая метка времени, которую создал Трент. Параметр T
n
- это время. Дополнительно используется информация об идентификаторе, ор и- гинального значения хэш-функции, времени и хэшированной метка предыдущего документа, помеченного
Трентом.
(3) Когда Трент помечает следующий документ, он посылает Алисе идентификатор отправителя этого док у- мента: I
n-1
Если кто-то оспаривает метку времени Алисы, ей надо только связаться с отправителями предыдущего и следующего документов: I
n-1 н I
n+1
. Если и их свидетельство под вопросом, можно обратиться к авторам док у- ментов I
n-1 н I
n+1
и т.д. Любой может показать, что его документ был помечен после одного документа и перед другим.
Этот протокол мешает Алисе и Тренту договориться и создать документ с временем создания, отличным от времени создания настоящего документа. Трент не может изменить дату документа Алисы на более раннюю,
так как для этого нужно знать заранее, для какого документа перед данным будет проставляться метка времени .
Даже если он сможет подделать предыдущий документ, ему придется знать, какой документ предшествовал предыдущему и так далее. Трент не может изменить дату документа Алисы и на более позднюю, потому что метка времени должна быть вставлена перед меткой времени документа, заверяемого сразу же после данного, а этот документ уже существует. Единственный возможный способ сломать эту схему - это ввести фиктивную цепочку документов перед и после документа Алисы, достаточно длинную, чтобы лишить терпения того, кто проверяет метку времени документа Алисы.
Распределенный протокол
Люди умирают, метки времени теряются. Между пометкой документа и его оспариванием может произойти многое, что помешает Алисе получить копию метки времени I
n-1
. Эта проблема может быть частично снята вставкой меток времени предыдущих 10 человек в метку Алисы и последующей передаче Алисе имен следу ю- щих 10 человек. Так у Алисы появится гораздо больше возможностей найти людей, все еще хранящих свои метки времени.
Развивая эту идею, следующий протокол позволяет обойтись и без Трента:
(1) Используя в качестве входа H
n
, Алиса генерирует последовательность случайных чисел с помощью кри п- тографически безопасного генератора случайных чисел.
V
1
, V
2
, V
3
, . . . V
k
(2) Алиса рассматривает каждое из этих чисел как идентификатор , I, другого человека и посылает каждому из этих людей H
n
(3) Каждый из них добавляет время и дату к значению хэш-функции, подписывает результат и отправляет его

обратно Алисе.
(4) Алиса собирает и хранит все подписи как метку времени.
Криптографически безопасный генератор случайных чисел , используемый на этапе (1), позволяет Алисе из- бежать преднамеренного выбора коррумпированных I в качестве свидетелей. Даже если она сделает простей- шие изменения в своем документе, пытаясь создать набор коррумпированных I, ее шансы добиться этого пре- небрежимо малы. Хэш-функция рандомизирует значения, и Алиса не может на них воздействовать .
Этот протокол работает, потому что подделать метку времени Алиса может, только договорившись о с о- трудничестве со всеми k людьми. Так как на этапе (1) она выбирала их случайным образом, вероятность этого очень низка. Чем коррумпированнее общество, тем больше должно быть число k.
Кроме того, должен использоваться некоторый механизм, учитывающий то, что ряд людей не смогут вовр е- мя возвратить метку времени. Все, что нужно для правильной метки времени - это некоторое подмножество k.
Детали зависят от реализации.
Дальнейшая работа
Дальнейшие улучшения протоколов метки времени описаны в [92]. Авторы используют двоичные деревья для увеличения количества меток времени, зависящих от данной метки, уменьшая вероятность создания цепо ч- ки фальшивых меток времени. Они также рекомендуют публиковать список значений хэш-функций за проше д- ший день в некотором общедоступном источнике, например газете . Это работает как отправка значения хэш- функции случайным людям в распределенном протоколе. Действительно, метка времени появляется в каждом номере воскресной Нью-Йорк Таймс с 1992 года.
Эти протоколы меток времени запатентованы [684, 685, 686]. Патенты принадлежат дочерней компании
Bellcore, названной Surety Technologies, которая продает Систему цифрового нотариата, поддерживающую эти протоколы. В первой версии клиенты посылали запросы о "заверении" на центральный координирующий центр .
Следуя методике Меркла по использованию хэш-функций для построения деревьев [1066], сервер строит дерево значений хэш-функции, листья которого представляют собой все запросы, полученные в течение данной секу н- ды, и посылает каждому автору запроса список значений хэш-функции, описывающий путь от его листа до ко р- ня. Клиентская часть программного обеспечения сохраняет этот список и может выдать "сертификат" Цифров о- го нотариата для любого файла, который был сертифицирован . Последовательность корней этих деревьев обр а- зует "Запись универсального подтверждения" ( "Universal Validation Record"), которая будет доступна в элек- тронном виде во многих хранилищах (и также выпущена на CD-ROM). Клиентская часть также содержит функ- цию "подтверждения", позволяющую пользователю проверить, был ли заверена именно текущая форма файла
(запросив из хранилища корень соответствующего дерева и сравнив его со значением хэш-функции, соответс т- вующим образом рассчитанным для файла, и сертификатом ). За дальнейшей информацией обращайтесь в
Surety Technologies, 1 Main St., Chatham, NJ, 07928; [phone]; Fax: [phone].
4.2 Подсознательный канал
Алиса и Боб были арестованы и отправлены в тюрьму, он - в мужскую, а она - в женскую . Уолтер, надзира- тель, разрешает Алисе и Бобу обмениваться сообщениями, но он не разрешает шифровать сообщения . Уолтер считает, что они планируют бегство, поэтому он хочет читать все, что они пишут .
Уолтер надеется также суметь обмануть Алису или Боба. Он хочет, чтобы один из них посчитал принятое им ложное сообщение настоящим. Алиса и Боб мирятся с риском возможного обмана, иначе они вообще не смогут общаться, но им нужно согласовать свои планы . Для этого им необходимо обмануть надзирателя и найти способ передавать секретную информацию. Им нужно создать подсознательный канал, скрытый канал связи в откр ы- тых сообщениях, хотя сообщения сами по себе не содержат секретной информации . С помощью обмена совер- шенно безобидными подписанными сообщениями они обменяются секретной информацией и одурачат Уолтера,
даже если он просматривает все сообщения.
Простым подсознательным каналом может быть число слов в предложении. Нечетное число слов в предл о- жении может соответствовать "1", а четное число слов -"0". Так, пока вы читаете этот самый обычный абзац, я передал вам сообщение "110". Проблематичность этого метода в том, что он является обычной стеганографией
(см. раздел 1.2), ключ не используется и безопасность зависит от секретности алгоритма .
Густавус Симмонс придумал идею организации подсознательного канала с помощью обычного алгоритма цифровой подписи [1458, 1473]. Так как подсознательные сообщения спрятаны в том, что выглядит нормал ь- ными цифровыми подписями, это форма маскировки . Уолтер видит, как подписанные безобидные сообщения передаются туда и обратно, но реальная передаваемая информация проходит незаметно для него по подсозн а- тельному каналу. В действительности, алгоритм подсознательного канала в подписях не отличим от нормальн о- го алгоритма в подписях, по крайней мере для Уолтера . Ер не только не может прочитать сообщение, перед а- ваемое по подсознательному каналу, но у него вообще нет ни малейшего представления о существовании такого

сообщения. В общем случае протокол выглядит примерно так:
(1) Алиса создает безобидное сообщение, все равно какое.
(2) Используя общий с Бобом ключ, Алиса подписывает безобидное сообщение, пряча свое подсознательное сообщение в подписи. (Это суть подсознательного протокола, см. раздел 23.3).
(3) Алиса посылает подписанное сообщение Бобу через Уолтера.
(4) Уолтер читает безобидное сообщение и проверяет подпись. Не обнаружив ничего подозрительного, он п е- редает подписанное сообщение Бобу.
(5) Боб проверяет подпись под безобидным сообщением, убеждаясь, что сообщение получено от Алисы.
(6) Боб игнорирует безобидное сообщение и, используя общий с Алисой секретный ключ, извлекает подсозн а- тельное сообщение.
А мошенничество? Уолтер не верит никому, и никто не верит Уолтеру. Он всегда может помешать передаче сообщений, но у него нет возможности подделать сообщение. Так как Уолтер не может создать правильной подписи, Боб обнаружит подделку на этапе (5). Уолтер не может читать подсознательные сообщения - у него нет нужного ключа. Что еще важнее, у него нет ни малейшего представления, что подсознательные сообщения с у- ществуют. Подписанные сообщения, использующие алгоритм цифровой подписи на вид ничем не отличаются от подписанных сообщений, содержащих подсознательные сообщения в подписи .
Более проблематичен обман своего партнера Алисой или Бобом. В некоторых реализациях подсознательного канала секретная информация, нужная Бобу для чтения подсознательного сообщения, совпадает с информацией,
нужной Алисе для подписи безобидного сообщения. Если это так, Боб может выдать себя за Алису. Он может подписать сообщения, выдав их за посланные Алисой, и Алиса ничего не сможет с этим поделать. Если ей н е- обходимо отправить ему подсознательное сообщение, она должна верить, что он не будет мошенничать с ее з а- крытым ключом.
В других реализациях подсознательного канала такой проблемы нет. Секретный ключ, общий для Алисы и
Боба, позволяет Алисе отправлять Бобу подсознательные сообщения, но закрытый ключ Алисы не передается, и
Боб не может подписывать сообщения ее подписью . Алисе не нужно верить, что Боб не будет мошенничать с ее закрытым ключом.
Применения подсознательного канала
Наиболее очевидным применением подсознательного канала является шпионская сеть. Если кто-то посылает и принимает сообщения, то передача сообщений по подсознательному каналу в подписанных документах не будет вызывать подозрений. Конечно же, вражеские шпионы могут делать то же самое.
Используя подсознательный канал, Алиса может, даже если ей угрожают, безопасно подписать документ .
Подписывая документ, она может вставить подсознательное сообщение, написав: "Я арестована ". Иные приме- нения не так бросаются в глаза. Компания может подписать документы и вставить подсознательные сообщения для отслеживания времени действия документов . Правительство может "пометить" электронные деньги . Мо- шенническая программа для подписи документов может использовать подсознательные сообщения в создава е- мых подписях для организации утечки секретной информации . Возможности бесконечны.
Подписи, свободные от подсознательного канала
Алиса и Боб обмениваются подписанными сообщениями, обговаривая сроки контракта. Они используют протокол цифровой подписи. Однако, эти переговоры на самом деле маскируют шпионскую деятельность Ал и- сы и Боба. Используя алгоритм цифровой подписи, они не волнуются о подписываемых ими сообщениях. Для обмена секретной информацией они используют подсознательный канал в подписях под документами . Контр- разведка, однако, не знает, что переговоры о контракте и используемые подписанные сообщения являются тол ь- ко прикрытием. Для противодействия подобной схеме были разработаны схемы подписи, свободной от подсо з- нательного канала. Используемые в этих схемах цифровые подписи невозможно изменить для организации подсознательного канала. Подробности см. в [480, 481].
4.3 Неотрицаемые цифровые подписи
Обычные цифровые подписи могут быть точно скопированы. Иногда это свойство полезно, например, при распространении публичных заявлений. В другой раз это может оказаться проблемой . Вообразите личное или деловое письмо, подписанное цифровой подписью . Если распространяется множество копий этого документа,
каждая из которых может быть проверена кем угодно, то это может привести к замешательству или шантажу .
Лучшим решением является цифровая подпись, правильность которой может быть доказана получателю, но которая не позволит получателю показать третьей стороне полученное сообщение без согласия разрешения л и-

ца, подписавшего сообщение.
Alice Software Company (Компания программного обеспечения Алисы) распространяет продукт DEW (Do-
Everything-Word, Делая со словом что угодно). Для гарантии отсутствия вирусов каждая копия содержит ци ф- ровую подпись. Однако, создатели хотят, чтобы только легальные покупатели продукта, а не компьютерные пираты могли проверить подпись. В то же время, если обнаруживаются копии DEW, содержащие вирус, у Alice
Software Company не должно быть возможности отрицать правильную подпись .
Неотрицаемые подписи [343,327] удобны для решения подобных задач. Как и обычная цифровая подпись,
неотрицаемая цифровая подпись зависит от подписанного документа и закрытого ключа человека, подписавш е- го документ. Но, в отличие от обычных цифровых подписей, неотрицаемая подпись не может быть проверена без разрешения подписавшего. Хотя для этих подписей можно было бы подобрать название получше, например,
"непередаваемые подписи", существующее название обусловлено тем обстоятельством, что если Алисе придется либо подтвердить, либо отрицать подпись - может быть в суде - она не сможет ложно отрицать свою настоящую подпись. Несмотря на сложность математики основная идея проста :
(1) Алиса предъявляет Бобу подпись.
(2) Боб создает случайное число и посылает его Алисе.
(3) Алиса выполняет вычисления, используя случайное число и свой закрытый ключ, и посылает Бобу резул ь- тат. Алиса может выполнить эти вычисления только, если подпись правильна.
(4) Боб проверяет это.
Также существует дополнительный протокол, позволяющий Алисе доказать, что она не подписывала док у- мент, и не допускающий возможности ложно отказаться от подписи .
Боб не может повернуться и убедить Кэрол, что подпись Алисы правильна, потому что Кэрол не знает, что числа Боба случайны. Он может легко без помощи Алисы изложить протокол на бумаге и послать результат
Кэрол. Кэрол может удостовериться в правильности подписи Алисы только, если она сама выполнит этот пр о- токол с Алисой. Сейчас кажется, что в этом немного смысла, но он появится, когда вы взглянете на математику раздела 23.4.
Это решение не совершенно. Иво Десмедт и Моти Юнг (Moti Yung) показали, что в некоторых случаях Боб может убедить Кэрол в правильности подписи Алисы [489].
Например, Боб покупает легальную копию DEW. Он может подтвердить подпись под программным проду к- том, когда захочет. Тогда, Боб может убедить Кэрол, что он работает на Alice Software Company, и продать ей пиратскую копию DEW. Когда Кэрол попытается подтвердить подпись Боба, он одновременно подтверждает подпись у Алисы. Когда Кэрол посылает ему случайное число, он отправляет его Алисе. Ответ Алисы он пере- сылает Кэрол. Кэрол убеждается в том, что она - легальный покупатель, хотя она таковым не является . Такое вскрытие является прмером проблемы великого гроссмейстера и подробно рассматривается в разделе 5.2.
Несмотря на это у неотрицаемых подписей множество применений, во многих случаях Алиса не хочет, чт о- бы кто угодно мог проверить ее подпись. Она может не хотеть, чтобы подпись под ее личной корреспонденцией могла быть проверена журналистами, чтобы ее письма были опубликованы и подтверждены независимо от ко н- текста, или просто, чтобы нельзя было обнаружить изменения в письмах, сделанные ею позже . Если она подпи- сывает информацию, которую она продает, то она не хочет, чтобы кто-то, не заплатив за информацию, мог по д- твердить ее достоверность. Защитить свои права Алиса может контролируя тех, кто проверяет ее подпись .
Ряд вариантов неотрицаемых подписей отделяет связь между подписавшим и сообщением от связи между подписавшим и подписью [910]. В одной схеме кто угодно может проверить, что подпись действительно была создана ее автором, а для проверки правильности подписи для данного сообщения требуется сотрудничество подписавшего.
Близким понятием является доверительная неотрицаемая подпись [1229]. Представьте, что Алиса работа- ет на Toxins, Inc., и передает обличающие документы в газету, используя протокол неотрицаемой подписи . Али- са может подтвердить свою подпись только репортеру газеты и никому больше . Однако, негодяй Боб подозрева- ет, что источником документов является Алиса . Он требует, чтобы Алиса использовала протокол снятия подп и- си, чтобы очистить свое имя, а Алиса отказывается . Боб настаивает, что единственной причиной отказа Алисы является ее виновность, и убивает ее.
Доверительные неотрицаемые подписи похожи на обычные неотрицаемые подписи за исключением прот о- кола снятия подписи, который может быть запущен только Трентом . Только Трент, а не Боб может потребовать от Алисы использовать протокол снятия. И если Трент представляет судебную систему, то он использует этот протокол только для разрешения формального спора .

4.4 Подписи уполномоченного свидетеля
Alice Software Company добилась бурного роста продаж, продавая DEW - такого, что Алиса большую часть времени посвящает подтверждению неотрицаемых подписей, а не работе над новыми возможностями.
Алисе хотелось бы назначить некоего человека в компании ответственным за подтверждение подписи. Ал и- са, ил любой другой программист, сможет подписывать документы с помощью неотрицаемого протокола. Но все подтверждения будут проводиться только Кэрол.
Оказывается, это возможно с использованием подписи уполномоченного свидетеля [333,1213]. Алиса мо- жет подписать документ, так что Боб убедится, что подпись правильна, но не сможет убедить в этом третье л и- цо. В то же время Алиса назначает Кэрол на должность будущего свидетеля своей . Алисе даже не нужно зара- нее просить разрешения у Кэрол, ей только нужно использовать открытый ключ Кэрол. И Кэрол сможет под- твердить подпись Алисы, если Алиса уехала из города, уволилась, была повышена или умерла .
Подписи уполномоченного свидетеля представляют собой некий компромисс между обычными цифров ы- ми подписями и неотрицаемыми подписями . Определенно существуют случаи, когда Алиса захочет ограничить число тех, кто может подтвердить ее подпись . С другой стороны, предоставление Алисе полного контроля по д- рывает сам институт подписей - Алиса может отказаться сотрудничать и в подтверждении, и в отрицании, она может заявить о потере ключей для подтверждения или отрицания, наконец, она может быть просто недоступна .
Подписи уполномоченного свидетеля могут предоставить Алисе защиту, создаваемую неотрицаемой подписью,
одновременно не позволяя ей злоупотреблять этой защитой . Алиса даже может предпочесть этот способ : подпи- си уполномоченного свидетеля могут помешать ложным применениям, защитить ее, если она действительно потеряла свой ключ, выручить, если она в отпуске, в больнице или даже умерла .
Эта идея может иметь различные применения. Например, Кэрол может сделаться государственным нотари у- сом. Она опубликует в каком-то каталоге свой открытый ключ, и люди получают возможность назначать ее свидетелем своих подписей. Получая небольшую плату за подтверждение подписей, она может жить припева ю- чи.
Кэрол может быть агентством по охране авторских прав, правительственным агентством или еще какой- нибудь организацией. Этот протокол позволяет отделить людей, подписывающих документы, от людей, которые помогают подтверждать подписи.
4.5 Подписи по доверенности
Подписи уполномоченного свидетеля позволяют подписавшему назначить кого-то другого для подтвержд е- ния подписи. Пусть Алиса хочет поехать в деловую поездку в некое место, где нет хорошей компьютерной сети
- в африканские джунгли, например. Или она не дееспособна после тяжелой операции . Она ожидает получения важной электронной почты и инструктирует своего секретаря Боба ответить соответствующим образом . Как