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} $^{m}$ → {0, 1} $^{n}$
2	Concatenation	C : {0, 1} $^{n}$ x {0, 1} $^{n}$ → {0, 1} $^{s}$
3	Non-linear Permutations	P,P $_{f}$ : {0, 1} $^{s}$ → {0, 1} $^{s}$
4	Truncation	T : {0, 1} $^{s}$ → {0, 1} $^{n}$

Обозначения:

F $_{n}$	Конечное поле из n элементов
<<<	Циклический сдвиг влево
$\oplus$	Исключающее ИЛИ (XOR)
<<	Битовый сдвиг влево
[n, m, d]	Код длины n, размерностью m и минимальным расстоянием d

Значения m, n и s для различных вариантов Hamsi представлены в следующей таблице:

	m	n	s
Hamsi-256	32	256	512
Hamsi-512	64	512	1024

Пусть (M₁||M₂||M₃|| . . . ||M $_{\ell }$ ||) уже дополненное сообщение, тогда разновидности Hamsi могут быть описаны следующим образом:

Hamsi-256:

h $_{i}$ = (T ◦ P ◦ C(E(M $_{i}$ ), h $_{i}$ −1)) ⊕ h $_{i}$ −1, h $_{0}$ = $i$ v₂₅₆, 0 < $i$ < $\ell$

h = (T ◦ P $_{f}$ ◦ C(E(M $_{\ell }$ ), h $_{\ell }$ −1)) ⊕ h $_{\ell }$ −1

Hamsi-512:

h $_{i}$ = (T ◦ P ◦ C(E(M $_{i}$ ), h $_{i}$ −1)) ⊕ h $_{i}$ −1, h $_{0}$ = $i$ v₅₁₂, 0 < $i$ < $\ell$

h = (T ◦ P $_{f}$ ◦ C(E(M $_{\ell }$ ), h $_{\ell }$ −1)) ⊕ h $_{\ell }$ −1

Начальные значения править

Начальным значением для алгоритма является начальное значение связывающего значения h $_{0}$ . Оно получено с помощью кодировки UTF-8 следующего сообщения: «Ozgul Kucuk, Katholieke Universiteit Leuven, Departement Elektrotechniek, Computer Security and Industrial Cryptography, Kasteelpark Arenberg 10, bus 2446, B-3001 Leuven-Heverlee, Belgium.» Начальные значения для различных разновидностей алгоритма представлены в следующей таблице:

i

v₂₅₆

0x76657273, 0x69746569, 0x74204c65, 0x7576656e

0x2c204b61, 0x74686f6c, 0x69656b65, 0x20556e69

i

v₅₁₂

0x73746565, 0x6c706172, 0x6b204172, 0x656e6265

0x72672031, 0x302c2062, 0x75732032, 0x3434362c

0x20422d33, 0x30303120, 0x4c657576, 0x656e2d48

0x65766572, 0x6c65652c, 0x2042656c, 0x6769756d

Дополнение сообщения править

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 $_{4}$ ^[9]. Для Hamsi-512 расширение сообщения длиной 64 бита в сообщение длиной 512 бит производится с помощью кода [256, 32, 131] над полем F $_{4}$ .

Конкатенация править

К словам расширенного сообщения (m $_{0}$ ,m $_{1}$ , . . . ,m $_{i}$ ) приписывается связывающее значение (c $_{0}$ , c $_{1}$ , . . . , c $_{j}$ ). Значения i и j равны 7 для Hamsi-256 и 15 для Hamsi-512. Затем над полученным сообщением будет произведена нелинейная перестановка P. Метод конкатенации определяет порядок следования битов на входе Р.

В Hamsi-256

C: {0, 1} $^{256}$ x{0, 1} $^{256}$ → {0, 1} $^{512}$ , а подробнее

C(m $_{0}$ ,m₁, . . . ,m₇, c₀, c₁, . . . , c₇) = (m₀,m₁, c₀, c₁, c₂, c₃,m₂,m₃,m₄, m₅, c₄, c₅, c₆, c₇,m₆,m₇)

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

m₀	m₁	c₀	c₁
c₂	c₃	m₂	m₃
m₄	m₅	c₄	c₅
c₆	c₇	m₆	m₇

В Hamsi-512

C: {0, 1} $^{512}$ × {0, 1} $^{512}$ → {0, 1} $^{1024}$ , а подробнее

C(m₀,m₁, . . . ,m₁₄,m₁₅, c₀, c₁, . . . , c₁₄, c₁₅) = (m₀,m₁, c₀, c₁,m₂,m₃, c₂, c₃, c₄, c₅,m₄,m₅, c₆, c₇,m₆,m₇,m₈, m₉, c₈, c₉,m₁₀,m₁₁, c₁₀, c₁₁, c₁₂, c₁₃,m₁₂,m₁₃, c₁₄, c₁₅,m₁₄,m₁₅)

Нелинейная перестановка P править

Нелинейная перестановка состоит из трех этапов

Над входными битами, константами и счетчиком выполняется операция XOR
Затем следует применение 4-битных S-боксов
И наконец несколько применений линейного преобразования L

Все это повторяется столько раз, сколько задано количество циклов. На вход каждый раз поступает сообщение (s₀, s₁, s₂, . . . , s_j), где j равно 15 для Hamsi-256 и 31 для Hamsi-512.

1) Прибавление констант и счетчика править

На этом этапе над входным сообщением, константами и счетчиком выполняется операция XOR. Счетчик определяет номер выполненного цикла. Для первого цикла c равен 0, для второго с = 1 и так далее. Используемые константы приведены в следующей таблице:

α₀ = 0xff00f0f0	α₁ = 0xccccaaaa	α₂ = 0xf0f0cccc	α₃ = 0xff00aaaa
α₄ = 0xccccaaaa	α₅ = 0xf0f0ff00	α₆ = 0xaaaacccc	α₇ = 0xf0f0ff00
α₈ = 0xf0f0cccc	α₉ = 0xaaaaff00	α₁₀ = 0xccccff00	α₁₁ = 0xaaaaf0f0
α₁₂ = 0xaaaaf0f0	α₁₃ = 0xff00cccc	α₁₄ = 0xccccf0f0	α₁₅ = 0xff00aaaa
α₁₆ = 0xccccaaaa	α₁₇ = 0xff00f0f0	α₁₈ = 0xff00aaaa	α₁₉ = 0xf0f0cccc
α₂₀ = 0xf0f0ff00	α₂₁ = 0xccccaaaa	α₂₂ = 0xf0f0ff00	α₂₃ = 0xaaaacccc
α₂₄ = 0xaaaaff00	α₂₅ = 0xf0f0cccc	α₂₆ = 0xaaaaf0f0	α₂₇ = 0xccccff00
α₂₈ = 0xff00cccc	α₂₉ = 0xaaaaf0f0	α₃₀ = 0xff00aaaa	α₃₁ = 0xccccf0f0

В Hamsi-256

(s₀, s₁, . . . , s₁₅) := (s₀ ⊕ α₀, s₁ ⊕ α₁ ⊕ c, s₂, . . . , s₁₅ ⊕ α₁₅)

В Hamsi-512

(s₀, s₁, . . . , s₃₁) := (s₀ ⊕ α₀, s₁ ⊕ α₁ ⊕ c, s₂, . . . , s₃₁ ⊕ α₃₁)

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} $^{128}$ → {0, 1} $^{128}$ . L оперирует с 32-битными словами. В общем виде преобразование можно записать в виде (s_i, s_j, s_k, s_l) := L(s_i, s_j, s_k, s_l).

Более подробное описание преобразования 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}⁵¹² → {0, 1}²⁵⁶ в Hamsi-256 определяется следующим образом:

T (s₀, s₁, s₂, . . . , s₁₄, s₁₅) = (s₀, s₁, s₂, s₃, s₈, s₉, s₁₀, s₁₁)

В Hamsi-512 округление T : {0, 1}¹⁰²⁴ → {0, 1}⁵¹² определяется так:

T (s₀, s₁, s₂, . . . , s₃₀, s₃₁) = (s₀, s₁, s₂, s₃, s₄, s₅, s₆, s₇, s₁₆, s₁₇, s₁₈, s₁₉, s₂₀, s₂₁, s₂₂, s₂₃)

Округление осуществляется после финального цикла нелинейной перестановки.

Нелинейная перестановка P_f править

Нелинейные перестановки P и P_f отличаются только константами. Также P_f применяется только к последнему блоку сообщений как финальное преобразование.

Константы для P_f:

α₀ = 0xcaf9639c	α₁ = 0x0ff0f9c0	α₂ = 0x639c0ff0	α₃ = 0xcaf9f9c0
α₄ = 0x0ff0f9c0	α₅ = 0x639ccaf9	α₆ = 0xf9c00ff0	α₇ = 0x639ccaf9
α₈ = 0x639c0ff0	α₉ = 0xf9c0caf9	α₁₀ = 0x0ff0caf9	α₁₁ = 0xf9c0639c
α₁₂ = 0xf9c0639c	α₁₃ = 0xcaf90ff0	α₁₄ = 0x0ff0639c	α₁₅ = 0xcaf9f9c0
α₁₆ = 0x0ff0f9c0	α₁₇ = 0xcaf9639c	α₁₈ = 0xcaf9f9c0	α₁₉ = 0x639c0ff0
α₂₀ = 0x639ccaf9	α₂₁ = 0x0ff0f9c0	α₂₂ = 0x639ccaf9	α₂₃ = 0xf9c00ff0
α₂₄ = 0xf9c0caf9	α₂₅ = 0x639c0ff0	α₂₆ = 0xf9c0639c	α₂₇ = 0x0ff0caf9
α₂₈ = 0xcaf90ff0	α₂₉ = 0xf9c0639c	α₃₀ = 0xcaf9f9c0	α₃₁ = 0x0ff0639c

Количество циклов править

Количество циклов для различных вариантов Hamsi приведены в таблице:

	Hamsi-256	Hamsi-512
P циклов	3	6
P_f циклов	6	12

Во втором туре соревнования SHA-3 появилась новая модификация алгоритма под названием Hamsi-256/8. Её отличие от Hamsi-256 в том, что количество P_f циклов теперь равно 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

[1] 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 года.

[2] Serpent: A proposal for the advanced encryption standard Архивная копия от 13 января 2013 на Wayback Machine.

[3] NIST.gov — Computer Security Division — Computer Security Resource Center (неопр.). Дата обращения: 28 ноября 2009. Архивировано 9 июля 2011 года.

[4] National Institute of Standards and Technology (неопр.). Дата обращения: 28 ноября 2009. Архивировано 17 июня 2015 года.

[5] NIST.gov — Computer Security Division — Computer Security Resource Center (неопр.). Дата обращения: 28 ноября 2009. Архивировано 10 апреля 2012 года.

[Status_Report_on_the_Second_Round_of_the_SHA-3-6] Status Report on the Second Round of the SHA-3 (неопр.). Дата обращения: 15 июня 2015. Архивировано 14 марта 2011 года.

[7] Merkle R.C. A Fast Software One-Way Hash Function. Journal of Cryptology, 3(1):43-58, 1990

[8] J.H. van Lint. Introduction to Coding Theory

[9] Bounds on the minimum distance of linear codes. http://codetables.de.BKLC/ (недоступная ссылка)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]