CubeHash

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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-х четырёх-байтовых слов x00000, x00001, x00010,..., x11111, каждое из которых представляется в little-endian форме 32-х битовых целых чисел. Первые три слова x00000, x00001, x00010 выставляются в h/8, b, r соответственно. Оставшиеся слова равны нулю. Затем состояние преобразуется посредством 10r одинаковых раундов.
Заполнение. Добавляется 1 бит ко входящему сообщению, затем оно дополняется минимально возможным количеством нулевых битов так, что бы количество битов было кратно 8b. Нужно отметить, что заполнение не требует разделение хранилища длины сообщения, блока для обработки и остального. Реализация может просто хранить одиночное число между 0 и 8b, чтобы записать число бит обработанных на данный момент в текущем блоке.
Завершение. К последнему состоянию слова x11111 по модулю два прибавляется 1. Далее состояние преобразуется путем проведения 10r одинаковых раундов.
Каждый раунд включает 10 шагов:

  • прибавление x0jklm к x1jklm по модулю 232 для каждого (j, k, l, m)
  • смещение влево по кругу на 7 бит слова x0jklm для каждого (j, k, l, m)
  • обмен x00klm c x01klm для каждого (k, l, m)
  • прибавление по модулю 2 числа x1jklm к x0jklm для каждого (j, k, l, m)
  • обмен x1jk0m с x1jk1m для каждого (j, k, m)
  • прибавление x0jklm к x1jklm по модулю 232 для каждого (j, k, l, m)
  • смещение влево по кругу на 11 бит слова x0jklm для каждого (j, k, l, m)
  • обмен x0j0lm с x0j1lm для каждого (j, l, m)
  • прибавление по модулю 2 числа x1jklm к x0jklm для каждого (j, k, l, m)
  • обмен x1jkl0 с x1jkl1 для каждого (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.
Однако, безопасность зависит от времени. Более безопасный вариант будет дольше вычислять хеш-значение.

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

Внешние ссылки[править | править вики-текст]

Официальный сайт алгоритма