В чем разница между слабым и сильным сопротивлением

Ответ 1

Слабое свойство сопротивления столкновению иногда также называют вторым сопротивлением прообразованию:

Для произвольного x не существует x 'с x'!= x, так что h (x) = h (x ')

Сильное сопротивление столкновению, с другой стороны, определяется как:

Нет x и x 'с x!= x', так что h (x) = h (x ')

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

Слабое сопротивление столкновению

Хорошим примером того, что нас действительно интересует только слабое сопротивление столкновению, будет простая схема хранения паролей. Предположим, мы храним пользовательские пароли в базе данных, сохраняя их хэш. Аутентификация будет успешной, если хэш некоторого пароля, который пользователь предоставляет, равен значению, которое было сохранено ранее (это, по сути, небезопасная схема, но, пожалуйста, несите меня на данный момент). Теперь в этом случае данный x является (неизвестным) исходным паролем, который был предоставлен ранее. Если злоумышленник мог эффективно решить проблему "второго прообраза" , он мог бы получить х ', чье хеш-значение такое же, как у исходного х, и, таким образом, будет успешно завершено. Обратите внимание, что возможность создания произвольных коллизий (т.е. Решение сильной проблемы столкновения) бесполезна вообще в этом сценарии, потому что не слишком вероятно, что x и x 'получаются похожими на фактические пароли, чьи хэши уже хранятся в базе данных.

Сильное сопротивление столкновению

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

Связь между

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

Рассмотрим хеш-функцию h и этот простой вероятностный алгоритм [1]:

Пусть 2ndPreimage - еще один вероятностный (e, Q) -алгоритм, который решает "второй прообраз" для хэш-функции h.

Choose x uniformly at random
value = 2ndPreimage(h, x)
case value == failure -> return failure
case value == x' (!= x) -> return (x, x')

Легко видеть, что это также (e, Q) -алгоритм, который решает проблему сильного столкновения. Это означает, что, учитывая, что у нас есть алгоритм для решения "второго прообраза" , мы также можем использовать этот алгоритм, который может вызвать столкновение. Поскольку мы не делали никаких предположений о базовой хеш-функции h, теперь мы можем с уверенностью сказать, что

Сильное сопротивление столкновению подразумевает слабое сопротивление столкновению, но противоположное не обязательно выполняется.

[1] e - вероятность успеха алгоритма, 0 <= e < 1. Q - максимальное количество запросов оракула (т.е. "Оценки" алгоритма). В случае успеха алгоритм возвращает действительное решение, иначе оно возвращает значение, указывающее на сбой.

Ответ 2

Я написал этот ответ из-за комментария Александра; Все определения скопированы с; Основы криптографической хэш-функции: определения, последствия и разделения для сопротивления прообразу, сопротивления второго прообраза и сопротивления столкновениям - П. Рогвей и Т. Шримптон.

• preimage -istance - по существу для всех предварительно заданных выходов в вычислительном отношении невозможно найти любой вход, который хэширует к этому выходу, т.е. найти любой прообраз x' такой, что h(x') = y, когда ему дан любой y, для которого a соответствующий ввод неизвестен.
• Сопротивление 2-го прообраза, слабое коллизия - в вычислительном отношении невозможно найти любой второй вход, который имеет тот же выход, что и любой указанный вход, т.е. с учетом x, чтобы найти 2-е прообраз x' != x, такой, что h(x) = h(x').
• сопротивление столкновению, сильное коллизия - в вычислительном отношении невозможно найти любые два различных входа x, x', которые хэшируют на один и тот же выход, т.е. такие, что h(x) = h(x').

Факт 1: сопротивление столкновению подразумевает сопротивление второму прообразу хеш-функций.

Факт 2: Сопротивление второго изображения подразумевает сопротивление прообразу.

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