Криптографические попытки взлома могут быть направлены против криптографических алгоритмов, и с-пользуемых в протоколах, против криптографических методов, используемых для реализации алгоритмов и протоколов или непосредственно против протоколов. Поскольку в этом разделе книги обсуждаются именно пр о-токолы, я предполагаю, что криптографические алгоритмы и методы безопасны , и рассматриваю только попыт-ки вскрытия протоколов.
Люди могут использовать множество способов взломать протокол. Некоторые, не являясь участниками пр о-токола, могут "подслушивать" какую-то часть или весь протокол. Это называется пассивным вскрытием,так как взломщик не воздействует на протокол. Все, что он может сделать - это проследить за протоколом и попы-таться добыть информацию. Этот тип вскрытия соответствует вскрытию с использованием только шифротекста, обсуждавшемуся в разделе 1.1. Так как пассивные вскрытия трудно обнаружить, протоколы стремятся предо т-вращать, а не обнаруживать их. В этих протоколах роль злоумышленника будет играть Ева.
В другом случае взломщик может попытаться изменить протокол для собственной выгоды . Он может выдать себя за другого, ввести новые сообщения в протокол, заменить одно сообщение другим, повторно передать ст а-рые сообщения, разорвать канал связи или изменить хранящуюся в компьютере информацию . Такие действия называются активным вскрытием, так как они требуют активного вмешательства . Эти формы вскрытия зависят от вида сети.
Пассивные взломщики стараются получить информацию об участниках протокола . Они собирают сообще-ния, переданные различными сторонами, и пытаются криптоанализировать их . Попытки активного вскрытия, с другой стороны, преследуют более широкий набор целей. Взломщик может быть заинтересован в получении информации, ухудшении работы системы или получении несанкционированного доступа к ресурсам .
Активные вскрытия более серьезны, особенно в отношении протоколов, в которых стороны не обязательно доверяют друг другу. Взломщик не обязательно кто-то совсем посторонний, он может быть зарегистрированным пользователем системы и даже системным администратором . Может быть даже несколько активных взломщи-ков, работающих вместе. В этой книге роль злонамеренного активного взломщика будет играть Мэ ллори.
Взломщиком может быть и один из участников протокола. Он может обманывать, выполняя протокол, или вовсе не следовать правилам протокола. Такой взломщик называется мошенником. Пассивные мошенникивыполняют правила протокола, но стараются получить больше информации, чем предусмотрено протоколом . Активные мошенникинарушают работу протокола, пытаясь смошенничать.
Очень трудно поддерживать безопасность протокола, если большинство его участников - активные моше н-ники, но иногда активное мошенничество может быть обнаружено законными участниками . Конечно, протоко-лы должны быть защищены и от пассивного мошенничества.
2.2 Передача информации с использованием симметричной криптографии
Как двум сторонам безопасно обмениваться информацией? Конечно же, шифрую свои сообщения. Посмот-рим, что должно произойти, когда Алиса посылает шифрованное сообщение Бобу (полный протокол гораздо сложнее).
(1) Алиса и Боб выбирают систему шифрования.
(2) Алиса и Боб выбирают ключ.
(3) Алиса шифрует открытый текст своего сообщения с использованием алгоритма шифрования и ключа, п о-лучая шифрованное сообщение.
(4) Алиса посылает шифрованное сообщение Бобу.
(5) Боб дешифрирует шифротекст сообщения с использованием алгоритма шифрования и ключа, получая о т-крытый текст сообщения.
Что может Ева, находясь между Алисой и Бобом, узнать, подслушивая этот протокол ? Если она может подслушать только передачу на этапе (4), ей придется подвергнуть шифротекст криптоанализу . Это пассивное вскрытие представляет собой вскрытие с использованием только шифротекста, применяемые алгоритмы усто й-чивы (насколько нам известно) по отношению к любым вычислительным мощностям, который может запол у-чить Ева для решения проблемы.
Ева, однако, не глупа. Она может также подслушать и этапы (1) и (2). Тогда ей станут известны алгоритм и ключ - также как и Бобу. Когда она перехватит сообщение на этапе (4), то ей останется только дешифровать его самостоятельно.
В хорошей криптосистеме безопасность полностью зависит от знания ключа и абсолютно не зависит от зн а-ния алгоритма. Именно поэтому управление ключами так важно в криптографии. Используя симметричный алгоритм, Алиса и Боб могут открыто выполнить этап (1), но этап (2) они должны сохранить в тайне . Ключ должен оставаться в секрете перед, после и в течение работы протокола - до тех пор, пока должно оставаться в тайне передаваемое сообщение - в противном случае сообщение тут же будет раскрыто . (О криптографии с открытыми ключами, решающей эту проблему иначе, рассказывается в разделе 2.5 .)
Мэллори, активный взломщик, может сделать кое-что другое. Он может попытаться нарушить линию связи не этапе (4), сделав так, что Алиса вообще не сможет передавать информацию Бобу . Мэллори также может перехватить сообщение Алисы и заменить его своим собственным. Если ему удалось узнать ключ (перехватив обмен информацией на этапе (2) или взломав криптосистему), он сможет зашифровать свое сообщение и отправить его Бобу вместо перехваченного, и Боб не сможет узнать, что сообщение отправлено не Алисой. Если Мэ л-лори не знает ключа, он может только создать сообщение, превращающееся при дешифровке в бессмыслицу . Боб, считая, что сообщение отправлено Алисой, может решить, что либо у Алисы, либо в сети возникли серье з-ные проблемы.
А Алиса? Что она может сделать, чтобы испортить протокол? Она может передать копию ключа Еве, и тогда Ева сможет читать все, что говорит Боб, и напечатать его слова в Нью-Йорк Тайме. Это серьезно, но проблема не в протоколе. Алиса и так может передавать Еве любые открытые тексты, передаваемые с использованием протокола. Конечно, то же самое может сделать и Боб. Протокол предполагает, что Алиса и Боб доверяют друг другу. Итак, симметричным криптосистемам присущи следующие проблемы :
— Распределение ключей должно проводиться в секрете. Ключи столь же важны, как и все сообщения, зашифрованные этими ключами, так как знание ключа позволяет раскрыть все сообщения . Для распространенных систем шифрования задача распределения ключей - серьезнейшая задача . Часто курьеры лично доставляют ключи по назначению.
— Если ключ скомпрометирован (украден, разгадан, выпытан, получен за взятку и т.д. ), то Ева сможет расшифровать все сообщения, зашифрованные этим ключом. Она сможет также выступить в качестве одной из сторон и создавать ложные сообщения, дурача другую сторону .
— В предположении, что каждая пара пользователей сети использует отдельный ключ, общее число ключей быстро возрастает с ростом числа пользователей. Сеть из п пользователей требует п{п - 1)/2 ключей. Например, для общения 10 пользователей между собой нужно 45 различных ключей, для 100 пользователей потребуется 4950 ключей. Решение проблемы - в уменьшении числа пользователей, но это не всегда во з-можно.
2.3 Однонаправленные функции
Понятие однонаправленной функцииявляется центральным в криптографии с открытыми ключами. Не являясь протоколами непосредственно однонаправленные функции представляют собой краеугольный камень большинства протоколов, обсуждаемых в этой книге .
Однонаправленные функции относительно легко вычисляются, но инвертируются с большим трудом. То есть, зная х просто рассчитать f(x), но по известному f(x) нелегко вычислить х. Здесь, "нелегко" означает, что для вычисления х uof(x) могут потребоваться миллионы лет, даже если над этой проблемой будут биться все компь ю-теры мира.
Хорошим примером однонаправленной функции служит разбитая тарелка . Легко разбить тарелку на тысячу крошечных кусочков.. Однако, нелегко снова сложить тарелку из этих кусочков.
Это звучит красиво, но туманно и непонятно. Математически строгого доказательства существования одн о-направленных функций нет, нет и реальных свидетельств возможности их построения [230, 530, 600, 661]. Несмотря на это, многие функции выглядят в точности как однонаправленные : мы можем рассчитать их и, до сих пор, не знаем простого способа инвертировать их. Например, в ограниченной окрестности легко вычислить х2, но намного сложнее х1'2. В оставшейся части раздела я собираюсь притвориться, что однонаправленные фун к-ции существуют. Мы поговорим об этом в еще разделе 11.2.
Итак, что же хорошего в однонаправленных функциях? Непосредственно их нельзя использовать для шифрования. Сообщение, зашифрованное однонаправленной функцией бесполезно - его невозможно дешифровать . (Упражнение: напишите на тарелке что-нибудь, разбейте тарелку на крошечные осколки и затем отдайте их приятелю. Попросите его прочитать сообщение. Посмотрите, как он будет озадачен однонаправленной функцией.) Для криптографии с открытыми ключами нам нужно что-то другое (хотя существуют и непосредственные криптографические применения однонаправленных функций - см. раздел 3.2).
Однонаправленная функция с люком- это особый тип однонаправленной функции, с секретной лазейкой . Ее легко вычислить в одном направлении и трудно - в обратном . Но если вам известен секрет, вы можете легко рассчитать и обратную функцию. То есть, легко вычислить f(x) по заданному х, но трудно по известному f(x) вычислить х. Однако, существует небольшая секретная информация, у, позволяющая, при знании f(x) и у, легко
ВЫЧИСЛИТЬ X.
В качестве хорошего примера однонаправленной функции с люком рассмотрим часы . Легко разобрать часы на сотни малюсеньких кусочков и трудно снова собрать из этих деталей работающие часы . Но, с секретной информацией - инструкцией по сборке - намного легче решить эту задачу .
2.4 Однонаправленные хэш-функции
У однонаправленной хэш-функцииможет быть множество имен: функция сжатия, функция сокращения contraction function, краткое изложение, характерный признак, криптографическая контрольная сумма, код целостности сообщения (message integrity check, MIC) и код обнаружения манипуляции (manipulation detection code, MDC). Как бы она не называлась эта функция является центральной в современной криптографии . Однонаправленные хэш-функции - это другая часть фундамента многих протоколов .
Хэш-функции, долгое время использующиеся в компьютерных науках, представляют собой функции, математические или иные, которые получают на вход строку переменной длины (называемую прообразом)и преобразуют ее в строку фиксированной, обычно меньшей, длины (называемую значением хэш -функции). В качестве простой хэш-функции можно рассматривать функцию, которая получает прообраз и возвращает байт, предста в-ляющий собой XOR всех входных байтов.
Смысл хэш-функции состоит в получении характерного признака прообраза - значения, по которому анал и-зируются различные прообразы при решении обратной задачи. Так как обычно хэш-функция представляет собой соотношение "многие к одному", невозможно со всей определенностью сказать, что две строки совпадают, но их можно использовать, получая приемлемую оценку точности .
Однонаправленная хэш-функция - это хэш-функция, которая работает только в одном направлении: легко вычислить значение хэш-функции по прообразу, но трудно создать прообраз, значение хэш -функции которого равно заданной величине. Упоминавшиеся ранее хэш-функции, вообще говоря, не являются однонаправленными: задав конкретный байт, не представляет труда создать строку байтов, XOR которых дает заданное значение. С однонаправленной хэш-функцией такого не выйдет. Хорошей однонаправленной хэш-функцией является хэш-функция без столкновений- трудно создать два прообраза с одинаковым значением хэш -функции.
Хэш-функция является открытой, тайны ее расчета не существует. Безопасность однонаправленной хэш-функцией заключается именно в ее однонаправленности. У выхода нет видимой зависимости от входа . Изменение одного бита прообраза приводи к изменению, в среднем, половины битов значения хэш -функции. Вычислительно невозможно найти прообраз, соответствующий заданному значению хэш -функции.
Посмотрите на это как на способ получить характерные признаки файлов . Если вы хотите проверить, что у кого-то есть тот же файл, что и у вас, но вы не хотите, чтобы этот файл был передан вам, попросите послать вам значение хэш-функции. Если присланное значение хэш-функции совпадет с рассчитанным вами, то почти наверняка чужой файл совпадает с вашим. Это особенно полезно при финансовых транзакциях, когда вы не хотите где-то в сети превратить снятие со счета $100 в снятие $1000. В обычных условиях вы можете использовать однонаправленную хэш-функцию без ключа, так что кто угодно может проверить значение хэш -функции. Если нужно, чтобы проверить значение хэш-функции мог только один получатель, прочтите следующий раздел .