Эллиптическая хеш-функция

Алгоритм эллиптической хеш-функции(ECOH) был представлен в качестве кандидата на SHA-3 в конкурсе хеш-функций NIST. Однако он был отклонен в начале конкурса, так как была обнаружена вторая предварительная атака.

ECOH основан на алгоритме хеширования MuHASH, который еще не был успешно атакован. Основное различие заключается в том, что там, где MuHASH применяет случайного оракула, ECOH применяет функцию заполнения.

ECOH не использует случайных оракулов, и его безопасность не связана напрямую с проблемой дискретного логарифма, но она по-прежнему основана на математических функциях. ECOH связан с задачей Семаева о нахождении решений низкой степени полиномов суммирования над бинарным полем, называемой задачей полинома суммирования. Эффективный алгоритм решения этой проблемы до сих пор не существует. Хотя не была доказано, что задача NP-полная, предполагается, что такого алгоритма не существует. При определенных предположениях нахождение коллизии в ECOH может также рассматриваться как экземпляр задачи о сумме подмножеств. Помимо решения задачи суммирования полиномов, существует еще один способ, как найти вторые предварительные образы и, следовательно, коллизии, обобщенная атака дня рождения Вагнера.

ECOH является хорошим примером хеш-функции, которая основана на математических функциях (с доказуемым подходом к безопасности), а не на перемешивании и арифметических операциях над битами для получения хеша.

Алгоритм

Дано $n$, ECOH-$m$ делит сообщение $M$ на $n$ блоков $M_0...M_{n-1}$ длиной $blen$. Если последний блок неполный, он выравнивается одной единицей и затем подходящим числом нулей. $O_i$ вычисляется для каждого блока с помощью конкатенации блока и $I_i$ $ilen$-битного представлением индекса сообщения $i$. $x_i$ вычисляется с помощью двух концентраций и XOR с битовой строкой $C_i$, представляющей битовое представление наименьшего неотрицательного числа длиной $clen$, представляющего x координату точки эллиптической кривой. Затем каждой $x_i$ ставится в соответствие точка эллиптической кривой $P_i$ с координатой $x_i$. Каждый блок преобразуется в точку эллиптической кривой $P_i$ и эти точки складываются.

$O_i=M_i\parallel I_i$

$x_i:=(0^{m-(blen+ilen+clen)}\parallel O_i\parallel 0^{64})\oplus C_i$

$P_i:=P(x_i,y_i)$

$Q:={\sum }_{i=0}^{n-1}{P}_i{\displaystyle }$

$R:=f(Q)$

$Q$ складывает все точки эллиптической кривой. Наконец, результат передается через выходную функцию преобразования $f=\lfloor x(Q+\lfloor x(Q)/2\rfloor G)/2\rfloor mod{2}^N$, где $N$ выходной размер функции, а $G$ фиксированная для кривой точка-генератор, чтобы получить результат $R$. подробнее об этом алгоритме см. В разделе «ECOH: Эллиптическая хеш функция».

Примеры

Было предложено четыре алгоритма ECOH, ECOH-224, ECOH-256, ECOH-384 и ECOH-512. Это число соответствует выходному размеру. Они отличаются по длине параметров, размеру блока и используемой эллиптической кривой. Первые два используют эллиптическую кривую B-283: $X^{283}+X^{12}+X^7+X^5+1$, с параметрами (128, 64, 64). ECOH-384 использует кривую B-409: $X^{409}+X^7+1$, с параметрами (192, 64, 64). ECOH-512 использует кривую B-571: $X^{571}+X^{10}+X^5+X^2+1$, с параметрами (256, 128, 128). Он может хешировать сообщения длиной до $2^{128}$ бит.

Свойства

• Инкрементальность: ECOH сообщение может быть быстро обновлено, учитывая небольшое изменение в сообщении и промежуточное значение в вычислении ECOH.
• Параллелезуемость: это означает, что вычисление $P{\text{'}}_{i}s$ может быть выполнено на параллельных системах.
• Скорость: Алгоритм ECOH примерно в тысячу раз медленнее, чем SHA-1. Однако, учитывая развитие настольного оборудования в сторону распараллеливания и умножения без переноса, ECOH может через несколько лет быть таким же быстрым, как SHA-1 для длинных сообщений. Для коротких сообщений ECOH является относительно медленным, если не используются расширенные таблицы.

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

Хеш-функции ECOH основаны на конкретных математических функциях. Они были разработаны таким образом, что задача нахождения коллизий должна быть сведена к известной и NP-полной задаче (задача суммы подмножеств). Это означает, что для того чтобы найти коллизию, нужно решить основную математическую задачу, которая считается и неразрешимой за полиномиальное время. Доказано, что функции с этими свойствами безопасны и совершенно уникальны среди остальных хеш-функций. Тем не менее, второй прообраз (и, следовательно, коллизия) был позже найден, потому что предположения, приведенные в доказательстве, были слишком сильными.

Суммирующий Многочлен Семаева

Одним из способов нахождения коллизий или вторых прообразов является решение многочленов суммирования Семаева. Для данной эллиптической кривой E, существует полиномы $f_n$ симметричные в $n$ переменных и которые исчезают, когда сумма точек, оцененных на абсциссе, равна 0 в $E$. До сих пор эффективного алгоритма для решения этой проблемы не существует, и предполагается, что он труден (но не доказано, что он NP-полный).

Более формально: пусть $F$ конечное поле, $E$ эллиптическая кривая с уравнением Вейерштрасса, имеющая коэффициенты в $F$ и $O$ точка бесконечности. Известно, что существует полиномы от многих переменных $f_n(X_1,\dots ,X_N)$ тогда и только тогда, если они существуют < $y_1,\dots ,y_n$ такие, что $(x_1,y_1)+\dots +(x_n,y_n)=O$. Этот многочлен имеет степень $2^{n-2}$ по каждой переменной. Задача состоит в том, чтобы найти этот многочлен.

Обсуждение доказуемой безопасности

Задача нахождения коллизий в ECOH аналогична задаче суммирования подмножеств. Решение задачи о сумме подмножеств почти так же сложно, как задача о дискретном логарифме. Обычно предполагается, что это невозможно сделать за полиномиальное время. Однако следует учитывать, что координата $x(Q)$ может является неслучайной, и иметь определенную структуру. Если учесть это предположение, то нахождение коллизий ECOH можно рассматривать как пример задачи о сумме подмножеств.

Вторая атака прообраза существует в форме обобщенной атаки на день рождения.

Второй прообраз атаки

Описание атаки: это общий случай атаки Дня Рождения Вагнера. Это требует 2¹⁴³ времени для ECON-224 и ECON-256, 2²⁰⁶ времени для ECOH-384 и 2²⁸⁷ времени для ECOH-512. Атака устанавливает блок контрольной суммы в фиксированное значение и использует поиск коллизий в точках эллиптической кривой. Для этой атаки у нас есть сообщение M и попробуйте найти M', которое хеширует одно и то же сообщение. Сначала мы разделили длину сообщения на шесть блоков.$M^{\prime }=(M_1,M_2,M_3,M_4,M_5,M_6)$. Пусть K-натуральное число. Мы выбираем K различных чисел для $(M_0,M_1)$ и определим $M_2$ как $M_2:=M_0+M_1$.Мы вычисляем K, соответствующее точкам на эллиптических кривых $P(M_0,0)+P(M_1,1)+P(M_2,2)$и храним их в списке. Затем мы выбираем K различных случайных значений для $(M_3,M_4)$, определим $M_5:=M_3+M_4$, вычисляем $Q-X_1-X_2-P(M_3,3)-P(M_4,4)-P(M_5,5)$, и храним их во втором списке. Обратите внимание, что цель Q известна. $X_1$ зависит только от длины сообщения, которое мы зафиксировали. $X_2$ зависит от длины и XOR всех блоков сообщений, но мы выбираем блоки сообщений таким образом, что это всегда равно нулю. Таким образом, $X_2$ фиксировано для всех наших попыток.

Если K больше квадратного корня из числа точек на эллиптической кривой, то мы ожидаем одну коллизию между двумя списками. Это дает нам сообщение $(M_1,M_2,M_3,M_4,M_5,M_6)$ с $Q=\sum _{i=0}^{5}P(M_i,i)+X_1+X_2$ Это означает, что это сообщение ведет к целевому значению Q и, следовательно, ко второму прообразу, о котором шла речь. Рабочая нагрузка, которую мы должны сделать здесь, — это два раза K частичных хеш-вычислений. Для получения дополнительной информации см. «A Second Pre-image Attack Against Elliptic Curve Only Hash (ECOH)».

Фактически параметры:

• ECON-224 и ECOH-256 используют эллиптическую кривую B-283 с приблизительно $2^{283}$ точек на кривой. Мы выбираем $K=2^{142}$ и получаем атаку со сложностью $2^{143}$.
• ECOH-384 использует эллиптическую кривую B-409 с приблизительно $2^{409}$ точек на кривой. Выбрав $K=2^{205}$ дает атаку со сложностью $2^{206}$.

• ECOH-384 использует эллиптическую кривую B-409 с приблизительно $2^{571}$ точек на кривой. Выбрав $K=2^{286}$ дает атаку со сложностью $2^{287}$.

ECOH2

Официальные комментарии по ECOH включали предложение под названием ECOH2, которое удваивает размер эллиптической кривой в попытке остановить вторую атаку прообраза Халкроу-Фергюсона с предсказанием улучшенной или аналогичной производительности.

Ссылки

• Daniel R. L. Brown, Matt Campagna, Rene Struik (2008). «ECOH: the Elliptic Curve Only Hash».
• Michael A. Halcrow, Niels Ferguson (2009). «A Second Pre-image Attack Against Elliptic Curve Only Hash (ECOH)».