Рейтинг:1

Является ли композиция устойчивых к коллизиям функций H' = h1(h2()) устойчивой к коллизиям?

флаг id

Предположим, что есть две устойчивые к коллизиям хэш-функции. $h_1$ и $h_2$ с выходными размерами $n_1$ и $n_2$ соответственно.

Является $H'(x) = h_1(h_2(x))$ устойчивость к столкновениям для различных отношений между $n_1$ и $n_2$?


Последние несколько дней это ошеломляло меня и моих коллег, поскольку два разных подхода противоречат друг другу:

1-й подход:

На основании определения сопротивления столкновению $H'$ имеет выход $n_1$ длину, и поэтому, если мы сможем найти атаку с меньшей сложностью, чем $\mathcal О(2^{n_1/2})$ он не устойчив к столкновениям.

Мы хотим $$\mathcal O(2^{n_2/2}) < \mathcal O(2^{n_1/2}) \подразумевается \ldots \подразумевается n_2 < n_1$$

Так что если $n_2 < n_1, Н'$ не является устойчивым к столкновениям, а в других случаях


2-й подход:

Предположим $H'$ не устойчив к столкновениям.

Тогда существуют разные $x_1$ и $x_2$ так что $H'(x_1) = H'(x_2)$ то есть $h_1(h_2(x_1)) = h_1(h_2(x_2))$

Это может случиться, если $h_2(x_1) = h_2(x_2)$, но $h_2$ устойчив к столкновениям

Это также может произойти, если $h_1(A) = h_1(B)$ куда $А = ч_2(х_1)$ и $B = h_2(x_2)$ но $h_1$ устойчив к столкновениям.

Мы доказали, что $H'$ является устойчивым к столкновению и отношения $n_1$ и $n_2$ не имеет значения.

kelalaka avatar
флаг in
Добро пожаловать на [cryptography.se].Это вопрос домашнего задания? (У нас есть дубликаты для этого)
kelalaka avatar
флаг in
Подсказка: если $n_1 = n_2$, то 1-й подход аналогичен 2-му. Когда они различаются, $n_2
John St avatar
флаг id
Это подготовка к моему магистерскому экзамену по прикладной криптографии, я видел дубликаты, но нигде не нашел первого подхода.
John St avatar
флаг id
Основываясь на вашем комментарии, я понимаю, что последние решения предполагают $n_1=n_2$? Хотя, как я могу понять, что это применимо и, следовательно, не применимо к этой проблеме?
Рейтинг:4
флаг my

Последние несколько дней это ошеломляло меня и моих коллег, поскольку два разных подхода противоречат друг другу.

Причина в том, что эти два подхода предполагают разные определения «устойчивости к коллизиям»; эти два определения не эквивалентны; то есть мы можем найти функции, которые соответствуют одному определению, но не соответствуют другому.

В первой попытке используется определение «нет присоединения для обнаружения столкновений, которое занимает меньше, чем $\mathcal{O}(2^{n/2})$ операции; так как $n$ исправлено, мы используем это как сокращение для «атака занимает $c2^{n/2}$ операции, для некоторых $с$ недалеко от 1 и некоторое разумное определение операции (в данном случае оценка хеш-функции).

Проблема с этим определением заключается в том, что оно приводит к некоторым абсурдным выводам, например, SHA-256, усеченный до 8 бит, является «устойчивым к коллизиям» по этому определению. С другой стороны, вывод SHAKE-256 объемом 1 кбайт не является «устойчивым к коллизиям», потому что вы можете найти коллизии с гораздо меньшим, чем $2^{8192/2}$ хеш-оценки.

Напротив, подход 2 использует определение «хэш-функция устойчива к коллизиям, если мы не можем найти коллизию». Выразить это формально немного сложно (поскольку входные данные могут быть длиннее выходных, должны быть коллизии, мы просто не знаем, что они собой представляют), а также потому, что это связано с вычислительными ресурсами. у нас есть (прямо сейчас SHA-256, усеченный до 200 бит, устойчив к коллизиям; возможно, это произойдет не через 20 лет, когда мы получим больше вычислительной мощности); с другой стороны, это ближе к интуитивному понятию «устойчивости к столкновениям», которое у нас есть.

При таком определении подход 2 можно было бы переформулировать так: «если мы предположим, $H'$ не устойчив к столкновению, то мы знаем $х\не у$ с $Н'(х) = Н'(у)$. Тогда либо $h_2(x) = h_2(y)$ (и, следовательно $h_2$ не устойчив к столкновению, поскольку мы знаем столкновение), или $h_2(x) \ne h_2(y)$, и в этом случае имеем $h_1(u) = h_1(v)$ за $u = h_2(x), v = h_2(y), u \ne v$ (и, следовательно $h_1$ не является устойчивым к столкновению, поскольку мы знаем столкновение).

John St avatar
флаг id
Означает ли это, что оба подхода допустимы, но включают разные определения устойчивости к столкновениям?
poncho avatar
флаг my
@JohnSt: на самом деле, я думал, что ясно дал понять, что не думаю, что определение в подходе 1 действительно настолько верно; однако, пока вы понимаете проблемы, вы можете принять собственное решение
John St avatar
флаг id
Ясно, спасибо за ваше объяснение, я был на борту корабля сближения 2 с самого начала, поэтому я буду использовать его на случай, если это проявится на экзамене, а также укажу, какое определение сопротивления столкновению я буду использовать.
Рейтинг:0
флаг id

У меня была возможность спросить моего профессора, и он ожидал первого решения, поскольку второе предполагает $ n_1 = n_2 $ (я до сих пор не знаю, почему и где это делается).

Он также объяснил, что:

  • а $n_2$ из 1000 бит, который затем преобразуется в $n_1$ из 2 бит считается устойчивым к коллизиям, поскольку вы используете полную безопасность, которую обеспечивают 2 бита, т. е. вы получаете все значение, за которое вы «заплатили» 2 бита.
  • Напротив, $n_2$ из 500 бит, который затем преобразуется в $n_1$ 1000 бит не считается устойчивым к коллизиям, поскольку вы «платите» за 1000 бит безопасности и используете только 500.

Это действительно помогло мне понять концепцию интуитивно и логично.

poncho avatar
флаг my
Итак, он утверждает, что хеш-функция с 2-битным выходом может быть «устойчивой к коллизиям»? Извините, но это серьезно противоречит моему пониманию того, что означает "сопротивление столкновениям"...
poncho avatar
флаг my
Чем больше я думаю об этом, тем меньше смысла имеет определение профессора. Мы определяем термины не потому, что нам нравится придумывать определения, а потому, что эти определения полезны. Мое определение устойчивости к столкновению (мы не знаем о столкновении и не знаем практического способа его обнаружения) подходит в качестве предположения безопасности для различных доказательств безопасности вещей, связанных с хеш-функциями. Напротив, я не могу придумать единственного применения для «для этой 2-битной хеш-функции мы не можем найти коллизию, не выполняя хэш-оценки $\sqrt{2^2}$»
John St avatar
флаг id
Я понимаю, что определение сопротивления столкновению - это скорее критерий реализации. Например, 2-битная функция реализована таким образом, чтобы обеспечить максимально возможное сопротивление для ее выходной длины. Является ли конечный продукт достаточным и имеет достаточную устойчивость к столкновениям (на основе потребностей, а не определения) - это другой вопрос.
John St avatar
флаг id
Тем не менее, я согласен, что определение немного своеобразное и вводящее в заблуждение.
John St avatar
флаг id
Примером использования этого определения является реализация любой функции $H'$, состоящей из нескольких функций, для максимально полного использования безопасности соответствующих функций. (т.е. вы не можете сломать его проще, затормозив внутреннюю функцию, которая является его частью)

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.