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

Предположим, что есть две устойчивые к коллизиям хэш-функции. $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$ не имеет значения.

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

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

В первой попытке используется определение «нет присоединения для обнаружения столкновений, которое занимает меньше, чем $\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$ не является устойчивым к столкновению, поскольку мы знаем столкновение).