Halka

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

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

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

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

Halka состоит из 24 раундов. Ниже приведён алгоритм шифра^[5].

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

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

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

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

Преобразование LFSR для ${\displaystyle m}$ циклов может быть записано как^[8]:

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

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

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

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

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

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

${\displaystyle W(t+m')=W(t+255-m)}$

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

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

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

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

Аппаратная реализация осуществляется следующим образом^[9]:

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

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

Линейное смещение мультипликативной инверсии равно ${\displaystyle 2^{-4}}$. Тогда полное линейное смещение Halka составит после 24 раундов ${\displaystyle ((2^{-4})^{2})^{24}=2^{-192}}$^[10].

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

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

Так как AES невосприимчив к кубическим атакам^[англ.], то и Halka устойчив к подобным атакам^[14].

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

• Облегчённая криптография (англ.)

Эта статья входит в число добротных статей русскоязычного раздела Википедии.