Halka

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

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

## Содержание

* 1 История
* 2 Возможное применение
* 3 Алгоритм
* 4 Мультипликативная инверсия с использованием LFSR
* 4.1 Математическое описание
* 4.2 Реализуемый алгоритм
* 4.3 Аппаратная реализация
* 5 Криптоанализ
* 5.1 Дифференциальный и линейный криптоанализ
* 5.2 Алгебраическая атака
* 5.3 Анализ на связанных ключах и сдвиговая атака
* 5.4 Кубическая атака
* 5.5 Структурные атаки
* 6 Примечания
* 7 Литература
* 8 Ссылки

## История

[править | править код]

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

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

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

[править | править код]

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

## Алгоритм

[править | править код]

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

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

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

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

[править | править код]

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

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

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

[править | править код]

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

W ( t + m ) = A m ⋅ W ( t ) {\displaystyle W(t+m)=A^{m}\cdot W(t)} ,

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

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

∀ t : W ( t + 2 n − 1 ) = A 2 n − 1 ⋅ W ( t ) = W ( t ) ⇒ A 2 n − 1 = E {\displaystyle \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 ) {\displaystyle W(t+m)} необходимо определить новое состояние LFSR  W ( t + m ′ ) {\displaystyle W(t+m')} такое, что  m + m ′ = 2 n − 1 {\displaystyle m+m'=2^{n}-1} :

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

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

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

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

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

[править | править код]

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

1. Имеются: 8-битный LFSR, начальное состояние initial_seed =  W ( t ) {\displaystyle W(t)} и первоначальный S-box_input =  W ( t + m ) {\displaystyle W(t+m)} .
2. Преобразование LFSR инициализируется как lfsr_state = S-box_input =  W ( t + m ) {\displaystyle W(t+m)} .
3. Преобразование LFSR запускается до тех пор, пока не будет выполнено равенство: lfsr_state = initial_seed =  W ( t ) {\displaystyle W(t)} .
4. Затем запускается обратное преобразование LFSR до тех пор, пока не будет совершенно в сумме 255 преобразований (то есть если прямое преобразование было выполнено  k {\displaystyle k} раз, то обратное  255 − k {\displaystyle 255-k} раз).
5. На выходе принимается lfsr_state =  W ( t + m ′ ) {\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, вероятность дифференциальной характеристики составляет  2 − 6 {\displaystyle 2^{-6}} [10]. За раунд дифференциальная вероятность равняется  ( 2 − 6 ) 2 = 2 − 12 {\displaystyle (2^{-6})^{2}=2^{-12}} [11]. После 24 раундов общая вероятность любой дифференциальной характеристики составит  ( 2 − 12 ) 24 = 2 − 228 {\displaystyle (2^{-12})^{24}=2^{-228}} [10]. Также существуют исследования, которые доказывают, что шифр Halka не так устойчив к дифференциальному анализу, как утверждает автор шифра[12].

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

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

[править | править код]

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

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

[править | править код]

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

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

[править | править код]

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

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

[править | править код]

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

## Примечания

[править | править код]

1. ↑ 1 2 R. Lidl, H. Niederreiter, 1994.
2. ↑ 1 2 Ultra-lightweight 8-bit Multiplicative Inverse Based S-box Using LFSR, 2014.
3. ↑ A. Bogdanov, 2007, p. 453—454.
4. ↑ Sourav Das, 2014.
5. ↑ 1 2 Sourav Das, 2014, p. 6.
6. ↑ D. Canright, 2005, p. 453.
7. ↑ 1 2 G. Hatzivasilis, 2017, p. 153.
8. ↑ 1 2 3 Ultra-lightweight 8-bit Multiplicative Inverse Based S-box Using LFSR, 2014, p. 2—3.
9. ↑ Ultra-lightweight 8-bit Multiplicative Inverse Based S-box Using LFSR, 2014, p. 4.
10. ↑ 1 2 3 Sourav Das, 2014, p. 8.
11. ↑ S. Hong , S. Lee, J. Lim, J. Sung, D. Cheon, I. Cho, 2001.
12. ↑ Shun, Yasutaka, Toshinobu, 2017.
13. ↑ 1 2 3 Sourav Das, 2014, p. 9.
14. ↑ Sourav Das, 2014, p. 9—10.

## Литература

[править | править код]

Книги

* R. Lidl, H. Niederreiter. Introduction to Finite Fields and Their Applications. — Revised Edition. — Cambridge: Cambridge University Press, 1994. — 416 с. — ISBN 0-521-46094-8.

Статьи

* Sourav Das. Halka: A Lightweight, Software Friendly Block Cipher Using Ultra-lightweight 8-bit S-box (англ.). — IACR Cryptology ePrint Archive, 2014. — Vol. 2014, no. 110. — P. 1—16.
* Sourav Das. Ultra-lightweight 8-bit Multiplicative Inverse Based S-box Using LFSR (англ.). — IACR Cryptology ePrint Archive, 2014. — Vol. 2014, no. 22. — P. 1—11. Архивировано 20 октября 2019 года.
* D. Canright. A Very Compact S-Box for AES (англ.) // Cryptographic Hardware and Embedded Systems. — Springer, Berlin, Heidelberg, 2005. — P. 441—455. — ISBN 978-3-540-28474-1. — doi:10.1007/11545262_32.
* George Hatzivasilis. A review of lightweight block ciphers (англ.) // Journal of Cryptographic Engineering. — Springer, Berlin, Heidelberg, 2017. — P. 141—184. — doi:10.1007/s13389-017-0160-y.
* A. Bogdanov, L. R. Knudsen, G. Leander, C. Paar, A. Poschmann, M. J. B. Robshaw, Y. Seurin, C. Vikkelsoe. PRESENT: An Ultra-Lightweight Block Cipher (англ.) // International workshop on cryptographic hardware and embedded systems. — Springer, Berlin, Heidelberg, 2007. — P. 450—466. — ISBN 978-3-540-74734-5. — doi:10.1007/978-3-540-74735-2_31.
* S. Hong , S. Lee, J. Lim, J. Sung, D. Cheon, I. Cho. Provable Security against Differential and Linear Cryptanalysis for the SPN Structure (англ.) // FSE 2000. Lecture Notes in Computer Science. — Springer, Berlin, Heidelberg, 2001. — Vol. 1978. — P. 273—283. — ISBN 978-3-540-44706-1. — doi:10.1007/3-540-44706-7_19.
* S. Hong , S. Lee, J. Lim, J. Sung, D. Cheon, I. Cho. Provable Security against Differential and Linear Cryptanalysis for the SPN Structure (англ.) // FSE 2000. Lecture Notes in Computer Science. — Springer, Berlin, Heidelberg, 2001. — Vol. 1978. — P. 273—283. — ISBN 978-3-540-44706-1. — doi:10.1007/3-540-44706-7_19.
* 中澤 俊, 五十嵐 保隆, 金子 敏信. 軽量型ブロック暗号 Halka の差分パス解析 (яп.) // Computer Security Symposium 2017. — the Information Processing Society of Japan, 2017. — 24 10月. — 第896—902 頁. — ISSN 1882-0840.

## Ссылки

[править | править код]

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

Симметричные криптосистемы

Потоковые шифры|

* A3
* A5
* A8
* Decim
* F-FCSR
* Grain
* HC-256
* KCipher-2
* MICKEY
* MUGI
* PIKE
* Phelix
* RC4
* Rabbit
* SEAL
* SNOW
* SOSEMANUK
* Salsa20
* STRUMOK
* Trivium
* VMPC

Сеть Фейстеля|

* ГОСТ 28147-89 (Магма)
* Blowfish
* Camellia
* CAST-128
* CAST-256
* CIPHERUNICORN-A
* CIPHERUNICORN-E
* CLEFIA
* Cobra
* DEAL
* DES
* DESX
* DFC
* E2
* EnRUPT
* FEAL
* HPC
* IDEA
* KASUMI
* Khafre
* Khufu
* LOKI97
* MacGuffin
* MARS
* MESH
* MISTY1
* NewDES
* NDS
* RC5
* RC6
* SEED
* Simon
* Sinople
* Skipjack
* SM4
* Speck
* TEA
* XTEA
* XXTEA
* Raiden
* RTEA
* Triple DES
* Twofish

SP-сеть|

* Кузнечик
* 3-WAY
* ABC
* ARIA
* AES (Rijndael)
* Akelarre
* Anubis
* BaseKing
* BassOmatic
* BelT
* CRYPTON
* Diamond2
* Grand Cru
* Hierocrypt-3
* Hierocrypt-L1
* KHAZAD
* Kalyna
* Lucifer
* Present
* Rainbow
* SAFER
* SHARK
* SQUARE
* Serpent
* Threefish

Другие|

* FROG
* NUSH
* REDOC
* SC2000
* SHACAL
* CS-Cipher

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

|