Открытый и закрытый ключ: для чего они применяются? Ключи шифрования Для чего нужны ключи шифрования
Безопасность зашифрованных данных обеспечивается не только сильными алгоритмами шифрования. Несоблюдение принципов использования ключей шифрования может поставить под угрозу защищенность информации даже при том, что в системе будут реализованы самые криптостойкие алгоритмы.
Предположим, есть два пользователя (назовем их I и J), решивших обмениваться зашифрованными сообщениями через Интернет. Посмотрим, как можно это сделать, на примере комплексного метода шифрования.
Комплексный метод
Этот метод применения алгоритмов симметричного и асимметричного шифрования устраняет ряд недостатков, свойственных каждому из них при раздельном применении. Итак, чтобы обменяться зашифрованными сообщениями через Интернет, пользователям I и J необходимо предварительно сделать следующее.
1. Выбрать алгоритмы шифрования и их параметры. Вспомним (см. статью , "BYTE/Россия" No 8"2003), что каждый алгоритм имеет множество параметров, которые должны быть идентичны, - иначе даже при наличии правильного ключа шифрования будет невозможно расшифровать информацию. Например, для алгоритма ГОСТ 28147-89 должны быть согласованы таблицы замен, используемый режим алгоритма и принципы формирования синхропосылок.
2. Сгенерировать свои ключи асимметричного шифрования. Пользователь I генерирует пару ключей KsI (secret - секретный) и KpI (publIc - открытый), пользователь J создает пару KsJ и KpJ.
3. Обменяться открытыми ключами или сделать их доступными друг другу. Предположим, что открытые ключи KpI и KpJ пользователи пересылают друг другу по электронной почте.
Не будем рассматривать здесь проблему перехвата открытых ключей при передаче и их подмены злоумышленником - это тема отдельного разговора. Предположим, ключи успешно переданы и получены, после чего можно отправлять зашифрованное сообщение. Это и делает пользователь J, отправляя пользователю I сообщение M.
Процесс обмена иллюстрирует рис. 1. Перед передачей сообщения пользователь J создает случайный ключ симметричного шифрования (назовем его Ksimm). Пользователь J асимметрично зашифровывает ключ Ksimm на открытом ключе пользователя I KpI и отправляет зашифрованный ключ пользователю I. Затем пользователь J зашифровывает ключом Ksimm сообщение M, и полученный шифртекст C отсылается пользователю I. Пользователь I получает зашифрованный ключ Ksimm и асимметрично расшифровывает его своим секретным ключом KsI. С помощью полученного ключа Ksimm пользователь I расшифровывает сообщение M.
Как было отмечено выше, недостатки алгоритмов симметричного и асимметричного шифрования при их совместном использовании частично компенсируются. В частности, скрытое распространение ключей симметричного шифрования достигается за счет того, что симметричный ключ Ksimm, на котором шифруется собственно информация, передается по открытым каналам связи в зашифрованном виде - для его зашифрования используется асимметричный алгоритм, не имеющий проблем с секретностью. Проблемы малой скорости асимметричного шифрования в данном случае практически не возникает, поскольку асимметричным алгоритмом шифруется только короткий ключ Ksimm, а все данные шифруются быстрым симметричным алгоритмом. Результат - быстрое шифрование в сочетании с удобным обменом ключами.
Ключевые схемы
Манипуляции с зашифрованием ключа Ksimm и его передачей вместе с сообщением являют собой пример ключевой схемы (так называются схемы использования ключей шифрования). В общем случае для разработки какой-либо системы, позволяющей шифровать файлы или сообщения, недостаточно просто реализовать алгоритм шифрования. Необходимо также продумать принципы генерации, передачи, хранения и использования ключей шифрования: так как недостаточная защита ключей на любом из этих этапов или неправильное их применение поставит под угрозу всю зашифрованную информацию. Ведь любая "слабость" этапов шифрования даст возможность злоумышленнику атаковать систему защиты с тем, чтобы получить ключ шифрования вместо того, чтобы пытаться взломать сильный криптоалгоритм. И если он сделает это достаточно грамотно - секретов от него уже не будет.
Рассмотрим типичные ключевые схемы, но для начала введем ряд определений (см. врезку "Типы шифрования").
Абонентское шифрование
Представленная на рис. 1 схема - простой пример абонентского шифрования. Ясно, что это не единственно возможная ключевая схема - вариантов таких схем великое множество, конкретный же выбирается, исходя из требований функциональности и безопасности конкретной системы защиты. В общем случае существует два вида ключевых элементов: файловые и долговременные.
Файловые ключи предназначены для шифрования собственно информации. Часто их название соответствует конкретному виду шифруемых данных: пакетные, сеансовые или дисковые. Обычно такие ключи генерируются случайным образом для каждого шифруемого объекта, например, для каждого файла, сообщения электронной почты, а иногда и IP-пакета. В нашем примере с пользователями I и J ключ Ksimm - это файловый ключ.
Долговременные ключи используются для шифрования и передачи файловых. В схеме на рис. 1 ключ KpI - долговременный.
Конечно, это не означает, что для шифрования любого объекта используется ровно два ключа: файловый плюс долговременный. Ниже мы рассмотрим пример ключевой схемы, в которой для шифрования файлового ключа используется суперпозиция двух долговременных ключей различного назначения. Кроме того, между файловым и долговременным ключами могут располагаться промежуточные, также получаемые с помощью датчика случайных чисел (например, файловый ключ шифруется на промежуточном, который, в свою очередь, шифруется на долговременном).
Независимо от количества ключей, используемых для шифрования конкретного объекта, существует некий особый долговременный ключ, на котором построена вся защита. Если такой ключ попадет в руки злоумышленника, защищенный объект будет им расшифрован независимо от количества других используемых при шифровании ключей. Именно этот ключ необходимо хранить, не допуская его компрометации (т. е. утери или хищения).
Обычно для хранения подобных ключей используется некий персональный ключевой носитель: дискета, смарт-карта, USB-токен, iButton и т. д., который всегда должен находиться у пользователя - владельца ключа. На схеме с рис. 1 такой ключевой элемент в явном виде отсутствует - это секретный ключ пользователя I, KsI, который должен находиться только у пользователя I. В противном случае злоумышленник, завладевший ключом KsI, легко расшифрует сообщение (сначала с помощью ключа KsI расшифровывается ключ Ksimm, а затем - и само сообщение).
Архивное шифрование
Схема архивного шифрования (рис. 2) очень похожа на описанную выше схему абонентского шифрования. Основное различие между ними только в том, что при шифровании файлов "для себя" (т. е. для хранения в зашифрованном виде на своем компьютере) не возникает проблем с распределением ключей шифрования. Это означает, что асимметричное шифрование в этом случае попросту не нужно, поэтому файловый ключ шифруется на долговременном с помощью симметричного алгоритма.
 |
Рис. 2. Архивное шифрование. |
Может показаться, что в данном случае нет логики в использовании файлового ключа: почему бы не шифровать файл непосредственно на долговременном ключе, не затрачивая время и ресурсы на генерацию, шифрование и передачу файлового? Однако использование файлового ключа (помимо описанного выше комбинирования симметричных и асимметричных алгоритмов) преследует иные цели.
Во-первых, уменьшается статистическая нагрузка на долговременный ключ (т. е. долговременным ключом шифруются только короткие файловые ключи, а файловые ключи каждый раз разные) - это существенно снижает вероятность успеха тех атак на долговременный ключ, которые используют большие объемы зашифрованной на конкретном ключе информации.
Во-вторых, при перешифровании (плановом или при компрометации ключа) зашифрованного объекта с одного долговременного ключа на другой достаточно лишь перешифровать короткий файловый ключ, хранящийся в заголовке. Сам же объект может быть сколь угодно большим - например, весь логический диск компьютера. Не стоит пугаться сложности схем архивного и абонентского шифрования - приведенные на них операции выполняются программами шифрования автоматически. Пользователь лишь указывает защищаемый файл и задает дополнительные параметры, например, на каком ключе или для какого пользователя нужно его шифровать.
Прозрачное шифрование
При прозрачном шифровании от пользователя обычно требуется лишь однократная настройка системы, после чего все, что необходимо, будет зашифровываться автоматически.
В настоящее время существует множество программ шифрования логических дисков. Большинство из них создают виртуальный логический диск, который физически представляет собой файл-контейнер, размещаемый на одном из существующих в системе логических дисков. Обычно пользователю достаточно один раз настроить программу прозрачного шифрования. Для этого он должен создать файл-контейнер, задать его размер, создать долговременный ключ шифрования логического диска (или задать пароль, из которого будет формироваться долговременный ключ) и т. д. При предъявлении данного долговременного ключа контейнер предстанет перед пользователем в виде дополнительного логического диска с прозрачным шифрованием: при записи на такой логический диск файлы автоматически зашифровываются, при чтении - расшифровываются.
Ключевая схема такого шифрования очень схожа с представленной на рис. 2. Разница лишь в том, что файловый ключ создается не для каждого записываемого на логический диск файла, а для всего логического диска (отсюда и название - дисковый ключ), и каждая из операций (получение дискового ключа с помощью датчика случайных чисел, его зашифрование на долговременном ключе и запись в заголовок виртуального логического диска) выполняется при создании файла-контейнера однократно. Если пользователь предъявляет верный долговременный ключ, то хранящийся в заголовке файловый ключ расшифровывается и участвует в дальнейших операциях шифрования файлов данного логического диска.
Трехключевая схема
Вернемся ненадолго к абонентскому шифрованию. Бывает, что в этом случае применяются только симметричные алгоритмы без асимметричного шифрования (хотя бы из-за того, что отечественный стандарт на алгоритм асимметричного шифрования попросту отсутствует). При этом предполагается, что ключи симметричного шифрования распространяются до начала использования такой системы по доверенным каналам связи (например, курьером).
Для этих ключей очень часто используется матрица размерностью N x N (где N - количество пользователей системы), в каждой ячейке которой содержится ключ парной связи - ключ для двух конкретных пользователей системы (номер каждого соответствует номерам строки и столбца ячейки с их ключом парной связи) для передачи зашифрованных сообщений только между ними. Соответственно любому другому пользователю системы, не говоря уж о внешних пользователях или злоумышленниках, зашифрованная таким образом информация будет недоступна.
Такая матрица ключей генерируется выделенным администратором безопасности, а не самими пользователями, причем последние получают лишь строки матрицы с набором ключей парной связи между конкретным пользователем и остальными пользователями системы. Такая строка называется сетевым набором.
Рассмотрим пример использования сетевого набора (рис. 3). В принципе его можно целиком хранить на персональном ключевом носителе, используя тот или иной ключ парной связи по мере необходимости. Однако при большом числе пользователей памяти ключевого носителя может просто не хватить. Поэтому сетевые наборы обычно хранят непосредственно на жестком диске компьютера, предварительно зашифровав их на еще одном ключе (такой ключ часто называется главным).
Как видно, долговременный ключевой элемент, на котором шифруется файловый, в данной схеме в явном виде отсутствует - это результат расшифрования на главном ключе ключа парной связи, который записан на жестком диске. В этом случае на персональном ключевом носителе можно хранить только главный ключ, поскольку именно он обеспечивает секретность остальных элементов ключевой схемы.
Формат зашифрованного объекта
Осталось сказать несколько слов о заголовке зашифрованного объекта. Очевидно, что необходим некий элемент, контролирующий правильность расшифрования объекта. Иначе при какой-либо ошибке расшифрования (например, при несовпадении параметров алгоритма, использовании неверного долговременного ключа и т. д.) невозможно будет понять, правильно ли расшифрованы данные (конечно, это не относится к случаю банального обмена зашифрованными текстовыми сообщениями, где корректность расшифрования можно проверить визуально). Такой элемент размещается в заголовке объекта, и обычно его роль выполняет имитоприставка (или любая другая контрольная сумма) исходных данных, вычисляемая на файловом ключе.
Имитоприставка вычисляется перед зашифрованием, записывается в заголовок, а после расшифрования ее значение вычисляется повторно и сравнивается с хранящимся в заголовке. Кроме того, чтобы не расшифровывать весь объект, в его заголовке хранится и другая имитоприставка - файлового ключа, которая вычисляется на долговременном ключе перед зашифрованием файлового и проверяется после его /расшифрования, но (!) до расшифрования всего объекта. С помощью этой второй имитоприставки можно легко диагностировать большинство ошибок расшифрования на ранней стадии.
Итак, зашифрованный объект обычно содержит как минимум следующие данные:
- собственно информация, зашифрованная на файловом ключе;
- файловый ключ, зашифрованный на долговременном ключе;
- имитоприставка файлового ключа на долговременном ключе;
- имитоприставка исходных данных на файловом ключе.
***
Описанные в данной статье ключевые схемы - не единственно возможные. В зависимости от целей конкретной системы защиты информации ключевые схемы могут быть как существенно более сложными, так и совсем простыми. Главное - ключевая схема не должна быть "слабым звеном" всей системы.
Какие бывают шифры
Что такое шифрование и дешифрование
Лекция 5. Кодирование и шифрование. Защита информации
Проблема защиты информации от несанкционированного доступа заметно обострилась в связи с широким распространением компьютерных сетей (особенно глобальных). Защита информации необходима для уменьшения вероятности разглашения, утечки, умышленного искажения, утраты или уничтожения информации, представляющей определенную ценность для ее владельца.
В настоящее время проблемами защиты информации занимается криптология , которая разделяется на два направления.
Криптография - наука о защите информации от несанкционированного получения ее посторонними лицами. Сфера ее интересов - разработка и исследование методов шифрования информации.
Сфера интересов криптоанализа противоположная - разработка и исследование методов дешифрования шифрограммы даже без знания ключа.
Под ключом понимается секретная информация, определяющая, какое преобразование из множества возможных преобразований выполняется в данном случае над открытым текстом.
Дешифрование - обратный шифрованию процесс. На основе ключа зашифрованный текст преобразуется в исходный открытый. Процесс получения открытого сообщения из шифрованного без заранее известного ключа называется вскрытием или взломом шифра.
Существует несколько классификаций шифров.
По характеру использования ключа алгоритмы шифрования можно разделить на симметричные и несимметричные .
В первом случае в шифраторе отправителя и дешифраторе получателя используется один и тот же ключ.
Во втором случае получатель вначале по открытому каналу передает отправителю открытый ключ, с помощью которого отправитель шифрует информацию. При получении информации получатель дешифрует ее с помощью второго секретного ключа.
При оценке эффективности шифра обычно руководствуются правилом Керкхоффа, согласно которому стойкость шифра определяется только секретностью ключа, т.е. известны все детали алгоритма шифрования и дешифрования, но неизвестен ключ.
Криптостойкостью называется характеристика шифра, определяющая его устойчивость к дешифрованию без знания ключа.
Алгоритмы шифрования с открытым ключом используют так называемые необратимые функции, которые обладают следующим свойством. При заданном значении аргумента х относительно просто вычислить значение функции f(x), однако, если известно значение функции f(x), то нет простого пути для вычисления значения аргумента х.
Все используемые в настоящее время криптосистемы с открытым ключом опираются на один из следующих типов необратимых преобразований:
· Разложение больших чисел на простые множители (алгоритм RSA).
· Вычисление логарифма или возведение в степень (алгоритм DH).
· Вычисление корней алгебраических уравнений.
Например, легко в уме найти произведение двух простых чисел 11 и 13 (143). Но попробуйте быстро в уме найти два простых числа, произведение которых равно 437 (19 и 23). Такие же трудности возникают и при использовании вычислительной техники (можно, но долго). Таким образом, в системе кодирования, основанной на разложении на множители, используются два разных ключа. Ключ шифрования основан на произведении двух огромных простых чисел, а ключ дешифрования - на самих простых числах.
Было предложено (в 40-х годах 20-го века) разрабатывать шифр так, чтобы его раскрытие было эквивалентно решению сложной математической задачи. Сложность задачи должна быть такой, чтобы объем необходимых вычислений превосходил бы возможности современных ЭВМ.
В несимметричных системах приходится применять длинные ключи (1024 бит и больше). Это резко увеличивает время шифрования, генерация ключей становится довольно длительной, зато пересылать ключи можно по открытым каналам связи.
В симметричных алгоритмах используют более короткие ключи, поэтому шифрование и дешифрование происходят быстрее. Но рассылка ключей становится сложной процедурой.
В США для передачи секретных сообщений наибольшее распространение получил стандарт DES. Он предусматривает троекратное шифрование данных разными ключами.
На протяжении всего времени дешифрованию криптограмм помогает частотный анализ появления отдельных символов и их сочетаний. Вероятности появления отдельных букв в тексте сильно различаются. Например, в русском языке буква "о" появляется в 45 раз чаще буквы "ф" и в 30 раз чаще буквы "э". Анализируя достаточно длинный текст, зашифрованный методом замены, можно по частотам появления символом произвести замену и восстановить исходный текст.
По мнению некоторых специалистов, нет нераскрываемых шифров. Рассекретить любую шифрограмму можно либо за большое время, либо за большие деньги (использование нескольких суперкомпьютеров).
Есть и другое мнение. Если длина ключа равна длине сообщения, а ключ генерируется из случайных чисел с равновероятным распределением и меняется с каждым новым сообщением, то шифр невозможно взломать даже теоретически.
Количество информации в ключе, как правило, измеряется в битах.
Для современных симметричных алгоритмов (AES, CAST5, IDEA, Blowfish, Twofish) основной характеристикой криптостойкости является длина ключа. Шифрование с ключами длиной 128 бит и выше считается сильным, так как для расшифровки информации без ключа требуются годы работы мощных суперкомпьютеров. Для асимметричных алгоритмов, основанных на проблемах теории чисел (проблема факторизации -- RSA, проблема дискретного логарифма -- Elgamal) в силу их особенностей минимальная надёжная длина ключа в настоящее время -- 1024 бит. Для асимметричных алгоритмов, основанных на использовании теории эллиптических кривых (ECDSA, ГОСТ Р 34.10-2001, ДСТУ 4145-2002), минимальной надёжной длиной ключа считается 163 бит, но рекомендуются длины от 191 бит и выше.
В этой методологии и для шифрования, и для расшифровки отправителем и получателем применяется один и тот же ключ, об использовании которого они договорились до начала взаимодействия. Если ключ не был скомпрометирован, то при расшифровке автоматически выполняется аутентификация отправителя, так как только отправитель имеет ключ, с помощью которого можно зашифровать информацию, и только получатель имеет ключ, с помощью которого можно расшифровать информацию. Так как отправитель и получатель -- единственные люди, которые знают этот симметричный ключ, при компрометации ключа будет скомпрометировано только взаимодействие этих двух пользователей. Проблемой, которая будет актуальна и для других криптосистем, является вопрос о том, как безопасно распространять симметричные (секретные) ключи.
Алгоритмы симметричного шифрования используют ключи не очень большой длины и могут быстро шифровать большие объемы данных.
Порядок использования систем с симметричными ключами:
Безопасно создается, распространяется и сохраняется симметричный секретный ключ.
Отправитель создает электронную подпись с помощью расчета хэш-функции для текста и присоединения полученной строки к тексту
Отправитель использует быстрый симметричный алгоритм шифрования-расшифровки вместе с секретным симметричным ключом к полученному пакету (тексту вместе с присоединенной электронной подписью) для получения зашифрованного текста. Неявно таким образом производится аутентификация, так как только отправитель знает симметричный секретный ключ и может зашифровать этот пакет. Только получатель знает симметричный секретный ключ и может расшифровать этот пакет.
Отправитель передает зашифрованный текст. Симметричный секретный ключ никогда не передается по незащищенным каналам связи.
Получатель использует тот же самый симметричный алгоритм шифрования-расшифровки вместе с тем же самым симметричным ключом (который уже есть у получателя) к зашифрованному тексту для восстановления исходного текста и электронной подписи. Его успешное восстановление аутентифицирует кого-то, кто знает секретный ключ.
Получатель отделяет электронную подпись от текста.
Получатель создает другую электронную подпись с помощью расчета хэш-функции для полученного текста.
Получатель сравнивает две этих электронных подписи для проверки целостности сообщения (отсутствия его искажения)
Доступными сегодня средствами, в которых используется симметричная методология, являются:
Kerberos, который был разработан для аутентификации доступа к ресурсам в сети, а не для верификации данных. Он использует центральную базу данных, в которой хранятся копии секретных ключей всех пользователей.
Сети банкоматов (ATM BankingNetworks). Эти системы являются оригинальными разработками владеющих ими банков и не продаются. В них также используются симметричные методологии.
Сравнение с асимметричными криптосистемами
Достоинства
скорость (по данным AppliedCryptography -- на 3 порядка выше)
простота реализации (за счёт более простых операций)
меньшая требуемая длина ключа для сопоставимой стойкости
изученность (за счёт большего возраста)
Недостатки
сложность управления ключами в большой сети. Означает квадратичное возрастание числа пар ключей, которые надо генерировать, передавать, хранить и уничтожать в сети. Для сети в 10 абонентов требуется 45 ключей, для 100 уже 4950, для 1000 -- 499500 и т. д.
сложность обмена ключами. Для применения необходимо решить проблему надёжной передачи ключей каждому абоненту, так как нужен секретный канал для передачи каждого ключа обеим сторонам.
Для компенсации недостатков симметричного шифрования в настоящее время широко применяется комбинированная (гибридная криптографическая схема), где с помощью асимметричного шифрования передаётся сеансовый ключ, используемый сторонами для обмена данными с помощью симметричного шифрования.
Важным свойством симметричных шифров является невозможность их использования для подтверждения авторства, так как ключ известен каждой стороне.
В этой методологии ключи для шифрования и расшифровки разные, хотя и создаются вместе. Один ключ делается известным всем, а другой держится в тайне. Хотя можно шифровать и расшифровывать обоими ключами, данные, зашифрованные одним ключом, могут быть расшифрованы только другим ключом.
Все асимметричные криптосистемы являются объектом атак путем прямого перебора ключей, и поэтому в них должны использоваться гораздо более длинные ключи, чем те, которые используются в симметричных криптосистемах, для обеспечения эквивалентного уровня защиты. Это сразу же сказывается на вычислительных ресурсах, требуемых для шифрования, хотя алгоритмы шифрования на эллиптических кривых могут смягчить эту проблему. Брюс Шнейер в книге «Прикладная криптография: протоколы, алгоритмы и исходный текст на C» приводит следующие данные об эквивалентных длинах ключей.
Для того чтобы избежать низкой скорости алгоритмов асимметричного шифрования, генерируется временный симметричный ключ для каждого сообщения и только он шифруется асимметричными алгоритмами. Само сообщение шифруется с использованием этого временного сеансового ключа и алгоритма шифрования/расшифровки. Затем этот сеансовый ключ шифруется с помощью открытого асимметричного ключа получателя и асимметричного алгоритма шифрования. После этого этот зашифрованный сеансовый ключ вместе с зашифрованным сообщением передается получателю. Получатель использует тот же самый асимметричный алгоритм шифрования и свой секретный ключ для расшифровки сеансового ключа, а полученный сеансовый ключ используется для расшифровки самого сообщения.
В асимметричных криптосистемах важно, чтобы сеансовые и асимметричные ключи были сопоставимы в отношении уровня безопасности, который они обеспечивают. Если используется короткий сеансовый ключ (например, 40-битовый DES), то не имеет значения, насколько велики асимметричные ключи. Хакеры будут атаковать не их, а сеансовые ключи. Асимметричные открытые ключи уязвимы к атакам прямым перебором отчасти из-за того, что их тяжело заменить. Если атакующий узнает секретный асимметричный ключ, то будет скомпрометирован не только текущее, но и все последующие взаимодействия между отправителем и получателем.
Порядок использования систем с асимметричными ключами:
Безопасно создаются и распространяются асимметричные открытые и секретные ключи. Секретный асимметричный ключ передается его владельцу. Открытый асимметричный ключ хранится в базе данных X.500 и администрируется центром выдачи сертификатов (по-английски -- CertificationAuthority или CA). Подразумевается, что пользователи должны верить, что в такой системе производится безопасное создание, распределение и администрирование ключами. Более того, если создатель ключей и лицо или система, администрирующие их, не одно и то же, то конечный пользователь должен верить, что создатель ключей на самом деле уничтожил их копию.
Создается электронная подпись текста с помощью вычисления его хэш-функции. Полученное значение шифруется с использованием асимметричного секретного ключа отправителя, а затем полученная строка символов добавляется к передаваемому тексту (только отправитель может создать электронную подпись).
Создается секретный симметричный ключ, который будет использоваться для шифрования только этого сообщения или сеанса взаимодействия (сеансовый ключ), затем при помощи симметричного алгоритма шифрования/расшифровки и этого ключа шифруется исходный текст вместе с добавленной к нему электронной подписью -- получается зашифрованный текст (шифр-текст).
Теперь нужно решить проблему с передачей сеансового ключа получателю сообщения.
Отправитель должен иметь асимметричный открытый ключ центра выдачи сертификатов (CA). Перехват незашифрованных запросов на получение этого открытого ключа является распространенной формой атаки. Может существовать целая система сертификатов, подтверждающих подлинность открытого ключа CA. Стандарт X.509 описывает ряд методов для получения пользователями открытых ключей CA, но ни один из них не может полностью защитить от подмены открытого ключа CA, что наглядно доказывает, что нет такой системы, в которой можно было бы гарантировать подлинность открытого ключа CA.
Отправитель запрашивает у CA асимметричный открытый ключ получателя сообщения. Этот процесс уязвим к атаке, в ходе которой атакующий вмешивается во взаимодействие между отправителем и получателем и может модифицировать трафик, передаваемый между ними. Поэтому открытый асимметричный ключ получателя «подписывается» CA. Это означает, что CA использовал свой асимметричный секретный ключ для шифрования асимметричного открытого ключа получателя. Только CA знает асимметричный секретный ключ CA, поэтому есть гарантии того, что открытый асимметричный ключ получателя получен именно от CA.
После получения асимметричный открытый ключ получателя расшифровывается с помощью асимметричного открытого ключа CA и алгоритма асимметричного шифрования/расшифровки. Естественно, предполагается, что CA не был скомпрометирован. Если же он оказывается скомпрометированным, то это выводит из строя всю сеть его пользователей. Поэтому можно и самому зашифровать открытые ключи других пользователей, но где уверенность в том, что они не скомпрометированы?
Теперь шифруется сеансовый ключ с использованием асимметричного алгоритма шифрования-расшифровки и асимметричного ключа получателя (полученного от CA и расшифрованного).
Зашифрованный сеансовый ключ присоединяется к зашифрованному тексту (который включает в себя также добавленную ранее электронную подпись).
Весь полученный пакет данных (зашифрованный текст, в который входит помимо исходного текста его электронная подпись, и зашифрованный сеансовый ключ) передается получателю. Так как зашифрованный сеансовый ключ передается по незащищенной сети, он является очевидным объектом различных атак.
Получатель выделяет зашифрованный сеансовый ключ из полученного пакета.
Теперь получателю нужно решить проблему с расшифровкой сеансового ключа.
Получатель должен иметь асимметричный открытый ключ центра выдачи сертификатов (CA).
Используя свой секретный асимметричный ключ и тот же самый асимметричный алгоритм шифрования получатель расшифровывает сеансовый ключ.
Получатель применяет тот же самый симметричный алгоритм шифрования-расшифровки и расшифрованный симметричный (сеансовый) ключ к зашифрованному тексту и получает исходный текст вместе с электронной подписью.
Получатель отделяет электронную подпись от исходного текста.
Получатель запрашивает у CA асимметричный открытый ключ отправителя.
Как только этот ключ получен, получатель расшифровывает его с помощью открытого ключа CA и соответствующего асимметричного алгоритма шифрования-расшифровки.
Затем расшифровывается хэш-функция текста с использованием открытого ключа отправителя и асимметричного алгоритма шифрования-расшифровки.
Повторно вычисляется хэш-функция полученного исходного текста.
Две эти хэш-функции сравниваются для проверки того, что текст не был изменен.
Особенности системы
Применение
Алгоритмы криптосистемы с открытым ключом можно использовать
Как самостоятельные средства для защиты передаваемой и хранимой информации
Как средства распределения ключей. Обычно с помощью алгоритмов криптосистем с открытым ключом распределяют ключи, малые по объёму. А саму передачу больших информационных потоков осуществляют с помощью других алгоритмов.
Как средства аутентификации пользователей.
Преимущества: Преимущество асимметричных шифров перед симметричными шифрами состоит в отсутствии необходимости предварительной передачи секретного ключа по надёжному каналу.
В симметричной криптографии ключ держится в секрете для обеих сторон, а в асимметричной криптосистеме только один секретный.
При симметричном шифровании необходимо обновлять ключ после каждого факта передачи, тогда как в асимметричных криптосистемах пару (E,D) можно не менять значительное время.
В больших сетях число ключей в асимметричной криптосистеме значительно меньше, чем в симметричной.
Недостатки: Преимущество алгоритма симметричного шифрования над несимметричным заключается в том, что в первый относительно легко внести изменения.
Хотя сообщения надежно шифруются, но «засвечиваются» получатель и отправитель самим фактом пересылки шифрованного сообщения.
Несимметричные алгоритмы используют более длинные ключи, чем симметричные. Ниже приведена таблица, сопоставляющая длину ключа симметричного алгоритма с длиной ключа несимметричного алгоритма с аналогичной криптостойкостью:
Процесс шифрования-расшифрования с использованием пары ключей проходит на два-три порядка медленнее, чем шифрование-расшифрование того же текста симметричным алгоритмом.
В чистом виде асимметричные криптосистемы требуют существенно больших вычислительных ресурсов, потому на практике используются в сочетании с другими алгоритмами.
Для ЭЦП сообщение предварительно подвергается хешированию, а с помощью асимметричного ключа подписывается лишь относительно небольшой результат хеш-функции.
Для шифрования они используются в форме гибридных криптосистем, где большие объёмы данных шифруются симметричным шифром на сеансовом ключе, а с помощью асимметричного шифра передаётся только сам сеансовый ключ.
В криптографии линейным криптоанализом называется метод криптоаналитического вскрытия, использующий линейные приближения для описания работы шифра.
Линейный криптоанализ был изобретён японским криптологом МицуруМацуи (MitsuruMatsui). Предложенный им в 1993 г. (на Еврокрипте-93) алгоритм был изначально направлен на вскрытие DES и FEAL. Впоследствии линейный криптоанализ был распространён и на другие алгоритмы. На сегодняшний день наряду с дифференциальным криптоанализом является одним из наиболее распространённых методов вскрытия блочных шифров. Разработаны атаки наблочные и потоковые шифры.
Открытие линейного криптоанализа послужило толчком к построению новых криптографических схем.
Принцип работы
Криптоанализ происходит в два шага. Первый -- построение соотношений между открытым текстом, шифротекстом и ключом, которые справедливы с высокой вероятностью. Второй -- использование этих соотношений вместе с известными парами открытый текст -- шифротекст для получения битов ключа.
Защита от линейного криптоанализа
Для атаки на блочный шифр с помощью линейного криптоанализа достаточно, как было описано выше, получить линейное соотношение, существенно смещённое по вероятности от 1/2. Соответственно, первая цель при проектировании шифра, стойкого к атаке, -- минимизировать вероятностные смещения, убедиться, что подобное соотношение не будет существовать. Другими словами, необходимо сделать так, чтобы при любом изменении текста или ключа в получающемся шифротексте ровно половина бит меняла своё значение на противоположное, причём каждый бит изменялся с вероятностью 1/2. Обычно это достигается путём выбора высоко нелинейных S-боксов и усилением диффузии.
Данный подход обеспечивает хорошее обоснование стойкости шифра, но чтобы строго доказать защищённость от линейного криптоанализа, разработчикам шифров необходимо учитывать более сложное явление -- эффект линейных оболочек (linearhulleffect).
Несколько более общая теория доказательства защищённости от класса атак, основанных на линейном криптоанализе, базируется на понятии декорреляции. Теория предполагает, чтобы устройство являлось так называемым декорреляционным модулем, эффективно блокирующим распространение традиционных линейных и дифференциальных характеристик. Следует заметить, что шифры, которые оптимальны против некоторого узкого класса атак, обычно слабы против других типов атак.
Управление ключами (УК) является настолько важной и развитой областью криптографии, что требует отдельного и детального рассмотрения. На системы УК возлагается огромный набор различных функций, обеспечение самых разных базовых и вновь приобретенных свойств криптосистем, которые ими укомплектованы. Подобные схемы могут выполнять хранение, пересылку, шифрование (то есть обеспечение конфиденциальности), аутентификацию, «сдачу на хранение» (депонирование) и разделение ключей. Единственным общим свойством систем УК является то, что как результат разнообразных трансформаций они должны снабдить криптосистему ключом (симметричным или асимметричным), на котором и будет произведен основной процесс шифрования документа. Техническая реализация систем управления открытыми ключами (англ. PKI -- PublicKeyInfrastructure)
В зависимости от того, какой тип ключа генерирует в итоге система УК, производится их деление на системы управления, симметричными ключами и системы управления асимметричными ключами. Системы управления симметричными ключами делятся в свою очередь на системы с наличием начальных мастер-ключей и системы с нулевой начальной информацией. Как отдельный материал рассмотрены системы депонирования ключей и системы разделения секрета. К сожалению, данный раздел не может охватить даже половины различных схем УК и криптографических протоколов на их основе -- на сегодняшний день исследователями разработано более сотни различных схем. Все чаще и чаще встречающееся сейчас введение третьего субъекта криптоопераций -- доверенных лиц с различными функциями и полномочиями -- породило целую волну протоколов, обеспечивающих новые свойства криптосистем (апеллируемость, подтверждение даты/времени подписания, депонирование ключей и т. п.).
С предварительной частичной установкой
Все системы управления симметричными ключами вне зависимости от того, сколько участников задействовано в процессе, классифицируются в первую очередь на системы, в которых между субъектами уже установлены защитные каналы (то есть присутствуют секретные мастер-ключи), и на системы в которых этого канала нет. В первом случае основной целью системы управления ключами является либо генерация ключей сеансов, либо обновление ключевой информации, либо, что чаще всего требуется, обмен секретным ключом между двумя абонентами, которые до этого напрямую подобного ключа не имели, хотя цепочка доверенных связей (например, через общего знакомого) уже существовала. Во втором случае, когда два пользователя не обладают никакой общей секретной информацией, им необходимо установить ключ, причем таким образом, чтобы прослушивающий весь обмен сообщениями злоумышленник не смог создать свою «третью» копию ключа.
Случай, когда два абонента уже могут общаться между собой по защищенному каналу, и при этом желают обменяться «свежей» ключевой информацией на самом деле не содержит практически никаких тонкостей. Необходимо только уделить внимание невозможности переотправки злоумышленником перехваченного ранее пакета с такой же информацией. Для этого в систему вводятся автоинкрементные счетчики и/или штампы даты/времени.
Несколько больший интерес представляют системы с тремя субъектами: двумя абонентами и доверенным сервером ключей. В этом случае считается, что сервер обслуживает большое количество равноправных клиентов, с каждым из них у сервера уже установлен защищенный канал связи, т. е. обмен ключами произошел. Теперь на определенном этапе функционирования системы у двух клиентов сервера, никогда до этого не общавшихся, возникло желание обменяться некоей приватной информацией.
В подобной ситуации классический протокол установления ключа сеанса выглядит примерно следующим образом --Вызывающий абонент обозначен А, вызываемый абонент -- В, доверенный сервер -- S, ключ которым априори обменялись А и S -- «A-S», ключ между абонентом В и S -- «B-S».
Ключи без предварительной установки
Задача у протоколов этого класса -- создать на основе сообщений, передаваемых по открытым каналам связи, у двух абонентов идентичную ключевую информацию, причем сделать это так, чтобы любое третье лицо, законспектировавшее все прошедшие переговоры, этого ключа получить не смогло. На первый взгляд задача кажется совсем неразрешимой, но методы достижения этой цели существуют и при этом весьма надежны. Основой для подобных протоколов являются схемы, очень напоминающие асимметричное шифрование.
Первоначально все стороны, участвующие в обмене ключей, договариваются о большом простом числе Р (не являющимся секретом). Любые два абонента (А и В), желающие создать секретный, ключ сеанса:
Создают соответственно два больших случайных числа (а и б), а также их инверсии по модулю р (а-1 modpи b-1 mod p) и держат их на своих системах в секрете.
Вызывающая сторона генерирует ключ сеанса k(k< р-2) и возводит его в степень а по модулю р, после чего отправляет полученное выражение вызываемому абоненту: M1=ka mod p.
Вызываемая сторона возводит полученное сообщение в степень bи отправляет обратно: М2 = (M1b mod p) = (kab mod p}.
Вызывающая сторона дешифрует полученное число инверсией числа а и отправляет обратно: МЗ = (М2-b mod р) = (kb mod p).
Наконец, абонент В дешифрует последнее сообщение инверсией числа b и получает желаемый ключ сеанса: k= (МЗ-b mod p) = (k mod p).
Асимметричная криптография, которая, казалось бы, решила проблему конфиденциальности сообщений без предварительной передачи секретного ключа по защищенному каналу, оказывается, всего лишь перенесла эту проблему в несколько иную область. При поверхностном взгляде на асимметричную систему кажется -- «ищи в сети открытый ключ получателя шифруй им сообщение и -- конфиденциальность достигнута». Но вот тут как раз появляется злоумышленник-посредник -- это он гипотетически мог расположить на множестве серверов в сети свой открытый ключ под именем абонента-получателя и свой почтовый адрес. В дальнейшем при получении любого письма он дешифрует его своим закрытым ключом, читает и пересылает истинному получателю, зашифровав уже на настоящем открытом ключе, который он действительно знает. Не спасают при этом и схемы ЭЦП, если злоумышленник подменил открытые ключи как отправителя, так и получателя. Эти соображения приводят к тому, что предварительный защищенный канал все-таки необходим -- для передачи открытого ключа и почтового адреса или хотя бы какого-либо подтверждающего блока данных (например, хэш-суммы открытого ключа).
Однако, асимметричные технологии сделали гораздо больший прорыв в схемах распространения ключей, чем симметричные -- были изобретены сертификаты. Сертификатом называется блок информации, содержащий данные, уникально идентифицирующие абонента, его открытый ключ и транспортный адрес, причем этот блок информации подписан с помощью ЭЦП другого лица. Абонент, о котором идет речь в сертификате, называется владельцем ключа, субъект сети, поставивший подпись под сертификатом -- заверяющим лицом (в законе РФ «Об электронно-цифровой подписи» - удостоверяющий центр). Предположим, абонент А никогда не общался с абонентом С и не может проверить подлинность его открытого ключа, но и А и С общались с неким абонентом В -- тогда В может выступить заверяющим лицом и подписать сертификат на владельца ключа С. Тогда абонент А, получив сертификат и проверив подпись В, в чьем открытом ключе он уверен, может отныне полагаться и на открытый ключ абонента С.
В чем же заключается тот самый «прорыв» в схеме распространения ключей? Самое замечательное свойство сертификатов в том, что их использование можно объединять в цепочку. Действительно, предположим, двум желающим пообщаться абонентам А и D не удалось найти общего знакомого, но выяснилось, что А знает некоего В, a D знает некоего С, которые знакомы между собой. Значит, В может отправить А сертификат о ключе С, а С может отправить А сертификат о ключе D. В итоге А получает уверенность в том, что открытый ключ D, имеющийся у него на руках, истинен. Таким образом, была построена цепочка доверия, которая по своей сути представляет тот самый предварительный защищенный канал между А и D (отправителем и получателем), но канал этот был собран (и причем по очень несложной и надежной схеме) из нескольких уже существовавших очищенных каналов. Возможность подобного построения защищенного канала «по требованию» из нескольких коротких, уже существовавших, и есть преимущество открытой криптографии.
В настоящее время развитие описанной схемы по всему миру идет очень интенсивно. Наметились следующие основные тенденции. Во-первых, стали появляться субъекты, чьей единственной функцией является хранение и заверение ключей -- центры сертификации (англ. CertificationAuthority --СА). Во-вторых, в процесс создания цепочек доверия стали активно включатся крупные производители программного обеспечения. Действительно, если пользователь ЭВМ приобретает лицензионное ПОв фирменной запечатанной коробке с голограммой и другими физическими степенями защиты, то задача подделки открытого ключа, находящегося на этом диске, становится на порядок более сложной. А имея несколько надежных открытых ключей крупных производителей ПО, пользователь уже в состоянии строить множество цепочек доверия к миллионам абонентов. И сами производители ПО получают в качестве дивидендов возможность аутентично присылать обновления программ по сети, подписанными теми же ключами, чьи открытые половинки были размещены на первоначальном компакт-диске.
Криптография воспринимается как волшебная палочка, по мановению которой любая информационная система становится защищенной. Но на удивление криптографические алгоритмы могут быть успешно атакованы. Все сложные теории криптоанализа нивелируются, если известна малейшая информация о промежуточных значениях шифра. Помимо ошибок в реализации, получить такую информацию можно, манипулируя или измеряя физические параметры устройства, которое выполняет шифр, и я постараюсь объяснить, как это возможно.
Откуда растут рога
Давай попробуем рассмотреть реализацию любого криптографического алгоритма сверху вниз. На первом этапе криптографический алгоритм записывается в виде математических операторов. Здесь алгоритм находится в среде, где действуют только законы математики, поэтому исследователи проверяют лишь математическую стойкость алгоритма, или криптостойкость. Этот шаг нас интересует мало, ибо математические операции должны быть переведены в код. На этапе работы кода критическая информация о работе шифра может утекать через лазейки в реализации. Переполнение буфера, неправильная работа с памятью, недокументированные возможности и другие особенности программной среды позволяют злоумышленнику найти секретный ключ шифра без использования сложных математических выкладок. Многие останавливаются на этом шаге, забывая, что есть еще как минимум один. Данные - это не абстракция, а реальное физическое состояние логических элементов, в то время как вычисления - это физические процессы, которые переводят состояние логических элементов из одного в другое. Следовательно, выполнение программы - это преобразование физических сигналов, и с такой точки зрения результат работы алгоритма определяется законами физики. Таким образом, реализация криптографического алгоритма может рассматриваться в математической, программной и физической средах.
В конечном счете любой алгоритм выполняется с помощью аппаратных средств , под которыми понимаются любые вычислительные механизмы, способные выполнять логические операции И, ИЛИ и операцию логического отрицания. К ним относятся стандартные полупроводниковые устройства, такие как процессор и ПЛИС, нейроны мозга, молекулы ДНК и другие . У всех вычислительных средств есть как минимум два общих свойства. Первое свойство - для того, чтобы выполнить вычисление, нужно затратить энергию. В случае полупроводниковых устройств мы говорим об электрической энергии, в случае нейронов мозга, вероятно, о затраченных калориях (видел когда-нибудь толстых шахматистов?), в случае ДНК это, к примеру, химические реакции с выделением теплоты. Второе общее свойство в том, что для корректного выполнения операций все вычислительные механизмы требуют нормальных внешних условий. Полупроводниковые устройства нуждаются в постоянном напряжении и токе, нейроны мозга в покое (пробовал вести машину, когда твоя девушка пытается выяснить отношения?), ДНК в температуре. На этих двух свойствах основаны аппаратные атаки (hardware attacks), о которых пойдет речь.
На первый взгляд кажется, что физические процессы абсолютно нерелевантны с точки зрения безопасности, но это не так. Энергию, которая была израсходована в данный конкретный момент работы алгоритма, можно измерить и связать с двоичными данными, которые позволят найти ключ шифрования. На измерении физических эффектов, протекающих во время вычислений, основаны все атаки, которые называются атаки по второстепенным каналам (Side Channel Attacks). В России этот термин еще не до конца устоялся, поэтому можно встретить словосочетания «атаки по побочным каналам», «атаки по сторонним каналам» и другие.
Нормальные внешние условия тоже являются немаловажными. Рассмотрим, к примеру, напряжение, которое необходимо подать на вход процессора. Что случится, если это напряжение упадет до нуля на несколько наносекунд? Как может показаться на первый взгляд, процессор не перезагрузится, но, скорее всего, континуум физических процессов будет нарушен и результат алгоритма будет неверным. Создав ошибку в нужный момент, злоумышленник может вычислить ключ, сравнивая правильный и неправильный шифротексты. Изменение внешних условий используется для вычисления ключей в атаках по ошибкам вычислений (Fault attacks). Опять же в России этот термин устоялся не полностью: называют их и атаками с помощью ошибок, и атаками методом индуцированных сбоев, и по-другому.
Атаки по второстепенным каналам
Мы начнем введение в атаки по второстепенным каналам с алгоритма DES, реализованного на C++ (схема алгоритма представлена на рис. 1, а его подробное описание ищи в Сети). Помимо того что ты увидишь, в каких неожиданных местах могут скрываться уязвимости, ты также узнаешь про основные приемы, используемые в атаках по второстепенным каналам. Эти приемы необходимо прочувствовать, так как они служат основой для более сложных атак, которые будут рассмотрены в последующих статьях.
Атаки по времени
Итак, атака по времени (Timing attack) на реализацию алгоритма DES. Полный код будет ждать тебя на нашем Гитхабе , нас же в данный момент интересует побитовая перестановка Р (ищи круг с буквой Р на рис. 2), выполняемая на последнем шаге блока Файстеля. В нашем случае код этой функции выполнен следующим образом:
#define GETBIT(x,i) ((x>>(i)) & 0x1)
uint8_t p_tab = {16,7,20,21,29,12,28,17,1,15,23,26,5,18,31,10,2,8,24,14,32,27,3,9,19,13,30,6,22,11,4,25};
uint32_t DES_P(const uint32_t var){
int iBit = 0;
uint32_t res = 0x0, one = 0x1;
for (iBit=0; iBit<32; iBit++)
if (GETBIT(var,32 - p_tab) == 1)
res |= one<<(31-iBit);
return res;
}
С точки зрения аппаратных атак этот код содержит гигантскую уязвимость: программа будет выполнять операцию res |= one<<(31-iBit) , то есть затрачивать дополнительное время (читай энергию), только если бит переменной var равен 1 . Переменная var , в свою очередь, зависит от исходного текста и ключа, поэтому, связав время работы программы со значением ключа, мы получим инструмент для атаки. Чтобы понять, как использовать связь между временем и данными, я рассмотрю два теоретических примера. Затем в третьем примере будет показано, как непосредственно найти ключ алгоритма, использующего данную реализацию.
Сравнение ключей при идеальных измерениях
Первый теоретический пример заключается в том, что у нас есть пять исходных текстов, идеально измеренное время шифрования каждого текста и два ключа: К1=0x3030456789ABCDEF , К2=0xFEDCBA9876540303 , из которых нужно выбрать правильный. Мы полагаем, что код не прерывался во время выполнения, данные были заранее размещены в кеше первого уровня, а время работы всех функций шифра за исключением функции DES_P было постоянным. Замечу, что шифротекстов нет, поэтому зашифровать один исходный текст с помощью двух ключей и сравнить получившиеся шифротексты с оригиналом не получится. Что в этом случае можно сделать?
Ты уже знаешь, что переменная var влияет на время работы, которое содержит две составляющие:
- переменное время, затрачиваемое на выполнение всех операций DES_P, которое зависит от количества бит переменной var для каждого раунда: a*(∑HW(var)) , где
- а - это постоянная времени, фактически это количество тактов процессора, затраченных на выполнение одной операции res |= one<<(31-iBit) ;
- HW(var) - расстояние Хемминга, то есть количество бит переменной var , установленных в 1. Знак суммы ∑ означает, что мы считаем расстояние Хемминга для всех 16 раундов;
- постоянное время, затрачиваемое на выполнение всех остальных операций, будет обозначено Т.
Следовательно, время работы всего алгоритма равно t = a*(∑HW(var)) + T . Параметры a и T нам неизвестны, и, сразу тебя обрадую, искать мы их не будем. Время шифрования каждого исходного текста t мы измерили идеально . Также у нас есть значения ключей, поэтому мы можем рассчитать переменную var для каждого раунда.
Я думаю, ты уже догадался, как проверить, какой из двух ключей правильный: нужно рассчитать сумму расстояний Хемминга ∑HW(var) для каждого исходного текста и одного значения ключа и сравнить получившиеся значения с измеренным временем. Очевидно, что с ростом значения ∑HW(var) время также должно увеличиваться. Следовательно, если ключ правильный, то такая зависимость будет прослеживаться, а вот для неправильного ключа такой зависимости не будет.
Все вышесказанное можно записать в виде одной таблицы (рис. 3).
В первой колонке у нас находятся исходные тексты, которые шифруются с помощью одного из ключей К1 или К2 (какого конкретно - нужно узнать). Во второй колонке - время, указанное в процессорных тактах, которое было затрачено на шифрование одного исходного текста. В третьей колонке находятся суммы значений расстояний Хемминга переменной var для всех раундов, полученные для каждого исходного текста и ключа К1 . В четвертой колонке такая же сумма расстояний Хемминга, но уже посчитанная для ключа К2 . Как несложно заметить, время работы шифра увеличивается с ростом значений расстояний Хемминга для ключа К1 . Соответственно, ключ К1 будет верным.
Конечно, это идеализированный пример, который не учитывает множество факторов, возникающих в реальности. Я хотел показать лишь примерный принцип атак по второстепенным каналам, а вот уже следующий пример будет объяснен на реально измеренных значениях времени, но перед этим нужно вспомнить кое-что из статистики.
Угадай число
Мне хотелось бы показать, что происходит со случайными величинами, когда они очень долго усредняются. Если ты хорошо знаешь статистику, то сразу переходи к следующей части, в противном случае давай рассмотрим небольшую игру, где компьютер случайно выбирает натуральное число А и предлагает тебе угадать его. Каждый раз компьютер выбирает дополнительную пару чисел (b, c) из диапазона от 0 до М и возвращает тебе лишь значения (А + b, c) . Числа b и с выбираются случайно и могут быть значительно больше числа А. Значение числа М ты не знаешь (но можешь примерно догадаться о его порядке из-за разброса значений c). Как угадать число А?
Программа, которая симулирует эту игру, приведена ниже:
Void Game(int *Ab, int *с){
static int A = 0;
int M = 1000;
srand((unsigned int)rdtsc());
if (A==0)
A = 1+rand()%100;
*Ab = A+(M*M*rand())%M;
*с = (M*M*rand())%M;
}
void Guess(){
int Ab, с, i, nTries = 100000;
double avg1 = 0.0, avg2 = 0.0;
for (i=0; i Согласно коду, значение А берется из диапазона от 1 до 100, а значения переменных b и с из диапазона от 0 до 999, что примерно в десять раз больше максимального значения А, то есть уровень шума значительно выше уровня самого значения! Но если пара значений (А + b, с) возвращается 100 тысяч раз (много, но и уровень шума тоже не маленький), то значение переменной А угадывается примерно в половине случаев. Для этого нужно усреднить все возвращенные значения А + b и все значения с, а затем посчитать разность средних. Эта разность и будет значением переменной А. Конечно, если мы уменьшим значение М, то и количество пар (A + b, с) , необходимых для вычисления ключа, будет меньшим. Теперь нужно разобраться, почему так происходит. Существует замечательный закон, который является ключевым для атак по второстепенным каналам, - закон больших чисел Чебышева. Согласно этому закону, при большом числе независимых опытов среднее арифметическое наблюденных значений μ(x) случайной величины x сходится по вероятности к ее математическому ожиданию
. Если рассматривать этот закон в рамках нашей игры, сумма значений A + b и c сойдется соответственно к А + μ(b) и μ(c) , а так как значения b и c выбираются случайно из одного диапазона, то μ(b) и μ(c) будут сходиться к их математическому ожиданию, следовательно, разность А + μ(b) – μ(c) будет сходиться к значению переменной А. Прерывания, кеширование данных и другие факторы не позволяют измерить время работы алгоритма с точностью до одного процессорного такта. В моих измерениях время работы алгоритма варьируется в пределах 5% от среднего значения. Этого достаточно, чтобы метод из первого примера перестал работать. Что можно придумать в этом случае? Сразу замечу, что одним лишь усреднением времени шифрования каждого исходного текста решить задачу не получится (хотя время будет измерено точнее). Во-первых, это далеко не всегда возможно, так как входные значения шифра могут контролироваться не нами. Во-вторых, даже усреднив миллион шифрований, ты не избавишься от проблемы кеширования данных, так как разместить все таблицы в кеше первого уровня сложно (ну по крайней мере об этом нужно позаботиться заранее), - о таких особенностях я расскажу как-нибудь в следующий раз. Теперь рассмотрим, как влияет закон больших чисел Чебышева на атаки по второстепенным каналам. Мы все так же рассматриваем реализацию DES, но сейчас время работы алгоритма записывается следующим образом: Таким образом, время работы алгоритма можно записать в виде t = a*(∑HW(var)) + T + Δ(t) . В таблице, представленной на рис. 4, приведены значения исходных текстов и реально измеренное время для них. Замечу, что ∑HW(var) для правильного ключа и каждого исходного текста равно 254, но при этом разница между наименьшим и наибольшим временем составляет 327 тактов! При таких вариациях в измерениях простое попарное сравнение расстояний Хемминга для одного исходного текста и времени его шифрования не даст результатов. Здесь мы должны воспользоваться законом больших чисел Чебышева. Что случится, если мы будем усреднять время алгоритма для разных шифротекстов, которые дают одинаковое расстояние Хемминга ∑HW(var) :
μ(t) = μ(a*(∑HW(var)) + T + Δ(t)) = μ(a*(∑HW(var))) + μ(T) + μ(Δ(t)) = a*(∑HW(var)) + T + μ(Δ(t))
Фактически, когда определяется среднее арифметическое времени для различных исходных текстов, происходит усреднение шумов, и, как мы знаем из статистики, эти шумы будут сходиться к одному и тому же значению при увеличении количества измерений, то есть μ(Δ(t)) будет сходиться к константе. Давай посмотрим на примере. Я измерил работу 100 тысяч операций шифрования алгоритма DES, то есть у меня есть 100 тысяч исходных текстов и соответствующих времен работы. В этот раз мы будем сравнивать четыре ключа: К1=0x3030456789ABCDEF , K2=0xFEDCBA9876540303 , K3=0x2030456789ABCDEF , K4=0x3030456789ABCDED . Как и в первом примере, мы рассчитываем значение расстояний Хемминга для всех исходных текстов и ключей К1,К2,К3,К4 - это сделано в таблице, представленной на рис. 5. Ни для одного из ключей нет очевидной зависимости времени от расстояний Хемминга. Давай усредним время работы шифрований (для каждого ключа по отдельности), у которых одно и то же расстояние Хемминга (возьмем лишь те исходные тексты, для которых ∑HW(var) лежит в интервале ). В этот раз мы построим график (рис. 6), где по оси Х будет отложено расстояние Хемминга, а по оси Y - среднее арифметическое времени для этого расстояния. Что мы видим на рис. 6? Для трех ключей (К2 , К3 , К4) время работы шифра слабо зависит от расстояния Хемминга, а для ключа К1 мы видим восходящий тренд. Обрати внимание на пилообразный вид графиков - это из-за того, что у нас не так много измерений и они не настолько точные, чтобы μ(Δ(t)) усреднилось к одному значению. Все же мы можем видеть, что среднее время работы шифра увеличивается с ростом расстояний Хемминга, посчитанных для ключа К1 , а для трех других ключей - нет. Поэтому предполагаем, что ключ К1 верный (это действительно так). С ростом количества данных восходящий тренд для правильного ключа будет разве что усиливаться, а для неправильных ключей все значения будут сходиться к среднему. «Гребенка» тоже будет исчезать с ростом количества данных. Согласись, строить такие графики и постоянно проверять их глазами довольно неудобно, для этого есть несколько стандартных тестов проверки зависимости между моделью и реальными данными: коэффициент корреляции, Т-тест и взаимная информация. Можно вспомнить и придумать еще парочку других коэффициентов, но мы будем в основном пользоваться коэффициентом корреляции Пирсона или, что то же самое, линейным коэффициентом корреляции pcc(x,y) (описание коэффициента есть на Wiki). Этот коэффициент характеризует степень линейной
зависимости между двумя переменными. В нашем случае зависимость именно линейная, ибо μ(t) = a*(∑HW(var)) + T + μ(Δ(t)) можно представить как y = a*x + b , где x - это рассчитываемое нами расстояние Хемминга, а y - реально измеренное время. Значение коэффициента корреляции Пирсона для средних значений времени и расстояний Хемминга показано в строке «с усреднением» на рис. 7. Значение коэффициента Пирсона для ключа К1 в три раза выше, чем для любого из трех других ключей. Это говорит о высоком линейном соответствии между моделируемыми и реальными данными, что лишний раз подтверждает использование ключа К1 . Коэффициент корреляции Пирсона можно применять даже без предварительного усреднения значений. В этом случае его величина будет существенно меньше, чем для усредненных значений, но все равно правильный ключ будет давать наибольший коэффициент корреляции (строка «без усреднения»). Таким образом, вначале визуально, а затем с помощью коэффициента корреляции мы смогли убедиться, что наша модель времени для ключа К1 лучше всего согласуется с реальными данными. Очевидно, что проверять все возможные значения основного ключа не представляется возможным, поэтому нам необходим другой метод, который позволит искать ключ по частям. Такой метод приводится в следующем примере, который уже можно рассматривать как применимую в жизни атаку. Вот мы и подошли к моменту, когда ключ будет искаться частями по 6 бит. Искать 6 бит мы будем абсолютно аналогично тому, как проверяли корректность 64 бит до этого (когда работали с четырьмя ключами). Значения 6 бит ключа, которые дают самую хорошую линейную связь между моделью и реальными данными, скорее всего, будут правильными. Как это работает? Давай рассмотрим, как можно представить время работы шифра, когда мы ищем лишь 6 бит ключа: Таким образом, время работы алгоритма можно записать в виде T = a*HW(var) + a*(∑ HW(var[:,1:32])) + Т + Δ(t).
Еще раз по поводу 6 бит ключа и 4 бит переменной var . Блок Файстеля берет 32 бита регистра R и с помощью специальной перестановки E() получает 48 бит, которые затем складываются с 48 битами ключа. На первом раунде значение R нам известно, а ключ нет. Далее результат сложения разбивается (внимание!) на восемь блоков по 6 бит, и каждый набор из 6 бит подается на свою собственную таблицу Sbox. Каждая из восьми таблиц заменяет шесть входных бит четырьмя выходными битами, поэтому на выходе получается 32-битная переменная var , которая уже влияет на время работы шифра. Если мы сгруппируем время работы всех операций шифрования, для которых расстояние Хемминга HW(var) одинаковое, то среднее арифметическое времени работы будет сходиться к следующему значению:
μ(t) = μ(a*HW(var)) + μ(a*(∑ HW(var[:,1:32]))) + μ(Т) + μ(Δ(t)) = a*HW(var) + μ(a*(∑ HW(var[:,1:32]))) + Т + μ(Δ(t)).
Так как мы берем одинаковые значения HW(var) и разные значения ∑ HW(var[:,1:32]) (мы берем исходные тексты, где HW(var) обязательно одинаковое, а остальные части нас не интересуют, поэтому суммы ∑ HW(var[:,1:32]) будут разные), то среднее арифметическое μ(a*(∑ HW(var[:,1:32]))) будет сходиться к константе (если совсем точно, то μ(∑ HW(var[:,1:32])) без учета первых четырех бит должна сходиться к 254), точно так же, как в предыдущем примере сходилась величина μ(Δ(t)) ! Первые четыре бита переменной var можно записать как var = Sbox{E(R) xor K} , где E(R) - первые 6 бит регистра R после операции E() ; K - первые 6 бит ключа; Sbox{} - таблица перестановки Sbox. Теперь заменим выражение для var :
μ(t) = a*HW(Sbox{E(R) xor K}) + μ(a*(∑ HW(var[:,1:32]))) + Т + μ(Δ(t)).
Значения μ(a*(∑ HW(var[:,1:32]))) , μ(Δ(t)) сходятся к своим средним арифметическим, когда они считаются для разных исходных текстов. Следовательно, при очень большом количестве усреднений значение μ(a*(∑ HW(var[:,1:32]))) + Т + μ(Δ(t)) можно просто заменить на const:
μ(t) = a*HW(Sbox{E(R) xor K}) + const.
Чтобы найти ключ в этом выражении, нужно для каждого значения 6 бит ключа выбрать исходные тексты с одинаковым HW(Sbox{E(R) xor K}) , усреднить их время выполнения и сравнить с моделью. Окончательный алгоритм поиска ключа запишем в виде псевдокода: For each key = 0:63
For each i = 1:N
P = plaintext(i) // Исходный текст
= IP(P) // Левая и правая части после начальной перестановки
hw_var[i] = HammingWeight(Sbox1(E(R) XOR key)) // Расстояние Хемминга для первых четырех бит переменной var
EndFor
// Коэффициент корреляции между N измеренными значениями времени и N посчитанными значениями расстояния Хемминга
pcc(key) = ComputePearsonCorrelation(t, hw_var)
EndFor
Этот алгоритм был реализован на С++ (полный исходный код будет ждать тебя на нашем Гитхабе), и посчитанные коэффициенты корреляции показаны на рис. 8. Для расчета корреляции был использован миллион измерений. Комбинации битов ключа 000010 =2 дает корреляцию в четыре раза выше, чем для любого другого значения, поэтому, скорее всего, эта комбинация битов является верной. Замечу, что мы ищем ключ первого раунда, который не равен изначальному ключу. После того как были найдены первые 6 бит ключа, можно искать следующие, пока ключ не будет восстановлен полностью. Сбор значений времени может занимать от нескольких часов до нескольких недель в зависимости от системы. Анализ данных обычно происходит значительно быстрее - за несколько часов, хотя тоже зависит от ситуации. Коммерческого ПО для атак по времени в открытом доступе нет, но ты всегда можешь воспользоваться моими исходниками. Пришло время закругляться. Первая статья всегда комом, ибо она может показаться легкой/непрактичной/неинтересной, но без вводной части далеко не уйдешь. Ну а в последующих мы изучение аппаратных атак, разберем, как воспользоваться потребленным питанием устройства, чтобы взломать шифр, и как восстановить ключ с помощью ошибок в вычислениях. Так что stay tuned, как говорят. Охрана тайны может строиться по принципу доступа к тайне только посвященных лиц, подразумевая, что непосвященные не имеют физического доступа к ней. В другом случае охрана тайны может строиться по принципу возможного доступа посторонних лиц, но с пониманием смысла тайны только посвященных лиц. Исторически второй метод получил большее распространение, чем первый, более дорогостоящий, а иногда и просто невозможный. С появлением письменности он стал распространенным, и стал практически всеобщим: тайные карты, зашифрованные письмена. Доступно всем, но понятно только посвященным. Сегодня это основной метод скрытия тайны для хранения и передачи информации.
Зашифрованное сообщение
скрывает смысл исходного (открытого) сообщения. Таким образом, процесс шифрования есть процесс скрытия смысла исходного сообщения в исходном алфавите. Зашифрованное сообщение становится нечитаемым. И только посвященные люди, которые знают некоторый секрет, могут расшифровать зашифрованное сообщение. В дальнейшем процессы шифрования и расшифровки мы будем объединять одним словом «шифрование» или оговаривать эти процессы отдельно. Вопросами построения систем шифрования занимается наука под названием криптография.
В результате применения шифрования появляется шифрованный текст, который и скрывает информационную тайну . Например, тайное послание «Завтра фирма Скотта будет продавать акции по пониженным ценам» имеет некоторый шифрованный текст в виде «?т6ifmфвщб4-!nmdавжшт». Шифрованный текст тайны доступен всем, более того, в шифрованном тексте имеется полное содержание тайны, он содержит весь смысл тайны, но тайна доступна только посвященным. Здесь необходимо сделать одно маленькое замечание и уточнение. Да, тайна легко и быстро доступна только посвященным лицам. Непосвященные лица могут проникнуть в тайну в течение более протяженного отрезка времени, затратив некоторые усилия. Успех непосвященных лиц гарантирован именно тем, что в шифрованном тексте содержится вся информация, скрывающая тайну . Для прочтения шифрованного текста
необходима некоторая дополнительная информация, которая позволяет легко и быстро постигнуть смысл скрываемого от посторонних сообщения. Нас будут интересовать шифровальные системы, которые обладают одной характерной особенностью для посвященных лиц: взаимно однозначным прямым и обратным преобразованием исходный (открытый) текст единственный шифрованный текст. В дальнейшем мы покажем, что для непосвященных лиц в некоторых случаях это может быть не совсем так. Современные криптографические системы
имеют набор возможных ключей гораздо больший, чем набор возможных ключей обыкновенного замка от вашей двери. Это число может быть соизмеримо с числом атомов нашей Вселенной (1077≈2264). Перебор всех возможных ключей эквивалентен взлому дверей, т.е. применению грубой силы. Можно сделать секретный уникальный замок, к которому типовая воровская отмычка не подойдет. В древние времена, когда монархи, удельные князья или графы создавали секретные убежища, подземные ходы, строителей обычно убивали, ослепляли, в общем, делали все, чтобы сохранить в тайне эти сооружения. А что вы будете делать с мастером вашего замка? Он же знает конструкцию замка, и, возможно, даже делал к нему ключ! Голландский военный криптограф Датчман А. Керкхоффс еще в 19 веке решил эту проблему, сформулировав в книге «Военная криптография», изданной в 1883 г., шесть основных требований к системе шифрования: система шифрования должна быть не раскрываемой, если не в теоретическом плане, то в практическом; компрометация системы не должна причинять неудобств ее пользователям; секретный ключ должен быть легко запоминаемым без его записи; криптограмма должна быть представлена в такой форме, чтобы ее можно было передать по телеграфу; аппаратура шифрования должна быть портативной и такой, чтобы ее мог обслуживать один человек; система не должна требовать запоминания длинного перечня правил и быть простой в использовании. Несмотря на примитивизм отдельных требований с позиции сегодняшних возможностей (не забудьте о 1883 г.), этот перечень содержит важный (второй) фундаментальный пункт требований к системе сохранения тайны: конструкция замка вашей двери (правило получения шифрованного текста) может быть известно всем. Секретным должен быть только ключ к нему. Если при этом ваша система окажется надежной против взлома, можете спать спокойно. Где же взять этот секретный ключ, ключ который бы никто не знал? Ответ может быть только один: необходимо сделать его самому. Итак, для вашего полного спокойствия вы должны приобрести алгоритм создания тайны у надежной фирмы с гарантией и самому сделать секретный ключ. В вашем РС ключ представляет собой
некоторый файл, который состоит их нулей и единиц. Каждый ноль или единица представляет собой одно из двух значений единицы информации, которая называется битом. Суммарное значение нулей и единиц в файле ключа определяет его длину. Например, ключ длиной 256 бит означает, что файл ключа содержит некоторое число нулей и единиц, суммарное число которых равно 256. Сколько же всего может быть ключей? Можно построить специальную вычислительную машину для быстрого перебора ключей. Наверное, эта машина будет стоить достаточно больших денег. Гордон Э.Мур (Gordon E. Moor) заметил, что за год размеры процессоров, их стоимость и время выполнения команд уменьшаются приблизительно на 40%. Эту закономерность называют в честь этого исследователя законом Мура. Можно проиллюстрировать действие закона Мура на примере вскрытия криптографического алгоритма DES с длиной ключа равной 46 бит. На текущий отрезок времени принято, что длина ключа в 246 бит вполне приемлема для защиты от полного перебора ключевого поля. Таким образом, ключ - это секретный параметр алгоритма криптографического преобразования данных, обеспечивающий выбор только одного варианта из всех возможных вариантов данного алгоритма. Теперь вы видите, какую важную роль играет ключ в деле стойкости системы шифрования. Поэтому канал передачи ключа должен быть абсолютно надежным, а сам ключ хорошо охраняемым от посторонних лиц. Предположим, что эти два условия соблюдены. И все-таки хакер на основе только перехваченных шифрованных текстов может, в конце концов, определить ваш секретный ключ
. Это происходит потому, что шифрованные тексты большинства практических систем шифрования имеют закономерность, трудно определяемую, но все-таки закономерность. В дальнейшем процесс хакерского расшифрования сообщений без предварительного знания ключа будем называть процессом дешифрования. Сравнение ключей при реальных измерениях
Коэффициент корреляции Пирсона
Атака на неизвестный ключ
Продолжение следует
Ключи в криптографии
Что позволяет вам быстро открыть свою закрытую дверь, вам, лицу, которому это позволено? Ключ, скажете вы. Ну а при хорошем замке квартирный вор повозится некоторое время, но тоже откроет вашу дверь, не имея ключа. Чтобы квартирный вор не смог быстро открыть дверь вашей квартиры, замок должен быть достаточно хорошим. От этого зависит время незаконного вскрытия вашей квартиры. В крайнем случае, вор может воспользоваться грубой силой, пытаясь взломать саму дверь. В криптографии ситуация аналогична: дверь - это шифрованный текст, который открывает вам путь к тайне. Ключ - это та дополнительная информация, которая позволяет посвященным лицам быстро прочесть шифрованный текст. Эту дополнительную информацию мы тоже будем называть криптографическим ключом или просто ключом. Ключ от квартиры нельзя терять, его нельзя отдавать посторонним лицам, которым вы не доверяете. Криптографический ключ по этим же причинам никому нельзя отдавать. Его необходимо держать в секрете, потому что с него очень легко сделать копию, легче, чем с обыкновенного дверного ключа. Обычный ключ от квартиры имеет небольшие размеры, чтобы было удобно его хранить. Криптографический ключ из этих же соображений также должен иметь небольшой размер, хотя сегодня при использовании ЭВМ это не столь жесткое требование. А что же в криптографии играет роль замка? Это устройство или правило (алгоритм), как создавать шифрованный текст. Минуточку, подождите! Если очень легко копировать настоящий ключ, то можно самому создавать его. Да, можно, но какой создать? Количество возможных ключей очень велико.
