Хеш только для эллиптической кривой

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

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

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

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

Алгоритм [ править ]

Учитывая , что ECOH делит сообщение на блоки . Если последний блок является неполным, он дополняется одной единицей, а затем соответствующим числом 0. Пусть, кроме того, будет функция, которая отображает блок сообщения и целое число в точку эллиптической кривой. Затем с помощью сопоставления каждый блок преобразуется в точку эллиптической кривой , и эти точки складываются вместе с еще двумя точками. Еще одна точка содержит заполнение и зависит только от длины сообщения. Второй дополнительный пункт зависит от длины сообщения и XOR всех блоков сообщения. Результат обрезается, чтобы получить хэш .${\ displaystyle n}$${\ displaystyle M}$${\ 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: хеширование только эллиптической кривой» .${\ 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 [ править ]

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

Суммирующий многочлен Семаева [ править ]

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

Более формально: Позвольте быть конечным полем, быть эллиптической кривой с уравнением Вейерштрасса, имеющим коэффициенты в и быть точкой бесконечности. Известно, что существует многочлен с несколькими переменными тогда и только тогда, когда существует < такой, что . Этот многочлен имеет степень по каждой переменной. Проблема в том, чтобы найти этот многочлен.${\displaystyle \mathbf {F} }$${\displaystyle E}$${\displaystyle \mathbf {F} }$${\displaystyle O}$${\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${\displaystyle M'=(M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})}$${\displaystyle (M_{0},M_{1})}$${\displaystyle M_{2}}$${\displaystyle M_{2}:=M_{0}+M_{1}}$соответствующие точки эллиптической кривой и сохраните их в списке. Затем мы выбираем K различных случайных значений , определяем , вычисляем и сохраняем их во втором списке. Обратите внимание, что цель Q известна. зависит только от длины сообщения, которое мы исправили. зависит от длины и XOR всех блоков сообщений, но мы выбираем блоки сообщений так, чтобы они всегда были равны нулю. Таким образом, это исправлено для всех наших попыток.${\displaystyle P(M_{0},0)+P(M_{1},1)+P(M_{2},2)}$${\displaystyle (M_{3},M_{4})}$${\displaystyle M_{5}:=M_{3}+M_{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 (M_{1},M_{2},M_{3},M_{4},M_{5},M_{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 K=2^{142}}$${\displaystyle 2^{143}}$
• ECOH-384 использует эллиптическую кривую B-409 с приблизительно точками на кривой. Выбор дает атаку со сложностью${\displaystyle 2^{409}}$${\displaystyle K=2^{205}}$${\displaystyle 2^{206}.}$
• ECOH-512 использует эллиптическую кривую B-571 с приблизительно точками на кривой. Выбор дает атаку со сложностью${\displaystyle 2^{571}}$${\displaystyle K=2^{286}}$${\displaystyle 2^{287}.}$

ECOH2 [ править ]

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

Ссылки [ править ]

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