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
0x76657273, 0x69746569, 0x74204c65, 0x7576656e
0x2c204b61, 0x74686f6c, 0x69656b65, 0x20556e69
v512
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[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.

Примечания[править | править код]

  1. L. R. Knudsen, C. Rechberger, S. S. Thomsen (2007). «Grindahl — a family of hash functions». Lecture Notes in Computer Science 4593: 39-57. DOI:10.1007/978-3-540-74619-5_3.
  2. Serpent: A proposal for the advanced encryption standard.
  3. NIST.gov — Computer Security Division — Computer Security Resource Center
  4. National Institute of Standards and Technology
  5. NIST.gov — Computer Security Division — Computer Security Resource Center
  6. Status Report on the Second Round of the SHA-3
  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/

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