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

• генерация ключей;
• хранение ключей;
• распределение ключей.

Генерация ключей. Истинно случайные и псевдослучайные последовательности . Генерация ключей должна производиться таким образом, чтобы предугадать значение ключа (даже зная, как он будет генерироваться) было практически невозможно. В идеальном случае вероятность выбора конкретного ключа из множества допустимых равна 1 /К, где К - мощность ключевого множества (ключи равновероятны).

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

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

Последовательность называется истинно случайной , если ее нельзя воспроизвести. Это означает, что если запустить генератор истинно случайных чисел дважды при одном и том же входе, то на его выходе получатся разные случайные последовательности.

В то же время из-за дешевизны и возможности неограниченного тиражирования наиболее распространенными являются программные реализа-

Рис. 2.60.

ции генераторов. Следует учитывать, что получаемая в этом случае последовательность будет псевдослучайной - если программный генератор повторно запустить с такими же начальными значениями, он выдаст ту же последовательность (рис. 2.61).

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

Рис. 2.61.

Наиболее простым и известным генератором псевдослучайных чисел является линейный конгруэнтный генератор, вырабатывающий последовательность чисел R(i):

где А и С - константы; R(0) - исходное значение, выбранное в качестве порождающего числа. Значение т обычно устанавливается равным 2п у где п - длина машинного слова в битах. Генератор имеет период М, после чего генерируемая последовательность начнет повторяться. Необходимо выбирать числа А и С таким образом, чтобы период М был максимальным. Доказано, что этого можно достичь тогда и только тогда, когда С - нечетное и A mod 4 = 1.

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

Так, например, при известных значениях R(0), R( 1), R(2), R(3) (или любых других четырех подряд идущих членов последовательности псевдослучайных чисел R(i)) параметры генератора могут быть получены из системы уравнений

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

В качестве примеров криптографически сильных генераторов псевдослучайных чисел можно привести режим OFB (и его модификацию CTR) блочных шифров , а также режим гаммирования отечественного криптоалгоритма ГОСТ 28147-89. При этом используются ключи, специально резервируемые для задач генерации. В качестве начальных значений могут браться, например, значения таймера вычислительной системы. Кроме того, криптографически сильные генераторы могут быть построены с использованием односторонних хэш-функций .

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

• генерируемая последовательность должна быть статистически неотличима за приемлемое время вычислений от абсолютно случайной последовательности;
• знание какой-либо начальной части последовательности не позволяет предсказать следующий бит этой последовательности за приемлемое время вычислений.

Для выявления возможных отклонений от случайности может быть использован ряд статистических тестов:

• классические статистические тесты (проверка гипотезы равномерного распределения случайной величины методом хи-квадрат, тесты на однородность и симметричность);
• тесты, применимые к двоичным последовательностям (метод серий, частотный периодический тест);
• тесты, специально разработанные или отобранные для применения в криптографии, - тесты NIST (16 тестов, рекомендованных Национальным институтом стандартов и технологий США); тесты DIEHARD , известные как один из наиболее строгих наборов тестов; тесты Д. Кнута, основанные на критерии хи-квадрат ; адаптивный тест «стопка книг» и др.

Генератор Блюм - Блюма - Шуба . Самым простым и эффективным на данный момент криптографически сильным генератором псевдослучайных чисел является генератор BBS (Blum - Blum - Shub), названный по именам создателей Л. Блюм, М. Блюма и М. Шуба и основанный на теории квадратичных вычетов но модулю.

Сначала находят два больших простых числа р } q примерно одного размера, которые при делении на 4 дают остаток 3:

Для нахождения чисел р и q можно сначала выбрать случайные целые числа и и v , вычислить р = Аи + 3, q = 4v + 3, а затем проверить их на простоту. Если полученное число оказалось не простым, то выбирают новое случайное значение. Затем вычисляется п = pq, названное числом Блюма. Далее выбирается случайное целое число s, 1 s взаимно простое с п , НОД(5, п) = . Генерируется начальное значение генератора х 0 = s modrc. Получили х {) - случайный квадратичный вычет по модулю п.

В качестве битов псевдослучайной последовательности ps требуемой длины L используются младшие биты чисел х

Интересной особенностью генератора BBS является то, что при знании разложения числа п на множители он допускает эффективное прямое определение любого бита последовательности ps. Любое х- может быть вычислено исходя лишь из начального значения х 0 и порядкового номера i:

Алгоритм BBS при корректном выборе начальных параметров удовлетворяет всем статистическим критериям, предъявляемым к псевдослучайным последовательностям. BBS-генератор непредсказуем налево и направо, т.е. невозможно предсказать предыдущий или последующий бит последовательности, имея какую-либо ее часть. Период псевдослучайной последовательности, вырабатываемой BBS-генератором, во много раз превышает размер модуля пК

Пример 2.11

Сформируем псевдослучайную 4-битовую последовательность с помощью BBS-генератора.

Найдем числа р и q. Выберем два случайных целых числа и = 3 и v = 5. Вычислим р = 4 3 + 3 = 15и р = 15 - не простое и не может использоваться в BBS-генераторе, а число q = 23 - простое. Выберем тогда новое значение и = 7,р = 7-4 + 3 = = 31 - простое. Число Блюма п = pq = 31 23 = 713.

Выберем случайное целое число 5, взаимно простое с п. Пусть s = 16, ПОД(16, 713) = 1. Тогда:

В качестве последовательности ps возьмем младшие биты чисел х { (0 - если число четное и 1 - если число нечетное), получаем ps = 0110.

Пусть теперь требуется ответить на вопрос: каким будет 12-й бит последовательности ps?

Зная разложение числа п на множители (р = 31 и q = 23), вычислим х и:

х и - четное, значит 12-й бит последовательности ps будет равен нулю.

Эффективность BBS-генератора можно повысить, не ослабляя результирующую последовательность ps, если использовать не один, а не более log 2 rj младших битов чисел x jf где г - количество двоичных разрядов числа Блюма п (т.е. примерно log 2 log 2 n младших битов).

Пример 2.12

Требуется выяснить максимально возможное число младших битов чисел х { , которые можно использовать в BBS-гснсраторс, нс ослабляя его, если п = 713.

Вычислим log 2 (713 + 1) « 9,48 (добавляем единицу для кодирования нуля), округлив вверх до ближайшего целого, получим г = 10 - число двоичных разрядов числа 713.

Вычислим log 2 10 ~ 3,32, округлив вниз до ближайшего целого, получаем 3. Значит, в эффективной реализации BBS-генератора можно использовать три младших бита чисел х { (для сравнения: log 2 log 2 713 ~ 3,24, результат тот же - три младших бита).

Стандарт ANSI Х9.17. Представляется естественным использовать криптостойкие алгоритмы шифрования для построения криптографически сильного генератора псевдослучайных чисел. Для этих целей подходят режимы OFB, CTR или гаммирования (для ГОСТ 28147-89). Данный метод обеспечивает достаточное качество генерируемой последовательности, так как криптографическая гамма обладает необходимыми статистическими характеристиками. Как и в случае иных генераторов псевдослучайных чисел, последовательность будет периодична. Так, гамма шифра алгоритма ГОСТ 28147-89 обладает периодом повторения 64-битовых блоков, равным 2 64 -2 32 .

Одной из схем генерации ключей с использованием симметричного шифра является стандарт ANSI Х9.17 с алгоритмом тройной DES (Triple DES, 3DES) с двойным ключом (рис. 2.62). В число приложений, использующих эту технологию, входит PGP.

Рис. 2.62.

Пусть функция E k (X) осуществляет шифрование X по ЗОЕБ-алгоритму (шифрование - дешифровка - шифрование) на заранее заготовленном ключе к = (К 1, К2), который используется только для генерации секретных ключей. Пусть далее вектор инициализации IV 0 является начальным 64-битным значением, которое держится в тайне от противника, а Г. представляет собой отметку времени, когда был сгенерирован i -й ключ. Тогда очередной случайный ключ R } вычисляется с помощью преобразования

Очередное значение вектора инициализации IV i+v которое будет использовано для генерации следующего случайного числа, вычисляется как

Основное назначение генератора ANSI Х9.17 состоит в получении большого количества ключей для многократных сеансов связи.

Вообще говоря, вместо 3DES можно использовать любой другой стойкий алгоритм шифрования, например ГОСТ 28147-89.

На практике необходимость дополнительных вызовов процедуры шифрования (одного в случае гаммирования и трех в стандарте ANSI Х9.17) делает генерацию весьма ресурсоемкой, что затрудняет ее аппаратную реализацию и определяет невысокие скоростные характеристики данного метода.

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

Ключевые пространства. Пространство ключей К (ключевое пространство) - это набор всех возможных значений ключа.

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

Неоднородные ключевые пространства используются для защиты от несанкционированного использования криптографического оборудования.

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

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

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

Неоднородное ключевое пространство характеризуется следующими особенностями:

• шифрование информации с помощью стойкого криптоалгоритма Е к имеет место только при использовании ключей специального вида;
• «правильный» (стойкий) ключ k = , где k" - собственно ключ шифрования длины n k , (|&| = п к) F - некоторая криптографическая функция; |F(k’) | - А, А - п к -
• вероятность случайно получить стойкий ключ пренебрежимо мала и равна 2“ д;
• если поступивший на вход криптомодуля ключ не является стойким, для шифрования информации применяется существенно менее стойкий алгоритм Е[.

Например, блочный алгоритм шифрования с длиной ключа 128 бит может использовать «составной» ключ из 192 бит. Тогда вероятность случайно использовать стойкий ключ будет достаточно мала - всего 2 -64 .

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

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

• на главный ключ (мастер-ключ);
• ключ шифрования ключей;
• ключ шифрования данных (сеансовый ключ).

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

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

При распределении ключей между абонентами системы необходимо выполнить следующие требования:

• обеспечить оперативность и точность распределения ключей;
• обеспечить секретность распределения ключей.

Распределение ключей может производиться:

• с использованием одного или нескольких центров распределения ключей (централизованное распределение);
• прямым обменом сеансовыми ключами между пользователями сети (децентрализованное распределение ключей).

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

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

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

• DRAFT NIST SP 800-90А, Rev. 1. Recommendation for Random Number Generation UsingDeterministic Random Bit Generators //NIST. Nov. 2014. URL: http://csrc.nist.gov/publications/drafts/800-90/sp800-90a_r l_draft_novembcr2014_vcr.pdf
• Там же; СТБ 34.101.47-2012. Государственный стандарт Республики Беларусь. Информационные технологии и безопасность. Криптографические алгоритмы генерации псевдослучайных чисел. Минск: Госстандарт, 2012. URL: http://apmi.bsu.by/assets/files/std/brng-specl7.pdf
• Брассар Ж. Современная криптология. Руководство.
• DRAFT NIST SP 800-90А, Rev. 1. Recommendation for Random Number Generation UsingDeterministic Random Bit Generators.

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

• Сеансовые (сессионные) ключи - ключи, вырабатываемые между двумя пользователями, обычно для защиты канала связи. Обычно сеансовым ключом является общий секрет - информация, которая вырабатывается на основе секретного ключа одной стороны и открытого ключа другой стороны. Существует несколько протоколов выработки сеансовых ключей и общих секретов, среди них, в частности, алгоритм Диффи - Хеллмана .
• Подключи - ключевая информация, вырабатываемая в процессе работы криптографического алгоритма на основе ключа. Зачастую подключи вырабатываются на основе специальной процедуры развёртывания ключа.

См. также

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

Откуда растут рога

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

В конечном счете любой алгоритм выполняется с помощью аппаратных средств , под которыми понимаются любые вычислительные механизмы, способные выполнять логические операции И, ИЛИ и операцию логического отрицания. К ним относятся стандартные полупроводниковые устройства, такие как процессор и ПЛИС, нейроны мозга, молекулы ДНК и другие . У всех вычислительных средств есть как минимум два общих свойства. Первое свойство - для того, чтобы выполнить вычисление, нужно затратить энергию. В случае полупроводниковых устройств мы говорим об электрической энергии, в случае нейронов мозга, вероятно, о затраченных калориях (видел когда-нибудь толстых шахматистов?), в случае ДНК это, к примеру, химические реакции с выделением теплоты. Второе общее свойство в том, что для корректного выполнения операций все вычислительные механизмы требуют нормальных внешних условий. Полупроводниковые устройства нуждаются в постоянном напряжении и токе, нейроны мозга в покое (пробовал вести машину, когда твоя девушка пытается выяснить отношения?), ДНК в температуре. На этих двух свойствах основаны аппаратные атаки (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, но сейчас время работы алгоритма записывается следующим образом:

• переменное время, затрачиваемое на выполнение операции DES_P , которое зависит от количества бит переменной var: a*(∑HW(var)) . а по-прежнему постоянная времени, а HW(var) - расстояние Хемминга;
• постоянное время, затрачиваемое на выполнение всех остальных Т;
• шумы измерений Δ(t) , которые нормально распределены в диапазоне . Значение D неизвестно, и, как всегда, искать его мы не будем.

Таким образом, время работы алгоритма можно записать в виде 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 бит ключа:

• переменное время, затрачиваемое на выполнение операции DES_P , зависящее от:
  • 4 бит переменной var первого раунда a*HW(var) (6 бит ключа первого раунда участвуют в формировании 4 бит переменной var);
  • всех остальных бит переменной var за исключением 4 бит первого раунда a*(∑ HW(var[:,1:32])) ;
• постоянное время Т;
• шумы измерений Δ(t) .

Таким образом, время работы алгоритма можно записать в виде

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, как говорят.

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

Предположим, есть два пользователя (назовем их 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). В принципе его можно целиком хранить на персональном ключевом носителе, используя тот или иной ключ парной связи по мере необходимости. Однако при большом числе пользователей памяти ключевого носителя может просто не хватить. Поэтому сетевые наборы обычно хранят непосредственно на жестком диске компьютера, предварительно зашифровав их на еще одном ключе (такой ключ часто называется главным).

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

Формат зашифрованного объекта

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

Имитоприставка вычисляется перед зашифрованием, записывается в заголовок, а после расшифрования ее значение вычисляется повторно и сравнивается с хранящимся в заголовке. Кроме того, чтобы не расшифровывать весь объект, в его заголовке хранится и другая имитоприставка - файлового ключа, которая вычисляется на долговременном ключе перед зашифрованием файлового и проверяется после его /расшифрования, но (!) до расшифрования всего объекта. С помощью этой второй имитоприставки можно легко диагностировать большинство ошибок расшифрования на ранней стадии.

Итак, зашифрованный объект обычно содержит как минимум следующие данные:

• собственно информация, зашифрованная на файловом ключе;
• файловый ключ, зашифрованный на долговременном ключе;
• имитоприставка файлового ключа на долговременном ключе;
• имитоприставка исходных данных на файловом ключе.

***

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

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

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

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

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

Кроме того, некоторые алгоритмы, например RSA , имеют следующую характеристику: каждый из двух ключей может использоваться как для шифрования, так и для дешифрования .

Сначала рассмотрим алгоритмы, обладающие обеими характеристиками, а затем перейдем к алгоритмам открытого ключа , которые не обладают вторым свойством.

При описании симметричного шифрования и шифрования с открытым ключом будем использовать следующую терминологию. Ключ , используемый в симметричном шифровании , будем называть секретным ключом . Два ключа, используемые при шифровании с открытым ключом , будем называть открытым ключом и закрытым ключом . Закрытый ключ держится в секрете, но называть его будем закрытым ключом , а не секретным, чтобы избежать путаницы с ключом, используемым в симметричном шифровании . Закрытый ключ будем обозначать KR , открытый ключ - KU .

Будем предполагать, что все участники имеют доступ к открытым ключам друг друга, а закрытые ключи создаются локально каждым участником и, следовательно, распределяться не должны.

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

Диффи и Хеллман описывают требования, которым должен удовлетворять алгоритм шифрования с открытым ключом .

1. Вычислительно легко создавать пару (открытый ключ KU, закрытый ключ KR ).
2. Вычислительно легко, имея открытый ключ и незашифрованное сообщение М , создать соответствующее зашифрованное сообщение:
3. Вычислительно легко дешифровать сообщение, используя закрытый ключ :

   М = D KR [C] = D KR ]

4. Вычислительно невозможно, зная открытый ключ KU , определить закрытый ключ KR .
5. Вычислительно невозможно, зная открытый ключ KU и зашифрованное сообщение С , восстановить исходное сообщение М .

   Можно добавить шестое требование, хотя оно не выполняется для всех алгоритмов с открытым ключом :

6. Шифрующие и дешифрующие функции могут применяться в любом порядке:

   М = Е KU ]

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

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

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

Мы видим, что разработка конкретного алгоритма с открытым ключом зависит от открытия соответствующей односторонней функции с люком .

Криптоанализ алгоритмов с открытым ключом

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

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

Другая форма атаки состоит в том, чтобы найти способ вычисления закрытого ключа , зная открытый ключ . Невозможно математически доказать, что данная форма атаки исключена для конкретного алгоритма открытого ключа . Таким образом, любой алгоритм, включая широко используемый алгоритм RSA , является подозрительным.

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

Основные способы использования алгоритмов с открытым ключом

Основными способами использования алгоритмов с открытым ключом являются шифрование/ дешифрование , создание и проверка подписи и обмен ключа.

Шифрование с открытым ключом состоит из следующих шагов:

Рис. 7.1.

1. Пользователь В создает пару ключей KU b и KR b , используемых для шифрования и дешифрования передаваемых сообщений.
2. Пользователь В делает доступным некоторым надежным способом свой ключ шифрования, т.е. открытый ключ KU b . Составляющий пару закрытый ключ KR b держится в секрете.
3. Если А хочет послать сообщение В , он шифрует сообщение, используя открытый ключ В KU b .
4. Когда В получает сообщение, он дешифрует его, используя свой закрытый ключ KR b . Никто другой не сможет дешифровать сообщение, так как этот закрытый ключ знает только В .

Если пользователь (конечная система) надежно хранит свой закрытый ключ , никто не сможет подсмотреть передаваемые сообщения.

Создание и проверка подписи состоит из следующих шагов:

Рис. 7.2.

1. Пользователь А создает пару ключей KR A и KU A , используемых для создания и проверки подписи передаваемых сообщений.
2. Пользователь А делает доступным некоторым надежным способом свой ключ проверки, т.е.