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

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

В чем измеряется производительность кода? Поскольку я первый об этом заговорил, то по праву первооткрывателя буду его измерять в RTT-шках;).

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

Студент ответит - одну, его преподаватель подумает и скажет, что четыре, профессионал - что пока только двенадцать операций.

Так вот, программный код, который загружает все исполнительные устройства процессора одновременно на протяжении всего времени исполнения кода, будет иметь производительность 12 RTT-шек. Максимум! Честно признаюсь, такого кода я раньше не писал, но в этой статье попытаюсь сделать над собой усилие.

Я докажу, что код с одновременным выполнением двенадцати 32-битных операций - возможен

Программный код, который использует в процессорном ядре одно исполнительное устройство, естественно, будет иметь производительность в 1 RTT-шку. Такой производительностью кода могут «похвастаться» программы, генерируемые компиляторами языков высокого уровня, и интерпретаторы виртуальных машин. Не нужно считать, что показатель загрузки процессора, который можно увидеть в диспетчере задач ОС, может служить объективным критерием эффективности кода. Загрузка ядра процессора может быть 100%, но при этом программный код будет использовать одно исполнительное устройство в нем (производительность 1 RTT). В этом случае при 100%-й загрузке процессорное ядро будет работать в 1/12 своей максимальной производительности. Другими словами, когда в диспетчере задач ОС Windows показывается максимальная загрузка процессора, его реальная производительность может варьироваться от 1 до 12 RTT. Увидев в окне производительности 100%-ю загрузку на каком-либо процессорном ядре, неправильно считать, что в этом ядре работают все исполнительные устройства, отнюдь!

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

Традиционная реализация ГОСТ 28147-89

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

Криптографическое преобразование по ГОСТ 28147-89 используется для поточного шифрования информации в каналах связи и на дисковых накопителях.

В настоящее время повсеместно применяется программная реализация данного ГОСТа на РОН центрального процессора. В известных методах реализации ГОСТа вся секретная информация (ключи шифрования, блоки замен) размещаются в оперативной памяти. Это снижает надежность шифрования, поскольку, имея дамп оперативной памяти, можно полностью выявить все секретные элементы криптопреобразования. Кроме этого, метод имеет ограничения по быстродействию, обусловленные расположением основных объектов криптопреобразования в ОП и неполной загрузкой исполнительных устройств ALU. Современные процессоры, реализуя криптопроцедуру по известному методу, могут обеспечить скорость шифрования на уровне 40–60 мегабайт в секунду. И если уж разбираться до конца, то причиной низкого быстродействия и слабой защищенности криптопреобразования является программная реализация блока подстановок. Описание его в ГОСТе см. на рис. 1.

По п. 1.2 ГОСТа этот блок реализует тетрадные (по четыре бита) перестановки в 32-битном слове, но архитектура процессора х86/64 и его система команд не способна эффективно манипулировать тетрадами.

Для программной реализации блока подстановок используют специальные таблицы в оперативной памяти, подготавливаемые на этапе инициализации криптофункции. Эти таблицы объединяют узлы замен смежных тетрад в байтовые таблицы размером 8 × 8 бит, таким образом, в оперативной памяти размещается четыре 256-байтных таблицы.

В более продвинутых реализациях эти таблицы имеют размер 1024 байта (256 слов по четыре байта). Это сделано для того, чтобы реализовать в таблицах дополнительно циклический сдвиг на 11 позиций полученного в результате подстановки 32-битного слова (следующая операция алгоритма преобразования по ГОСТу). Пример реализации ГОСТа по данному методу показан в приложении 1 (на диске).

Информация блока подстановок является секретным компонентом криптофункции (как это сформулировано в ГОСТе, см. на рис. 2).

Размещение этих таблиц с ключами блока подстановок в ОП противоречит требованиям ГОСТа (п. 1.7), поскольку секретная информация становится доступной для сторонних программ, работающих на вычислительной установке. ФСБ, сертифицирующая в том числе и программные реализации шифрования по ГОСТу, на данное нарушение смотрит, мягко говоря, снисходительно. Если для размещения ключей в ОП ФСБ еще требует наличия «фигового листочка» - маскирования ключей операцией XOR, то для блоков замен в ОП ничего не требуется, они хранятся в открытом виде.

Короче говоря, ФСБ пропускает такие программные реализации криптопроцедуры, несмотря на явное снижение стойкости такого решения и прямое нарушение собственных требований по ГОСТу (п. 1.7). И это несмотря на общеизвестные методы взлома шифров через съем дампа памяти…

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

Но хватит лирики, важно в рамках рассматриваемой темы то, что этот программный код имеет производительность в 1 RTT-шку. Теперь напишем код с производительностью 2 RTT-шки.

Многопоточная реализация ГОСТ 28147-89

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

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

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

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

Загрузкой работой всех АЛУ управляет специальный аппаратный блок внутри процессорного ядра - планировщик, который просматривает исполняемый код форвардно, на глубину до 32–64 байт. Если планировщик обнаруживает команды, которые можно запускать на АЛУ без конфликтов, то он их запускает одновременно на разных исполнительных устройствах. При этом счетчик выполненных команд указывает на ту исполняемую команду (их в такой схеме несколько), после которой все команды уже выполнены.

Большинство программных последовательностей, генерируемых автоматически (компиляторами), не могут загрузить все АЛУ и FPU, находящиеся в ядре процессора. В этом случае оборудование процессора простаивает, что значительно снижает его результирующую производительность. Разработчики процессоров это понимают и вводят режимы увеличения частоты ядра, когда оборудование используется не полностью. Также для этого предназначены системы гипертрейдинга, и эту систему я буду использовать для «прессования» кода по максимуму в дальнейшем.

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

Характерной иллюстрацией возможности выполнения нескольких независимых программных потоков на одном ядре процессора служит реализация ГОСТа, выполняемая в два потока на единственном ядре процессора. Идея кода проста: имеется два блока данных для шифрации/дешифрации, но одно ядро процессора, которое будет выполнять преобразование. Можно выполнить для этих двух блоков данных преобразование последовательно, так и делается до настоящего времени. В этом случае время, требуемое на выполнение преобразований, удваивается.

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

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

Далее показан пример с чередованием команд из разных потоков обработки. В этом случае команды, относящиеся к разным блокам данных, чередуются. Планировщик выбирает независимые друг от друга команды и передает их на выполнение в АЛУ1 и АЛУ2. Группировка команд первого и второго потока на этих АЛУ осуществляется автоматически, поскольку в алгоритм работы планировщика заложена группировка команд с зацеплением по общим данным на одном и том же исполнительном устройстве.

Чтобы такой программный код работал без простоев АЛУ, необходимо, чтобы каждый программный поток работал со своим набором регистров. Кеш в этой схеме становится узким местом (у него только два порта выдачи данных), поэтому ключи храним в MMX-регистрах. Поскольку в данном случае узлы замены (и сдвига) в памяти только читаются, то они могут быть общими для обоих программных потоков.

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

Метод параллельного шифрования эффективно реализуется только для 64-битного режима работы процессора, поскольку в этом режиме имеется достаточное количество РОН (целых 16 штук!). Пример реализации ГОСТа по данному методу показан в приложении 2 (на диске).

Ясно, что данная реализация ГОСТа имеет производительность кода 2 RTT-шки. А теперь посмотрим, как это сказывается на времени выполнения.

Цикл шифрования для одного потока (приложение 1) составляет 352 такта, и за это время обсчитывается 8 байт данных, для двухпоточной реализации ГОСТа (приложение 2) требуется 416 тактов процессора, но при этом обсчитывается 16 байт. Таким образом, результирующая скорость преобразования повышается с 80 до 144 мегабайт для процессора частотой 3,6 ГГц.

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

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

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

Использование SSE-регистров и AVX-команд современных процессоров для реализации ГОСТ 28147-89

Современные процессоры архитектуры х86/64 имеют в своем составе набор регистров SSE размером 16 байт и специализированные FPU (как минимум два) для выполнения различных операций над этими регистрами. Возможна реализация ГОСТа на этом оборудовании, причем в этом случае узлы замены можно размещать не в виде таблиц в оперативной памяти, а непосредственно на выделенных SSE-регистрах.

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

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

Схема одного из возможных размещений узлов замены на SSE-регистрах показана на рис. 4.

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

• Ядро процессора переведено в режим хоста гипервизора, и в нем принудительно отключен блок прерываний (APIC). В этом случае ядро процессора полностью изолировано от ОС и приложений, функционирующих на вычислительной установке.
• Загрузка SSE-регистров и изоляция вычислительного ядра производится до начала старта ОС, оптимальным является выполнение этих процедур с модуля доверенной загрузки (МДЗ).
• Программы криптопроцедур по ГОСТу размещаются в немодифицируемой области памяти вычислительной установки (либо БИОС, либо в флеш-памяти МДЗ).

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

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

Имея узлы хранения подстановок на SSE-регистрах и многовходовый коммутатор в блоках FPU, можно организовать следующее преобразование в блоке подстановок (рис. 5).

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

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

Работой коммутаторов управляет специальная трехадресная команда AVX VPSHUFB. Ее первый операнд является приемником информации из коммутаторов, второй - источником, к которому подключены входы коммутаторов. Третий операнд является управляющим регистром для коммутаторов, каждый байт которого ассоциирован с соответствующим коммутатором; значение в нем задает номер направления, с которого коммутатор считывает информацию. Описание этой команды из официальной документации Intel см. на рис. 5. На рис. 6 приведена схема работы этой команды - изображена только половина SSE-регистров, для второй половины все аналогично.

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

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

Как говорится, «Наш финиш - горизонт», поэтому выжимать так выжимать... будем прессовать и складывать в пакеты!

Это не игра слов, а суровая FPUшная реальность - регистры SSE можно разбивать на равные части и выполнять над этими частями одинаковые преобразования одной командой. Для того чтобы процессор это понял, имеется магическая буковка «Р» - пакет, которая ставится перед мнемоникой команды, и не менее магические буковки «Q», «D», «W», «B», которые ставятся в конце и объявляют, на какие части разбиты в этой команде регистры SSE.

Нас интересует пакетный режим с разбивкой SSE-регистра на четыре 32-битных блока; соответственно, все команды будут иметь префикс «P», а в конце - символ «D». Это дает возможность одной процессорной командой параллельно обрабатывать сразу четыре блока по 32 бита, то есть в параллель рассчитывать четыре блока данных.

Программа, реализующая этот метод, имеется в приложении 3, там же - все пояснения.

Впрочем, прессовать так прессовать! В современных процессорах имеется как минимум два блока FPU, и для их полной загрузки можно использовать два потока независимых команд. Если грамотно чередовать команды из независимых потоков, то можно загрузить работой оба блока FPU полностью и получить сразу восемь параллельно обрабатываемых потоков данных. Такая программка была написана, и ее можно посмотреть в приложении 4, только смотреть нужно осторожно - можно слететь с катушек. Это, что называется, «код не для всех...».

Цена вопроса

Использование SSE-регистров для хранения узлов замены понятно - оно дает некую гарантию изоляции секретной информации, а вот смысл расчета самой криптофункции на FPU неочевиден. Поэтому были проведены замеры времени выполнения стандартных процедур по методу прямой замены в соответствии с ГОСТом для четырех и для восьми потоков.

Для четырех потоков была получена скорость выполнения 472 процессорных такта. Таким образом, для процессора с частотой 3,6 ГГц один поток считается со скоростью 59 мегабайт в секунду, а четыре потока соответственно со скоростью 236 мегабайт в секунду.

Для восьми потоков была получена скорость выполнения 580 процессорных тактов. Таким образом, для процессора с частотой 3,6 ГГц один поток считается со скоростью 49 мегабайт в секунду, а восемь потоков со скоростью 392 мегабайта в секунду.

Как может заметить читатель, код в примере № 3 имеет производительность 4 RTT, а код в примере № 4 имеет производительность 8 RTT. В этих примерах на SSE-регистрах закономерности те же, что и при использовании РОН, только планировщик снизил свою эффективность. Сейчас он обеспечивает 20%-е увеличение длительности при двукратном увеличении длины кода.

Причем эти результаты были получены с использованием универсальных AVX-команд, имеющихся как в процессорах Intel, так и в процессорах AMD. Если выполнить оптимизацию под процессор AMD, результат будет значительно лучше. Звучит поперек тренда, но тем не менее это правда, и вот почему: процессоры AMD имеют дополнительный набор команд, так называемое XOP-расширение, и в этом дополнительном наборе команд есть такие, которые значительно упрощают реализацию алгоритма ГОСТа.

Имеются в виду команды логического пакетного сдвига байтов и пакетного циклического сдвига двойных слов. В примерах, приведенных в приложениях 3 и 4, используются последовательности универсальных команд, реализующих необходимое преобразование: в первом случае одна «лишняя» команда, а в другом случае сразу четыре лишних команды. Так что резервы оптимизации есть, и немалые.

Если речь зашла о дальнейшей оптимизации, нелишне помнить о наличии 256-битных регистров (YMM-регистры), используя которые можно теоретически еще удвоить скорость вычислений. Но пока это только перспектива, на данный момент процессоры очень сильно замедляются, когда выполняют 256-битные инструкции (FPU имеют ширину тракта 128 бит). Эксперименты показали, что на современных процессорах счет в 16 потоков на YMM-регистрах выигрыша не дает. Но это только пока, на новых моделях процессоров, несомненно, будет увеличено быстродействие 256-битных команд, и тогда использование 16 параллельных потоков станет целесообразно и приведет к еще большему увеличению скорости работы криптопроцедуры.

Теоретически можно рассчитывать на скорость 600–700 мегабайт в секунду при наличии в процессоре двух FPU с шириной рабочего тракта 256 бит каждый. В этом случае можно говорить о написании кода с эффективностью 16 RTT, и это не фантастика, а ближайшая перспектива.

Смешанный режим

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

Рассчитывать на прибавку в 50% здесь не приходится, узким местом становится кеш-память, где хранятся технологические маски, но прибавку в 100 дополнительных мегабайт все же получить можно. Этот вариант не приведен в приложениях (макросы аналогичны используемым в коде на 8 RTT), но он имеется в программных файлах. Так что если кто не верит в возможность шифрования со скоростью 500 мегабайт в секунду на одном процессорном ядре, пусть запустит тестовые файлы. Там же есть и тексты с комментариями, чтобы никто не подумал, что я лукавлю.

Такой фокус возможен только на процессорах Intel, у AMD только два блока FPU на два процессорных модуля (аналог режима гипертрейдинг). Но зато имеется еще четыре АЛУ, которые грех не использовать.

Можно загнать процессорные модули «Бульдозера» в режим, аналогичный режиму гипертрейдинга, но запускать на разных модулях в одном потоке преобразование на РОН, а в другом потоке на SSE-регистрах и получить те же 12 RTT. Этот вариант я не проверял, но, думаю, на AMD код в 12 RTT будет работать более эффективно. Желающие могут попробовать, тестовые программы можно подкорректировать для работы на «Бульдозерах» достаточно легко.

Кому это нужно?

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

Причем, как это ни странно, встроенное в процессоры шифрование по AES-алгоритму оказывается значительно медленнее, тесты показывают скорость на уровне 100–150 мегабайт в секунду, и это при аппаратной реализации алгоритма! Проблема заключается в однопоточном счете и блоке замен, который оперирует байтами (таблица из 256 строк). Так что ГОСТ оказывается эффективнее в реализации на архитектуре х86/64, кто бы мог подумать…

Это если говорить о достигнутом уровне скорости шифрования. А если иметь в виду теоретические изыски в области повышения эффективности кода, то скорее всего это никому не нужно. Специалистов уровня 3–6 RTT практически нет, компиляторы вообще генерят код на уровне 1–2,5 RTT, а основная масса программистов не знает ассемблера, а если и знает его правописание, то не понимает устройства современного процессора. А без этих знаний что ассемблер, что какой-нибудь там СИ-шарп - без разницы.

Но не все так печально: в «сухом остатке» после недели бессонных ночей имеется новый алгоритм реализации ГОСТа, который грех не запатентовать. И заявки на патенты (целых три) уже оформлены и поданы, так что, господа коммерсанты, выстраивайтесь в очередь - женщинам и детям скидка.

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

Николя Куртуа - «великий и ужасный»

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

В октябре 2010 года был начат процесс рассмотрения вопроса о включении алгоритма ГОСТ 28147-89 в международный стандарт ISO/IEC 18033-3. Уже в мае 2011 года на электронном архиве ePrint появилась статья известного криптографа Николя Куртуа , отмеченного весьма неоднозначным отношением к нему мирового криптографического сообщества. Публикации Куртуа представляют собой печальный пример манипулирования понятиями, которое не открывает никаких новых свойств рассматриваемого объекта, но с претензией на сенсацию провоцирует распространение в некомпетентной среде ошибочных мнений о его действительных свойствах.

Алгебраический метод

Рассуждения Куртуа строятся вокруг двух классов методов криптоанализа: алгебраических методов и дифференциальных. Рассмотрим первый класс методов.

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

Алгебраический метод, эксплуатируемый Куртуа, коротко можно описать так. На первом этапе используются такие свойства ГОСТ 28147-89, как существование неподвижной точки для части шифрующего преобразования, а также так называемой точки отражения (reflection point). Благодаря этим свойствам из достаточно большого количества пар открытых-шифрованных текстов выбирается несколько пар, которые позволяют рассматривать преобразования не на 32, а лишь на 8 раундах. Второй этап состоит в том, что по полученным на первом этапе результатам 8-ми раундовых преобразований строится система нелинейных уравнений, неизвестными в которой являются биты ключа. Далее эта система решается (это звучит просто, но в действительности является самой трудоемкой частью метода, т.к. система состоит из нелинейных уравнений).

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

Дифференциальный метод

Рассмотрим второй метод Куртуа, который основан на дифференциальном криптоанализе.

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

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

Куртуа использует несколько модифицированный вариант дифференциального метода. Сразу же отметим, что свой анализ Куртуа проводит для S-блоков, отличных от действующих и от предложенных в ISO. В работе приводятся дифференциальные характеристики (те самые номера, в которых должны отличаться блоки) для малого числа раундов. Обоснование продления характеристик на большее число раундов, как водится, основано на «фактах». Куртуа высказывает, опять же, ничем, кроме его авторитета, не подкрепленное предположение, что изменение S-блоков не повлияет на стойкость ГОСТ 28147-89 против его атаки (при этом по непонятным причинам S-блоки из 1-го рабочего проекта дополнения к стандарту ISO/IEC 18033-3 не рассматривались). Анализ, проведенный авторами статьи , показывает, что даже если принять на веру необоснованные «факты» Куртуа и провести анализ ГОСТ 28147-89 с другими S-блоками, то атака опять же оказывается не лучше полного перебора.

Детальный анализ работ Куртуа с подробным обоснованием беспочвенности всех утверждений о снижении стойкости российского стандарта был проведен в работах [ , ].

При этом абсолютное отсутствие аккуратности выкладок признает даже сам Куртуа! Следующий слайд взят из презентации Куртуа на секции коротких объявлений FSE 2012.

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

• «I think that the audiences of Asiacrypt will not feel it is interesting». Рецензент Asiacrypt 2011.
• «… there is a big, big, big problem: this attack, which is the main contribution of the paper has already been published at FSE’11 (it was even the best paper), …». Рецензент Crypto 2011.

Таким образом, профессиональная часть международной криптографической общественности относится к качеству работ Куртуа с не меньшим сомнением, чем, скажем, к не подтвержденным никакими последовательными выкладками заявлениям некоторых российских специалистов об их умении взламывать AES за 2 100 или к очередным "доказательствам" на две страницы гипотезы о неравенстве сложностных классов P и NP.

Атаки Исобе и Динура-Данкельмана-Шамира

Общая идея атак Исобе () и Динура-Данкельмана-Шамира (далее: атака ДДШ) () заключается в построении для определенного (зависящего от ключа) узкого множества открытых текстов эквивалентного на этом множестве преобразования, имеющего более простую, чем само шифрующее преобразование, структуру. В случае метода Исобе это множество таких 64-битных блоков x, что F 8 -1 (Swap(F 8 (z))) = z, где z = F 16 (x), через F 8 (x) и F 16 (x) обозначены первые 8 и первые 16 раундов шифрования ГОСТ 28147-89 соответственно, через Swap - операция обмена местами половинок 64-байтового слова. При попадании открытого текста в это множество результат полного 32-раундового преобразования ГОСТ 28147-89 совпадает с результатом 16-раундового, что и эксплуатируется автором атаки. В случае метода ДДШ это множество таких x, что F 8 (x) = x (неподвижная точка преобразования F 8). Для всякого открытого текста из этого множества преобразование ГОСТ 28147-89 работает в точности так же, как последние его 8 раундов, что и упрощает анализ.

Трудоемкость атаки Исобе составляет 2 224 операций зашифрования, атаки ДДШ - 2 192 . Однако все вопросы о том, следует ли, что атаки Исобе и ДДШ вносят новые ограничения на условия применения нашего алгоритма, снимает оценка требований к объему материала, необходимого для проведения каждой из атак: для метода Исобе требуется 2 32 пар открытых и шифрованных текстов, а для метода ДДШ - 2 64 . Обработка таких объемов материала без смены ключа априорно неприемлема для любого блокового шифра с длиной блока 64: на материале объемом 2 32 , с учетом задачи о днях рождения (см., например, ), близка к 1/2 вероятность появления повторяющихся блоков, что предоставит нарушителю возможность делать по шифрованным текстам некоторые заключения об открытых текстах без определения ключа. Наличие же 2 64 пар открытых и шифрованных текстов, полученных на одном ключе, фактически позволяет противнику осуществлять операции зашифрования и расшифрования вообще без знания этого ключа. Это обусловлено чисто комбинаторным свойством: противник в этом случае обладает всей таблицей шифрующего преобразования. Такая ситуация абсолютно недопустима ни при каких разумных эксплуатационных требованиях. Например, в КриптоПро CSP присутствует техническое ограничение на объём шифруемого (без преобразования ключа) материала в 4 Мб (см. ). Таким образом, строгий запрет на использование ключа на материале такого объема присущ всякому блоковому шифру с длиной блока 64 бита, а следовательно, атаки Исобе и ДДШ никоим образом не сужают область использования алгоритма ГОСТ 28147-89 при сохранении максимально возможной стойкости 2 256 .

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

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

Отметим, что определенные небрежности в оценках средней трудоемкости присутствуют и в работе Динура, Данкельмана и Шамира. Так, при построении атаки не уделяется должного внимания следующему моменту: для существенной доли ключей множество открытых текстов x, таких, что F 8 (x) = x, является пустым: неподвижных точек у 8 раундов преобразования может просто не быть. Существование неподвижных точек зависит также и от выбора узлов замены. Таким образом, атака является применимой только при определенных узлах замены и ключах.

Стоит упомянуть также еще об одной работе с атакой на ГОСТ 28147-89. В феврале 2012 года на электронном архиве ePrint международной криптографической ассоциации появилась обновленная версия статьи (от ноября 2011 года), которая содержала новую атаку на ГОСТ 28147-89. Характеристики представленной атаки таковы: объем материала - 2 32 (как у Исобе), а трудоемкость - 2 192 (как у ДДШ). Таким образом, эта атака улучшала рекордную по времени атаку ДДШ по объему материала с 2 64 до 2 32 . Отметим отдельно, что авторы честно привели все выкладки с обоснованием трудоемкости и объема материала. Через 9 месяцев в приведенных выкладках была найдена принципиальная ошибка, и с ноября 2012 года обновленная версия статьи в электронном архиве уже не содержит каких-либо результатов касательно отечественного алгоритма.

Атаки в предположении, что нарушитель знает «кое-что» о ключах

Заметим напоследок, что в литературе также имеется некоторое количество работ (см., например, и ), посвященных атакам на ГОСТ 28147-89 в так называемой модели со связанными ключами. Данная модель в своей основе содержит предположение о возможности нарушителя получать доступ для анализа не просто к парам открытых и шифрованных с помощью искомого ключа текстов, но также к парам открытых и шифрованных текстов, полученных с помощью (также неизвестных) ключей, отличающихся от искомого известным регулярным образом (например, в фиксированных битовых позициях). В данной модели действительно удается получить интересные результаты о ГОСТ 28147-89, однако в этой модели не менее сильные результаты удается получать и о, например, получившем наиболее широкое распространение в современных сетях общего пользования стандарте AES (см, например, ). Заметим, что условия для проведения такого рода атак возникают при использовании шифра в некотором протоколе. Нельзя не отметить, что результаты такого рода, хоть и представляют несомненный академический интерес с точки зрения изучения свойств криптографических преобразований, но фактически не относятся к практике. Например, все сертифицированные ФСБ России средства криптографической защиты информации выполняют строжайшие требования по схемам выработки ключей шифрования (см., например, ). Как указано в результатах проведенного в анализа, при наличии 18 связанных ключей и 2 10 пар блоков открытого и шифрованного текста трудоемкость полного вскрытия закрытого ключа, при вероятности успеха 1-10 -4 , действительно составляет 2 26 . Однако при соблюдении упомянутых выше требований по выработке ключевого материала вероятность обнаружения таких ключей равна 2 -4352 , то есть в 2 4096 раз меньше, чем если просто попытаться угадать секретный ключ с первой попытки.

К работам, относящимся к модели со связанными ключами, относится также и работа , наделавшая в 2010 году много шума в российских электронных изданиях, не страдающих от привычки внимательно проверять материал в процессе гонки за сенсациями. Результаты, представленные в ней, не были подкреплены каким-либо сколь-нибудь строгим обоснованием, зато содержали громкие заявления о возможности взламывать государственный стандарт Российской Федерации на слабеньком ноутбуке за считанные секунды - в общем, статья была написана в лучших традициях Николя Куртуа. Но, несмотря на совершенно очевидную мало-мальски знакомому с основными принципами научности публикаций читателю безосновательность статьи, именно для успокоения российской общественности после работы Рудским был написан подробный и обстоятельный текст , содержащий всесторонний анализ данной недостатьи. В статье с говорящим названием "О нулевой практической значимости работы «Key recovery attack on full GOST block cipher with zero time and memory»" приводится обоснование того, что средняя трудоемкость приведенного в метода не меньше, чем трудоемкость полного перебора.

Сухой остаток: какова стойкость на практике?

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

Атака	Трудоемкость	Память	Требуемый материал
Исобе	2 224	2 64	2 32
Динур-Данкельман-Шамир, FP, 2DMitM	2 192	2 36	2 64
Динур-Данкельман-Шамир, FP, low-memory	2 204	2 19	2 64
	2 224	2 36	2 32
Динур-Данкельман-Шамир, Reflection, 2DMitM	2 236	2 19	2 32
Полный перебор	2 256	1	4
Количество наносекунд с возникновения Вселенной	2 89

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

В нашей стране установлен единый алгоритм криптографического представления данных для систем обработки информации в сетях ЭВМ, отдельных вычислительных комплексов и ЭВМ, который определяется ГОСТ 28147-89 .

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

При описании алгоритма используются следующие обозначения:

L и R - последовательности битов;
LR - конкатенация последовательностей L и R, в которой биты последовательности R следуют за битами последовательности L;
(+) - поразрядное сложение по модулю 2 (операция "исключающее ИЛИ");
[+] - сложение 32-разрядных чисел по модулю 2 32 ;
{+} - сложение 32-разрядных чисел по модулю 2 32 -1.

Числа суммируются по следующему правилу:

A [+] B = A + B, если A + B < 2 32 ,
A [+] B = A + B - 2 32 , если A + B >= 2 32 . A {+} B = A + B , если A + B < 2^32 - 1, A {+} B = A + B - (2^32 - 1), если A + B >= 2^32 - 1.

Алгоритм предусматривает четыре режима работы:

В любом случае для шифрования данных используется 256-битовый ключ K, который представляется в виде восьми 32-битовых подключей K i:

K = K 7 K 6 K 5 K 4 K 3 K 2 K 1 K 0 .

Расшифрование выполняется по тому же ключу, что и шифрование, но этот процесс является инверсией процесса шифрования данных.

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

Первый и самый простой режим - замена . Данные, подлежащие шифрованию, разбивают на 64-битовые блоки. Процедура шифрования блока открытых данных T 0 включает 32 цикла (j=1...32).

Блок T 0 разделяется на две последовательности по 32 бита: В(0)A(0), где В(0) - левые или старшие биты, A(0) - правые или младшие биты.

Эти последовательности вводят в накопители N 1 и N 2 перед началом первого цикла шифрования.

Первый цикл (j=1) процедуры шифрования 64-битового блока данных описывается следующими формулами:

Здесь i обозначает номер итерации (i = 1, 2,..., 32).

Функция f называется функцией шифрования. Ее аргументом является сумма по модулю 2 32 числа A(i), полученного на предыдущем шаге итерации, и числа X(j) ключа (размерность каждого из этих чисел равна 32 знакам).

Функция шифрования включает две операции над полученной 32-разрядной суммой. Первая операция называется подстановкой К. Блок подстановки К состоит из 8 узлов замены К(1) ... К(8) с памятью 64 бит каждый. Поступающий на блок подстановки 32-разрядный вектор разбивается на 8 последовательно идущих 4-х разрядных векторов, каждый из которых преобразуется в 4-х разрядный вектор соответствующим узлом замены, представляющим собой таблицу из 16 целых чисел в диапазоне 0...15.

Входной вектор определяет адрес строки в таблице, число из которой является выходным вектором. Затем 4-х разрядные выходные векторы последовательно объединяются в 32-разрядный вектор. Таблицы блока подстановки К содержит ключевые элементы, общие для сети ЭВМ и редко изменяемые.

Вторая операция - циклический сдвиг влево 32-разрядного вектора, полученного в результате подстановки К. 64-разрядный блок зашифрованных данных Т ш представляется в виде Т ш =A(32)B(32).

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

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

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

Открытые данные, разбитые на 64-разрядные блоки Т(i) (i=1, 2,..., m, где m определяется обьемом шифруемых данных), зашифровываются в режиме гаммирования путем поразрядного сложения по модулю 2 с гаммой шифра Г ш, которая вырабатывается блоками по 64 бит, то есть Г ш = (Г(1),Г(2),...,Г(i),...,Г(m)).

Уравнение зашифрования данных в режиме гаммирования может быть представлено в следующем виде:

Ш(i) = A (Y(i-1) [+] C2, Z(i-1) {+} C1) (+) T(i) = Г(i) (+) T(i) .
Здесь Ш(i) - 64-разрядный блок зашифрованного текста,
A - функция шифрования в режиме простой замены (аргументами этой функции являются два 32-разрядных числа),
С1 и С2 - константы, заданные в ГОСТ 28147-89,
Y(i) и Z(i) - величины, которые определяются итерационно по мере формирования гаммы следующим образом:
(Y(0), Z(0)) = A(S), где S - 64-разрядная двоичная последовательность (синхропосылка);
(Y(i), Z(i)) = (Y(i-1) [+] C2, Z(i-1) {+} C1) для i = 1, 2,...,m.

Расшифрование данных возможно только при наличии синхропосылки, которая не является секретным элементом шифра и может храниться в памяти ЭВМ или передаваться по каналам связи вместе с зашированными данными.

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

Режим гаммирования с обратной связью очень похож на режим гаммирования. Как в и режиме гаммирования открытые данные, разбитые на 64-разрядные блоки Т(i) (i=1, 2,..., m , где m определяется обьемом шифруемых данных), зашифровываются путем поразрядного сложения по модулю 2 с гаммой шифра Г ш, которая вырабатывается блоками по 64 бит:

Г ш = (Г(1),Г(2),...,Г(i),...,Г(m)).

Число двоичных разрядов в блоке Т(m) может быть меньше 64, при этом неиспользованная для шифрования часть гаммы шифра из блока Г(m) отбрасывается.

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

Здесь Ш(i) - 64-разрядный блок зашифрованного текста,
A - функция шифрования в режиме простой замены. Аргументом функции на первом шаге итеративного алгоритма является 64-разрядная синхропосылка, а на всех последующих - предыдущий блок зашифрованных данных Ш(i-1).

Bыработки имитовставки

Процесс выработки имитовстаки единообразен для любого из режимов шифрования данных.

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

Для получения имитовставки открытые данные представляются в виде 64-разрядных блоков Т(i) (i = 1, 2,..., m , где m определяется объемом шифруемых данных). Первый блок открытых данных Т(1) подвергается преобразованию, соответствующему первым 16 циклам алгоритма зашифрования в режиме простой замены. Причем в качестве ключа для выработки имитовставки используется ключ, по которому шифруются данные.

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

Имитовставка Ир передается по каналу связи или в память ЭВМ после зашифрованных данных. Поступившие зашифрованные данные расшифровываются, и из полученных блоков открытых данных T(i) вырабатывается имитовставка Ир", которая затем сравнивается с имитовставкой Ир, полученной из канала связи или из памяти ЭВМ. В случае несовпадения имитовставок все расшифрованные данные считают ложными.

Алгоритм шифрования ГОСТ 28147-89, его использование и программная реализация для компьютеров платформы Intel x86.

Андрей Винокуров

Описание алгоритма.

Термины и обозначения.

Описание стандарта шифрования Российской Федерации содержится в очень интересном документе, озаглавленном «Алгоритм криптографического преобразования ГОСТ 28147-89» . То, что в его названии вместо термина «шифрование» фигурирует более общее понятие « криптографическое преобразование », вовсе не случайно. Помимо нескольких тесно связанных между собой процедур шифрования, в документе описан один построенный на общих принципах с ними алгоритм выработки имитовставки . Последняя является не чем иным, как криптографической контрольной комбинацией, то есть кодом, вырабатываемым из исходных данных с использованием секретного ключа с целью имитозащиты , или защиты данных от внесения в них несанкционированных изменений.

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

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

Если элемент данных состоит из нескольких элементов меньшего размера, то этот факт обозначается следующим образом: X =(X 0 ,X 1 ,…,X n –1)=X 0 ||X 1 ||…||X n –1 . Процедура объединения нескольких элементов данных в один называется конкатенацией данных и обозначается символом «||». Естественно, для размеров элементов данных должно выполняться следующее соотношение: |X |=|X 0 |+|X 1 |+…+|X n -1 |. При задании сложных элементов данных и операции конкатенации составляющие элементы данных перечисляются в порядке возрастания старшинства. Иными словами, если интерпретировать составной элемент и все входящие в него элементы данных как целые числа без знака, то можно записать следующее равенство:

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

X =(x 0 ,x 1 ,…,x n –1)=x 0 +2 1 ·x 1 +…+2 n –1 ·x n –1 .

Таким образом, если вы обратили внимание, для ГОСТа принята т.н. «little-endian» нумерация разрядов, т.е. внутри многоразрядных слов данных отдельные двоичные разряды и их группы с меньшими номерами являются менее значимыми. Об этом прямо говорится в пункте 1.3 стандарта: «При сложении и циклическом сдвиге двоичных векторов старшими разрядами считаются разряды накопителей с большими номерами». Далее, пункты стандарта 1.4, 2.1.1 и другие предписывают начинать заполнение данными регистров-накопителей виртуального шифрующего устройства с младших, т.е. менее значимых разрядов. Точно такой же порядок нумерации принят в микропроцессорной архитектуре Intel x86, именно поэтому при программной реализации шифра на данной архитектуре никаких дополнительных перестановок разрядов внутри слов данных не требуется.

Если над элементами данных выполняется некоторая операция, имеющая логический смысл, то предполагается, что данная операция выполняется над соответствующими битами элементов. Иными словами A B =(a 0 b 0 ,a 1 b 1 ,…,a n –1 b n –1), где n =|A |=|B |, а символом « » обозначается произвольная бинарная логическая операция; как правило, имеется в виду операция исключающего или , она же – операция суммирования по модулю 2:

Логика построения шифра и структура ключевой информации ГОСТа.

Если внимательно изучить оригинал ГОСТ 28147–89, можно заметить, что в нем содержится описание алгоритмов нескольких уровней. На самом верхнем находятся практические алгоритмы, предназначенные для шифрования массивов данных и выработки для них имитовставки. Все они опираются на три алгоритма низшего уровня, называемые в тексте ГОСТа циклами . Эти фундаментальные алгоритмы упоминаются в данной статье как базовые циклы , чтобы отличать их от всех прочих циклов. Они имеют следующие названия и обозначения, последние приведены в скобках и смысл их будет объяснен позже:

• цикл зашифрования (32-З);
• цикл расшифрования (32-Р);
• цикл выработки имитовставки (16-З).

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

Таким образом, чтобы разобраться в ГОСТе, надо понять три следующие вещи:

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

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

Основной шаг криптопреобразования.

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

Рисунок 1. Схема основного шага криптопреобразования алгоритма ГОСТ 28147-89.

Ниже даны пояснения к алгоритму основного шага:

Шаг 0

• N – преобразуемый 64-битовый блок данных, в ходе выполнения шага его младшая (N 1) и старшая (N 2) части обрабатываются как отдельные 32-битовые целые числа без знака. Таким образом, можно записать N= (N 1 ,N 2).
• X – 32-битовый элемент ключа;

Шаг 1

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

Шаг 2

Поблочная замена. 32-битовое значение, полученное на предыдущем шаге, интерпретируется как массив из восьми 4-битовых блоков кода: S= (S 0 , S 1 , S 2 , S 3 , S 4 , S 5 , S 6 , S 7), причем S 0 содержит 4 самых младших, а S 7 – 4 самых старших бита S .

Далее значение каждого из восьми блоков заменяется новым, которое выбирается по таблице замен следующим образом: значение блока S i меняется на S i -тый по порядку элемент (нумерация с нуля) i -того узла замены (т.е. i -той строки таблицы замен, нумерация также с нуля). Другими словами, в качестве замены для значения блока выбирается элемент из таблицы замен с номером строки, равным номеру заменяемого блока, и номером столбца, равным значению заменяемого блока как 4-битового целого неотрицательного числа. Отсюда становится понятным размер таблицы замен: число строк в ней равно числу 4-битовых элементов в 32-битовом блоке данных, то есть восьми, а число столбцов равно числу различных значений 4-битового блока данных, равному как известно 2 4 , шестнадцати.

Шаг 3

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

Шаг 4

Побитовое сложение: значение, полученное на шаге 3, побитно складывается по модулю 2 со старшей половиной преобразуемого блока.

Шаг 5

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

Шаг 6

Полученное значение преобразуемого блока возвращается как результат выполнения алгоритма основного шага криптопреобразования.

Базовые циклы криптографических преобразований.

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

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

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

Цикл зашифрования 32-З:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 .

Рисунок 2а. Схема цикла зашифрования 32-З

Цикл расшифрования 32-Р:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 .

Рисунок 2б. Схема цикла расшифрования 32-Р

Цикл выработки имитовставки 16-З:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 .

Рисунок 2в. Схема цикла выработки имитовставки 16-З.

Каждый из циклов имеет собственное буквенно-цифровое обозначение, соответствующее шаблону «n-X» , где первый элемент обозначения (n ), задает число повторений основного шага в цикле, а второй элемент обозначения (X ), буква, задает порядок зашифрования («З») или расшифрования («Р») в использовании ключевых элементов. Этот порядок нуждается в дополнительном пояснении:

Цикл расшифрования должен быть обратным циклу зашифрования, то есть последовательное применение этих двух циклов к произвольному блоку должно дать в итоге исходный блок, что отражается следующим соотношением: Ц 32-Р (Ц 32-З (T ))=T , где T – произвольный 64-битовый блок данных, Ц X (T ) – результат выполнения цикла X над блоком данных T . Для выполнения этого условия для алгоритмов, подобных ГОСТу, необходимо и достаточно, чтобы порядок использования ключевых элементов соответствующими циклами был взаимно обратным. В справедливости записанного условия для рассматриваемого случая легко убедиться, сравнив приведенные выше последовательности для циклов 32-З и 32-Р. Из сказанного вытекает одно интересное следствие: свойство цикла быть обратным другому циклу является взаимным, то есть цикл 32-З является обратным по отношению к циклу 32-Р. Другими словами, зашифрование блока данных теоретически может быть выполнено с помощью цикла расшифрования, в этом случае расшифрование блока данных должно быть выполнено циклом зашифрования. Из двух взаимно обратных циклов любой может быть использован для зашифрования, тогда второй должен быть использован для расшифрования данных, однако стандарт ГОСТ28147-89 закрепляет роли за циклами и не предоставляет пользователю права выбора в этом вопросе.

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

Схемы базовых циклов приведены на рисунках 2а-в. Каждый из них принимает в качестве аргумента и возвращает в качестве результата 64-битовый блок данных, обозначенный на схемах N . Символ Шаг(N ,X ) обозначает выполнение основного шага криптопреобразования для блока данных N с использованием ключевого элемента X . Между циклами шифрования и вычисления имитовставки есть еще одно отличие, не упомянутое выше: в конце базовых циклов шифрования старшая и младшая часть блока результата меняются местами, это необходимо для их взаимной обратимости.

Основные режимы шифрования.

ГОСТ 28147-89 предусматривает три следующих режима шифрования данных:

• простая замена,
• гаммирование,
• гаммирование с обратной связью,

и один дополнительный режим выработки имитовставки.

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

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

T о,T ш – массивы соответственно открытых и зашифрованных данных;

, – i - тые по порядку 64-битовые блоки соответственно открытых и зашифрованных данных:, , последний блок может быть неполным: ;

n – число 64-битовых блоков в массиве данных;

Ц X – функция преобразования 64-битового блока данных по алгоритму базового цикла «X».

Теперь опишем основные режимы шифрования:

Простая замена.

Зашифрование в данном режиме заключается в применении цикла 32-З к блокам открытых данных, расшифрование – цикла 32-Р к блокам зашифрованных данных. Это наиболее простой из режимов, 64-битовые блоки данных обрабатываются в нем независимо друг от друга. Схемы алгоритмов зашифрования и расшифрования в режиме простой замены приведены на рисунках 3а и б соответственно, они тривиальны и не нуждаются в комментариях.

Рисунок. 3а. Алгоритм зашифрования данных в режиме простой замены

Рисунок. 3б. Алгоритм расшифрования данных в режиме простой замены

Размер массива открытых или зашифрованных данных, подвергающийся соответственно зашифрованию или расшифрованию, должен быть кратен 64 битам: | T о |=| T ш |=64· n , после выполнения операции размер полученного массива данных не изменяется.

Режим шифрования простой заменой имеет следующие особенности:

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

На первый взгляд, перечисленные выше особенности делают практически невозможным использование режима простой замены, ведь он может применяться только для шифрования массивов данных с размером кратным 64 битам, не содержащим повторяющихся 64-битовых блоков. Кажется, что для любых реальных данных гарантировать выполнение указанных условий невозможно. Это почти так, но есть одно очень важное исключение: вспомните, что размер ключа составляет 32 байта, а размер таблицы замен – 64 байта. Кроме того, наличие повторяющихся 8-байтовых блоков в ключе или таблице замен будет говорить об их весьма плохом качестве, поэтому в реальных ключевых элементах такого повторения быть не может. Таким образом, мы выяснили, что режим простой замены вполне подходит для шифрования ключевой информации, тем более, что прочие режимы для этой цели менее удобны, поскольку требуют наличия дополнительного синхронизирующего элемента данных – синхропосылки (см. следующий раздел). Наша догадка верна, ГОСТ предписывает использовать режим простой замены исключительно для шифрования ключевых данных.

Гаммирование.

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

Теперь перейдем непосредственно к описанию режима гаммирования. Гамма для этого режима получается следующим образом: с помощью некоторого алгоритмического рекуррентного генератора последовательности чисел (РГПЧ) вырабатываются 64-битовые блоки данных, которые далее подвергаются преобразованию по циклу 32-З, то есть зашифрованию в режиме простой замены, в результате получаются блоки гаммы. Благодаря тому, что наложение и снятие гаммы осуществляется при помощи одной и той же операции побитового исключающего или, алгоритмы зашифрования и расшифрования в режиме гаммирования идентичны, их общая схема приведена на рисунке 4.

РГПЧ, используемый для выработки гаммы, является рекуррентной функцией: – элементы рекуррентной последовательности, f – функция преобразования. Следовательно, неизбежно возникает вопрос о его инициализации, то есть об элементе В действительности, этот элемент данных является параметром алгоритма для режимов гаммирования, на схемах он обозначен как S , и называется в криптографии синхропосылкой , а в нашем ГОСТе – начальным заполнением одного из регистров шифрователя. По определенным соображениям разработчики ГОСТа решили использовать для инициализации РГПЧ не непосредственно синхропосылку, а результат ее преобразования по циклу 32-З: . Последовательность элементов, вырабатываемых РГПЧ, целиком зависит от его начального заполнения, то есть элементы этой последовательности являются функцией своего номера и начального заполнения РГПЧ: где f i (X )=f (f i –1 (X )), f 0 (X )=X . С учетом преобразования по алгоритму простой замены добавляется еще и зависимость от ключа:

где Г i – i -тый элемент гаммы, K – ключ.

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

Теперь подробно рассмотрим РГПЧ, используемый в ГОСТе для генерации элементов гаммы. Прежде всего, надо отметить, что к нему не предъявляются требования обеспечения каких-либо статистических характеристик вырабатываемой последовательности чисел. РГПЧ спроектирован разработчиками ГОСТа исходя из необходимости выполнения следующих условий:

• период повторения последовательности чисел, вырабатываемой РГПЧ, не должен сильно (в процентном отношении) отличаться от максимально возможного при заданном размере блока значения 2 64 ;
• соседние значения, вырабатываемые РГПЧ, должны отличаться друг от друга в каждом байте, иначе задача криптоаналитика будет упрощена;
• РГПЧ должен быть достаточно просто реализуем как аппаратно, так и программно на наиболее распространенных типах процессоров, большинство из которых, как известно, имеют разрядность 32 бита.

Исходя из перечисленных принципов, создатели ГОСТа спроектировали весьма удачный РГПЧ, имеющий следующие характеристики:

Где C 0 =1010101 16 ;

Где C 1 =1010104 16 ;

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

Второе выражение нуждается в комментариях, так как в тексте ГОСТа приведено нечто другое: , с тем же значением константы C 1 . Но далее в тексте стандарта дается комментарий, что, оказывается, под операцией взятия остатка по модулю 2 32 –1 там понимается не то же самое, что и в математике. Отличие заключается в том, что согласно ГОСТу (2 32 –1)mod (2 32 –1)=(2 32 –1), а не 0. На самом деле, это упрощает реализацию формулы, а математически корректное выражение для нее приведено выше.

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

Схема алгоритма шифрования в режиме гаммирования приведена на рисунке 4, ниже изложены пояснения к схеме:

Рисунок 4. Алгоритм зашифрования (расшифрования) данных в режиме гаммирования.

Шаг 0

Определяет исходные данные для основного шага криптопреобразования:

• T о(ш) – массив открытых (зашифрованных) данных произвольного размера, подвергаемый процедуре зашифрования (расшифрования), по ходу процедуры массив подвергается преобразованию порциями по 64 бита;
• S – синхропосылка , 64-битовый элемент данных, необходимый для инициализации генератора гаммы;

Шаг 1

Начальное преобразование синхропосылки, выполняемое для ее «рандомизации», то есть для устранения статистических закономерностей, присутствующих в ней, результат используется как начальное заполнение РГПЧ;

Шаг 2

Один шаг работы РГПЧ, реализующий его рекуррентный алгоритм. В ходе данного шага старшая (S 1) и младшая (S 0) части последовательности данных вырабатываются независимо друг от друга;

Шаг 3

Гаммирование. Очередной 64-битовый элемент, выработанный РГПЧ, подвергается процедуре зашифрования по циклу 32–З, результат используется как элемент гаммы для зашифрования (расшифрования) очередного блока открытых (зашифрованных) данных того же размера.

Шаг 4

Результат работы алгоритма – зашифрованный (расшифрованный) массив данных.

Ниже перечислены особенности гаммирования как режима шифрования:

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

• хранить или передавать синхропосылку вместе с зашифрованным массивом данных, что приведет к увеличению размера массива данных при зашифровании на размер синхропосылки, то есть на 8 байт;
• использовать предопределенное значение синхропосылки или вырабатывать ее синхронно источником и приемником по определенному закону, в этом случае изменение размера передаваемого или хранимого массива данных отсутствует;

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

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

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

где обозначает инвертированное по отношению к t значение бита ().

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

Гаммирование с обратной связью.

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

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

Рисунок 5. Алгоритм зашифрования (расшифрования) данных в режиме гаммирования с обратной связью.

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

Гаммирование;

Гаммирование с обратной связью;

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

Выработка имитовставки к массиву данных.

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

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

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

Схема алгоритма выработки имитовставки приведена на рисунке 6.

Рисунок 6. Алгоритм выработки имитовставки для массива данных.

В качестве имитовставки берется часть блока, полученного на выходе, обычно – 32 его младших бита. При выборе размера имитовставки надо принимать во внимание, что вероятность успешного навязывания ложных данных равна величине 2 –| I | на одну попытку подбора, если в распоряжении злоумышленника нет более эффективного метода подбора, чем простое угадывание. При использовании имитовставки размером 32 бита эта вероятность равна

Обсуждение криптографических алгоритмов ГОСТа.

Криптографическая стойкость ГОСТа.

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

• можно ли вообще раскрыть данный шифр;
• если да, то насколько это трудно сделать практически;

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

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

В ГОСТе используется 256-битовый ключ и объем ключевого пространства составляет 2 256 . Ни на одном из существующих в настоящее время или предполагаемых к реализации в недалеком будущем электронном устройстве нельзя подобрать ключ за время, меньшее многих сотен лет. Эта величина стала фактическим стандартом размера ключа для симметричных криптоалгоритмов в наши дни, – так, новый стандарт шифрования США также его поддерживает. Прежний же американский стандарт, DES с его реальным размером ключа в 56 бит и объемом ключевого пространства всего 2 56 уже не является достаточно стойким в свете возможностей современных вычислительных средств. Это было продемонстрировано в конце 90-х годов несколькими успешными попытками взлома DES переборным путем. Кроме того, DES оказался подвержен специальным способам криптоанализа, таким как дифференциальный и линейный. В этой связи DES может представлять скорее исследовательский или научный, чем практический интерес. В 1998 году его криптографическая слабость была признана официально, – национальный институт стандартов США рекомендовал использовать троекратное шифрование по DES. А в конце 2001 года был официально утвержден новый стандарт шифрования США, AES, построенный на иных принципах и свободный от недостатков своего предшественника .

Замечания по архитектуре ГОСТа.

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

Алгоритмы «основных шагов криптопреобразования» для шифров, подобных ГОСТу, построены идентичным образом, и эта архитектура называется сбалансированная сеть Файстеля (balanced Feistel network) по имени человека, впервые предложившего ее . Схема преобразования данных на одном цикле, или, как его принято называть, раунде , приведена на рисунке 7.

Рисунок 7. Содержание основного шага криптопреобразования для блочных шифров, подобных ГОСТу.

На вход основного шага подается блок четного размера, старшая и младшая половины которого обрабатываются отдельно друг от друга. В ходе преобразования младшая половина блока помещается на место старшей, а старшая, скомбинированная с помощью операции побитового « исключающего или » с результатом вычисления некоторой функции, на место младшей. Эта функция, принимающая в качестве аргумента младшую половину блока и элемент ключевой информации (X ), является содержательной частью шифра и называется его функцией шифрования . По разным соображениям оказалось выгодно разделить шифруемый блок на две одинаковые по размеру части: |N 1 |=|N 2 | – именно этот факт отражает слово «сбалансированная» в названии архитектуры. Впрочем, шифрующие несбалансированные сети также используются время от времени, хотя и не так часто, как сбалансированные. Кроме того, соображения стойкости шифра требуют, чтобы размер ключевого элемента не был меньше размера половины блока: в ГОСТе все три размера равны 32 битам.

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

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

Ни одна из рассмотренных автором реализаций DESа для платформы Intel x86 не достигает даже половины производительности предложенной вашему вниманию в настоящей статье реализации ГОСТа несмотря на вдвое более короткий цикл. Все сказанное выше свидетельствует о том, что разработчики ГОСТа учли как положительные, так и отрицательные стороны DESа, а также более реально оценили текущие и перспективные возможности криптоанализа. Впрочем, брать DES за основу при сравнении быстродействия реализаций шифров уже не актуально. У нового стандарта шифрования США дела с эффективностью обстоят гораздо лучше – при таком же как у ГОСТа размере ключа в 256 бит AES работает быстрее него примерно на 14% – это если сравнивать по числу «элементарных операций». Кроме того, ГОСТ практически не удается распараллелить, а у AES возможностей в этом плане намного больше. На некоторых архитектурах это преимущество AES может быть меньше, на других – больше. Так, на процессоре Intel Pentium оно достигает 28%. Подробности можно найти в .

Требования к качеству ключевой информации и источники ключей.

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

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

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

Ключ

Ключ должен являться массивом статистически независимых битов, принимающих с равной вероятностью значения 0 и 1. Нельзя полностью исключить при этом, что некоторые конкретные значения ключа могут оказаться «слабыми», то есть шифр может не обеспечивать заданный уровень стойкости в случае их использования. Однако, предположительно, доля таких значений в общей массе всех возможных ключей ничтожно мала. По крайней мере, интенсивные исследования шифра до сих пор не выявили ни одного такого ключа ни для одной из известных (т.е. предложенных ФАПСИ) таблиц замен. Поэтому ключи, выработанные с помощью некоторого датчика истинно случайных чисел, будут качественными с вероятностью, отличающейся от единицы на ничтожно малую величину. Если же ключи вырабатываются с помощью генератора псевдослучайных чисел, то используемый генератор должен обеспечивать указанные выше статистические характеристики, и, кроме того, обладать высокой криптостойкостью, – не меньшей, чем у самого ГОСТа. Иными словами, задача определения отсутствующих членов вырабатываемой генератором последовательности элементов не должна быть проще, чем задача вскрытия шифра. Кроме того, для отбраковки ключей с плохими статистическими характеристиками могут быть использованы различные статистические критерии. На практике обычно хватает двух критериев, – для проверки равновероятного распределения битов ключа между значениями 0 и 1 обычно используется критерий Пирсона («хи квадрат»), а для проверки независимости битов ключа – критерий серий. Об упомянутых критериях можно прочитать в учебниках или справочниках по математической статистике.

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

В случае же, когда необходимо выработать большой по объему массив ключевой информации, возможно и очень широко распространено использование различных программных датчиков псевдослучайных чисел. Поскольку от подобного датчика требуются высокие показатели криптостойкости, естественным является использование в качестве него генератора гаммы самого шифра – просто «нарезаем» вырабатываемую шифром гамму на «куски» нужного размера, для ГОСТа – по 32 байта. Конечно, для такого подхода нам потребуется «мастер-ключ», который мы можем получить описанным выше методом электронной рулетки, а с его помощью, используя шифр в режиме генератора гаммы, получаем массив ключевой информации нужного нам объема. Так эти два способа выработки ключей, – «ручной» и «алгоритмический», – работают в тандеме, дополняя друг друга. Схемы генерации ключей в «малобюджетных» системах криптозащиты информации практически всегда построены по такому принципу.

Таблица замен

Таблица замен является долговременным ключевым элементом, то есть действует в течение гораздо более длительного срока, чем отдельный ключ. Предполагается, что она является общей для всех узлов шифрования в рамках одной системы криптографической защиты. Даже при нарушении конфиденциальности таблицы замен стойкость шифра остается чрезвычайно высокой и не снижается ниже допустимого предела. Поэтому нет особой нужды держать таблицу в секрете, и в большинстве коммерческих применений ГОСТа так оно и делается. С другой стороны, таблица замен является критически важным элементом для обеспечения стойкости всего шифра. Выбор ненадлежащей таблицы может привести к тому, что шифр будет легко вскрываться известными методами криптоанализа. Критерии выработки узлов замен – тайна за семью печатями и ФАПСИ вряд ли ей поделится с общественностью в ближайшем обозримом будущем. В конечном итоге, для того, чтобы сказать, является ли данная конкретная таблица замен хорошей или плохой, необходимо провести огромный объем работ – многие тысячи человеко- и машино-часов. Единожды выбранная и используемая таблица подлежит замене в том и только в том случае, если шифр с ее использованием оказался уязвимым к тому или иному виду криптоанализа. Поэтому лучшим выбором для рядового пользователя шифра будет взять одну из нескольких таблиц, ставших достоянием гласности. Например, из стандарта на хеш-функцию , она же «центробанковская» ; сведения об этих таблицах можно найти в открытой печати и даже в интернете, если хорошо поискать.

Для тех же, кто не привык идти легкими путями, ниже приведена общая схема получения качественных таблиц:

1. С помощью той или иной методики вырабатываете комплект из восьми узлов замен с гарантированными характеристиками нелинейности. Таких методик существует несколько, одна из них – использование так называемых бент-функций.
2. Проверяете выполнение простейших «критериев качества» – например, тех, что опубликованы для узлов замены DES. Вот еще несколько общих соображений на этот счет: Каждый узел замен может быть описан четверкой логических функций от четырех логических аргументов. Если эти функции, записанные в минимальной форме (т.е. с минимально возможной длиной выражения) окажутся недостаточно сложными, такой узел замены отвергается. Кроме того, отдельные функции в пределах всей таблицы замен должны отличаться друг от друга в достаточной степени. На этом этапе отсеиваются многие заведомо некачественные таблицы.
3. Для шифра с выбранными вами таблицами строите различные модели раунда, соответствующие разным видам криптоанализа, и измеряете соответствующие «профильные» характеристики. Так, для линейного криптоанализа строите линейный статистический аналог раунда шифрования и вычисляете «профильную» характеристику – показатель нелинейности. Если она оказывается недостаточной, таблица замен отвергается.
4. Наконец, используя результаты предыдущего пункта, подвергаете шифр с выбранной вами таблицей интенсивным исследованиям – попытке криптоанализа всеми известными методами. Именно этот этап является наиболее сложным и трудоемким. Но если он сделан качественно, то с высокой степенью вероятности можно констатировать, что шифр с выбранными вами таблицами не будет вскрыт простыми смертными, и, – не исключено, – окажется не по зубам спецслужбам.

Можно, однако, поступить гораздо проще. Все дело в том, что чем больше в шифре раундов, тем меньшее влияние на стойкость всего шифра имеют характеристики стойкости одного раунда. В ГОСТе аж 32 раунда – больше, чем практически во всех шифрах с аналогичной архитектурой. Поэтому для большинства бытовых и коммерческих применений бывает достаточно получить узлы замен как независимые случайные перестановки чисел от 0 до 15. Это может быть практически реализовано, например, с помощью перемешивания колоды из шестнадцати карт, за каждой из которых закреплено одно из значений указанного диапазона.

Относительно таблицы замен необходимо отметить еще один интересный факт. Для обратимости циклов шифрования «32-З» и «32-Р» не требуется, чтобы узлы замен были перестановками чисел от 0 до 15. Все работает даже в том случае, если в узле замен есть повторяющиеся элементы, и замена, определяемая таким узлом, необратима, – однако в этом случае снижается стойкость шифра. Почему это именно так, не рассматривается в настоящей статье, однако в самом факте убедиться несложно. Для этого достаточно попытаться сначала зашифровать, а затем расшифровать блок данных, используя такую «неполноценную» таблицу замен, узлы которой содержат повторяющиеся значения.

Вариации на тему ГОСТа

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

Как поступить в этом и аналогичном ему случаях, чтобы увеличить быстродействие шифрования? Ответ лежит на поверхности – использовать модификацию шифра с меньшим количеством основных шагов (раундов) в базовых циклах. Во сколько раз мы уменьшаем число раундов шифрования, во столько же раз возрастает быстродействие. Указанного изменения можно достигнуть двумя путями, – уменьшением длины ключа и уменьшением числа «циклов просмотра» ключа. Вспомните, что число основных шагов в базовых циклах шифрования равно N =n·m , где n – число 32-битовых элементов в ключе, m – число циклов использования ключевых элементов, в стандарте n =8, m =4. Можно уменьшить любое из этих чисел, но простейший вариант – уменьшать длину ключа, не трогая схемы его использования.

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

Что касается устойчивости шифра к взлому «экстенсивными» методами, то есть к «переборной» атаке, тот тут все более или менее ясно: ключ размером 64 бита находится где-то на грани доступности этому виду атаки, шифр с ключом 96 бит и выше (помните, что ключ должен содержать целое число 32-битовых элементов) вполне устойчив против него. Действительно, несколько лет назад прежний стандарт шифрования США, DES, был неоднократно взломан переборным путем, – сначала его взломала вычислительная сеть, организованная на базе глобальной сети Интернет, а затем – специализированная, т.е. сконструированная специально для этого вычислительная машина. Примем, что стандартный вариант ГОСТа при программной реализации на современных процессорах работает вчетверо быстрее DES. Тогда 8-раундовый «редуцированный ГОСТ» будет работать в 16 раз быстрее DES. Примем также, что за прошедшее с момента взлома DES время производительность вычислительной техники согласно закону Мура возросла вчетверо. Получаем в итоге, что сейчас проверка одного 64-битового ключа для «редуцированного ГОСТа» с восемью циклами осуществляется в 64 раза быстрее, чем в свое время выполнялась проверка одного ключа DES. Таким образом, преимущество такого варианта ГОСТа перед DES по трудоемкости переборной атаки сокращается с 2 64–56 = 2 8 = 256 до 256/ 64 = 4 раз. Согласитесь, это весьма иллюзорное различие, почти что ничего.

Гораздо сложнее оценить устойчивость ослабленных модификаций ГОСТа к «интенсивным» способам криптоанализа. Однако общую закономерность можно проследить и здесь. Дело в том, что «профильные» характеристики многих наиболее сильных на сегодняшний момент видов криптоанализа зависят экспоненциально от числа раундов шифрования. Так, для линейного криптоанализа (ЛКА) это будет характеристика линейности L :

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

С другой стороны, ГОСТ проектировался с большим запасом прочности и на сегодняшний день устойчив ко всем известным видам криптоанализа, включая дифференциальный и линейный. Применительно к ЛКА это означает, что для его успешного проведения требуется больше пар «открытый блок – зашифрованный блок», чем «существует в природе», то есть более 2 64 . С учетом сказанного выше это означает, что для успешного ЛКА 16-раундового ГОСТа потребуется не менее блоков или 2 35 байтов или 32 Гбайта данных, а для 8-раундового – не менее блоков или 2 19 байтов или 0.5 Мбайт.

Выводы из всего, сказанного выше, приведены в следующей таблице, обобщающей характеристики редуцированных вариантов ГОСТа.

Число раундов	Размер ключа, бит	Индекс быстро-действия	Вероятные характеристики шифра(очень грубая оценка)
24	192	1,33	Устойчив к большинству известных видов КА, или находиться на грани устойчивости. Практическая реализация КА невозможна из-за высоких требований к исходным данным и трудоемкости.
16	128	2	Теоретически неустойчив к некоторым видам криптоанализа, однако их практическая реализация в большинстве случаев затруднена из-за высоких требований к исходным данным и трудоемкости.
12	95	2,67	Неустойчив к некоторым известным видам криптоанализа, однако годится для обеспечения секретности небольших объемов данных (до десятков-сотен Кбайт) на короткий срок.
8	64	4	Неустойчив к некоторым известным видам криптоанализа, однако годится для обеспечения секретности небольших объемов данных (до десятков Кбайт) на короткий срок.

Два последних варианта, с 12 и 8 раундами, способны обеспечить весьма и весьма ограниченную во времени защиту. Их использование оправдано лишь в задачах, где требуется лишь краткосрочная секретность закрываемых данных, порядка нескольких часов. Возможная область применения этих слабых вариантов шифра – закрытие UDP-трафика электронных биржевых торговых систем. В этом случае каждый пакет данных (datagram, средняя «D» из аббревиатуры UDP) шифруется на отдельном 64-битовом ключе, а сам ключ шифруется на сеансовом ключе (ключе, область действия которого – один сеанс связи между двумя компьютерами) и передается вместе с данными.

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

У рассматриваемого вопроса есть и обратная сторона. Что если скорость шифрования некритична, а требования к стойкости весьма жестки? Повысить стойкость ГОСТа можно двумя путями – условно назовем их «экстенсивный» и «интенсивный». Первый из них – это ни что иное, как простое увеличение числа раундов шифрования. Мне не совсем понятно, зачем это может реально понадобиться, ведь отечественный стандарт и без этого обеспечивает необходимую стойкость. Впрочем, если вы страдаете паранойей больше необходимого уровня (а все «защитники информации» просто обязаны ею страдать, это условие профпригодности такое, вопрос только в степени тяжеcти случая:), это поможет вам несколько успокоиться. Если вы не уверены в этом КГБ-шном шифре или используемой вами таблице замен, просто удвойте, учетверите, и т.д. число раундов – кратность выберите исходя из тяжести вашего случая. Указанный подход позволяет реально увеличить стойкость шифра, – если раньше криптоанализ был просто невозможным, то теперь он невозможен в квадрате!

Более хитрым и интересным является вопрос, а можно ли увеличить стойкость шифра, не меняя количества и структуры основных шагов шифрования. Как ни удивительно, ответ на этот него положительный, хотя мы опять ступаем на зыбкую почву спекуляций. Дело в том, что в ГОСТе на основном шаге преобразования предполагается выполнение замены 4 на 4 бит, а на практике (речь об этом еще впереди) все программные реализации выполняют замену побайтно, т.е. 8 на 8 бит – так делается по соображениям эффективности. Если сразу спроектировать такую замену как 8-битовую, то мы существенно улучшим характеристики одного раунда. Во-первых, увеличится «диффузионная» характеристика или показатель «лавинности» – один бит исходных данных и/или ключа будет влиять на большее число бит результата. Во вторых, для больших по размеру узлов замены можно получить более низкие дифференциальную и линейную характеристики, уменьшив тем самым подверженность шифра одноименным видам криптоанализа. Особенно актуально это для редуцированных циклов ГОСТа, а для 8 и 12-раундовых вариантов такой шаг просто необходим. Это несколько скомпенсирует потерю стойкости в них от уменьшения числа раундов. Что затрудняет использование этого приема – так это то, что конструировать подобные «увеличенные» узлы замены вам придется самостоятельно. А также то, что более крупные узлы вообще конструировать заметно труднее, чем меньшие по размеру.

Нестандартное использование стандарта.

Безусловно, основное назначение криптоалгоритмов ГОСТ – это шифрование и имитозащита данных. Однако им можно найти и другие применения, связанные, естественно, с защитой информации. Коротко расскажем о них:

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

• Как уже отмечалось выше, гамму можно использовать как «сырье» для выработки ключей. Для этого нужно лишь получить отрезок гаммы нужной длины – 32 байта. Таким способом ключи можно изготавливать по мере необходимости и их не надо будет хранить, – если такой ключ понадобится повторно, будет достаточно легко его выработать снова. Надо только будет вспомнить, на каком ключе он был выработан исходно, какая использовалась синхропосылка и с какого байта выработанной гаммы начинался ключ. Вся информация, кроме использованного ключа, несекретна. Данный подход позволит легко контролировать достаточно сложную и разветвленную систему ключей, используя всего лишь один «мастер-ключ».
• Аналогично предыдущему, гамму можно использовать в качестве исходного «сырья» для выработки паролей. Тут может возникнуть вопрос, зачем вообще нужно их генерировать, не проще ли по мере надобности их просто выдумывать. Несостоятельность такого подхода была наглядно продемонстрирована серией инцидентов в компьютерных сетях, самым крупным из которых был суточный паралич интернета в ноябре 1988 года, вызванный «червем Морриса». Одним из способов проникновения злоумышленной программы на компьютер был подбор паролей: программа пыталась войти в систему, последовательно перебирая пароли из своего внутреннего списка в несколько сотен, причем в значительной доле случаев ей это удавалось сделать. Фантазия человека по выдумыванию паролей оказалась весьма бедной. Именно поэтому в тех организациях, где безопасности уделяется должное внимание, пароли генерирует и раздает пользователям системный администратор по безопасности. Выработка паролей чуть сложнее, чем выработка ключей, так как при этом «сырую» двоичную гамму необходимо преобразовать к символьному виду, а не просто «нарезать» на куски. Кроме того, отдельные значения, возможно, придется отбросить, чтобы обеспечить равную вероятность появления всех символов алфавита в пароле.
• Еще один способ использования криптографической гаммы – гарантированное затирание данных на магнитных носителях. Дело в том, что даже при перезаписи информации на магнитном носителе остаются следы предыдущих данных, которые может восстановить соответствующая экспертиза. Для уничтожения этих следов такую перезапись надо выполнить многократно. Оказалось, что потребуется перезаписывать информацию на носитель меньшее количество раз, если при такой процедуре использовать случайные или псевдослучайные данные, которые останутся неизвестными экспертам, пытающимся восстановить затертую информацию. Гамма шифра здесь будет как нельзя кстати.

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

• Мы знаем, что один из таких вариантов использования ГОСТа – выработка имитовставки для массивов данных. Однако на базе любого блочного шифра, и ГОСТа в том числе, достаточно легко построить схему вычисления односторонней хэш-функции, называемой также в литературе MDC, что в разных источниках расшифровывается как код обнаружения изменений / манипуляций (M odification/M anipulation D etection C ode) или дайджест сообщения (M essage D igest C ode). Первая расшифровка появилась в литературе гораздо раньше, вторую, более короткую, я думаю, придумали те, кому оказалось не под силу запомнить первую:), – это была шутка. MDC может непосредственно использоваться в системах имитозащиты в качестве аналога имитовставки, не зависящего, однако, от секретного ключа. Кроме того, MDC широко используется в схемах электронно-цифровой подписи (ЭЦП), ведь большинство таких схем сконструированы таким способом, что подписывать удобно блок данных фиксированного размера. Как известно, на базе обсуждаемого стандарта ГОСТ 28147-89 построен стандарт Российской Федерации на вычисление односторонней хэш-функции ГОСТ Р34.11-94 .
• Менее известно, что на базе любого блочного шифра, и ГОСТа в том числе, может быть построена вполне функциональная схема ЭЦП, с секретным ключом подписи и открытой проверочной комбинацией. По ряду причин эта схема не получила широкого практического распространения, однако в отдельных случаях до сих пор может рассматриваться как весьма привлекательная альтернатива доминирующим ныне в мире «математическим» схемам ЭЦП.

Литература

Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования ГОСТ 28147-89. Гос. Ком. СССР по стандартам, М., 1989. ftp://ftp.wtc-ural.ru/pub/ru.crypt/GOST-28147
Шеннон Клод. Математическая теория секретных систем. В сборнике «Работы по теории информации и кибернетике», М., ИЛ, 1963, с. 333-369. http://www.enlight.ru/crypto/articles/shannon/shann__i.htm
Announcing Approval of Federal Information Processing Standard (FIPS) 197, Advanced Encryption Standard (AES), Federal Register Vol. 66, No. 235 / Thursday, December 6, 2001 / Notices, pp 63369–63371. http://csrc.nist.gov/encryption/aes/
Файстель Хорст. Криптография и компьютерная безопасность. Перевод А.Винокурова по изданию Horst Feistel. Cryptography and Computer Privacy, Scientific American, May 1973, Vol. 228, No. 5, pp. 15-23. http://www.enlight.ru/crypto/articles/feistel/feist_i.htm
Шнайер Брюс. Прикладная криптография. 2-е изд. Протоколы, алгоритмы и исходные тексты на языке Си., М., «Триумф», 2002 http://www.ssl.stu.neva.ru/psw/crypto/appl_rus/appl_cryp.htm
Menezes Alfred, van Oorschot Paul, Vanstone Scott. Handbook of applied cryptography. ttp://www.cacr.math.uwaterloo.ca/hac/
Винокуров Андрей. Как устроен блочный шифр? Рукопись. http://www.enlight.ru/crypto/articles/vinokurov/blcyph_i.htm
Винокуров Андрей. Выпуски по криптографии для электронного журнала iNFUSED BYTES online. http://www.enlight.ru/crypto/articles/ib/ib.htm
Винокуров Андрей, Применко Эдуард. Текст доклада «О программной реализация стандартов шифрования РФ и США», конференция по информатизации, Москва, МИФИ, 28-29 января 2001г. Опубликован в материалах конференции.
Информационная технология. Криптографическая защита информации. Функция хэширования ГОСТ Р34.11-94, Госстандарт РФ, М., 1994.

Этот алгоритм является обязательным для применения в качестве алгорит­ма шифрования в государственных организациях РФ и ряде коммерческих .

Описание алгоритма

Схема алгоритма показана на рис. 3.1 . Как видно, схема этого алгоритма достаточно проста, что однозначно упрощает его программ­ную или аппаратную реализацию.

Алгоритм ГОСТ 28147-89 шифрует информацию блоками по 64 бита, кото­рые разбиваются на два субблока по 32 бита (N1 и N2). Субблок N1 опре­деленным образом обрабатывается, после чего его значение складывается

со значением субблока N2 (сложение выполняется по модулю 2), затем суб­блоки меняются местами. Такое преобразование выполняется определенное количество раундов: 16 или 32 в зависимости от режима работы алгоритма (описаны далее). В каждом раунде выполняются следующие операции:

1. Наложение ключа. Содержимое субблока /VI складывается по модулю 2 32 с частью ключа Кх.

Ключ шифрования алгоритма ГОСТ 28147-89 имеет размерность 256 би­тов, а Кх— это его 32-битная часть, т. е. 256-битный ключ шифрования представляется в виде конкатенации 32-битных подключей (рис. 3.2):

Щ ATI, АГ2, Ю, АГ4, К5, Кб, К7.

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

Рис. 3.1. Схема алгоритма ГОСТ 28147-

Рис. 3.2. Ключ шифрования алгоритма ГОСТ 28147-89

2. Табличная замена. После наложения ключа субблок /VI разбивает­ся на 8 частей по 4 бита, значение каждой из которых по отдельности заменяется в соответствии с таблицей замены для данной части суб­блока. Табличные замены (Substitution box, S-box) часто используются в современных алгоритмах шифрования, поэтому стоит рассмотреть их подробнее.

Табличная замена используется таким образом: на вход подается блок данных определенной размерности (в этом случае — 4-битный), числовое представление которого определяет номер выходного значения. Напри­мер, имеем S-box следующего вида:

4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.

Пусть на вход пришел 4-битный блок «0100», т. е. значение 4. Согласно таблице, выходное значение будет равно 15, т.е. «1111» (0 заменяется на 4, 1 — на 11, значение 2 не изменяется и т. д.).

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

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.

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

Режимы работы алгоритма

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

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

□ режим гаммирования;

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

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

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

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

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

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

□ КО, Kl, К2, КЗ, К4, К5, Кб, АГ7, КО, ATI и т. д. — в раундах с 1-го по 24-й;

□ К1, Кб, К5, К4, КЗ, К2, К\, КО —в раундах с 25-го по 32-й.

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

□ КО, К\, К2, КЗ, К4, К5, Кб, КП — в раундах с 1-го по 8-й;

□ КП, Кб, К5, К4, КЗ, К2, К\, КО, К1, Кб и т. д. — в раундах с 9-го по 32-й.

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

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

В режиме гаммирования (рис. 3.3) каждый блок открытого текста побитно складывается по модулю 2 с блоком гаммы шифра размером 64 бита. Гамма шифра — это специальная последовательность, которая вырабатывается с помощью описанных выше преобразований следующим образом:

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

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

3. Содержимое N1 складывается по модулю (2 32 – 1) с константой CI = 2 24 + 2 16 + 2 8 + 4 , результат сложения записывается в регистр /VI.

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

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

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

Для расшифровывания аналогичным образом выполняется выработка гаммы, затем снова применяется операция XOR к битам зашифрованного текста и гаммы.

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

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

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

В режиме гаммирования с обратной связью в качестве заполнения регистров /VI и Л/2, начиная со 2-го блока, используется не предыдущий блок гаммы, а результат зашифровывания предыдущего блока открытого текста (рис. 3.4). Первый же блок в данном режиме генерируется полностью аналогично пре­дыдущему.

Рис. 3.4. Выработка гаммы шифра в режиме гаммирования с обратной связью

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

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

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

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

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

3. М и N2 снова зашифровываются в сокращенном режиме простой замены и т. д. до последнего блока информации.

Имитоприставкой считается 64-битное результирующее содержимое регист­ров N1 и N2 или его часть. Чаще всего используется 32-битная имитопри­ставка, т. е. половина содержимого регистров. Этого достаточно, посколь­ку, как и любая контрольная сумма, имитоприставка предназначена, прежде всего, для защиты от случайных искажений информации. Для защиты же от преднамеренной модификации данных применяются другие криптогра­фические методы — в первую очередь электронная цифровая подпись {см. разд. 1.1).

Имитоприставка используется следующим образом:

1. При зашифровывании какой-либо информации вычисляется имитопри­ставка открытого текста и посылается вместе с шифртекстом.

2. После расшифровывания имитоприставка снова вычисляется и сравнива­ется с присланной.

3. Если вычисленная и присланная имитоприставки не совпадают— шифр-текст был искажен при передаче или использовались неверные ключи при расшифровывании.

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

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

Криптостойкость алгоритма

В 1994 г. описание алгоритма ГОСТ 28147-89 было переведено на англий­ский язык и опубликовано ; именно после этого стали появляться ре­зультаты его анализа, выполненного зарубежными специалистами; однако в течение значительного времени не было найдено каких-либо атак, прибли­жающихся к практически осуществимым .

□ большой длины ключа — 256 битов; вместе с секретной синхропосылкой эффективная длина ключа увеличивается до 320 битов;

□ 32 раундов преобразований; уже после 8 раундов достигается полный эф­фект рассеивания входных данных: изменение одного бита блока откры­того текста повлияет на все биты блока шифртекста, и наоборот, т. е. су­ществует многократный запас стойкости.

Рассмотрим результаты криптоанализа алгоритма ГОСТ 28147-89.

Анализ таблиц замен

Поскольку таблицы замен в стандарте не приведены, в ряде работ (на­пример, в ) высказывается предположение, что «компетентная органи­зация» может выдать как «хорошие», так и «плохие» таблицы замен. Однако в известнейший эксперт Брюс Шнайер называет такие предположения «слухами». Ясно, что криптостойкость алгоритма во многом зависит от свойств используемых таблиц замен, соответственно, существуют слабые таблицы замен (пример см. выше), применение которых может упростить вскрытие алгоритма. Тем не менее, возможность использования различных таблиц замен кажется весьма достойной идеей, в пользу которой можно при­вести два следующих факта из истории стандарта шифрования DES (подроб­ности см. в разд. 3.15):

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

□ были предприняты попытки усилить DES против линейного и дифферен­циального криптоанализа путем использования более стойких таблиц за­мен; такие таблицы, действительно более стойкие, были предложены, на­пример, в алгоритме s 5 DES ; но, увы, заменить DES на s 5 DES было невозможно, поскольку таблицы замен жестко определены в стандарте , соответственно, реализации алгоритма наверняка не поддерживают возможность смены таблиц на другие.

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

1. Устанавливается нулевой ключ и выполняется поиск «нулевого вектора», т. е. значения z = /(0), где /() — функция раунда алгоритма. Этот этап занимает порядка 2 операций шифрования.

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

Модификации алгоритма и их анализ

В работе проведен криптоанализ модификаций алгоритма ГОСТ 28147-89:

□ алгоритма GOST-H, в котором, относительно оригинального алгоритма, изменен порядок использования подключей, а именно в раундах с 25-го по 32-й подключи используются в прямом порядке, т. е. точно так же, как и в предыдущих раундах алгоритма;

□ 20-раундового алгоритма GOST®, в раунде которого для наложения клю­ча используется операция XOR вместо сложения по модулю 2 32 .

По результатам анализа сделан вывод о том, что GOST-H и GOST© слабее исходного алгоритма ГОСТ 28147-89, поскольку оба имеют классы слабых ключей. Стоит отметить, что в части криптоанализа GOST© работа слово в слово повторяет раздел, посвященный криптоанализу алгоритма ГОСТ 28147-89, вышедшей в 2000 г. известной работы (без каких-либо ссылок на оригинал). Это ставит под сомнение профессионализм авторов ра­боты и остальные ее результаты.

Весьма интересная модификация алгоритма предложена в работе : таб­лицы S\…Ss обязательно должны быть различными; в каждом раунде алго­ритма должна выполняться их перестановка по определенному закону. Дан­ная перестановка может быть зависимой от ключа шифрования, а может быть и секретной (т. е. являться частью ключа шифрования большего размера по сравнению с исходным 256-битным ключом). Оба этих варианта, по мнению их авторов, существенно усиливают стойкость алгоритма против линейного и дифференциального криптоанализа.

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

Анализ полнораундового алгоритма

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

Отечественные ученые А. Г. Ростовцев и Е. Б. Маховенко в 2001 г. в работе предложили принципиально новый метод криптоанализа (по мнению авторов, существенно более эффективный, чем линейный и дифференциаль­ный криптоанализ ) путем формирования целевой функции от известного открытого текста, соответствующего ему шифртекста и искомого значения ключа и нахождения ее экстремума, соответствующего истинному значению ключа. Они же нашли большой класс слабых ключей алгоритма ГОСТ 28147-89, которые позволяют вскрыть алгоритм с помощью всего 4-х выбранных от­крытых текстов и соответствующих им шифртекстов с достаточно низкой сложностью. Криптоанализ алгоритма продолжен в работе .

В 2004 г. группа специалистов из Кореи предложила атаку, с помощью кото­рой, используя дифференциальный криптоанализ на связанных ключах, мож­но получить с вероятностью 91,7 % 12 битов секретного ключа . Для атаки требуется 2 35 выбранных открытых текстов и 2 36 операций шифрова­ния. Как видно, данная атака, практически, бесполезна для реального вскры­тия алгоритма.