А.Винокуров. Серия выпусков по криптографии для электронного журнала "iNFUSED BYTES Online".


На домашнюю страничку Содержание Предыдущий выпуск Следующий выпуск

Выпуск 10. Новые подходы в построении блочных шифров с секретным ключом.


Сообщение на эту тему было подготовлено мной и прочитано моим содокладчиком на XXVI международной конференции "Информационные технологии в науке, образовании, телекоммуникации, бизнесе и охране природных ресурсов", проходившей с 20 по 30 мая 1999 года в г. Гурзуф, Украина. В настоящем выпуске представлены основные положения этого выступления, переработанные и дополненные с учетом событий, прошедших с того времени.

Исходным пунктом истории развития современных блочных шифров с секретным ключом является криптографическая система "Люцифер", разработанная в исследовательской лаборатории фирмы IBM в конце 60-х - начале 70-х годов XX века под руководством доктора Хорста Файстеля. В дальнейшем в эту систему были внесены определенные изменения, в результате чего возникла общая архитектура блочных шифров с секретным ключом, получившая название "сеть Файстеля" по имени одного из своих создателей. Эта архитектура доминировала в криптографии до середины девяностых годов, и самые известные блочные шифры с секретным ключом построены в соответствии с ее принципами. Безусловным лидером среди них по распространенности реализаций является стандарт шифрования США, алгоритм DES, доживающий, впрочем, в своем нынешнем качестве последние месяцы, - уже определен его преемник. Российский стандарт ГОСТ 28147-89, также относится к этому классу шифров.

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

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

2. Принадлежность к сбалансированным сетям Файстеля. В криптоалгоритмах этого типа шифруемый блок данных разделяется на две одинаковые по размеру части: старшую (H) и младшую (L). На каждом раунде из младшей части и ключевого элемента раунда (ki) с помощью функции шифрования раунда (fi) вырабатывается элемент данных, используемый для модификации старшей части путем наложения на нее через операцию побитового суммирования по модулю 2: H'=H (+) fi(L,ki). Между раундами старшая и младшая часть блока меняются местами. При такой конструкции шифра преобразование одного раунда обратно самому себе, а процедуры за- и расшифрования отличаются только порядком использования функций шифрования на раундах. Если последовательность раундовых функций шифрования палиндромиальна (идентична своему обращению), и, в частности, если на всех раундах используетс одна и та же функция шифрования, то процедуры за- и расшифрования отличаются только порядком использования ключевых элементов. Это позволяет воплотить обе функции в одном фрагменте аппаратной схемы или программного кода, способствуя тем самым получению максимально компактной реализации.

3. Простая структура раунда. Раунды шифрования большинства шифров "первой волны" составлены из нескольких простых операций. Так, в Российском стандарте функция шифрования
fГОСТ(L,k)=Rot11(S((L+k)mod232))
состоит всего из трех шагов:

В прежнем стандарте шифрования США функция шифрования
fDES(L,k)=P(S(Exp32,48(L) (+) k))
состоит из четырех шагов:

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

Используемые блоки замен небольшие по размеру, как правило, фиксированные, и тщательно выверенные. Для их проектирования применялись специальные закрытые методики, не публикуемые разработчиками шифров, предположительно основанные на использовании так называемых бент-функций или родственных подходов. Комбинирование ключевых элементов с данными осуществляется обычно посредством аддитивных бинарных операций. Так, в шифре DES использовано побитовое суммирование по модулю 2, а в Российском стандарте -суммирование по модулю 232. Реже встречается комбинирование через параметризованные битами ключа узлы замен, как в шифре "Люцифер".

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

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

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

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

В силу вышесказанного криптографическая стойкость многих старых шифров сегодня может быть поставлена под сомнение. Например, сообщения, зашифрованные DES, неоднократно успешно дешифровались с использованием распределенной вычислительной сети, организованной через Internet, и с помощью специально созданного для этой цели компьютера. Все это с одной стороны, и растущие потребности сферы информационных технологий в криптографической защите с другой, приводило к интенсивным исследованиям в соответствующей отрасли криптографии и к созданию новых шифров, зачастую использующих принципиально новые идеи и подходы. Интенсивность этой работы существенно возросла в последнее время, когда стал очевидным факт, что многие шифры "первого поколения" не могут долее считаться достаточно надежными для того, чтобы удовлетворять растущие потребности бизнеса в защите информации. В итоге несколько лет назад в США был объявлен конкурс на выработку нового, усовершенствованного стандарта шифрования, заранее получившего аббревиатуру AES (Advanced Encryption Standard). Конкурс завершился в октябре 2000 года, но его победителю, которым стал шифр Rijndael, еще предстоит процедура официального утверждения в этом новом качестве. Комитетом по выработке стандарта были сформулированы следующие требования к шифрам-кандидатам:

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

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

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

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

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

В качестве кандидатов на место нового стандарта различные организации, компании и частные лица выдвинули 15 перечисленных ниже шифров:
CAST-256, CRYPTON, DEAL, DFC, E2, HPC, FROG, LOOKI-97, MAGENTA, MARS, R6, RIJNDAEL, SAFER+, SERPENT, TWOFISH.
Большинство из них разработаны в последние несколько лет и отражают, таким образом, новейшие достижения рассматриваемой области криптографии. Ниже в таблице 1 дан краткий обзор по ключевым моментам архитектуры этих шифров [по работе: Eli Biham. A note on comparing the AES candidates.]:

Таблица 1. Характеристики шифров-кандидатов на AES.
Шифр Архитектура Число раундов Особые архитектурные решения
CAST-256UFN 48 
CryptonSQUARE 12 
DealBFN 6,8В качестве функции шифрования используется алгоритм DES.
DFCBFN 8Техника декоррелирования (decorrelation) и операции мультипликативной группы.
E2BFN 12 
Frog* 8Техника "бомба перестановок" (bomb permutation).
HPC* 8

Техника "взбитый пудинг" (hasty pudding).

LOKI97BFN 16 
MagentaBFN 6,8 
MarsUFN 32Вращение на переменное число разрядов, мультипликативные операции, некриптографические раунды.
RC6BFN 20Вращение на переменное число разрядов, мультипликативные операции.
RijndaelSQUARE 10,12,14 
Safer+SPN 8,12,16Техника "PHT"
SerpentSPN 32Техника "bitslice"
TwofishBFN 16 
Типы архитектур обозначены следующим образом:
BFN - Balanced Feistel Network - сбалансированная сеть Файстеля;
UFN - Unbalanced Feistel Network - несбалансированная сеть Файстеля;
SPN - Substitution-Permutation Network - подстановочно-перестановочная сеть;
SQUARE - архитектура "квадрат";
* - полностью нетрадиционная архитектура.

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

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

Ряд шифров-кандидатов (E2, DFC, DEAL) являются классическими сетями Файстеля, некоторые другие (LOKI-97, TWOFISH) тоже соответствуют этому архитектурному принципу, но содержат небольшие отклонения от него. Так, в шифре LOKI-97 к каждому преобразованию раунда добавляется модификация половины шифруемого блока с помощью прибавления ключевого элемента, выполняемая дважды за раунд, а в шифре TWOFISH половина блока между раундами шифрования циклически сдвигается на один бит. Указанные отклонения от классической схемы призваны увеличить сложность криптографического преобразования и направлены против отдельных видов криптоанализа.

Другая часть шифров (MARS, CAST-256) относится к классу несбалансированных сетей Файстеля, причем среди них встречаются шифры как с доминирующей (большей по размеру) изменяемой на раунде частью (MARS), так и доминирующей неизменной частью (CAST-256). Несбалансированные сети Файстеля стали рассматриваться как возможные решения лишь в последнее десятилетие и не так хорошо изучены, как сбалансированные. В своей работе "Несбалансированные сети Файстеля и разработка блочных шифров" Брюс Шнайер и Джон Келси отметили ряд преимуществ, присущих этой архитектуре. Доминирование неизменной части позволяет усложнить характер зависимости значения функции шифрования от своих аргументов ввиду их большего размера, однако размер самого значения при этом меньше. Как следствие, для достижения такой же стойкости, как у сбалансированной сети, необходимо увеличить число раундов, что, конечно, снизит быстродействие. В схемах с доминированием изменяемой части функция шифрования зависит от меньшего по размеру фрагмента блока данных, поэтому для нее легче установить закономерности. Однако на каждом раунде изменяется большая часть шифруемого блока, что усложняет преобразование и компенсирует указанный недостаток. Авторы упомянутой выше статьи отметили, что стойкость шифров этого типа к линейному криптоанализу возрастает.

Некоторые из предложенных шифров (SERPENT, SAFER+) относятся к классу SP-сетей, являющихся шифрующими структурами более общего типа, нежели сети Файстеля. Эта архитектура известна достаточно давно, - следует отметить, что к ней относится "прародитель" всех современных блочных криптоалгоритмов - шифр "Люцифер". Как правило, SP-сети общего вида устойчивы к различным вариантам криптоанализа, хорошо зарекомендовавшим себя против сетей Файстеля. Это обусловлено потенциально более высокой степенью нелинейности шифрующего преобразования. Однако и обоснование надежности шифров данного типа порой гораздо сложнее, так как свойства цепочек преобразований, построенных таким образом, гораздо менее предсказуемы. В общем случае при использовании шифрующих SP-сетей процедуры за- и расшифрования существенно различны и не могут быть совмещены, что увеличивает ресурсоемкость реализации вдвое по сравнению с сетями Файстеля. По этой причине, а также в силу вышеупомянутой сложности разработки шифры этого типа не получили в прошлом широкого распространения. Однако в настоящее время в связи с бурным развитием микроэлектроники и криптологии они становятся перспективным направлением синтеза шифров и основой все большего числа новых разработок.

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

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

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

Практически все предложенные кандидаты на место нового стандарта являются однородными или почти однородными шифрующими структурами. В последнем случае раунды отличаются друг от друга используемыми таблицами подстановок или константами сдвига. Отдельно стоит шифр MARS, имеющий существенно неоднородную структуру, - в нем используются 4 серии по 8 раундов различного типа. Безусловно, указанный подход значительно усложняет реализацию шифров, однако простота реализации не является главным требованиям, предъявляемым к современным шифрам. В шифрах с полностью нетрадиционной архитектурой (HPC, FROG) высокая неоднородность обычно достигается за счет используемых в них нестандартных решений.

3. Еще одной особенностью современных шифров является более сложная структура раундов. Это отчетливо прослеживается на шифрах-кандидатах на место нового стандарта. Из всех предложенных криптоалгоритмов только R6 предусматривает относительно простой раунд шифрования. Например, в алгоритме DEAL функцией шифрования является преобразование половины блока по алгоритму DES, только без начальной и конечной битовых перестановок. В LOKI-97 функция шифрования предусматривает следующие операции над данными:

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

В шифре TWOFISH функция шифрования предполагает выполнение следующих операций над данными:

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

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

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

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

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

5. Блочные шифры "первого поколения" имели ключи фиксированного размера и использовали достаточно простую схему выработки ключевых элементов из ключа. Так, в алгоритмах DES и ГОСТ ключевые элементы содержат некоторые подмножества битов исходного ключа. Все шифры, выдвинутые в качестве кандидатов на AES, допускают использование ключей различного размера и имеют достаточно сложную схему выработки последовательности ключевых элементов для раундов шифрования. При этом могут использоваться те же самые функции преобразований, которые применяются и для шифрования. Например, в шифре LOKI-97 для выработки последовательности ключевых элементов используется несбалансированная сеть Файстеля и применяется та же самая функция шифрования, что и при собственно шифровании. Другой возможный подход к выработке ключевых элементов заключается в том, чтобы с помощью генератора псевдослучайных чисел сформировать из ключа числовую последовательность, и затем подвергнуть ее элементы зашифрованию по тому же самому алгоритму на фиксированном, заранее определенном ключе. Все подобные подходы характеризуются тем, что сложность схемы выработки ключевых элементов сопоставимы по сложности и криптостойкости с самим алгоритмом шифрования. Упрощенные подходы, подобные использованному в Российском стандарте шифрования, больше не встречаются в практике разработки современных блочных шифров.

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

6. Согласно требованию к новому стандарту, размер шифруемого блока составляет для всех кандидатов 128 битов. Считается, что шифры с размером блока данных в 64 бита больше не могут считаться достаточно устойчивыми к отдельным экстенсивным методам криптоанализа, ставшим возможными в последнее время в результате бурного развития вычислительной техники. Некоторые из шифров-кандидатов на AES были построены на основе шифров с меньшим размером блока для того, чтобы удовлетворить упомянутому требованию. При этом было использовано несколько интересных подходов. Так, шифр DEAL был создан на основе криптоалгоритма DES с 64-битовым размером блока. Для удвоения размера блока DES используется в качестве функции шифрования в алгоритме DEAL, то есть оперирует его полублоками. Данный подход является универсальным и может быть использован для удвоения размера блока любого шифра. Однако он имеет существенный недостаток - скорость работы такого "сложного шифра" снижается во столько раз, сколько пар раундов содержит такой шифр. Так, скорость работы реализаций DEAL с его шестью раундами примерно равна скорости работы тройного DES и в три раза меньшей скорости работы DES.

Другой подход к увеличению размера блока заключается в том, чтобы перейти от сбалансированной сети Файстеля к несбалансированной, как это сделано в шифре CAST-256. Этот шифр разработан на базе шифра CAST-128 c 64-битовым размером блока. При этом в CAST-256 используется без каких-либо изменений функция шифрования из CAST-128.

Ряд предложенных шифров (RIJNDAEL) демонстрируют в вопросе выбора размера блока данных определенную гибкость и позволяют использовать блок переменного размера - 128, 192 или 256 бит. В силу приведенного выше замечания о возможном использовании криптоалгоритмов в схеме реализации хэш-функций данная его особенность может оказаться весьма полезной.

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

На домашнюю страничку Содержание Предыдущий выпуск Следующий выпуск


[Оглавление] [Предыдущий выпуск] [Следующий выпуск]
[Начало осмотра] [Что нового] [Статьи] [Выпуски в "Байтах"] [Что скачать] [Криптоалгоритмы] [Глоссарий] [Ссылки] [Гостевая книга] [Форум] [Напиши мне]

Версия от 23.12.00. (c) 1998-2000 Андрей Винокуров.