Отечественный стандарт шифрования ГОСТ 28147-89

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИИ И АВТОМАТИКИ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ) Факультет ВИС Базовая кафедра № 244

Реферат по дисциплине

" Методы и средства защиты ЗКИ"

тема

" Отечественный стандарт шифрования ГОСТ 28 147– — 89″

Выполнил студент Омельянюк В.В.

Группа ВАИУ — 02 — 09

Проверил Благов А.В.

Москва 2011

• Введение
• 1. Общее представление о ГОСТ 28 147–89
• 2. Режимы работы алгоритма ГОСТ 28 147–89
• 3. Атаки на системы защиты информации
• 4. Типы атак
• 5. Цели атак
• 6. Приемы и методы атак
• 7. Метод грубой силы
• 8. Атаки класса «встреча посередине»
• 9. Характеристики ГОСТ 28 147–89 и американского шифра Rijndael
• Заключение
• Список литературы

Стандарт шифрования ГОСТ 28 147–89 относится к симметричным (одноключевым) криптографическим алгоритмам. Он введен в действие с июля 1990 года и устанавливает единый алгоритм криптографических преобразований для систем обмена информацией в вычислительных сетях, определяет правила шифрования и расшифровки данных, а также выработки имитовставки. Алгоритм в основном удовлетворяет современным криптографическим требованиям, не накладывает ограничений на степень секретности защищаемой информации и обеспечивается сравнительно несложными аппаратными и программными средствами.

Несмотря на то, что ГОСТ 28 147–89 был принят в далеком 1989 году, в наши дни он является весьма широко используемым как в России, так и в мире в целом. Во-первых, этому способствует отечественное законодательство. Во-вторых, данный алгоритм разрабатывался с огромным запасом в криптостойкости, причем с совсем небольшим ущербом скорости шифрования.

1. Общее представление о ГОСТ 28 147–89

Алгоритм ГОСТ 28 147–89 является классическим алгоритмом симметричного шифрования на основе сети Фейстеля (см. рис.1). Данный алгоритм шифрует информацию блоками по 64 бита (такие алгоритмы называются «блочными»). Смысл сети Фейстеля состоит в том, что блок шифруемой информации разбивается на два или более субблоков, часть которых обрабатывается по определенному закону, после чего результат этой обработки накладывается (операцией побитового сложения по модулю 2) на необрабатываемые субблоки. Затем субблоки меняются местами, после чего обрабатываются снова и т. д. определенное для каждого алгоритма число раз — раундов.

Рис. 1. Сеть Фейстеля

Основное отличие алгоритмов симметричного шифрования друг от друга состоит именно в различных функциях обработки субблоков. Данная функция часто называется «основным криптографическим преобразованием», поскольку именно она несет основную нагрузку при шифровании информации. Основное преобразование алгоритма ГОСТ 28 147–89 является достаточно простым, что обеспечивает высокое быстродействие алгоритма; в нем выполняются следующие операции (см. рис.2):

американский шифр стандарт алгоритм Рис. 2. Основное преобразование алгоритма ГОСТ 28 147–89

1. Сложение субблока с определенным фрагменом ключа шифрования по модулю 232. Кх — это 32-битная часть («подключ») 256-битного ключа шифрования, который можно представить как конкатенацию 8 подключей: К = К0К1К2К3К4К5К6К7. В зависимости от номера раунда и режима работы алгоритма, для данной операции выбирается один из подключей.

2. Табличная замена. Для ее выполнения субблок разбивается на 8 4-битных фрагментов, каждый из которых прогоняется через свою таблицу замены. Таблица замены содержит в определенной последовательности значения от 0 до 15 (т.е. все варианты значений 4-битного фрагмента данных); на вход таблицы подается блок данных, числовое представление которого определяет номер выходного значения. Например, подается значение 5 на вход следующей таблицы: «13 0 11 74 91 10 143 5 122 15 8 6». В результате на выходе получается значение 9 (поскольку 0 заменяется на 13, 1 — на 0, 2 — на 11 и т. д.).

3. Побитовый циклический сдвиг данных внутри субблока на 11 бит влево.

2. Режимы работы алгоритма ГОСТ 28 147–89

Алгоритм ГОСТ 28 147–89 имеет 4 режима работы:

1. Режим простой замены.

2. Режим гаммирования.

3. Режим гаммирования с обратной связью.

4. Режим выработки имитоприставок.

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

Режим простой замены

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

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

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

К ((r — 1) % 8) — для раундов с 1 — го по 24-й (r обозначает номер раунда, а % - операция вычисления остатка от деления), т. е. К0, К1, К2, К3, К4, К5, К6, К7, К0, К1, К2 и т. д.;

К ((32 — r) % 8) — для раундов с 25-го по 32-й, т. е. в обратном порядке: К7, К6, К5, К4, К3, К2, К1, К0.

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

в прямом порядке в раундах с 1-го по 8-й;

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

Для собственно шифрования информации используются режимы гаммирования и гаммирования с обратной связью. В данных режимах шифрование информации производится побитовым сложением по модулю 2 каждого 64-битного блока шифруемой информации с блоком гаммы шифра. Гамма шифра — это псевдослучайная последовательность, вырабатываемая с использованием основного преобразования алгоритма ГОСТ 28 147–89 следующим образом (см. рис.3):

Рис. 3. Режим гаммирования

1. В регистры N1 и N2 записывается их начальное заполнение — 64-битная величина, называемая «синхропосылкой» .

2. Выполняется зашифровывание содержимого регистров N1 и N2 (в данном случае — синхропосылки) в режиме простой замены.

3. Содержимое N1 складывается по модулю (232 — 1) с константой С1 = 224 + 216 + 28 + 24, результат сложения записывается в регистр N1.

4. Содержимое N2 складывается по модулю 232 с константой С2 = 224 + 216 + 28 + 1, результат сложения записывается в регистр N2.

5. Содержимое регистров N1 и N2 подается на выход в качестве 64-битного блока гаммы шифра (т.е. в данном случае N1 и N2 образуют первый блок гаммы).

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

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

А Ч В Ч В=А

для любых последовательностей одинаковой размерности, А и В, где Ч — операция побитного сложения по модулю 2.

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

Существуют реализации алгоритма ГОСТ 28 147–89, в которых синхропосылка также является секретным элементом, наряду с ключом шифрования. Фактически в этом случае можно считать, что ключ шифрования увеличивается на длину синхропосылки (64 бита), что усиливает стойкость алгоритма.

Режим гаммирования с обратной связью

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

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

Шифрование открытых данных в этом режиме происходит по той же схемной реализации, что и в режиме гаммирования, и отличается лишь введением дополнительной обратной связи с выхода сумматора СМ5 на входы накопителей HI и Н2.

В ключевое запоминающее устройство вводится ключевая последовательность длиной 256 бит, после чего формируется синхропосылка S, записываемая в накопители HI и Н2, содержимое которых шифруется в режиме простой замены. Результат шифрования в накопителях HI и Н2 представляет собой первый 64-разрядный блок гаммашифра П.

Полученный гамма-шифр П суммируется поразрядно по модулю 2 с первым 64-разрядным блоком открытых данных Т0 1 в сумматоре СМ5. Результат суммирования — первый 64-разрядный блок зашифрованных данных Тш1. Первый блок зашифрованных данных Тш1 по обратной связи поступает на накопители Н1 и Н2 и является исходной информацией для формирования второго блока гамма-шифра Г2.

Содержимое накопителей HI и Н2 шифруется в режиме простой замены. Результат шифрования в накопителях HI и Н2 представляет второй 64-разрядный блок гамма-шифра Г2. Этот гамма-шифр суммируется по модулю 2 поразрядно со вторым 64разрядным блоком открытых данных Т02 в сумматоре СМ 5. В результате получается второй 64-разрядный блок зашифрованных данных Тш2 и т. д. Если в последнем m блоке открытых данных Тот число двоичных разрядов меньше 64, неиспользованная часть гамма-шифра отбрасывается.

Расшифровка данных происходит в обратном порядке на основе знания ключевой последовательности и синхропосылки S.

Режима выработки имитоприставок

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

В режиме выработки имитоприставки выполняются следующие операции:

1. Первый 64-битный блок информации, для которой вычисляется имитоприставка, записывается в регистры N1 и N2 и зашифровывается в сокращенном режиме простой замены, в котором выполняется 16 раундов основного преобразования вместо32-х.

2. Полученный результат суммируется по модулю 2 со следующим блоком открытого текста и сохраняется в N1 и N2.

3. И т.д. до последнего блока открытого текста.

В качестве имитоприставки используется результирующее содержимое регистров N1 и N2 или его часть (в зависимости от требуемого уровня стойкости) — часто имитоприставкой считается 32-битное содержимое регистра N1.

С учетом способности процессоров Intel Pentium параллельно выполнять команды, раунд ГОСТа может быть реализован за 6 тактов работы процессора, а весь процесс шифрования — за 32*6 = 192 такта. Добавляя еще 8 тактов на различные внутрипроцессорные задержки, получим оценку затрат процессорного времени на реализацию цикла шифрования по алгоритму ГОСТ 28 147–89 в 200 тактов. На процессоре Pentium Pro 200 это позволит достичь предела быстродействия шифрования миллион блоков в секунду, или 8 Мбайт/с (на самом деле эта величина будет меньше).

3. Атаки на системы защиты информации

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

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

Рис. 4. Пассивный перехват зашифрованных данных.

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

Рис. 5. Активное воздействие на шифратор

4. Типы атак

В зависимости от данных, которые криптоаналитик может «добыть» у шифратора, существуют следующие виды атак:

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

2. Атака с выбранным открытым текстом. У криптоаналитика есть возможность выбора открытых текстов для получения соответствующих им шифртекстов (как это может быть полезно криптоаналитику, будет рассмотрено ниже).

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

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

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

Теперь опишем существующие криптоаналитические методы — от более простых к более сложным.

5. Цели атак

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

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

6. Приемы и методы атак

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

Наиболее известный прием атаки носит название метод грубой силы. Суть его — в простом переборе всех возможных вариантов ключей шифрования алгоритма. Следовательно, чтобы исключить появление условий для такой атаки, алгоритм шифрования должен только иметь достаточно длинный ключ. Именно поэтому одно из главных требований при разработке современных алгоритмов симметричного шифрования — размер ключа не менее 128 бит. Считается, что такой длины ключа (при сегодняшнем состоянии вычислительной техники и с учетом ее развития) должно заведомо хватить на десятки лет вперед. Впрочем, разработчики алгоритма DES в 1977 г. также считали достаточным его 56-разрядный ключ.

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

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

Рис. 3. Дифференциальный криптоанализ.

С другой стороны, современные криптостойкие алгоритмы шифрования разрабатываются с учетом всех известных криптоаналитических атак. Так, на проходивших недавно конкурсах по выбору стандартов шифрования — в США это конкурс AES (Advanced Encryption Standard), в Евросоюзе — конкурс NESSIE (New European Schemes for Signatures, Integrity, and Encryption) — алгоритмы, претендующие на роль стандарта, анализировались на стойкость не только ко всем известным атакам, но и к потенциально возможным.

Атаки на реализации

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

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

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

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

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

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

подача на вход питания напряжения, существенно большего, чем расчетное, — пиковая атака;

изменение тактовой частоты шифратора при использовании внешней управляющей синхронизации;

облучение шифратора точно наведенным пучком света — оптическая атака;

подача на вход шифратора специально подобранных неверных данных для расшифровывания.

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

Рис. 4. Активное воздействие на шифратор.

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

7. Метод грубой силы

Метод грубой силы (brute-force attack) предполагает перебор всех возможных вариантов ключа шифрования до нахождения искомого ключа.

Пусть размер ключа шифрования в битах равен b. Соответственно, существует 2b вариантов ключа. Криптоаналитик должен методично перебрать все возможные ключи, т. е. (если рассматривать b-битную последовательность как число) применить в качестве ключа значение 0, затем 1, 2, 3 и т. д. до максимально возможного (2b — 1). В результате ключ шифрования обязательно будет найден, причем в среднем такой поиск потребует 2b/2, т. е.2b-1 тестовых операций шифрования.

Понятно, что необходим какой-либо критерий правильности найденного ключа. С атакой с известным открытым текстом все достаточно просто — при тестировании каждого ключа Kx шифртекст C расшифровывается (в результате получается некое значение M') и сравнивается с соответствующим ему открытым текстом M; совпадение M = M' говорит о том, что искомый ключ найден.

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

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

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

3. Стоит отметить, что многие средства шифрования информации внедряют в формат зашифрованного объекта контрольную сумму открытого текста для проверки его целостности после расшифрования (см. подробное описание в [14]). Это может быть, например, имитоприставка, вычисленная согласно отечественному криптостандарту ГОСТ 28 147–89 [13], или просто CRC32. Главное, что такая контрольная сумма может быть идеальным эталоном при криптоанализе, вполне подходящим для определения верного ключа.

Защита от атак методом грубой силы весьма проста — достаточно лишь увеличить размер ключа. Понятно, что увеличение размера ключа на 1 бит увеличит количество ключей (и среднее время атаки) в 2 раза.

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

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

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

Все эти методы были опробованы на стандарте шифрования США DES. Еще при его принятии в качестве стандарта у многих специалистов возникли обоснованные сомнения в достаточности размера его ключа (56 бит). Причем, с развитием компьютерной техники полный перебор ключа становился все более реальным. В 1993 году Майкл Винер (Michael Wiener) разработал принципы конструкции специализированного компьютера стоимостью порядка $ 1 000 000, способного перебрать ключи DES за 3,5 часа. Причем, данный компьютер имел возможность наращивания — при не фантастических для крупной организации или спецслужбы затратах порядка $ 10 000 000 полный перебор ключа DES должен был занять не более 21 минуты. Ясно, что сейчас такой компьютер стоил бы в десятки раз дешевле.

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

Современная вычислительная техника не позволяет «в лоб» атаковать 128-битный ключ полным перебором. Однако, атаки методом грубой силы часто используются в контексте других атак — например, с помощью дифференциального криптоанализа (данный метод будет описан в следующей части статьи) сужается область возможных ключей, после чего выполняется перебор оставшихся вариантов (один из вариантов подобной атаки описан в работе [2]).

8. Атаки класса «встреча посередине»

Атака «встреча посередине» была изобретена в 1981 г. известными криптологами Ральфом Мерклем (Ralph C. Merkle) и Мартином Хеллманом (Martin E. Hellman) именно в применении к алгоритму Double DES. Кроме того, эта атака (но в заметно более сложном исполнении) применима и к одному из вариантов «тройного» DES (Triple DES).

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

1. Атака «встреча посередине» позволяет вычислить 192-битный ключ алгоритма DEAL (один из участников конкурса AES — см.) выполнением порядка 2¹⁶⁶ тестовых операций шифрования; для вычисления 256-битного ключа необходимо порядка 2²²² операций. И то, и другое не является практически осуществимым, но доказывает невысокий запас криптостойкости алгоритма DEAL.

2. Аналогично непрактичная атака возможна против еще одного участника конкурса AES — SAFER +. Для его вскрытия необходимо 2²⁴⁰ операций шифрования (при 256-битном ключе).

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

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

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

Простейший пример атак класса встреча посередине (meet-in-the-middle) — вскрытие любого алгоритма шифрования, представляющего собой двойное шифрование данных с помощью какого-либо «одинарного» алгоритма. Рассмотрим алгоритм Double DES, представляющий собой двойное шифрование обычным DES’ом (см. рис.5):

Рис. 5 Алгоритм Double DES.

C = DES_k2/2 (DES_k½ (M)),

где k_½ и k_2/2 — половины двойного ключа алгоритма Double DES, каждая из которых представляет собой обычный 56-битный ключ DES.

Double DES решает основную проблему алгоритма DES (56-битный ключ шифрования слишком короток — как было показано выше) — 112-битный ключ Double DES невозможно вскрыть полным перебором. Однако, вскрытие Double DES легко выполняется атакой на основе известных открытых текстов. Предположим, у криптоаналитика есть открытый текст M1 и результат его зашифрования — С1. Он может выполнить следующую последовательность действий (см. рис.6):

Рис. 6 Пример атаки «встреча посередине» .

1. Выполняется зашифрование DES_kx (M1) на всем ключевом множестве (kx = 0…2⁵⁶-1) с записью результатов в некоторую таблицу.

2. Производится расшифрование DES^-1_ky (C1) также на всем ключевом множестве; результаты расшифрования сравниваются со всеми записями в таблице, сформированной на шаге 1.

3. Если какой-либо результат, полученный на шаге 2, совпал с одним из результатов шага 1, то можно предположить, что нужный ключ найден, т. е. соответствует совпадающему результату kx = k_½, а ky = k_2/2.

Следует учесть, что таких совпадений может быть много — порядка 2⁴⁸. Для «уточнения» правильного ключа из этих примерно 2⁴⁸ вариантов достаточно наличия еще одной пары текстов: M2 и C2. Криптоаналитик может использовать их абсолютно так же, как и первую пару (M1, C1), но перебор вариантов kx и ky осуществляется уже только по совпадениям первого перебора. В результате будет найден единственно верный ключ (вероятность повторного совпадения ничтожно мала — около 2^-16, в этом случае используется третья пара — M3 и C3 — при ее наличии).

В результате воздействия данной атаки сложность вычисления ключа Double DES всего в 2 раза выше, чем полный перебор ключей обычного DES, что несравнимо меньше 2¹¹² возможных вариантов «двойного» ключа. Алгоритм Double DES, собственно, и не используется, а упоминается лишь в подобных иллюстрациях к атаке «встреча посередине» .

9. Характеристики ГОСТ 28 147–89 и американского шифра Rijndael

Характеристики быстродействия программных реализаций, выполненных по алгоритму ГОСТ 28 147–89 и новому американскому стандарту шифрования — шифру Rijndael.

Рассмотренные алгоритмы обладают сопоставимыми характеристиками быстродействия при реализации на 32-битных платформах. При использовании 8-битных платформ картина будет примерно такой же.

Что касается аппаратной реализации, то, в отличие от алгоритмов шифрования ГОСТа, Rijnael позволяет достичь высокой степени параллелизма при выполнении шифрования, оперирует блоками меньшего размера и содержит меньшее число раундов, в силу чего его аппаратная реализация на базе одной и той же технологии теоретически может быть более быстродействующей (примерно в 4 раза).

Проведенное выше сопоставление параметров алгоритмов шифрования ГОСТ 2 814 789 и Rijndael показывает, что, несмотря на существенное различие архитектурных принципов, на которых базируются шифры, их основные рабочие параметры примерно одинаковы. Исключением является то, что, по всей вероятности, Rijnael будет иметь определенное преимущество в быстродействии перед ГОСТом при аппаратной реализации на базе одной и той же технологии. По ключевым параметрам криптостойкости для алгоритмов такого рода ни один из них не обладает значительным преимуществом; примерно одинаковы и скорости оптимальной программной реализации для процессоров Intel Pentium, что можно экстраполировать на все современные 32-разрядные процессоры. Таким образом, можно сделать вывод, что отечественный стандарт шифрования соответствует требованиям, предъявляемым к современным шифрам, и может оставаться стандартом еще достаточно долгое время. Очевидным шагом в его оптимизации может стать переход от замен в 4-битных группах к байтовым заменам, за счет чего должна возрасти устойчивость алгоритма к известным видам криптоанализа.

Заключение

В шифре ГОСТ 28 147–89 используется 256-битовый ключ, и объем ключевого пространства составляет 2256. Ни на одном из существующих в настоящее время или предполагаемых к реализации в недалеком будущем компьютере общего применения нельзя подобрать ключ за время, меньшее многих сотен лет. Российский стандарт ГОСТ 28 147–89 проектировался с большим запасом и по стойкости на много порядков превосходит американский стандарт DES с его реальным размером ключа в 56 бит и объемом ключевого пространства всего 256.

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

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

При разработке алгоритма ГОСТ 28 147–89 криптографами отечественных спецслужб была заложена избыточная стойкость — до сих пор не известны более эффективные методы взлома данного алгоритма, чем метод полного перебора возможных вариантов ключей шифрования. А полный перебор 2256 ключей (не считая секретной синхропосылки) при современном развитии компьютерной техники за реальное время осуществить невозможно.

Российский стандарт шифрования ГОСТ 28 147–89 удобен как для аппаратной, так и для программной реализации. При размере блока данных 64 бита основная работа ведется с половинками этого блока — 32-битными словами, что позволяет эффективно реализовать российский стандарт шифрования на большинстве современных компьютеров.

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

1. http://daily. sec.ru/publication. cfm? rid=45&pid=9574

2. http://www.des-crypto.ru/cryptography/gost/

3. http://www.rsdn.ru/article/crypto/gost28147₁. xml

4. http://www.bytemag.ru/articles/detail. php? ID=9053

5. http://www.paveldvlip.ru/algorithms/gost_28 147−89.html