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

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

Алгоритм

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

<math>O_i = M_i \parallel I_i</math>

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

<math>P_i := P(x_i, y_i)</math>

<math>Q := \textstyle \sum_{i=0}^{n-1}P_i \displaystyle</math>

<math>R := f(Q)</math>

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

Примеры

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

Свойства

• Инкрементальность: ECOH сообщение может быть быстро обновлено, учитывая небольшое изменение в сообщении и промежуточное значение в вычислении ECOH.
• Параллелезуемость: это означает, что вычисление <math>P'_is</math> может быть выполнено на параллельных системах.
• Скорость: Алгоритм ECOH примерно в тысячу раз медленнее, чем SHA-1. Однако, учитывая развитие настольного оборудования в сторону распараллеливания и умножения без переноса, ECOH может через несколько лет быть таким же быстрым, как SHA-1 для длинных сообщений. Для коротких сообщений ECOH является относительно медленным, если не используются расширенные таблицы.

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

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

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

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

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

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

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

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

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

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

Если K больше квадратного корня из числа точек на эллиптической кривой, то мы ожидаем одну коллизию между двумя списками. Это дает нам сообщение <math>(M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})</math> с <math>Q=\sum _Шаблон:I=0^{5}P(M_{i},i)+X_{1}+X_{2}</math> Это означает, что это сообщение ведет к целевому значению Q и, следовательно, ко второму прообразу, о котором шла речь. Рабочая нагрузка, которую мы должны сделать здесь, — это два раза K частичных хеш-вычислений. Для получения дополнительной информации см. «A Second Pre-image Attack Against Elliptic Curve Only Hash (ECOH)».

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

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

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

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)».