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 получение словоподобных структур, используемых винтегральныхиколлизионных атаках,невозможно, что делает его невосприимчивым к подобным атакам.

Ссылки

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