Существуют арбитражные компьютерные протоколы. Они предполагают, что участвующие стороны честны, но при подозрении о возможном мошенничестве по существующему набору данных третья сторона, которой доверяют участники, сможет обнаружить факт мошенничества . Хороший арбитражный протокол позволяет арбитру установить и личность мошенника. Арбитражные протоколы обнаруживают, а не предупреждают моше н-ничество. Неотвратимость обнаружения выступает в качестве предупредительной меры, предотвращая моше н-ничество.

Самодостаточные протоколы

Самодостаточный протокол является лучшим типом протокола. Он полностью обеспечивает честность сторон (см. 1-й(в)). Для выполнения протокола не нужен ни посредник, не решающий споры арбитр . Само построение протокола обеспечивает отсутствие споров. Если одна из сторон попытается смошенничать, мошенн и-чество будет немедленно обнаружено другой стороной, и протокол прекратит выполняться. Чего бы не пыталась добиться мошенничающая сторона, этому не суждено случиться.

В лучшем мире любой протокол должен быть самодостаточным, но, к несчастью, не существует самодост а-точных протоколов для каждой ситуации.

Попытки вскрытия протоколов

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

Люди могут использовать множество способов взломать протокол. Некоторые, не являясь участниками пр о-токола, могут "подслушивать" какую-то часть или весь протокол. Это называется пассивным вскрытием, так как взломщик не воздействует на протокол. Все, что он может сделать - это проследить за протоколом и поп ы-таться добыть информацию. Этот тип вскрытия соответствует вскрытию с использованием только шифротекста, обсуждавшемуся в разделе 1.1. Так как пассивные вскрытия трудно обнаружить, протоколы стремятся предо т-вращать, а не обнаруживать их. В этих протоколах роль злоумышленника будет играть Ева.

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

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

Активные вскрытия более серьезны, особенно в отношении протоколов, в которых стороны не обязательно доверяют друг другу. Взломщик не обязательно кто-то совсем посторонний, он может быть зарегистрированным пользователем системы и даже системным администратором . Может быть даже несколько активных взломщ и-ков, работающих вместе. В этой книге роль злонамеренного активного взломщика будет играть Мэ ллори.

Взломщиком может быть и один из участников протокола . Он может обманывать, выполняя протокол, или вовсе не следовать правилам протокола. Такой взломщик называется мошенником. Пассивные мошенники выполняют правила протокола, но стараются получить больше информации, чем предусмотрено протоколом . Активные мошенники нарушают работу протокола, пытаясь смошенничать.

Очень трудно поддерживать безопасность протокола, если большинство его участников - активные моше н-ники, но иногда активное мошенничество может быть обнаружено законными участниками . Конечно, протоколы должны быть защищены и от пассивного мошенничества .

2.2 Передача информации с использованием симметричной криптографии

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

(1) Алиса и Боб выбирают систему шифрования.

(2) Алиса и Боб выбирают ключ.

(3) Алиса шифрует открытый текст своего сообщения с использованием алгоритма шифрования и ключа, п о-лучая шифрованное сообщение.

(4) Алиса посылает шифрованное сообщение Бобу.

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

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

Ева, однако, не глупа. Она может также подслушать и этапы (1) и (2). Тогда ей станут известны алгоритм и ключ - также как и Бобу. Когда она перехватит сообщение на этапе (4), то ей останется только дешифровать его самостоятельно.

В хорошей криптосистеме безопасность полностью зависит от знания ключа и абсолютно не зависит от зн а-ния алгоритма. Именно поэтому управление ключами так важно в криптографии . Используя симметричный алгоритм, Алиса и Боб могут открыто выполнить этап (1), но этап (2) они должны сохранить в тайне . Ключ должен оставаться в секрете перед, после и в течение работы протокола - до тех пор, пока должно оставаться в тайне передаваемое сообщение - в противном случае сообщение тут же будет раскрыто . (О криптографии с открытыми ключами, решающей эту проблему иначе, рассказывается в разделе 2.5 .)

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

А Алиса? Что она может сделать, чтобы испортить протокол? Она может передать копию ключа Еве, и тогда Ева сможет читать все, что говорит Боб, и напечатать его слова в Нью-Йорк Тайме. Это серьезно, но проблема не в протоколе. Алиса и так может передавать Еве любые открытые тексты, передаваемые с использованием протокола. Конечно, то же самое может сделать и Боб. Протокол предполагает, что Алиса и Боб доверяют друг другу. Итак, симметричным криптосистемам присущи следующие проблемы :

- Распределение ключей должно проводиться в секрете. Ключи столь же важны, как и все сообщения, зашифрованные этими ключами, так как знание ключа позволяет раскрыть все сообщения . Для распространенных систем шифрования задача распределения ключей - серьезнейшая задача . Часто курьеры лично доставляют ключи по назначению .

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

- В предположении, что каждая пара пользователей сети использует отдельный ключ, общее число ключей быстро возрастает с ростом числа пользователей. Сеть из n пользователей требует n{n - l)/2 ключей. Например, для общения 10 пользователей между собой нужно 45 различных ключей, для 100 пользователей потребуется 4950 ключей. Решение проблемы - в уменьшении числа пользователей, но это не всегда во з-можно.

2.3 Однонаправленные функции

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

Однонаправленные функции относительно легко вычисляются, но инвертируются с большим трудом. То есть, зная x просто рассчитать f(x), но по известному f(x) нелегко вычислить x. Здесь, "нелегко" означает, что для вычисления x по f(x) могут потребоваться миллионы лет, даже если над этой проблемой будут биться все компь ю-теры мира.

Хорошим примером однонаправленной функции служит разбитая тарелка . Легко разбить тарелку на тысячу крошечных кусочков. . Однако, нелегко снова сложить тарелку из этих кусочков .

Это звучит красиво, но туманно и непонятно. Математически строгого доказательства существования одн о-направленных функций нет, нет и реальных свидетельств возможности их построения [230, 530, 600, 661]. Несмотря на это, многие функции выглядят в точности как однонаправленные : мы можем рассчитать их и, до сих пор, не знаем простого способа инвертировать их. Например, в ограниченной окрестности легко вычислить x2, но намного сложнее x"2. В оставшейся части раздела я собираюсь притвориться, что однонаправленные фун к-ции существуют. Мы поговорим об этом в еще разделе 1 1.2.

Итак, что же хорошего в однонаправленных функциях ? Непосредственно их нельзя использовать для ши ф-рования. Сообщение, зашифрованное однонаправленной функцией бесполезно - его невозможно дешифровать . (Упражнение: напишите на тарелке что-нибудь, разбейте тарелку на крошечные осколки и затем отдайте их приятелю. Попросите его прочитать сообщение. Посмотрите, как он будет озадачен однонаправленной функцией.) Для криптографии с открытыми ключами нам нужно что-то другое (хотя существуют и непосредственные криптографические применения однонаправленных функций - см. раздел 3.2).

Однонаправленная функция с люком - это особый тип однонаправленной функции, с секретной лазейкой . Ее легко вычислить в одном направлении и трудно - в обратном . Но если вам известен секрет, вы можете легко рассчитать и обратную функцию. То есть, легко вычислить f(x) по заданному x, но трудно по известному f(x) вычислить X. Однако, существует небольшая секретная информация, у, позволяющая, при знании f(x) и у, легко вычислить x.

В качестве хорошего примера однонаправленной функции с люком рассмотрим часы . Легко разобрать часы на сотни малюсеньких кусочков и трудно снова собрать из этих деталей работающие часы . Но, с секретной информацией - инструкцией по сборке - намного легче решить эту задачу .

2.4 Однонаправленные хэш-функции

У однонаправленной хэш-функции может быть множество имен: функция сжатия, функция сокращения contraction function, краткое изложение, характерный признак, криптографическая контрольная сумма, код целостности сообщения (message integrity check, MIC) и код обнаружения манипуляции (manipulation detection code, MDC). Как бы она не называлась эта функция является центральной в современной криптографии . Однонаправленные хэш-функции - это другая часть фундамента многих протоколов .

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

Смысл хэш-функции состоит в получении характерного признака прообраза - значения, по которому анал и-зируются различные прообразы при решении обратной задачи . Так как обычно хэш-функция представляет собой соотношение "многие к одному", невозможно со всей определенностью сказать, что две строки совпадают, но их можно использовать, получая приемлемую оценку точности .

Однонаправленная хэш-функция - это хэш-функция, которая работает только в одном направлении: легко вычислить значение хэш-функции по прообразу, но трудно создать прообраз, значение хэш -функции которого равно заданной величине. Упоминавшиеся ранее хэш-функции, вообще говоря, не являются однонаправленн ыми: задав конкретный байт, не представляет труда создать строку байтов, XOR которых дает заданное значение. С однонаправленной хэш-функцией такого не выйдет. Хорошей однонаправленной хэш-функцией является хэш-функция без столкновений - трудно создать два прообраза с одинаковым значением хэш -функции.

Хэш-функция является открытой, тайны ее расчета не существует . Безопасность однонаправленной хэш-функцией заключается именно в ее однонаправленности. У выхода нет видимой зависимости от входа . Изменение одного бита прообраза приводи к изменению, в среднем, половины битов значения хэш -функции. Вычислительно невозможно найти прообраз, соответствующий заданному значению хэш -функции.

Посмотрите на это как на способ получить характерные признаки файлов . Если вы хотите проверить, что у кого-то есть тот же файл, что и у вас, но вы не хотите, чтобы этот файл был передан вам, попросите послать вам значение хэш-функции. Если присланное значение хэш-функции совпадет с рассчитанным вами, то почти наверняка чужой файл совпадает с вашим. Это особенно полезно при финансовых транзакциях, когда вы не хотите где-то в сети превратить снятие со счета $100 в снятие $1000. В обычных условиях вы можете использовать однонаправленную хэш-функцию без ключа, так что кто угодно может проверить значение хэш -функции. Если нужно, чтобы проверить значение хэш-функции мог только один получатель, прочтите следующий раздел .

Коды проверки подлинности сообщения

Код проверки подлинности сообщения (message authentication code, MAC), известный также как код про-