Hamsi — криптографическая хеш-функция, в основу которой положены алгоритмы Grindahl и SerpentSerpent: A proposal for the advanced encryption standard .. Эта хеш-функция не запатентована и является общественным достоянием. Существуют две разновидности алгоритма: Hamsi-256 и Hamsi-512. В основе алгоритма лежат функция разложения и циклическая трансформация. Циклическая трансформация работает с четырьмя строками матрицы состояний. Число столбцов этой матрицы равно 4 для Hamsi-256, 8 для Hamsi-512. Элементами матрицы являются слова размером 32 бита.
История
Hamsi была одним из участников в открытом конкурсе SHA-3 Национального института стандартов и технологий по разработке новых криптографических хеш-функций, которые преобразуют сообщения переменной длины в сжатые текстовые строки фиксированной длины, что может быть использовано для электронно-цифровых подписей, аутентификации сообщений и других применений. В первом раунде соревнования приняли участие 51 кандидат. 14 из них (включая Hamsi) прошли во второй тур. Однако Hamsi не попала в число 5 кандидатов последнего тура, объявленных 10 декабря 2010 года.
Описание
Общая структура
Hamsi использует такие преобразования, как конкатенация (), перестановка () и округление (), которые также используются в других алгоритмах хеширования, например SnefruMerkle R.C. A Fast Software One-Way Hash Function. Journal of Cryptology, 3(1):43-58, 1990 и Grindahl. В алгоритме также применяется функции расширения текста сообщения () и распространения связывающего значения () на каждой итерации. Для нелинейных перестановок () используются линейные преобразования и один S-box из блочного шифрования Serpent. Общую структуру Hamsi можно представить в виде:
1Message ExpansionE : {0, 1} → {0, 1}2ConcatenationC : {0, 1} x {0, 1} → {0, 1}3Non-linear Permutations P,P : {0, 1} → {0, 1}4TruncationT : {0, 1} → {0, 1}
Обозначения:
FКонечное поле из n элементов<<< Циклический сдвиг влево Исключающее ИЛИ (XOR)<< Битовый сдвиг влево[n, m, d] Код длины n, размерностью m и минимальным расстоянием d
Значения m, n и s для различных вариантов Hamsi представлены в следующей таблице:
mnsHamsi-25632256512Hamsi-512645121024
Пусть (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 соответственно. Если длина блока меньше чем необходимо, тогда происходит дополнение сообщения (). Дополнение происходит следующим образом. К сообщению справа добавляется один бит значением '1', а затем добавляются биты со значениями равными '0' до тех пор пока длина сообщения не станет равной 32 или 64. Пример:
Есть сообщение длиной 24 бита 1010 0110 1110 1111 1111 0000
После дополнения до 32-х битного оно будет выглядеть так
1010 0110 1110 1111 1111 00001000 0000
Расширение сообщения
Hamsi использует линейные кодыJ.H. van Lint. Introduction to Coding Theory для расширения сообщений. Для Hamsi-256 расширение сообщения длиной 32 бита в сообщение длиной 256 бит производится с помощью кода [128, 16, 70] над полем FBounds on the minimum distance of linear codes. http://codetables.de.BKLC/. Для 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)
Порядок слов легче всего запомнить с помощью следующей таблицы, результат из которой можно получить построчным считыванием:
m0m1c0c1c2c3m2m3m4m5c4c5c6c7m6m7
В 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||15s[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:
<big>α0 = 0xcaf9639c<big>α1 = 0x0ff0f9c0 <big>α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-256Hamsi-512P циклов36Pf циклов612
Во втором туре соревнования SHA-3 появилась новая модификация алгоритма под названием Hamsi-256/8. Её отличие от Hamsi-256 в том, что количество Pf циклов теперь равно 8.
Примечания
Литература
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
Категория:Криптографические хеш-функции