Halka

Halka — блочный шифр с размером блока 64 бита, длиной ключа 80 бит и количеством раундов 24. В данном шифре используются в качестве нелинейных элементов 8-битные S-блоки. Главной особенностью является вычисление Шаблон:Не переведено 5 на основе LFSRШаблон:Sfn, требующего 138 логических элементовШаблон:Sfn, что делает данный шифр применимым в облегчённой криптографии, несмотря на использование 8-битного S-блока. Развёртывание ключа осуществляется по схеме, аналогичной той, что используется для блочного шифра PRESENTШаблон:Sfn. Данный шифр был представлен в 2014 году.

История

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

• это первое использование 8-битного S-блока в облегчённой криптографии;
• традиционно LFSR был использован только в потоковых шифрах, в то время как Halka — блочный;
• Halka сочетает в себе сильные стороны как AES, так и PRESENT.

Возможное применение

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

Алгоритм

Halka состоит из 24 раундов. Ниже приведён алгоритм шифраШаблон:Sfn.

Обозначим в $i$-м раунде состояние 64-битного блока как $V_i=(v_0^i...v_{63}^i)$ и раундовый ключ, т.е. ключ, используемый в одном раунде и получаемый из первоначального ключа, как $K_i=(k_0^i...k_{63}^i)$.

1. На вход принимаются значение ключа $K$ и незашифрованный текст $P$.
2. Значение блока $V_1$ в первом раунде равняется $P$.
3. Генерируются раундовые ключи на основе ключа $K$.
4. Далее циклически для 24 раундов выполняются:
   1. Трансформация при шифровании, при которой к состоянию $V_i$ применяется XOR с раундовым ключом $K_i$,
   2. AES-подобное нелинейное преобразование (S-блок), построение которого состоит из взятия мультипликативной инверсии с использованием LFSR в поле Галуа $GF(2^8)$, причем предварительно $V_i$ разделяется на восемь равных 8-битных частей, над которыми и производятся данные операции, после чего результаты конкатенируются.
   3. Перестановка битов в блоке $V_i$ случайным образом, однако с условием, что все биты одной 8-битной части текущего блока $V_i$ переходят в биты различных 8-битных частей блока следующего уровня.
5. Цикл завершается.
6. Выполняется последняя операция XOR для $V_{25}$ и $K_{25}$.

Мультипликативная инверсия с использованием LFSR

Главной особенностью Halka является реализация мультипликативного инвертирования для нелинейного преобразования (S-блок) с использованием LFSR, использующего в качестве функции обратной связи примитивный многочлен $x^8+x^4+x^3+x^2+1$ и требующего на 8-битный S-блок всего 138 логических элементов. В то время как для ранее известных реализаций требуется не менее 253Шаблон:SfnШаблон:Sfn. Реализация шифра Halka малоресурсна, но несмотря на это, она удобна в использовании по отношению к программному обеспечениюШаблон:Sfn.

В данном разделе описывается вычисление мультипликативной инверсии при помощи регистра сдвига с обратной связью (LFSR)Шаблон:Sfn.

Математическое описание

Преобразование LFSR для $m$ циклов может быть записано какШаблон:Sfn:

$W(t+m)=A^m\cdot W(t)$, где $A$ — матрица преобразования LFSR, $W(t)$ — состояние LFSR в $t$-й отсчёт времени или начальное состояние, а $W(t+m)$ — состояние LFSR в $(t+m)$-й отсчёт времени, то есть после запуска $m$ тактовых циклов.

Так как в качестве функции обратной связи используется примитивный многочлен, LFSR будет генерировать последовательность с максимальным периодом. Поэтому если $n$ — длина LFSR, то выполнение $2^n-1$ циклов возвращает начальное состояние, при этом все промежуточные значения будут различными:

$\mathrm{\forall }t:W(t+2^n-1)=A^{2^n-1}\cdot W(t)=W(t)\Rightarrow A^{2^n-1}=E$.

Для вычисления мультипликативной инверсии заданного входного вектора $W(t+m)$ необходимо определить новое состояние LFSR $W(t+m^{\prime })$ такое, что $m+m^{\prime }=2^n-1$:

$W(t+m+m^{\prime })=W(t+2^n-1)=W(t)$, что равносильно $A^m\cdot A^{m^{\prime }}=A^{2^n-1}$.

Для 8-битного LFSR это означает следующее:

$W(t+m^{\prime })=W(t+255-m)$

Последнее равенство используется в реализации алгоритма мультипликативной инверсии с использованием LFSRШаблон:Sfn. Произвольный выбор начального состояния $W(t)$ позволяет не выделять аффинное преобразование после взятия мультипликативной инверсии в отдельный шаг, как это сделано в AES, так как $W(t+m^{\prime })$ уже является результатом применения к мультипликативной инверсии $W(t+m)$ некоторого преобразования, однозначно определяемого по $W(t)$. Такой подход позволяет избежать трудоёмких операций вроде матричного умножения. При этом выбор конкретного начального значения не оказывает существенного влияния на криптографические свойства шифраШаблон:Sfn.

Реализуемый алгоритм

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

1. Имеются: 8-битный LFSR, начальное состояние initial_seed = $W(t)$ и первоначальный S-box_input = $W(t+m)$.
2. Преобразование LFSR инициализируется как lfsr_state = S-box_input = $W(t+m)$.
3. Преобразование LFSR запускается до тех пор, пока не будет выполнено равенство: lfsr_state = initial_seed = $W(t)$.
4. Затем запускается обратное преобразование LFSR до тех пор, пока не будет совершенно в сумме 255 преобразований (то есть если прямое преобразование было выполнено $k$ раз, то обратное $255-k$ раз).
5. На выходе принимается lfsr_state = $W(t+m^{\prime })$.

Данный алгоритм даёт на выходе мультипликативную инверсию входного 8-битного блока S-box_input Шаблон:Sfn.

Аппаратная реализация

Аппаратная реализация осуществляется следующим образомШаблон:Sfn:

1. Конструируется LFSR из восьми триггеров с двумя входами (например, D-триггеры).
2. Конструируются необходимые логические элементы, обеспечивающие на входе LFSR функцию обратной связи.
3. Конструируется логическая схема, подключающаяся ко входам триггеров, обеспечивающая обратное преобразование LFSR для того же примитивного многочлена.
4. Выход LFSR подключается к 8-входному вентилю NAND (через несколько вентилей NOT), выход которого подключён ко входам триггеров так, чтобы организовать логику управления LFSR в обратном направлении.
5. Используется 8-битный счётчик LFSR. Выходной сигнал счётчика подключается к 8-входному вентилю NAND (через несколько вентилей NOT), чтобы сигнализировать о завершении 255 циклов. Конечное состояние LFSR содержит мультипликативную инверсию поданного начального значения.

Криптоанализ

Дифференциальный и линейный криптоанализ

Для 8-битных S-блоков, используемых в Halka, вероятность дифференциальной характеристики составляет $2^{-6}$Шаблон:Sfn. За раунд дифференциальная вероятность равняется $(2^{-6}{)}^2=2^{-12}$ Шаблон:Sfn. После 24 раундов общая вероятность любой дифференциальной характеристики составит $(2^{-12}{)}^{24}=2^{-228}$Шаблон:Sfn. Также существуют исследования, которые доказывают, что шифр Halka не так устойчив к дифференциальному анализу, как утверждает автор шифраШаблон:Sfn.

Линейное смещение мультипликативной инверсии равно $2^{-4}$. Тогда полное линейное смещение Halka составит после 24 раундов $((2^{-4}{)}^2{)}^{24}=2^{-192}$Шаблон:Sfn.

Алгебраическая атака

Для Halka не требуется анализ против алгебраических атак, потому что AES-подобное нелинейное преобразование(S-блок) не может быть описано квадратными уравнениямиШаблон:Sfn.

Анализ на связанных ключах и сдвиговая атака

Нет никаких доказательств того, что алгоритм планирования ключей PRESENT, используемый в Halka, может быть подвержен атаке на связанных ключах и сдвиговой атаке. Кроме того, 8-битный S-блок, используемый в Halka, усиливает данный алгоритм развёртывания ключейШаблон:Sfn.

Кубическая атака

Так как AES невосприимчив к Шаблон:Не переведено 5, то и Halka устойчив к подобным атакамШаблон:Sfn.

Структурные атаки

В силу побитовой перестановки Halka получение словоподобных структур, используемых в интегральных и коллизионных атаках, невозможно, что делает его невосприимчивым к подобным атакамШаблон:Sfn.

Литература

Книги

• Шаблон:Книга

Статьи

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья

Ссылки

• Облегчённая криптографияШаблон:Ref-en