Разница между нарушением однонаправленного хеш-свойства _brute force_ и проверкой столкновения

Question

Для любой хэш-функции, концептуально говоря или иным образом, в чем разница между вышеупомянутыми 2 операциями. Я подошел к проблеме следующим образом:

H=hash(someplaintext)
n=0
while 1:
    if hash(str(n))==H:
        print n
    n+=1

Оба свойства могут быть доказаны таким образом, что-то не так? Игнорируйте эффективность, использование памяти или любое другое свойство. Пожалуйста, ответьте на мой вопрос, строго исходя из правильности

Answer 1

«Односторонний» означает, что при наличии функции output вы не можете найти соответствующий input , за исключением случаев, когда вы пробуете много потенциальных входов и получаете удачу.Столкновение связано с нахождением двух различных входных данных, которые дают одинаковый выходной сигнал, без каких-либо предварительно определенных ограничений для указанного выходного сигнала.

Существует три классических свойства, которые должна иметь хорошая (криптографическая) хеш-функция:

• Сопротивление прообразам: дано x , должно быть невозможно найти m такой, что h (m) = x .
• Сопротивление вторым прообразам: дано m , должно быть невозможно найти m ' отличных от m ,такой, что h (m) = h (m ') .
• Сопротивление столкновениям: должно быть невозможно найти m и m ', отличных друг от друга, так что h (m) = h (m') .

Это можно рассматривать как три задачи дляатакующий, отсортированный по убыванию сложности.Для прообразов я даю вам вывод и призываю вас найти соответствующий ввод.Для второго прообраза я даю вам вход (и неявно соответствующий выход) и призываю вас найти другой соответствующий вход.Для столкновений это похоже на второй вызов прообраза, за исключением того, что я не требую, чтобы вы находили конкретный результат;любой сделает.Или, если сформулировать это наоборот: вызов для второго прообраза подобен вызову для столкновения, в котором атакующее не может свободно выбрать одно из конфликтующих сообщений.

Без использования какой-либо слабости вСама хеш-функция, общие методы поиска прообразов, вторых прообразов и столкновений для хеш-функции с выводом n -бит, стоят примерно 2 ⁿ (для прообразов и вторых прорисовок) и 2 ^{n / 2} (для столкновений).Таким образом, обнаружение столкновений значительно проще.Для прообразов вы просто пробуете вводные данные, пока вам не повезет (это то, что вы называете "грубой силой");каждая попытка имеет вероятность 2 ^-n для успеха.Для столкновений это относится к атаке на день рождения : в основном, когда вы накопили около sqrt (2 ⁿ ) пар ввода / вывода, вероятность двуху тех пар, у которых одинаковый выходной сигнал, возрастает довольно быстро.

С точки зрения дней рождения, это означает, что если вы выбираете 20 человек случайным образом, высоки шансы, что у двух из них будет один и тот же день рождения, но вы этого не сделаетевыбрать какой день или людей.С другой стороны, если вы хотите найти кого-то с тем же днем ​​рождения, что и вас , то вам придется в среднем выбирать 365 человек.

Answer 2

Возможно, я неправильно понимаю ваш вопрос, но вот мое мнение:

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

\epsilon < \frac{1}{p(n)}

где p(n) обозначает многочлен в терминах n (простите за синтаксис латекса)

В вашем случае вы просто обнаружили коллизию, это не доказывает, что хеш-функция не является односторонней, поскольку вы просматриваете все возможности, то есть вы не нарушали условие 1 / p (n) .