Чтобы обезопасить информацию, хранящуюся на компьютере или передаваемую по компьютерным сетям, используют алгоритмы шифрования (см. статью С. Панасенко «Защита информации в компьютерных сетях: шифрование», «Мир ПК», № 2/02). Они должны быть стойкими, чтобы невозможно было раскрыть зашифрованные данные, а кроме того, быстрыми, чтобы удавалось шифровать большие объемы данных, не затрачивая на это все ресурсы компьютера или сетевого оборудования.
Известно много алгоритмов шифрования, одновременно и быстрых, и достаточно стойких, а также универсальных: их можно применять и на высокопроизводительных серверах, и на персональных компьютерах, и в различных встраиваемых системах. Но существует отдельный класс специфических устройств с крайне ограниченными ресурсами, для которых не подходят распространенные алгоритмы обычной криптографии. К ним относятся следующие:
Известно много алгоритмов шифрования, одновременно и быстрых, и достаточно стойких, а также универсальных: их можно применять и на высокопроизводительных серверах, и на персональных компьютерах, и в различных встраиваемых системах. Но существует отдельный класс специфических устройств с крайне ограниченными ресурсами, для которых не подходят распространенные алгоритмы обычной криптографии. К ним относятся следующие:
• ультрадешевые мобильные телефоны;
• low-end смарт-карты, в том числе беспроводные;
• беспроводные сенсоры;
• различные контроллеры, обеспечивающие работу промышленных распределенных измерительно-управляющих систем;
• радиометки (Radio Frequency Identificators -- RFIDs).
• low-end смарт-карты, в том числе беспроводные;
• беспроводные сенсоры;
• различные контроллеры, обеспечивающие работу промышленных распределенных измерительно-управляющих систем;
• радиометки (Radio Frequency Identificators -- RFIDs).
Шифрование в пассивных радиометках -- особый случай даже среди перечисленных устройств с крайне низкими ресурсами. Пассивные радиометки не имеют собственного элемента питания и активируются наведенным сигналом считывателя. Следовательно, шифрование в них должно быть максимально простым -- радиометка должна до затухания наведенного сигнала успеть зашифровать данные и передать свой ответ обратно считывателю (см. статью А. Баулина «RFID-метки», «Мир ПК», № 6/08).
Обычные алгоритмы шифрования для такого случая не подходят -- они достаточно сложны. За данную узкоспецифичную область отвечает отдельное направление, называемое lightweight, или
«облегченной», криптографией.
Обычные алгоритмы шифрования для такого случая не подходят -- они достаточно сложны. За данную узкоспецифичную область отвечает отдельное направление, называемое lightweight, или
«облегченной», криптографией.
К облегченной криптографии относятся алгоритмы, разрабатываемые специально для устройств с ограниченными или крайне ограниченными вычислительными ресурсами. В принципе критерии, по которым тот или иной криптографический алгоритм можно отнести к облегченной криптографии, достаточно размыты. Тем не менее общие свойства таких алгоритмов -- сверхнизкие требования к ресурсам того устройства, на котором предполагается их использовать, а именно:
• к требуемой площади кристалла, на котором алгоритм может быть аппаратно реализован (радиометки должны быть максимально дешевыми, а площадь кристалла должна напрямую влиять на их стоимость);
• к вычислительной мощности микропроцессора или микроконтроллера, на котором выполняются вычисления;
• к оперативной памяти устройства;
• к энергонезависимой памяти устройства и т. п.
Облегченная криптография представляет собой относительно свежее направление в криптографии -- первые известные достижения в этой области появились не более десяти лет назад. Посмотрим, какие бывают облегченные алгоритмы шифрования и чем они отличаются от обычных.
• к энергонезависимой памяти устройства и т. п.
Облегченная криптография представляет собой относительно свежее направление в криптографии -- первые известные достижения в этой области появились не более десяти лет назад. Посмотрим, какие бывают облегченные алгоритмы шифрования и чем они отличаются от обычных.
Алгоритм KATAN
KATAN -- семейство алгоритмов шифрования KATAN32, KATAN48, KATAN64. Число в названии алгоритма обозначает размер блока шифруемых данных в битах. Все алгоритмы используют 80-битовый ключ шифрования.
Любой из алгоритмов KATAN загружает шифруемый блок данных в два сдвиговых регистра, образующих внутреннее состояние алгоритма (т.е. некое промежуточное значение, зависящее от блока данных и ключа шифрования; именно оно и обрабатывается алгоритмом в процессе шифрования). Шифрование состоит из 254 раундов, в каждом из которых используются нелинейные функции, формирующие обратную связь регистров.
Структура одного раунда шифрования показана на рис. 1.
Любой из алгоритмов KATAN загружает шифруемый блок данных в два сдвиговых регистра, образующих внутреннее состояние алгоритма (т.е. некое промежуточное значение, зависящее от блока данных и ключа шифрования; именно оно и обрабатывается алгоритмом в процессе шифрования). Шифрование состоит из 254 раундов, в каждом из которых используются нелинейные функции, формирующие обратную связь регистров.
Структура одного раунда шифрования показана на рис. 1.
_(1178).jpg)
Алгоритм Curupira
Одним из авторов алгоритма Curupira является Винсент Риджмен (Vincent Rijmen), который входит в число создателей AES, современного стандарта шифрования США. Curupira несколько похож на AES, только в нем используются более простые операции, а также у него меньшее внутреннее состояние, размер которого всего 96 бит, а не 128 битов, как у алгоритма AES.
Curupira шифрует данные 96-битовыми блоками с использованием ключа одного из следующих фиксированных размеров: 96, 144 и 192 бита. Блок данных представляется в виде байтового массива размером 3 X 4 (это и есть внутреннее состояние алгоритма), над которым в каждом раунде выполняется следующая последовательность операций:
• табличная замена каждого байта состояния (рис. 2);
• байтовая перестановка в пределах строк массива состояния;
• рассеивающее преобразование, выполняемое путем умножения фиксированной матрицы на состояние алгоритма;
• наложение операцией XOR ключа шифрования на состояние определенного
фрагмента.
• табличная замена каждого байта состояния (рис. 2);
• байтовая перестановка в пределах строк массива состояния;
• рассеивающее преобразование, выполняемое путем умножения фиксированной матрицы на состояние алгоритма;
• наложение операцией XOR ключа шифрования на состояние определенного
фрагмента.
Количество раундов алгоритма не является строго определенным. Для каждого размера ключа предусмотрено минимальное и максимальное число раундов: от 10 для 96-битового ключа до 23 для 192-битового. Перед первым раундом на блок данных операцией XOR накладывается первый фрагмент ключа, а в последнем раунде не выполняется рассеивающее преобразование.
_(1176).jpg)
Алгоритм PRESENT
Алгоритм PRESENT выполняет 31 раунд преобразований. Размер блока данных -- 64 бита. Поддерживаются ключи размером 80 и 128 битов.
Каждый раунд шифрования состоит из трех уровней (рис. 3):
• уровень наложения фрагмента ключа операцией XOR;
• уровень рассеивающих преобразований, где выполняется параллельная замена 4-битовых фрагментов состояния с помощью идентичных таблиц замен S;
• уровень перемешивающих преобразований, осуществляющий битовую перестановку аналогично бывшему стандарту шифрования DES.
Каждый раунд шифрования состоит из трех уровней (рис. 3):
• уровень наложения фрагмента ключа операцией XOR;
• уровень рассеивающих преобразований, где выполняется параллельная замена 4-битовых фрагментов состояния с помощью идентичных таблиц замен S;
• уровень перемешивающих преобразований, осуществляющий битовую перестановку аналогично бывшему стандарту шифрования DES.
_(3904).jpg)
Алгоритм Hummingbird
Алгоритм Hummingbird шифрует данные 16-битовыми блоками с использованием 256-битового ключа. В основу этого алгоритма положена оригинальная гибридная архитектура. Процедура шифрования может быть представлена в виде непрерывной работы роторной машины, где в роли четырех виртуальных роторов выступают четыре алгоритма шифрования, выполняющих операции над короткими 16-битовыми блоками данных. Основными компонентами алгоритма являются (рис. 4):
• преобразование, представляющее собой «внутренний» 16-битовый алгоритм шифрования; он выполняет четыре раунда преобразований, в каждом из них осуществляются наложение ключа, табличная замена и битовая перестановка;
• четыре регистра внутреннего состояния;
• дополнительный 16-разрядный сдвиговый регистр с линейной обратной связью.
В алгоритме активно используются операции сложения по модулю 216 (на рисунке обозначены знаком ‘+’), с помощью которых значения регистров состояния накладываются на блоки шифруемых данных. Фактически высокоуровневую структуру алгоритма можно представить как четырехраундовый шифр с различными операциями обратной связи.
• преобразование, представляющее собой «внутренний» 16-битовый алгоритм шифрования; он выполняет четыре раунда преобразований, в каждом из них осуществляются наложение ключа, табличная замена и битовая перестановка;
• четыре регистра внутреннего состояния;
• дополнительный 16-разрядный сдвиговый регистр с линейной обратной связью.
В алгоритме активно используются операции сложения по модулю 216 (на рисунке обозначены знаком ‘+’), с помощью которых значения регистров состояния накладываются на блоки шифруемых данных. Фактически высокоуровневую структуру алгоритма можно представить как четырехраундовый шифр с различными операциями обратной связи.
_(7031).jpg)
Особенности облегченных алгоритмов шифрования
Основная тенденция развития современных алгоритмов шифрования -- их усложнение и утяжеление. Увеличиваются размеры основных параметров алгоритмов: блока обрабатываемых данных, ключа шифрования, внутреннего состояния и т. д. Это позволяет компенсировать постоянное наращивание мощностей компьютерных систем, а также лавинообразное увеличение объемов обрабатываемых данных. В свою очередь, неизбежно возрастает ресурсоемкость алгоритмов шифрования и сложность их реализации в угоду безопасности и производительности.
Но для устройств с крайне ограниченными ресурсами такой подход в принципе неверен. Как пишет один из основоположников облегченной криптографии Аксель Пошманн (Axel Poschmann), при создании облегченных алгоритмов шифрования во главу угла ставится стоимость реализации алгоритма в устройстве при адекватном уровне безопасности и должной производительности, т. е. важен компромисс между этими тремя параметрами, зависящий от конкретных требований к устройству. Задача авторов облегченного алгоритма шифрования -- найти такой компромисс.
Чем же облегченные алгоритмы шифрования отличаются от универсальных? Вот основные подходы, позволяющие криптографам создать нетребовательные к ресурсам и при этом относительно стойкие алгоритмы шифрования:
• уменьшение (до разумных пределов) размеров основных параметров алгоритма -- блока шифруемых данных, ключа шифрования и внутреннего состояния алгоритма;
• попытки компенсации вынужденной потери стойкости алгоритмов за счет проектирования на основе хорошо изученных, широко применяемых операций, осуществляющих элементарные линейные/нелинейные преобразования. Такие операции можно представить как детали некоего конструктора, из которых криптографы «собирают» алгоритм, обладающий нужными качествами;
• уменьшение размеров данных, используемых в конкретных операциях. Например, в алгоритмах шифрования часто применяются таблицы замен; чтобы хранить таблицу, заменяющую 8-битовые фрагменты данных, необходимо 256 байт, но такую таблицу можно составить из комбинации двух 4-битовых таблиц, требующих всего 32 байта в сумме (данный подход выбрали авторы описанного выше алгоритма Curupira);
• использование «дешевых» с точки зрения ресурсоемкости, но эффективных преобразований, таких как управляемые битовые перестановки (в которых выбирается конкретный вариант перестановки в зависимости от значения управляющего бита; этим битом может быть, например, определенный бит ключа), сдвиговые регистры и пр.;
• применение преобразований, в отношении которых возможны варианты реализации в зависимости от ресурсов конкретного шифратора (например, уменьшение требований к памяти, но в ущерб скорости шифрования, или наоборот).
Следует отметить, что облегченные алгоритмы шифрования создаются либо для систем с низким или средним уровнем безопасности, либо для систем, где будет учтена специфика используемых алгоритмов и будет найдено решение, позволяющее сделать реализацию алгоритма максимально безопасной для его уровня стойкости.
Но для устройств с крайне ограниченными ресурсами такой подход в принципе неверен. Как пишет один из основоположников облегченной криптографии Аксель Пошманн (Axel Poschmann), при создании облегченных алгоритмов шифрования во главу угла ставится стоимость реализации алгоритма в устройстве при адекватном уровне безопасности и должной производительности, т. е. важен компромисс между этими тремя параметрами, зависящий от конкретных требований к устройству. Задача авторов облегченного алгоритма шифрования -- найти такой компромисс.
Чем же облегченные алгоритмы шифрования отличаются от универсальных? Вот основные подходы, позволяющие криптографам создать нетребовательные к ресурсам и при этом относительно стойкие алгоритмы шифрования:
• уменьшение (до разумных пределов) размеров основных параметров алгоритма -- блока шифруемых данных, ключа шифрования и внутреннего состояния алгоритма;
• попытки компенсации вынужденной потери стойкости алгоритмов за счет проектирования на основе хорошо изученных, широко применяемых операций, осуществляющих элементарные линейные/нелинейные преобразования. Такие операции можно представить как детали некоего конструктора, из которых криптографы «собирают» алгоритм, обладающий нужными качествами;
• уменьшение размеров данных, используемых в конкретных операциях. Например, в алгоритмах шифрования часто применяются таблицы замен; чтобы хранить таблицу, заменяющую 8-битовые фрагменты данных, необходимо 256 байт, но такую таблицу можно составить из комбинации двух 4-битовых таблиц, требующих всего 32 байта в сумме (данный подход выбрали авторы описанного выше алгоритма Curupira);
• использование «дешевых» с точки зрения ресурсоемкости, но эффективных преобразований, таких как управляемые битовые перестановки (в которых выбирается конкретный вариант перестановки в зависимости от значения управляющего бита; этим битом может быть, например, определенный бит ключа), сдвиговые регистры и пр.;
• применение преобразований, в отношении которых возможны варианты реализации в зависимости от ресурсов конкретного шифратора (например, уменьшение требований к памяти, но в ущерб скорости шифрования, или наоборот).
Следует отметить, что облегченные алгоритмы шифрования создаются либо для систем с низким или средним уровнем безопасности, либо для систем, где будет учтена специфика используемых алгоритмов и будет найдено решение, позволяющее сделать реализацию алгоритма максимально безопасной для его уровня стойкости.
Развитие облегченных алгоритмов шифрования
Что же будет происходить дальше с облегченными алгоритмами шифрования? Можно предположить, что развитие облегченных алгоритмов шифрования будет в ближайшие годы весьма активным, поскольку они крайне востребованы. Можно также предположить, что будут наблюдаться две тенденции развития таких алгоритмов.
1. Даже перечисленные в начале статьи устройства (для которых характерны крайне ограниченные ресурсы) очень сильно различаются своими характеристиками. По сравнению с персональным компьютером все они крайне слабы, но сравните между собой самый простой мобильный телефон и пассивные RFID, не обладающие даже источником питания. Вполне вероятно, что из облегченной криптографии в ближайшее время выделится новое направление (назовем его «наилегчайшим» -- ultra-lightweight), в рамках которого будут создаваться алгоритмы для самых-самых ограниченных в ресурсах устройств. Создание же единого алгоритма для всего спектра облегченных устройств делает технически сложным его применение в устройствах Low-end и нецелесообразным -- в устройствах High-end данного спектра.
1. Даже перечисленные в начале статьи устройства (для которых характерны крайне ограниченные ресурсы) очень сильно различаются своими характеристиками. По сравнению с персональным компьютером все они крайне слабы, но сравните между собой самый простой мобильный телефон и пассивные RFID, не обладающие даже источником питания. Вполне вероятно, что из облегченной криптографии в ближайшее время выделится новое направление (назовем его «наилегчайшим» -- ultra-lightweight), в рамках которого будут создаваться алгоритмы для самых-самых ограниченных в ресурсах устройств. Создание же единого алгоритма для всего спектра облегченных устройств делает технически сложным его применение в устройствах Low-end и нецелесообразным -- в устройствах High-end данного спектра.
2. Углубление разрыва между программно и аппаратно ориентированными облегченными алгоритмами шифрования. Глубочайшую разницу между требованиями к алгоритму с целью минимизации используемых ресурсов при программной и при аппаратной реализации продемонстрировал упомянутый выше Аксель Пошманн на примере аппаратно ориентированного алгоритма PRESENT: его раунд, крайне просто реализуемый аппаратно, требует существенных ресурсов при программной реализации.
Об авторах:
Сергей Панасенко -- начальник отдела разработки программного обеспечения фирмы АНКАД, кандидат технических наук, serg@panasenko.ru;
Сергей Смагин -- инженер-программист фирмы АНКАД, serg@ochacovo.ru.