Только хэш эллиптической кривой

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

ECOH основан на алгоритме хэширования MuHASH , который пока не был успешно атакован . Однако MuHASH слишком неэффективен для практического использования, и пришлось внести изменения. Главное отличие в том, что там, где MuHASH применяет случайный оракул ^{[ необходимо разъяснение ]} , ECOH применяет функцию дополнения . Предполагая случайные оракулы, поиск коллизии в MuHASH подразумевает решение задачи дискретного логарифма . Таким образом, MuHASH является доказуемо безопасным хешем , т. е. мы знаем, что поиск коллизии по крайней мере так же сложен, как и некоторая известная сложная математическая задача.

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

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

Учитывая , ECOH делит сообщение на блоки . Если последний блок неполный, он дополняется одной 1, а затем соответствующим числом 0. Пусть далее будет функцией, которая сопоставляет блок сообщения и целое число с точкой эллиптической кривой. Затем с помощью отображения каждый блок преобразуется в точку эллиптической кривой , и эти точки складываются с двумя другими точками. Одна дополнительная точка содержит заполнение и зависит только от длины сообщения. Вторая дополнительная точка зависит от длины сообщения и XOR всех блоков сообщений. Результат усекается для получения хеша .${\displaystyle n}$${\displaystyle М}$${\displaystyle n}$${\displaystyle M_{0},\ldots ,M_{n-1}}$${\displaystyle P}$${\displaystyle P}$${\displaystyle P_{i}}$${\displaystyle X_{1}}$${\displaystyle X_{2}}$${\displaystyle H}$

${\displaystyle {\begin{align}P_{i}&{}:=P(M_{i},i)\\X_{1}&{}:=P'(n)\\X_{2}&{}:=P^{*}(M_{i},n)\\Q&{}:=\sum _{i=0}^{n-1}P_{i}+X_{1}+X_{2}\\R&{}:=f(Q)\end{align}}}$

Две дополнительные точки вычисляются с помощью и . складывает все точки эллиптической кривой и две дополнительные точки вместе. Наконец, результат передается через функцию преобразования выходных данных f для получения результата хэша . Чтобы узнать больше об этом алгоритме, см. "ECOH: the Elliptic Curve Only Hash".${\displaystyle P'}$${\displaystyle P^{*}}$${\displaystyle Q}$${\displaystyle R}$

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

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

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

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

Более формально: Пусть будет конечным полем, будет эллиптической кривой с уравнением Вейерштрасса с коэффициентами в и будет точкой бесконечности. Известно, что существует многомерный многочлен тогда и только тогда, когда существуют < такие, что . Этот многочлен имеет степень по каждой переменной. Задача состоит в том, чтобы найти этот многочлен.${\displaystyle \mathbf {F} }$${\displaystyle E}$${\displaystyle \mathbf {F} }$${\displaystyle О}$${\displaystyle f_{n}(X_{1},\ldots ,X_{N})}$${\displaystyle y_{1},\ldots ,y_{n}}$${\displaystyle (x_{1},y_{1})+\ldots +(x_{n},y_{n})=O}$${\displaystyle 2^{n-2}}$

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

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

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

Если K больше квадратного корня из числа точек на эллиптической кривой, то мы ожидаем одно столкновение между двумя списками. Это дает нам сообщение с: Это означает, что это сообщение приводит к целевому значению Q и, таким образом, ко второму прообразу, который был вопросом. Рабочая нагрузка, которую мы должны выполнить здесь, составляет два раза по K частичных вычислений хеша. Для получения дополнительной информации см. "Вторая атака прообраза против хэша только на эллиптической кривой (ECOH)".${\displaystyle (М_{1},М_{2},М_{3},М_{4},М_{5},М_{6})}$${\displaystyle Q=\sum _{i=0}^{5}P(M_{i},i)+X_{1}+X_{2}}$

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

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

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

• Дэниел Р. Л. Браун, Мэтт Кампанья, Рене Струк (2008). «ECOH: хэш только на эллиптической кривой».
• Майкл А. Хэлкроу, Нильс Фергюсон (2009). «Вторая атака с использованием прообраза против хэша только на эллиптических кривых (ECOH)».