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

Только хэш эллиптической кривой (ECOH)
Общий
Дизайнеры	Дэниел Р.Л. Браун, Мэтт Кампанья, Рене Струик
Впервые опубликовано	2008
Получено из	МуХАШ
Деталь
Размеры дайджеста	224, 256, 384 или 512
Лучший публичный криптоанализ
	Второе предварительное изображение

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

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

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

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

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

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

${\begin{aligned}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{aligned}}$

Два дополнительных балла рассчитываются по формуле $P'$ и $P^{*}$ . $Q$ складывает все точки эллиптической кривой и две дополнительные точки вместе. Наконец, результат передается через функцию выходного преобразования f, чтобы получить результат хеширования. $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^{87}+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

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

суммирования Полином Семаева

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

Более формально: Пусть $\mathbf {F}$ быть конечным полем, $E$ — эллиптическая кривая с уравнением Вейерштрасса, имеющим коэффициенты $\mathbf {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 аналогична проблеме суммы подмножеств . Решение задачи о сумме подмножеств почти так же сложно, как и задача дискретного логарифма . Обычно предполагается, что это невозможно за полиномиальное время . Однако следует предположить существенно расплывчатую эвристику, а точнее, один из задействованных в вычислении параметров не обязательно является случайным, но имеет определенную структуру. Если принять эту свободную эвристику, то обнаружение внутреннего коллизия ECOH можно рассматривать как пример проблемы суммы подмножества .

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

Вторая атака по прообразу [ править ]

Описание атаки Вагнера : Это обобщенная атака в честь дня рождения . Требуется 2 ¹⁴³ время для ECOH-224 и ECOH-256, 2 ²⁰⁶ время для ECOH-384 и 2 ²⁸⁷ время для ECOH-512. Атака устанавливает для блока контрольной суммы фиксированное значение и использует поиск коллизий в точках эллиптической кривой. Для этой атаки у нас есть сообщение M , и мы пытаемся найти M' , хэш которого соответствует тому же сообщению. Сначала мы разделили длину сообщения на шесть блоков. Так $M'=(M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})$ . Пусть К — натуральное число. Выбираем 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 вычислений частичного хэша. Для получения дополнительной информации см. «Вторая атака предварительного изображения против хэша только эллиптических кривых (ECOH)» .

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

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

ECOH2 [ править ]

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

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

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