CubeHash

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

Так как раунд вычислений в CubeHash является обратимым, то начальное состояние может быть вычислено путём произведения обратных операция над конечным состоянием. Атака на основе одного блока основана на этом обстоятельстве.

Рассмотрим алгоритм этой атаки.

Возьмём хеш H некоторого сообщения, b байт второго прообраза сообщения вычисляются, используя CubeHashr/b-h.

1. Установим первые h/8 байт финального состояния, используя хеш H, а оставшиеся 128-h/8 байт, используя пробное значение T, получаем состояние 6. Метод выбора пробного значения будет описан далее.
2. Применяя 10r обратных раундов к состоянию 6, получаем состояние 5. Обратные раунды функции можно получить, делая шаги алгоритма в обратном порядка, то есть, заменяя смещения по кругу влево на смещения по кругу вправо и сложение заменяя вычитанием по модулю 2³².
3. Применим операцию исключающего или к 1 и последнему слову состояния 5, таким образом, получаем состояние 4
4. Сделав r обратных раундов с состоянием 4, получаем состояние 3.
5. Применим операцию исключающего или к сообщения 0x80 и первым байтом состояния 4, получив в итоге состояние 3.
6. Сделав r обратных раундов с состоянием 2, получаем состояние 1.
7. Если последние 128 — b байт состояния 1 не совпадают с 128-b байт инициализирующего вектора (состояние 0), тогда пробное сообщение было неудачно выбрано.
8. В противном случае пробное сообщение выбрано удачно. Второй прообраз вычисляется, используя исключающее или над первыми b байтами состояния 1 и первыми b байтами состояния инициализирующего вектора.

Повторяя описанную выше процедуру с различными значениями T, в конечном итоге будет сгенерирован второй прообраз. Метод выбора значения T не является критичным. Например, последовательность чисел следующих друг за другом может быть использована.

Предполагая, что CubeHash (в прямом или обратном сообщении) ведёт себя, как случайное отображение для произвольного пробного значения T, тогда вероятность того, что последние 128-b байт состояния 1 будут равны соответствующим байтам инициализирующего вектора равна 2^−8(128-b). Таким образом, число пробных сообщений перед достижением успеха 2^8(128-b). Если 2^8(128-b) < 2^h тогда атака на основе одного блока найдет второй прообраз за меньшее количество попыток, по сравнению с полным перебором. Другими словами атака на основе одного блока более эффективна, чем полный перебор для следующих значения h = 224 и b > 100, для h = 256 и b > 96, для h=384 и b> 80, для h=512 и b > 64.

Однако ожидаемое число попыток нужных для достижения успеха не зависит от числа раундов r. Конечно, время нужное для осуществления атаки увеличивается линейно от r, а не как показательная функция. Также следует заметить, что для b = 128 любое значение T будет сразу являться вторым прообразом.

Рассмотрим алгоритм улучшения атаки нахождения первого прообраза.

1. Исходя из значений (h,b,r) вычисляем инициализирующий вектор (состояние 0).
2. Для h бит и 1024-h, выполняем 10r обратных раундов и операцию исключающего или, чтобы получить состояние f.
3. Находим две n блочные последовательности, которые отображают состояние 0 и состояние f, в два состояния, которые имеют одинаковые последние 1024-h бит.

Существует 2^nb возможных входных n блоков и одного из них произойдет коллизия. Число попыток нужных для нахождения коллизии оценивается как

2 * (521 / b — 4) * 2^{512 — 4b} = 2 * 522 — 4b — logb

Кроме того учтём, что каждый раунд требует 2¹¹ битовых операция, тогда формула изменится на 2^{533-4b-logb+logr} битовых операций. Ускорение данной атаки может быть достигнуто за счёт того, что поиск коллизии будем производить не только после вычисления n-го блока, но и в каждом различном состоянии которого мы достигли (будем использовать и промежуточные состояния). Таким образом мы избавимся от множителя (512/b-4). Тогда число попыток нужных для нахождения коллизии будет оцениваться как 2^513-4b битовых операций. Рассмотрим CubeHash-512 с параметрами h, b, r равными 512, 1, 8 соответственно. Для улучшенного алгоритма количество попыток нужных для нахождения коллизии равно 2⁵²³ в сравнении со стандартным алгоритмом атаки с попытками для нахождения коллизии 2⁵³². Если r = 8, для улучшенного алгоритма нужно, чтобы b > 3 для того чтобы число попыток было меньше чем 2⁵¹², для обычного алгоритма должно выполнятся условия b > 5.

Как было сказано выше, алгоритм CubeHash очень симметричен и в нём не используются какие-либо константы. Поэтому существует много классов симметрии относительно перестановок. Самый эффективный способ атаки — это использовать класс симметрии, для которого расширение сообщения может генерировать симметричные сообщения. Например, мы можем использовать класс симметрии называемый C2. Для этого класса состояние называется симметричным если x_ijkl0=x_ijkl1 для любых i, j, k, l.

Когда параметр b равен 32, то есть CubeHash является нормальным, инъекция сообщения дает контроль над x_00klm для любых k, l, m.

Поэтому, для того чтобы достичь симметричного состояния нужно просто достичь состояния удовлетворяющему следующему 384-битному уравнения

x_01kl0=x_01kl1

x_10kl0=x_10kl1

x_11kl0=x_11kl1

для любых k, l.

И тогда инъекция сообщения может быть использована для достижения полностью симметричного состояния. Ожидаемая сложность при этом 2³⁸⁴.

Это может быть использовано для атаки нахождения прообраза. Алгоритм можно записать следующим образом

1. Найти сообщение А, которое будет симметрично с инициализирующим вектором
2. Найти сообщение D, которое симметрично в обратном порядке с заданным.
3. Сформировать 2¹⁹² симметричных сообщений B_j. Затем вычислить состояния, получающееся после выполнения операции или над A и B_j
4. Сформировать 2¹⁹² симметричных сообщений С_j. Затем вычислить состояния, получающееся после выполнения операции или над выполнения C_j и D.
5. С высокой вероятностью найдётся пара значений, удовлетворяющих

b_01kl0=c_01kl0

b_10kl0=c_10kl0

b_11kl0=c_11kl0

тогда из симметрии следуют следующие равенства

b_01kl1=c_01kl1

b_10kl1=c_10kl1

b_11kl1=c_11kl1

выполняющиеся для любых k, l.

Затем используем блок Х, чтобы сопоставить первые 256 бит. Это даёт прообраз — выполняем операцию или над A, B_i0, X, C_i0, D.

Сложность шагов 1 и 2 это 2³⁸⁴, а сложность шагов 3 и 4 это 2¹⁹². Следует заметить, что он может быть реализован без больших затрат памяти. Эта атака имеет такую же сложность, как атака основанная на мощности, когда B является степенью двойки, но она становится эффективней когда b не является степенью двойки.

Наиболее трудоёмкая часть атаки, основанной на симметрии — это вычисления нужные для вычисления симметричного состояния. Тем не менее, оказывается, что эта задача легко решается с использованием алгоритма Гровера на квантовом компьютере. На самом деле нахождение состояния, удовлетворяющего уравнению, описанному выше, эквивалентно нахождению прообраза нуля для хеш функции, которая будет перебирать раунды функции CubeHash, и выход которой будет представлен

x₀₁₀₀₀ ${\displaystyle \oplus _{2}}$ x₀₁₀₀₁

x₀₁₀₁₀ ${\displaystyle \oplus _{2}}$ x₀₁₀₁₁

x₀₁₁₀₀ ${\displaystyle \oplus _{2}}$ x₀₁₁₀₁

x₀₁₁₁₀ ${\displaystyle \oplus _{2}}$ x₀₁₁₁₁

x₁₀₀₀₀ ${\displaystyle \oplus _{2}}$ x₁₀₀₀₁

x₁₀₀₁₀ ${\displaystyle \oplus _{2}}$ x₁₀₀₁₁

x₁₀₁₀₀ ${\displaystyle \oplus _{2}}$ x₁₀₁₀₁

x₁₀₁₁₀ ${\displaystyle \oplus _{2}}$ x₁₀₁₁₁

x₁₁₀₀₀ ${\displaystyle \oplus _{2}}$ x₁₁₀₀₁

x₁₁₀₁₀ ${\displaystyle \oplus _{2}}$ x₁₁₀₁₁

x₁₁₁₀₀ ${\displaystyle \oplus _{2}}$ x₁₁₁₀₁

x₁₁₁₁₀ ${\displaystyle \oplus _{2}}$ x₁₁₁₁₁

Для 384-битной функции алгоритм Гровера имеет сложность, равную 2¹⁹² операций. Тогда атака с использованием симметрии будет требовать 2¹⁹² операций при условии, что квантовые компьютеры являются доступными.