«Облегчённые» поточные шифры

From CryptoWiki
Jump to: navigation, search

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

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

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

Вернуться к оглавлению

Contents

LFSR

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

Принцип работы

LFSR1.png
Рисунок 1. Регистр сдвига с линейной обратной связью

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

  • читается бит, расположенный в ячейке L - 1; этот бит является очередным битом выходной последовательности;
  • функции обратной связи вычисляет новое значение для ячейки 0, используя текущие значения ячеек;
  • содержимое каждой i-й ячейки перемещается в следующую ячейку i+1, где i = 0;1;...;L-2;
  • в ячейку 0 записывается бит, ранее вычисленный функцией обратной связи.

Если функция обратной связи выполняет логическую операцию «XOR» (исключающее ИЛИ), значения бит (ячеек) могут быть вычислены по следующим формулам:

LFSR3.png
LFSR4.png
LFSR5.png

FCSR

Впервые идея использования регистра сдвига с обратной связью по переносу (FCSR) для создания поточного фильтра была предложена Клаппером и Горески в 1994 году. Позднее ими был разработан алгоритм такого шифра. Один FCSR без подключения линейного компонента не может быть использован в качестве поточного шифра, так как легко дешифруется. В 2002 году был предложен самосинхронизующийся поточный шифр, основанный на совместном использовании FCSR и LFSR. Позднее он был подвергнут атаке с выбором шифротекста. В 2005 году Арно и Бергер предложили идею совместного использования FCSR и линейного фильтра для создания поточного шифра, который получил название F-FCSR (Filtered FCSR). Позже ими были предложены 4 алгоритма, реализующих эту идею: F-FCSR-SF1, F-FCSR-SF, F-FCSR-DF1 и F-FCSR-DF8. Первые два использовали статические фильтры, последние — фильтры, зависящие от ключа. Позже была выявлена слабость всех этих алгоритмов перед различными видами атак. В 2005 Терри Бергер, Франсуа Арноль и Седрик Лараду предложили два шифра на основе F-FCSR для участия в конкурсе eSTREAM: F-FCSR-H для аппаратной реализации и F-FCSR-8 для программной. В результате последующих испытаний у первоначальных версий F-FCSR-H и F-FCSR-8 были найдены уязвимости, которые позже были исправлены в версиях F-FCSR-H v.2 и F-FCSR-16. Улучшенный вариант F-FCSR-H v.2 стал финалистом eSTREAM. Но после обнаружения уязвимости был исключен из eSTREAM Portfolio (rev.1).

Принцип работы

F-FCSR7.png
Рисунок 2. Конфигурация Галуа для FCSR

FCSR реализуется в двух конфигурациях: Галуа и Фиббоначи. В F-FCSR используется конфигурация Галуа, так как она эффективней. Вводятся следующие обозначения:

  1. q — целостность соединения (connection integer) — отрицательное нечетное целое число, удовлетворяющее следующим условиям:
    • F-FCSR1.png
    • T = (|q| − 1)/2 — простое, 2T — период битовой последовательности p/q
    • Число единиц в двоичном представлении числа (1 − q)/2 порядка n/2
  2. p — параметр, зависящий от ключа, такое, что 0 < p < |q|
  3. n — размер главного регистра FCSR, |q| в двоичной записи имеет n + 1 знаков: 2n < −q < 2n+1
  4. d: d = (1 − q)/2, в двоичной записи F-FCSR2.png, di = {0, 1}, dn-1 = 1
  5. M — n-разрядный главный регистр, значения его i-го разряда, F-FCSR3.png.
  6. C — l-разрядный регистр сдвига, l + 1 — число единиц в двоичной записи d, F-FCSR4.png.
  7. (m, c) — состояние FCSR

Если (m, c) — состояние FCSR в момент времени t0, F-FCSR5.png F-FCSR6.png, то F-FCSR8.png — двоичное представление p/q, где p = m + 2c.

Семейство поточных шифров Grain

В этом разделе описывается семейство поточных шифров Grain. Главным его отличием от остальных алгоритмов, представленных на проекте eSTREAM, является чрезвычайно малая аппаратная реализация. В течение этого проекта (eSTREAM) начальная версия v0 была доработана после некоторых наблюдений Berbain. Окончательный вариант Grain известен как Grain v1.

Как и другие шифры, Grain v1 достаточно современен для того чтобы использовать публичные, т.е. общедоступные векторы инициализации (IV), хотя и 80-битные. Признавая необходимость в 128-битных ключах, Hell предложил 128-битные ключи для Grain, в котором используются 96-битные векторы инициализации. Принцип тот же, что и у 80-битной версии, но особенностью является нелинейная часть шифра, а именно меньшая степень чем в v0.

Общая идея Grain состоит в использовании ключа размера |k|; NFSR и LFSR аналогично c размером |k| и выходной функции, которая использует состояние обоих регистров. LFSR обеспечивает функционирование NFSR путем передачи данных. В NFSR поступает ключ, а LFSR - вектор инициализации, дополняемый константой. После этого ключ и вектор инициализации загружаются, но перед генерацией гаммы состояние определяется путем 2 · |k| обновлений, где происходит обратная связь выходной последовательности в LSRF. После инициализации начинается генерирование гаммы.

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

Grain v1

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

Первый этап - это этап инициализации внутреннего состояния с помощью секретного ключа и вектора инициализации. После этого состояние повторно обновляется и используется для генерации гаммы. Основные элементы поточного шифра Grain, как было упомянуто выше, - это два 80-битных регистров сдвига, где один имеет линейную обратную связь (LFSR), а другой нелинейную обратную связь (NFSR). Размер ключа составляет 80-бит, в образовании которого используется 64-бита вектора инициализации. К сожалению, первоначальная версия Grain v0 имела уязвимость в функции вывода, которую обнаружили во время первого этапа оценки. В Grain v1 проблема с ветором инициализации была решена.

Основную структуру алгоритма можно увидеть на рисунке 3. Два многочлена степени 80 f(x) и g(х) используются в качестве функции обратной связи для регистров сдвига с обратной связью LFSR и NFSR. Функция выхода h(х) использует в качестве входной последовательности биты из обоих регистров сдвига с обратной связью. Кроме того, семь бит из NFSR XOR-ятся и результат прибавляется к функции h(x). Этот результат используется в фазе инициализации в качестве дополнительной обратной связи LFSR и NFSR (серые линий на рисунке обозначают эту обратную связь). Во время нормальной работы это значение используется в качестве гаммы.

Grain v1.png
Рисунок 3. Схема поточного шифра Grain v1

Аппаратный модуль Grain v1 был реализован с 16-битным AMBA APB интерфейсом и технологическим процессом в 0,35 мкм на CMOS. Этот интерфейс подходит к 16-битной архитектуре. Причиной для этой реализации на 16-битах слова является подход с низким энергопотреблением. Подробности итераций прохода данных представлены на рисунке 4. Видно, что регистры сдвига обратной связи NFSR и LFSR обрабатывают 16 бит за такт. Только один регистр действует в тот же момент времени, что облегчает ввод ключа и вектор инициализации, потому что те же самые 16 проводов подключены ко всем регистрам. Кроме того, значительно уменьшается среднее потребление энергии. Это происходит за счет наличия временного регистра, который хранит промежуточные результаты. Кроме того все комбинационные схемы, как функции обратной связи g, f и h должны быть реализованы в шестнадцатеричной системе счисления. Входы этих функции - это выбранные биты из регистров, которые не показаны подробно на этом рисунке. h функция также включает в себя XOR операции выходной функции. Выход модуля уже зарегистрирован и вместо гаммы и зашифрованного результата входных данных хранится в регистре. Вместо того, чтобы мультиплексор сам выбирал корректную обратную функцию для временного регистра, команда AND используются для включения и отключения соответствующих входов. Производство 16-битного результата шифрования требует 13 тактов после инициализации.

Grain v1 1.png
Рисунок 4. Схема обработки данных поточного шифра Grain v1

Ниже представлена таблица со значениями GE для основных элементов реализации Grain v1.

Таблица 1. Компоненты реализации Grain v1
Компонент реализации Минимальная площадь (radix - 1), GE Минимальная прощадь (radix - 16), GE
NFSR + LFSR (160 бит)
1,275
1,130
Временный регистр
0
85
Регистр выхода
50
150
Комбинация логики с misc
315
1,835
Контроллер (FSM)
120
160
Суммарно
1,760
3,360

Trivium

Разработчиками поточного шифра Trivium являются Кристоф де Каниэр и Барт Пренель. Это аппаратно-ориентированный синхронный поточный шифр, который был разработан для исследования того, насколько простым должен быть шифр, чтобы не жертвовать его безопасностью. Можно генерировать до 2^64 битов гаммы из 80-битного ключа и 80 битов вектора инициализации. Состояние состоит из 288 бит которые обозначены как S0, S2, ..., s287. В течение инициализации, которая не показана на схеме, ключ и вектор не загружаются в состояние и в то же время обновление фнкции происходит 1152 раз без использования выхода для гаммы. В описании алгоритма, N используется для определения количества выходных битов поточного шифра.

Реализация модуля Trivium имеет тот же 16-битный AMBA APB интерфейс, как и Grain v1. Использование 16-битного процессора также мотивировано энергосбережением, которое является необходимым критерием для «облегчённых» шифров. Рисунок 5 показывает подробную информацию об архитектуре Trivium. "Коробки" с входящем полем comb являются комбинационными логическими элементами алгоритма, которые используются для обновления состояния в соответствии со спецификацией. 288 бит для определения состояния разделяются в 16-разрядные регистры. Кроме того необходимо два временных регистра для хранения промежуточных результатов. Выходной регистр снова используется для непосредственного применения операции XOR гаммы с входным значением. Во время инициализации ключ, вектор инициализации и константы загружаются в регистры. Затем комбинационные схемы используются для обновления регистров, где также используются временные регистры для предотвращения перезаписи необходимых значений. Генерация 16-битной гаммы требует 22 такта после фазы инициализации.

Trivium1.png
Рисунок 5. Схема обработки данных поточного шифра Trivium

Ниже представлена таблица со значениями GE для основных элементов реализации Trivium.

Таблица 2. Компоненты реализации Trivium
Компонент реализации Минимальная площадь (radix - 1), GE Минимальная прощадь (radix - 16), GE
Регистры состояния (288 бит)
1,840
2,040
Временный регистр
0
200
Регистр выхода
50
150
Комбинация логики с misc
290
410
Контроллер (FSM)
210
290
Суммарно
2,390
3,090

Bean

Bean является поточным шифром, который имеет некоторые сходства с Grain: The NFSR и LFSR у второго заменяются на два FCSR. Существует определенный смысл этой замены, так как LFSR в Grain используется для обеспечения большего периода последовательности и случайности, в то время как NFSR используется для обеспечения нелинейности. A FCSR комбинируют обеспечение обоих свойств LFSR и NFSR, плюс остаются такими же компактными на аппаратном уровне. Помимо этого Bean использует реализацию на архитектуре Фибоначчи, в отличие от Grain, который реализован на архитектуре Галуа.

На рисунке 6 представлена архитектура реализации поточного шифра Bean.

Bean 1.png
Рисунок 6. Архитектура Фибоначчи в поточном шифре Bean

Генерация гаммы

У обоих регистров сдвига размер составляет 80 бит, как и размер ключа. Состояние первого FCSR 1 обозначается Bean 2.png, а состояние FCSR 2 Bean 3.png, которые определяются следующим образом:

Bean 4.png

Обновление состояния FCSR 1:

Bean 5.png

Обновление состояния FCSR 2:

Bean 6.png

Функция Bean 7.png используется для создания самой гаммы. Используется S-box, на вход которого подается 6 бит, а на выходе 4. Биты гаммы получаются из Bean 8.png:

Bean 9.png

А функция Bean 7.png имеет вид:

Bean 10.png

Hummingbird

В отличие от существующих легких криптографических примитивов, в которых присутствует либо блочный шифр, либо поточный шифр, Hummingbird является сочетанием двух вышеупомянутых шифров с 16-битным размером блока, 256-битным размером ключа, и 80-битным внутренним состоянием. Размер ключа и внутреннего состояния Hummingbird обеспечивает уровень безопасности, адекватный для многих приложений RFID. Для ясности, мы используем обозначения, перечисленные в таблице 1 описания алгоритма. На рисунке 7 показана структура верхнего уровня шифрования Hummingbird в процессе зашифрования.

Lightweight crypto Hummingbird 1.png
Рисунок 7. Структура верхнего уровня шифрования Hummingbird

Общая структура алгоритма шифрования Hummingbird состоит из четырех 16-битных блочных шифров Lightweight crypto Humminbird text 1.png - четырех 16-битных регистров внутреннего состояния RS1,RS2,RS3 и RS4, и 16-ступенчатого LFSR. 256-битный секретный ключ K делится на четыре 64-битных подключа k1,k2,k3 и k4, которые используются в четырех блочных шифров. 16-битный блок открытого текста Lightweight crypto Humminbird text 2.png шифруется взятием по модулю Lightweight crypto Humminbird text 3.png добавлением Lightweight crypto Humminbird text 2.png и содержащий первый регистр RS1 внутреннего состояния. Результат сложения затем шифруется с первым блочным шифром Lightweight crypto Humminbird text 4.png. Эта процедура повторяется таким же образом, еще три раза, и выход Lightweight crypto Humminbird text 5.png является зашифрованным текстом Lightweight crypto Humminbird text 6.png. Кроме того, состояние четырех регистров внутреннего состояния также будут обновлены непредсказуемым способом, основанным на их текущих состояниях, выходах первых трех блочных шифров, и состоянии LFSR. Процесс расшифровки происходит по схеме аналогичной шифрованию.

На практике в Hummingbird используют четыре 16-битных случайные Lightweight crypto Humminbird text 7.png которые в первую очередь выбираются для инициализации четырех внутренних состояний регистров Lightweight crypto Humminbird text 8.png (i = 1, 2, 3, 4),далее следуют четыре последовательных шифрования сообщения (RS1+ RS3)mod2 с Hummingbird, работающим в режиме инициализации. Последний 16-битный зашифрованный текст используется для инициализации LFSR. Кроме того, 13тый бит LFSR всегда имеет значение, чтобы предотвратить нулевой регистр. LFSR также «шагнул» с целью обновлениярегистра внутреннего состояния RS2.

Четыре одинаковых 16-битных блочных шифра используются в последовательном порядке в схеме шифрования Hummingbird.16-битный блочный шифр является типичной SP-сетью с 16-битным размером блока и 64-битным ключом.Он состоит из 4 итераций, и на последней итерации включает в себя только функцию смешения содержимого ключа и шаги замещения S-бокса. Как и в любой другой SP-сети, одна очередная итерация состоит из трех этапов: шаг смешения ключа, слой замены и слой перестановки. В этом 16-битном блочном шифре для смешения ключа используются простое исключение или операция, с целью эффективной реализации в программной и аппаратной части.

Глоссарий

Библиографический указатель

Перейти к списку литературы по разделу «Облегчённые» поточные шифры.

Вернуться к оглавлению

Кузнецов Н.П., 2015 г.