- The Hash Function Hamsi
-
The Hash Function Hamsi
Содержание
Краткое описание
The Hash Funtion Hamsi — криптографическая хэш-функция, за основу которой взяты алгоритмы Grindahl[1] и Serpent[2]. Данная хэш-функция не запатентована и является общественным достоянием. Существуют две разновидности алгоритма: Hamsi-256 и Hamsi-512. В основе алгоритма лежат функция разложения и циклическая трансформация. Циклическая трансформация работает с четырьмя строками матрицы состояний. Число столбцов этой матрицы равно 4 для Hamsi-256, 8 для Hamsi-512. Элементами матрицы являются слова размером 32 бита.
История
В настоящее время Национальный институт стандартов и технологий[3] проводит открытый конкурс[4] по разработке новых криптографических хэш-функций, которые преобразуют сообщения переменной длины в сжатые текстовые строки фиксированной длины, что может быть использовано для электронно-цифровых подписей, аутентификации сообщений и других применений. Новый алгоритм хэширования будет назван «SHA-3». В первом раунде соревнования приняли участие 51 кандидат. 14 из них (включая Hamsi) прошли во второй тур[5].
The Hash Funtion Hamsi
Общая структура
Hamsi использует такие преобразования, как конкатенация (англ. Concatenation), перестановка (англ. Permutation) и округление (англ. Truncation), которые также используются в других алгоритмах хэширования, например Snefru[6] и 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,Pf : {0, 1}s → {0, 1}s 4 Truncation T : {0, 1}s → {0, 1}n Обозначения:
Fn Конечное поле из 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:
hi = (T ◦ P ◦ C(E(Mi), hi−1)) ⊕ hi−1, h0 = iv256, 0 < i <
h = (T ◦ Pf ◦ C(E(M), h−1)) ⊕ h−1
Hamsi-512:
hi = (T ◦ P ◦ C(E(Mi), hi−1)) ⊕ hi−1, h0 = iv512, 0 < i <
h = (T ◦ Pf ◦ C(E(M), h−1)) ⊕ h−1
Начальные значения
Начальным значением для алгоритма является начальное значение связывающего значения h0. Оно получено с помощью кодировки UTF-8 следующего сообщения: «Ozgul Kucuk, Katholieke Universiteit Leuven, Departement Elektrotechniek, Computer Security and Industrial Cryptography, Kasteelpark Arenberg 10, bus 2446, B-3001 Leuven-Heverlee, Belgium.» Начальные значения для различных разновидностей алгоритма представлены в следующей таблице:
iv256 0x76657273, 0x69746569, 0x74204c65, 0x7576656e 0x2c204b61, 0x74686f6c, 0x69656b65, 0x20556e69 iv512 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 использует линейные коды[7] для расширения сообщений. Для Hamsi-256 расширение сообщения длиной 32 бита в сообщение длиной 256 бит производится с помощью кода [128, 16, 70] над полем F4[8]. Для Hamsi-512 расширение сообщения длиной 64 бита в сообщение длиной 512 бит производится с помощью кода [256, 32, 131] над полем F4.
Конкатенация
К словам расширенного сообщения (m0,m1, . . . ,mi) приписывается связывающее значение (c0, c1, . . . , cj). Значения i и j равны 7 для Hamsi-256 и 15 для Hamsi-512. Затем над полученным сообщением будет произведена нелинейная перестановка P. Метод конкатенации определяет порядок следования битов на входе Р.
В Hamsi-256
C: {0, 1}256x{0, 1}256 → {0, 1}512, а подробнее
C(m0,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}512 × {0, 1}512 → {0, 1}1024, а подробнее
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}128 → {0, 1}128. 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.
Ссылки
- ↑ R. Knudsen, L., Rechberger, C., S. Thomsen. Grindahl — a family of hash functions. In Biryukov, A, ed.: Fast Software Encryption, FSE 2007. Volume 4593 of Lecture Notes in Computer Science, Springer-Verlag (2007) 39-57
- ↑ Serpent: A proposal for the advanced encryption standard. http://www.cl.cam.ac.uk/~rja14/serpent.html
- ↑ http://www.nist.gov/
- ↑ http://csrc.nist.gov/groups/ST/hash/sha-3/index.html
- ↑ http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html
- ↑ 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 October 2008). Проверено 11 декабря 2008.
http://homes.esat.kuleuven.be/~okucuk/hamsi/index.html
http://www.cosic.esat.kuleuven.be/publications/article-1203.pdf
Wikimedia Foundation. 2010.