Hamsi (Hamsi)
Hamsi — криптографическая хеш-функция, в основу которой положены алгоритмы Grindahl[1] и Serpent[2]. Эта хеш-функция не запатентована и является общественным достоянием. Существуют две разновидности алгоритма: Hamsi-256 и Hamsi-512. В основе алгоритма лежат функция разложения и циклическая трансформация. Циклическая трансформация работает с четырьмя строками матрицы состояний. Число столбцов этой матрицы равно 4 для Hamsi-256, 8 для Hamsi-512. Элементами матрицы являются слова размером 32 бита.
История
[править | править код]Hamsi была одним из участников в открытом конкурсе[3] SHA-3 Национального института стандартов и технологий[4] по разработке новых криптографических хеш-функций, которые преобразуют сообщения переменной длины в сжатые текстовые строки фиксированной длины, что может быть использовано для электронно-цифровых подписей, аутентификации сообщений и других применений. В первом раунде соревнования приняли участие 51 кандидат. 14 из них (включая Hamsi) прошли во второй тур[5]. Однако Hamsi не попала в число 5 кандидатов последнего тура, объявленных 10 декабря 2010 года[6].
Описание
[править | править код]Общая структура
[править | править код]Hamsi использует такие преобразования, как конкатенация (англ. Concatenation), перестановка (англ. Permutation) и округление (англ. Truncation), которые также используются в других алгоритмах хеширования, например Snefru[7] и Grindahl. В алгоритме также применяется функции расширения текста сообщения (англ. Message expansion) и распространения связывающего значения (англ. Chaining value) на каждой итерации. Для нелинейных перестановок (англ. Non-linear Permitations) используются линейные преобразования и один S-box из блочного шифрования Serpent. Общую структуру Hamsi можно представить в виде:
1 | Message Expansion | E : {0, 1} → {0, 1} |
2 | Concatenation | C : {0, 1} x {0, 1} → {0, 1} |
3 | Non-linear Permutations | P,P : {0, 1} → {0, 1} |
4 | Truncation | T : {0, 1} → {0, 1} |
Обозначения:
F | Конечное поле из n элементов |
<<< | Циклический сдвиг влево |
Исключающее ИЛИ (XOR) | |
<< | Битовый сдвиг влево |
[n, m, d] | Код длины n, размерностью m и минимальным расстоянием d |
Значения m, n и s для различных вариантов Hamsi представлены в следующей таблице:
m | n | s | |
Hamsi-256 | 32 | 256 | 512 |
Hamsi-512 | 64 | 512 | 1024 |
Пусть (M1||M2||M3|| . . . ||M||) уже дополненное сообщение, тогда разновидности Hamsi могут быть описаны следующим образом:
Hamsi-256:
h = (T ◦ P ◦ C(E(M), h−1)) ⊕ h−1, h = v256, 0 < <
h = (T ◦ P ◦ C(E(M), h−1)) ⊕ h−1
Hamsi-512:
h = (T ◦ P ◦ C(E(M), h−1)) ⊕ h−1, h = v512, 0 < <
h = (T ◦ P ◦ C(E(M), h−1)) ⊕ h−1
Начальные значения
[править | править код]Начальным значением для алгоритма является начальное значение связывающего значения h. Оно получено с помощью кодировки UTF-8 следующего сообщения: «Ozgul Kucuk, Katholieke Universiteit Leuven, Departement Elektrotechniek, Computer Security and Industrial Cryptography, Kasteelpark Arenberg 10, bus 2446, B-3001 Leuven-Heverlee, Belgium.» Начальные значения для различных разновидностей алгоритма представлены в следующей таблице:
v256 |
| ||||
v512 |
|
Дополнение сообщения
[править | править код]Hamsi оперирует с блоками сообщений длиной 32 и 64 бита для алгоритмов Hamsi-256 и Hamsi-512 соответственно. Если длина блока меньше чем необходимо, тогда происходит дополнение сообщения (англ. Message padding). Дополнение происходит следующим образом. К сообщению справа добавляется один бит значением '1', а затем добавляются биты со значениями равными '0' до тех пор пока длина сообщения не станет равной 32 или 64. Пример:
Есть сообщение длиной 24 бита
1010 0110 1110 1111 1111 0000 |
После дополнения до 32-х битного оно будет выглядеть так
1010 0110 1110 1111 1111 0000 | 1000 0000 |
Расширение сообщения
[править | править код]Hamsi использует линейные коды[8] для расширения сообщений. Для Hamsi-256 расширение сообщения длиной 32 бита в сообщение длиной 256 бит производится с помощью кода [128, 16, 70] над полем F[9]. Для Hamsi-512 расширение сообщения длиной 64 бита в сообщение длиной 512 бит производится с помощью кода [256, 32, 131] над полем F.
Конкатенация
[править | править код]К словам расширенного сообщения (m,m, . . . ,m) приписывается связывающее значение (c, c, . . . , c). Значения i и j равны 7 для Hamsi-256 и 15 для Hamsi-512. Затем над полученным сообщением будет произведена нелинейная перестановка P. Метод конкатенации определяет порядок следования битов на входе Р.
В Hamsi-256
C: {0, 1}x{0, 1} → {0, 1}, а подробнее
C(m,m1, . . . ,m7, c0, c1, . . . , c7) = (m0,m1, c0, c1, c2, c3,m2,m3,m4, m5, c4, c5, c6, c7,m6,m7)
Порядок слов легче всего запомнить с помощью следующей таблицы, результат из которой можно получить построчным считыванием:
m0 | m1 | c0 | c1 |
c2 | c3 | m2 | m3 |
m4 | m5 | c4 | c5 |
c6 | c7 | m6 | m7 |
В Hamsi-512
C: {0, 1} × {0, 1} → {0, 1}, а подробнее
C(m0,m1, . . . ,m14,m15, c0, c1, . . . , c14, c15) = (m0,m1, c0, c1,m2,m3, c2, c3, c4, c5,m4,m5, c6, c7,m6,m7,m8, m9, c8, c9,m10,m11, c10, c11, c12, c13,m12,m13, c14, c15,m14,m15)
Нелинейная перестановка P
[править | править код]Нелинейная перестановка состоит из трех этапов
- Над входными битами, константами и счетчиком выполняется операция XOR
- Затем следует применение 4-битных S-боксов
- И наконец несколько применений линейного преобразования L
Все это повторяется столько раз, сколько задано количество циклов. На вход каждый раз поступает сообщение (s0, s1, s2, . . . , sj), где j равно 15 для Hamsi-256 и 31 для Hamsi-512.
1) Прибавление констант и счетчика
[править | править код]На этом этапе над входным сообщением, константами и счетчиком выполняется операция XOR. Счетчик определяет номер выполненного цикла. Для первого цикла c равен 0, для второго с = 1 и так далее. Используемые константы приведены в следующей таблице:
α0 = 0xff00f0f0 | α1 = 0xccccaaaa | α2 = 0xf0f0cccc | α3 = 0xff00aaaa |
α4 = 0xccccaaaa | α5 = 0xf0f0ff00 | α6 = 0xaaaacccc | α7 = 0xf0f0ff00 |
α8 = 0xf0f0cccc | α9 = 0xaaaaff00 | α10 = 0xccccff00 | α11 = 0xaaaaf0f0 |
α12 = 0xaaaaf0f0 | α13 = 0xff00cccc | α14 = 0xccccf0f0 | α15 = 0xff00aaaa |
α16 = 0xccccaaaa | α17 = 0xff00f0f0 | α18 = 0xff00aaaa | α19 = 0xf0f0cccc |
α20 = 0xf0f0ff00 | α21 = 0xccccaaaa | α22 = 0xf0f0ff00 | α23 = 0xaaaacccc |
α24 = 0xaaaaff00 | α25 = 0xf0f0cccc | α26 = 0xaaaaf0f0 | α27 = 0xccccff00 |
α28 = 0xff00cccc | α29 = 0xaaaaf0f0 | α30 = 0xff00aaaa | α31 = 0xccccf0f0 |
В Hamsi-256
(s0, s1, . . . , s15) := (s0 ⊕ α0, s1 ⊕ α1 ⊕ c, s2, . . . , s15 ⊕ α15)
В Hamsi-512
(s0, s1, . . . , s31) := (s0 ⊕ α0, s1 ⊕ α1 ⊕ c, s2, . . . , s31 ⊕ α31)
2) Этап подстановки
[править | править код]На этом этапе происходит подстановка 4-битных S-боксов, взятых из алгоритма Serpent. Hamsi очень удобно спроектирован для параллельного вычисления. Все 128 идентичных S-боксов (256 для Hamsi-512) могут обсчитываться в одно и то же время, что ускоряет работу алгоритма. S-box используемый в Hamsi:
x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
s[x] | 8 | 6 | 7 | 9 | 3 | C | A | F | D | 1 | E | 4 | 0 | B | 5 | 2 |
3) Этап преобразования
[править | править код]Этап преобразования основан на нескольких применениях линейного преобразования L: {0, 1} → {0, 1}. L оперирует с 32-битными словами. В общем виде преобразование можно записать в виде (si, sj, sk, sl) := L(si, sj, sk, sl).
Более подробное описание преобразования L(a, b, c, d):
a := a <<< 13
c := c <<< 3
b := b ⊕ a ⊕ c
d := d ⊕ c ⊕ (a << 3)
b := b <<< 1
d := d <<< 7
a := a ⊕ b ⊕ d
c := c ⊕ d ⊕ (b << 7)
a := a <<< 5
c := c <<< 22
Округление
[править | править код]Округление T : {0, 1}512 → {0, 1}256 в Hamsi-256 определяется следующим образом:
T (s0, s1, s2, . . . , s14, s15) = (s0, s1, s2, s3, s8, s9, s10, s11)
В Hamsi-512 округление T : {0, 1}1024 → {0, 1}512 определяется так:
T (s0, s1, s2, . . . , s30, s31) = (s0, s1, s2, s3, s4, s5, s6, s7, s16, s17, s18, s19, s20, s21, s22, s23)
Округление осуществляется после финального цикла нелинейной перестановки.
Нелинейная перестановка Pf
[править | править код]Нелинейные перестановки P и Pf отличаются только константами. Также Pf применяется только к последнему блоку сообщений как финальное преобразование.
Константы для Pf:
α0 = 0xcaf9639c | α1 = 0x0ff0f9c0 | α2 = 0x639c0ff0 | α3 = 0xcaf9f9c0 |
α4 = 0x0ff0f9c0 | α5 = 0x639ccaf9 | α6 = 0xf9c00ff0 | α7 = 0x639ccaf9 |
α8 = 0x639c0ff0 | α9 = 0xf9c0caf9 | α10 = 0x0ff0caf9 | α11 = 0xf9c0639c |
α12 = 0xf9c0639c | α13 = 0xcaf90ff0 | α14 = 0x0ff0639c | α15 = 0xcaf9f9c0 |
α16 = 0x0ff0f9c0 | α17 = 0xcaf9639c | α18 = 0xcaf9f9c0 | α19 = 0x639c0ff0 |
α20 = 0x639ccaf9 | α21 = 0x0ff0f9c0 | α22 = 0x639ccaf9 | α23 = 0xf9c00ff0 |
α24 = 0xf9c0caf9 | α25 = 0x639c0ff0 | α26 = 0xf9c0639c | α27 = 0x0ff0caf9 |
α28 = 0xcaf90ff0 | α29 = 0xf9c0639c | α30 = 0xcaf9f9c0 | α31 = 0x0ff0639c |
Количество циклов
[править | править код]Количество циклов для различных вариантов Hamsi приведены в таблице:
Hamsi-256 | Hamsi-512 | |
P циклов | 3 | 6 |
Pf циклов | 6 | 12 |
Во втором туре соревнования SHA-3 появилась новая модификация алгоритма под названием Hamsi-256/8. Её отличие от Hamsi-256 в том, что количество Pf циклов теперь равно 8.
Примечания
[править | править код]- ↑ L. R. Knudsen, C. Rechberger, S. S. Thomsen. Grindahl — a family of hash functions (неопр.) // Lecture Notes in Computer Science. — 2007. — Т. 4593. — С. 39—57. — doi:10.1007/978-3-540-74619-5_3. Архивировано 15 сентября 2012 года.
- ↑ Serpent: A proposal for the advanced encryption standard Архивная копия от 13 января 2013 на Wayback Machine.
- ↑ NIST.gov — Computer Security Division — Computer Security Resource Center . Дата обращения: 28 ноября 2009. Архивировано 9 июля 2011 года.
- ↑ National Institute of Standards and Technology . Дата обращения: 28 ноября 2009. Архивировано 17 июня 2015 года.
- ↑ NIST.gov — Computer Security Division — Computer Security Resource Center . Дата обращения: 28 ноября 2009. Архивировано 10 апреля 2012 года.
- ↑ Status Report on the Second Round of the SHA-3 . Дата обращения: 15 июня 2015. Архивировано 14 марта 2011 года.
- ↑ Merkle R.C. A Fast Software One-Way Hash Function. Journal of Cryptology, 3(1):43-58, 1990
- ↑ J.H. van Lint. Introduction to Coding Theory
- ↑ Bounds on the minimum distance of linear codes. http://codetables.de.BKLC/ (недоступная ссылка)
Литература
[править | править код]- Özgül Kücük. The Hash Function Hamsi (PDF) (31 октября 2008). Дата обращения: 11 декабря 2008. Архивировано 11 апреля 2012 года.
- https://web.archive.org/web/20100825061836/http://homes.esat.kuleuven.be/~okucuk/hamsi/index.html
- http://www.cosic.esat.kuleuven.be/publications/article-1203.pdf