Hamsi — криптографическая хеш-функция , в основу которой положены алгоритмы и Serpent . Эта хеш-функция не запатентована и является общественным достоянием . Существуют две разновидности алгоритма : Hamsi-256 и Hamsi-512. В основе алгоритма лежат функция разложения и циклическая трансформация . Циклическая трансформация работает с четырьмя строками матрицы состояний. Число столбцов этой матрицы равно 4 для Hamsi-256, 8 для Hamsi-512. Элементами матрицы являются слова размером 32 бита .

История

Hamsi была одним из участников в открытом конкурсе SHA-3 Национального института стандартов и технологий по разработке новых криптографических хеш-функций , которые преобразуют сообщения переменной длины в сжатые текстовые строки фиксированной длины, что может быть использовано для электронно-цифровых подписей , аутентификации сообщений и других применений. В первом раунде соревнования приняли участие 51 кандидат. 14 из них (включая Hamsi) прошли во второй тур . Однако Hamsi не попала в число 5 кандидатов последнего тура, объявленных 10 декабря 2010 года .

Описание

Общая структура

Hamsi использует такие преобразования, как конкатенация ( англ. Concatenation ), перестановка ( англ. Permutation ) и округление ( англ. Truncation ), которые также используются в других алгоритмах хеширования , например Snefru и . В алгоритме также применяется функции расширения текста сообщения ( англ. Message expansion ) и распространения связывающего значения ( англ. Chaining value ) на каждой итерации . Для нелинейных перестановок ( англ. Non-linear Permitations ) используются линейные преобразования и один S-box из блочного шифрования Serpent . Общую структуру Hamsi можно представить в виде:

1	Message Expansion	E : {0, 1} ${\displaystyle ^{m}}$ → {0, 1} ${\displaystyle ^{n}}$
2	Concatenation	C : {0, 1} ${\displaystyle ^{n}}$ x {0, 1} ${\displaystyle ^{n}}$ → {0, 1} ${\displaystyle ^{s}}$
3	Non-linear Permutations	P,P ${\displaystyle _{f}}$ : {0, 1} ${\displaystyle ^{s}}$ → {0, 1} ${\displaystyle ^{s}}$
4	Truncation	T : {0, 1} ${\displaystyle ^{s}}$ → {0, 1} ${\displaystyle ^{n}}$

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

F ${\displaystyle _{n}}$	Конечное поле из n элементов
<<<	Циклический сдвиг влево
${\displaystyle \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 ${\displaystyle _{\ell }}$ ||) уже дополненное сообщение, тогда разновидности Hamsi могут быть описаны следующим образом:

Hamsi-256:

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

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

Hamsi-512:

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

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

Начальные значения

Начальным значением для алгоритма является начальное значение связывающего значения h ${\displaystyle _{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.» Начальные значения для различных разновидностей алгоритма представлены в следующей таблице:

${\displaystyle i}$ v 256	0x76657273, 0x69746569, 0x74204c65, 0x7576656e 0x2c204b61, 0x74686f6c, 0x69656b65, 0x20556e69
${\displaystyle i}$ v 512	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 использует линейные коды для расширения сообщений. Для Hamsi-256 расширение сообщения длиной 32 бита в сообщение длиной 256 бит производится с помощью кода [128, 16, 70] над полем F ${\displaystyle _{4}}$ . Для Hamsi-512 расширение сообщения длиной 64 бита в сообщение длиной 512 бит производится с помощью кода [256, 32, 131] над полем F ${\displaystyle _{4}}$ .

Конкатенация

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

В Hamsi-256

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

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

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

m 0	m 1	c 0	c 1
c 2	c 3	m 2	m 3
m 4	m 5	c 4	c 5
c 6	c 7	m 6	m 7

В Hamsi-512

C: {0, 1} ${\displaystyle ^{512}}$ × {0, 1} ${\displaystyle ^{512}}$ → {0, 1} ${\displaystyle ^{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 и так далее. Используемые константы приведены в следующей таблице:

α 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

(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} ${\displaystyle ^{128}}$ → {0, 1} ${\displaystyle ^{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 :

α 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
P f циклов	6	12

Во втором туре соревнования SHA-3 появилась новая модификация алгоритма под названием Hamsi-256/8. Её отличие от Hamsi-256 в том, что количество P _f циклов теперь равно 8.

Примечания

Литература

• Özgül Kücük. (неопр.) (PDF) (31 октября 2008). Дата обращения: 11 декабря 2008. 11 апреля 2012 года.