Чтобы обезопасить информацию, хранящуюся на компьютере или передаваемую по компьютерным сетям, используют алгоритмы шифрования (см. статью С. Панасенко «Защита информации в компьютерных сетях: шифрование», «Мир ПК», № 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.
Алгоритм 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 накладывается первый фрагмент ключа, а в последнем раунде не выполняется рассеивающее преобразование.
Алгоритм PRESENT
Алгоритм PRESENT выполняет 31 раунд преобразований. Размер блока данных -- 64 бита. Поддерживаются ключи размером 80 и 128 битов.
Каждый раунд шифрования состоит из трех уровней (рис. 3):
• уровень наложения фрагмента ключа операцией XOR;
• уровень рассеивающих преобразований, где выполняется параллельная замена 4-битовых фрагментов состояния с помощью идентичных таблиц замен S;
• уровень перемешивающих преобразований, осуществляющий битовую перестановку аналогично бывшему стандарту шифрования DES.
Каждый раунд шифрования состоит из трех уровней (рис. 3):
• уровень наложения фрагмента ключа операцией XOR;
• уровень рассеивающих преобразований, где выполняется параллельная замена 4-битовых фрагментов состояния с помощью идентичных таблиц замен S;
• уровень перемешивающих преобразований, осуществляющий битовую перестановку аналогично бывшему стандарту шифрования DES.
Алгоритм Hummingbird
Алгоритм Hummingbird шифрует данные 16-битовыми блоками с использованием 256-битового ключа. В основу этого алгоритма положена оригинальная гибридная архитектура. Процедура шифрования может быть представлена в виде непрерывной работы роторной машины, где в роли четырех виртуальных роторов выступают четыре алгоритма шифрования, выполняющих операции над короткими 16-битовыми блоками данных. Основными компонентами алгоритма являются (рис. 4):
• преобразование, представляющее собой «внутренний» 16-битовый алгоритм шифрования; он выполняет четыре раунда преобразований, в каждом из них осуществляются наложение ключа, табличная замена и битовая перестановка;
• четыре регистра внутреннего состояния;
• дополнительный 16-разрядный сдвиговый регистр с линейной обратной связью.
В алгоритме активно используются операции сложения по модулю 216 (на рисунке обозначены знаком ‘+’), с помощью которых значения регистров состояния накладываются на блоки шифруемых данных. Фактически высокоуровневую структуру алгоритма можно представить как четырехраундовый шифр с различными операциями обратной связи.
• преобразование, представляющее собой «внутренний» 16-битовый алгоритм шифрования; он выполняет четыре раунда преобразований, в каждом из них осуществляются наложение ключа, табличная замена и битовая перестановка;
• четыре регистра внутреннего состояния;
• дополнительный 16-разрядный сдвиговый регистр с линейной обратной связью.
В алгоритме активно используются операции сложения по модулю 216 (на рисунке обозначены знаком ‘+’), с помощью которых значения регистров состояния накладываются на блоки шифруемых данных. Фактически высокоуровневую структуру алгоритма можно представить как четырехраундовый шифр с различными операциями обратной связи.
Особенности облегченных алгоритмов шифрования
Основная тенденция развития современных алгоритмов шифрования -- их усложнение и утяжеление. Увеличиваются размеры основных параметров алгоритмов: блока обрабатываемых данных, ключа шифрования, внутреннего состояния и т. д. Это позволяет компенсировать постоянное наращивание мощностей компьютерных систем, а также лавинообразное увеличение объемов обрабатываемых данных. В свою очередь, неизбежно возрастает ресурсоемкость алгоритмов шифрования и сложность их реализации в угоду безопасности и производительности.
Но для устройств с крайне ограниченными ресурсами такой подход в принципе неверен. Как пишет один из основоположников облегченной криптографии Аксель Пошманн (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.