CubeHash^[1] - это параметризуемое семейство криптографических хеш-функций CubeHashr/b. CubeHash8/1 была предложена Дэниелом Бернштейном в качестве нового стандарта для SHA-3 в конкурсе хеш-функций, проводимым Национальным институтом стандартов и технологий (НИСТ). Вначале НИСТ требовал около 200 циклов на байт^[2]. После некоторых уточнений от НИСТ автор сменил параметры на CubeHash16/32, которая примерно в 16 раз быстрее чем CubeHash8/1 и легко догоняет SHA-256 и SHA-512 на различных платформах^[3]. CubeHash прошла во второй уровень конкурса, но так и не попала в пятерку финалистов.

Описание алгоритма

Работа CubeHash r/b-h базируется на трёх параметрах: r, b и h.

• r - количество раундов (не менее 1)
• b - размер блока в байтах (от 1 до 128)
• h - размер хеша в битах (может быть 8, 16, 24, 32,..., 512)

Алгоритм имеет 5 основных шагов:

• инициализация 128-байтового состояния как функция (h,b,r)
• разбиение входящего сообщения на части. Каждая часть включает один или более b-байтовых блоков
• для каждого b-байтового блока части сообщения: выполняется операция исключающего "или" над блоком и первыми b байтами состояния и затем преобразует его посредством r одинаковых раундов
• завершение состояния
• вывод первых h/8 байт состояния

Инициализация. 128-байтовое состояние рассматривается как последовательность 32-х четырёх-байтовых слов x₀₀₀₀₀, x₀₀₀₀₁, x₀₀₀₁₀,..., x₁₁₁₁₁, каждое из которых представляется в little-endian форме 32-х битовых целых чисел. Первые три слова x₀₀₀₀₀, x₀₀₀₀₁, x₀₀₀₁₀ выставляются в h/8, b, r соответственно. Оставшиеся слова равны нулю. Затем состояние преобразуется посредством 10r одинаковых раундов.
Заполнение. Добавляется 1 бит ко входящему сообщению, затем оно дополняется минимально возможным количеством нулевых битов так, что бы количество битов было кратно 8b. Нужно отметить, что заполнение не требует разделение хранилища длины сообщения, блока для обработки и остального. Реализация может просто хранить одиночное число между 0 и 8b, чтобы записать число бит обработанных на данный момент в текущем блоке.
Завершение. К последнему состоянию слова x₁₁₁₁₁ по модулю два прибавляется 1. Далее состояние преобразуется путем проведения 10r одинаковых раундов.
Каждый раунд включает 10 шагов:

• прибавление x_0jklm к x_1jklm по модулю 2³² для каждого (j, k, l, m)
• смещение влево по кругу на 7 бит слова x_0jklm для каждого (j, k, l, m)
• обмен x_00klm c x_01klm для каждого (k, l, m)
• прибавление по модулю 2 числа x_1jklm к x_0jklm для каждого (j, k, l, m)
• обмен x_1jk0m с x_1jk1m для каждого (j, k, m)
• прибавление x_0jklm к x_1jklm по модулю 2³² для каждого (j, k, l, m)
• смещение влево по кругу на 11 бит слова x_0jklm для каждого (j, k, l, m)
• обмен x_0j0lm с x_0j1lm для каждого (j, l, m)
• прибавление по модулю 2 числа x_1jklm к x_0jklm для каждого (j, k, l, m)
• обмен x_1jkl0 с x_1jkl1 для каждого (j, k, l)

Примеры хешей

Данный пример использует CubeHash 8/1-512.
Инициализирующий вектор одинаковых для всех 8/1-512 хешей и выглядит как:

6998f35dfb0930c760948910e626160f36077cf3b58b0d0c57cf193d3341e7b8\
a334805b2089f9ef31ffc4142aef3850fe121839e940a4527d5293a27045ca12\
9358096e81bf70349a90a44a93c33edb14c3e9844a87dbd0bc451df25212b3ac\
6aabe51c5df0f63bddbb8ae8fad3cf0fd52582fbad2e2446094025a521a23d5c

Хеширование ASCII сообщения "Hello" (hex: 0x48, 0x65, 0x6c, 0x6c, 0x6f) использует 6 блоков. Первые 5 блоков приходят(т.к. в данном случае каждая буква - один байт) из сообщения и ещё один блок для заполнения.
Значение 512 битового хеша равно:

7ce309a25e2e1603ca0fc369267b4d43f0b1b744ac45d6213ca08e7567566444\
8e2f62fdbf7bbd637ce40fc293286d75b9d09e8dda31bd029113e02ecccfd39b

Небольшое изменение в сообщении (например, изменение одного бита) ведёт к значительному изменению хеша (так называемый лавинный эффект).
Для примера возьмём сообщение "hello", отличающееся от "Hello" всего в один бит. Хеш этого сообщения равен:

01ee7f4eb0e0ebfdb8bf77460f64993faf13afce01b55b0d3d2a63690d25010f\
7127109455a7c143ef12254183e762b15575e0fcc49c79a0471a970ba8a66638

Изменение параметров

CubeHash r/b-h принимает много различных параметров, используемых для определения хеша. Это придаёт гибкость алгоритму по отношению к конечному пользователю, который сам определяет наилучшие параметры для использования. Ниже представлены некоторые примеры хешей различных сообщений, использующие разные параметры алгоритма. Все сообщения записаны в ASCII. Три параметра, используемые в генерации хеша, представлены в r/b-h формате.

Сообщение: ""  (пустая строка, строка с нулевой длинной)
CubeHash 16/32-512: 4a1d00bbcfcb5a9562fb981e7f7db3350fe2658639d948b9d57452c22328bb32\
                    f468b072208450bad5ee178271408be0b16e5633ac8a1e3cf9864cfbfc8e043a

CubeHash 8/1-512: 90bc3f2948f7374065a811f1e47a208a53b1a2f3be1c0072759ed49c9c6c7f28\
                  f26eb30d5b0658c563077d599da23f97df0c2c0ac6cce734ffe87b2e76ff7294

CubeHash 1/1-512: 3f917707df9acd9b94244681b3812880e267d204f1fdf795d398799b584fa8f1\
                  f4a0b2dbd52fd1c4b6c5e020dc7a96192397dd1bce9b6d16484049f85bb71f2f

CubeHash 16/32-256: 44c6de3ac6c73c391bf0906cb7482600ec06b216c7c54a2a8688a6a42676577d

CubeHash 8/1-256: 38d1e8a22d7baac6fd5262d83de89cacf784a02caa866335299987722aeabc59

CubeHash 1/1-256: 80f72e07d04ddadb44a78823e0af2ea9f72ef3bf366fd773aa1fa33fc030e5cb

Сообщение: "Hello"
CubeHash 16/32-512: dcc0503aae279a3c8c95fa1181d37c418783204e2e3048a081392fd61bace883\
                    a1f7c4c96b16b4060c42104f1ce45a622f1a9abaeb994beb107fed53a78f588c

CubeHash 8/1-512: 7ce309a25e2e1603ca0fc369267b4d43f0b1b744ac45d6213ca08e7567566444\
                  8e2f62fdbf7bbd637ce40fc293286d75b9d09e8dda31bd029113e02ecccfd39b

CubeHash 1/1-512: 13cf99c1a71e40b135f5535bee02e151eb4897e4de410b9cb6d7179c677074eb\
                  6ef1ae9a9e685ef2d2807509541f484d39559525179d53838eda95eb3f6a401d

CubeHash 16/32-256: e712139e3b892f2f5fe52d0f30d78a0cb16b51b217da0e4acb103dd0856f2db0

CubeHash 8/1-256: 692638db57760867326f851bd2376533f37b640bd47a0ddc607a9456b692f70f

CubeHash 1/1-256: f63041a946aa98bd47f3175e6009dcb2ccf597b2718617ba46d56f27ffe35d49

Безопасность

Стойкость этого алгоритма увеличивается как при уменьшении b к 1, так и при увеличении r.
Поэтому CubeHash 8/1-512 стойче (более безопаснее) чем CubeHash 1/1-512, а CubeHash 1/1-512 стойче чем CubeHash 1/2-512. Самый слабый из возможных версий данного алгоритма - это CubeHash 1/128-h.
Однако, безопасность зависит от времени. Более безопасный вариант будет дольше вычислять хеш-значение.

Примечания