Halka (Halka)

Halka
Создатель	Сурав Дас
Создан	2014 год
Опубликован	2014 год
Размер ключа	80 бит
Размер блока	64 бит
Число раундов	24
Тип	SP-сеть

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

История

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

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

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

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

Алгоритм

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

Обозначим в $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. Реализация шифра Halka малоресурсна, но несмотря на это, она удобна в использовании по отношению к программному обеспечению.

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

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

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

$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$ циклов возвращает начальное состояние, при этом все промежуточные значения будут различными:

$\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')$ такое, что $m+m'=2^{n}-1$:

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

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

$W(t+m')=W(t+255-m)$

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

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

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

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')$.

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

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

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

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}$. За раунд дифференциальная вероятность равняется $(2^{-6})^{2}=2^{-12}$ . После 24 раундов общая вероятность любой дифференциальной характеристики составит $(2^{-12})^{24}=2^{-228}$. Также существуют исследования, которые доказывают, что шифр Halka не так устойчив к дифференциальному анализу, как утверждает автор шифра.

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

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

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

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

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

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

Так как AES невосприимчив к кубическим атакам, то и Halka устойчив к подобным атакам.

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

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

Ссылки

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