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

Алгоритм эллиптической хеш-функции(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:=\textstyle \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'_{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},\ldots ,X_{N})$ тогда и только тогда, если они существуют < $y_{1},\ldots ,y_{n}$ такие, что $(x_{1},y_{1})+\ldots +(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'=(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)».