книги / Практическая криптография

зать, что искомое z является одним словом и может быть вычислено путем умножения наименее значимого слова числа х на слово-константу, которое зависит только от п. Если наименее значимое слово числа x + zn будет равно нулю, мы можем поделить это число на 2Ш, сдвигая двоичное представление сразу на слово вправо. Это намного быстрее, нежели сдвигать его по биту.

16.3Атаки с использованием побочных каналов

Мы уже затрагивали тему тайминг-атак и других атак с использованием побочных каналов в разделе 9.5. Причина, по которой мы были столь немно­ гословны, состоит отнюдь не в их безобидности. Напротив — наибольшую опасность для криптографических систем с открытым ключом представля­ ют именно тайминг-атаки.

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

Некоторые шифры требуют программных реализаций, применяющих раз­ личные пути кода для обработки тех или иных частных случаев. В качестве примера таких шифров можно привести IDEA [60, 61] и MARS [13]. Другие шифры используют операции процессора, время выполнения которых зави­ сит от обрабатываемых данных. У некоторых процессоров время выполнения умножения (используемого шифрами RC6 [77] и MARS) или циклического сдвига битов (используемого шифрами RC6 и RC5), величина которого за­ висит от данных, во многом определяется спецификой входных данных. Все это делает возможным осуществление тайминг-атак. Отметим, что функции, с которыми мы работали при написании этой книги, подобные типы операций не используют.

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

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

Еще один метод борьбы с тайминг-атаками — стандартизация времени вы­ полнения операции. В процессе разработки системы мы выбираем длитель­ ность d, которая превышает любое потенциальное время выполнения данного вычисления. Затем мы замечаем момент времени £, в который было нача­ то вычисление, и выжидаем по окончании вычисления до момента времени t + d. Данная идея подразумевает несколько расточительное использование системных ресурсов, но вообще-то она неплоха. Нам нравится это решение, но оно защищает систему только от тайминг-атак в “чистом” виде. Если зло­ умышленник способен измерять выдаваемое компьютером радиоизлучение или, скажем, потребление памяти, он, вероятно, сможет обнаружить задерж­ ку между фактическим окончанием вычисления и моментом времени t + d. Это, в свою очередь, позволит злоумышленнику осуществлять тайминг-атаки наравне с атаками других типов. Тем не менее для проведения атаки, осно­ ванной на измерении радиоизлучения, злоумышленник должен находиться в непосредственной близости от атакуемой машины. Это значительно сокра­ щает вероятность угрозы по сравнению с тайминг-атаками, которые с успехом можно осуществлять и через Internet.

Помимо всего прочего, для защиты от тайминг-атак можно применять методы, основанные на использовании слепых подписей [55]. Такие методы позволяют скрыть практически все различия во времени выполнения неко­ торых типов вычислений.

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

каждой операции с участием открытого ключа, но и время, которое прохо­ дит между принятием запроса и отправкой ответа. Если запрос поступает в момент времени £, мы должны отправить ответ в момент времени t + С, где С — некоторая константа. Впрочем, чтобы окончательно исключить вся­ кую возможность утечки информации о времени выполнения вычислений, нам следовало бы гарантировать, что ответ на запрос действительно будет готов к моменту времени t + С. Для достижения этой цели частоту принятия входных запросов, вероятно, понадобится ограничить до некоторого фикси­ рованного верхнего уровня.

16.4 Протоколы

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

Более правильно сохранять явное состояние протокола и обновлять его каждый раз при получении нового сообщения. Реализовать данный подход несколько сложнее, но в то же время он обеспечивает гораздо больше гибко­ сти, нежели предыдущий.

16.4.1Выполнение протоколов поверх безопасного канала общения

Многие криптографические протоколы выполняются поверх небезопас­ ных каналов общения. Иногда, впрочем, имеет смысл запускать протокол поверх безопасного канала общения. В качестве примера можно привести ситуацию, когда каждый пользователь взаимодействует с центром распро­ странения ключей (ЦРК) по безопасному каналу общения. ЦРК применяет простой протокол для распространения ключей между пользователями си­ стемы, чтобы те могли общаться друг с другом. (Что-то подобное выполняет протокол Kerberos.) Если вы применяете криптографический протокол для взаимодействия с участником, с которым вы уже обменялись ключом, сле­ дует использовать полную функциональность безопасного канала общения. В частности, требуется реализовать защиту от атак воспроизведения. Это не составит труда, зато позволит предотвратить большое количество атак на криптографические протоколы.

Иногда наличие безопасного канала общения позволяет сократить функ­ циональность протокола. Например, если безопасный канал общения обес­ печивает защиту от атак воспроизведения, самому протоколу этого делать не нужно. Тем не менее старое доброе правило модуляризации гласит, что протокол должен минимизировать свою зависимость от безопасного канала общения.

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

16.4.2Получение сообщения

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

• И дентиф икатор протокола. В точности идентифицирует протокол

и его версию. Особо важную роль здесь играют идентификаторы версий.

•И дентиф икатор экземпляра протокола. Идентифицирует, к како­ му экземпляру протокола принадлежит данное сообщение. Пользовате­ ли А и Б могут одновременно запустить два сеанса протокола согласо­ вания ключей, и мы не хотим их перепутать.

•И дентиф икатор сообщения. Идентифицирует сообщение в рамках заданного протокола. Самый легкий способ идентификации — просто пронумеровать сообщения.

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

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

318 Глава 16. Проблемы реализации. Часть II

Если полученное сообщение действительно имеет номер п, значит, все в порядке. Просто обработайте его в соответствии с правилами протокола. Но что, если номер сообщения будет другим?

Если номер полученного сообщения больше п или меньше п — 1, это сви­ детельствует о том, что в системе не все в порядке. Подобное сообщение не могло быть сгенерировано системой, а значит, является подделкой. Содержи­ мое такого сообщения следует проигнорировать.

Если полученное сообщение имеет номер п —1, значит, отправленное со­ общение п могло быть утеряно. По крайней мере это могло случиться, если протокол выполняется поверх ненадежного транспортного уровня. Посколь­ ку мы хотим минимизировать зависимость протокола от других частей си­ стемы, то предполагаем именно наличие ненадежного канала общения.

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

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

Если протокол выполняется поверх небезопасного канала общения, тогда отправка каждого из отброшенных сообщений могла быть делом рук зло­ умышленника, пытающегося вмешаться в выполнение протокола. В идеале нам нужно было бы проигнорировать сообщения злоумышленника и просто завершить протокол. Это, конечно же, не всегда возможно. Например, если поддельное сообщение п - 1 дойдет до нас первым, мы отправим ответ. Ес­ ли позднее мы получим “настоящее” сообщение п - 1, то будем вынуждены его проигнорировать. Разрешить данную проблему невозможно, поскольку мы не можем отправить второй ответ, не подвергая риску безопасность си­ стемы. Но мы не знаем, какое из двух полученной сообщений с номером п - 1 было настоящим. Поэтому следует просто занести в журнал сведения об ошибке, вызванной получением второго сообщения с номером п —1, и про­

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

16.4.3Время ожидания

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

Самый простой способ реализовать время ожидания — это отсылать со­ стоянию протокола сообщения об истекшем времени. Для контроля за вре­ менем ожидания можно применять таймеры, значения которых явно уста­ навливаются протоколом, или же сообщения, которые отсылаются каждые несколько секунд или около того.

Одним из распространенных типов атак является отправка на конкрет­ ный компьютер огромного количества сообщений типа “начало протокола”. Каждый раз, когда система получает подобное сообщение, она инициирует новое состояние выполнения протокола. Через несколько миллионов подоб­ ных сообщений у компьютера заканчивается память и система “зависает”. В качестве хорошего примера подобной атаки можно привести синхронную атаку (SYN flood attack). Защититься от таких атак очень сложно, но они показывают, как важно удалять устаревшие состояния протокола. Если вы­ полнение протокола замерло и не возобновляется в течение слишком долгого времени, его состояние необходимо удалить.

Величина времени ожидания постоянно является предметом ожесточен­ ных споров. По своему опыту мы знаем, что пакет, отправленный по Internet, доходит до адресата примерно через секунду или же не доходит вообще. Если в течение пяти секунд на сообщение не было получено ответа, имеет смысл отправить его еще раз. Трех попыток должно быть вполне достаточно; если уровень потери сообщений настолько высок, что мы потеряли четыре по­ следовательных сообщения за 15 с, данное соединение вряд ли годится для выполнения протокола. Мы предпочитаем проинформировать пользователя о проблеме уже через 20 с, а не заставлять его пребывать в напрасном ожи­ дании ответа несколько минут или более.

Часть III

Управление ключами

Глава 17

Часы

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

17.1Зачем нужны часы

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

17.1.1Срок действия

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

17.1.2 Уникальные значения

Еще одной удобной особенностью текущего времени является возмож­ ность применять его в качестве уникального значения в рамках одного ком­

пьютера. В предыдущих главах не раз упоминались оказии. Важным свой­ ством оказии является то, что никакое ее значение не используется дважды, по крайней мере на протяжении заданного периода времени. Иногда этот пе­ риод времени ограничен, например использование оказии в рамках сеанса безопасного канала общения. В этой ситуации оказию можно генерировать с помощью счетчика. В других случаях оказия должна оставаться уникаль­ ной до следующей перезагрузки компьютера. Существует два универсальных способа генерации значений оказии. Первый заключается в использовании те­ кущего времени часов совместно с некоторым механизмом, гарантирующим, что одно и то же значение времени никогда не будет использовано дважды. Второй способ подразумевает использование генератора псевдослучайных чи­ сел, который рассматривается в главе 10, “Генерация случайных чисел”. Недо­ статком использования случайной оказии является то, что она должна быть очень большой. Чтобы достигнуть уровня безопасности в 128 бит, следова­ ло бы использовать 256-битовую оказию. Не все криптографические функции поддерживают оказии таких размеров. Более того, на некоторых платформах очень сложно реализовать генератор псевдослучайных чисел. В качестве за­ мечательного альтернативного способа генерации оказий можно предложить надежные часы.

17.1.3Монотонность

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

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