Блог

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

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

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

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

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

• Устойчивость к прообразам: учитывая 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. Что касается коллизий, это относится к атаке на день рождения: в принципе, как только вы накопили около пар ввода / вывода ), вероятность того, что две из этих пар будут иметь одинаковый результат, возрастает довольно быстро.

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

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

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

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

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

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