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

24

Википедия определяет вторую атаку прообразом как:

учитывая фиксированное сообщение m1, найдите другое сообщение m2, такое что hash (m2) = hash (m1).

Википедия определяет атаку столкновением как:

найдите два произвольных разных сообщения m1 и m2, таких что hash (m1) = hash (m2).

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

Каковы существенные различия в том, как осуществляется вторая атака прообраз и атака столкновений? Каковы различия в результатах?

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

Томас Оуэнс
источник
1
Ваше впечатление правильное - в этом разница. Часть, где вы ошибаетесь, заключается в том, что это ОГРОМНОЕ различие на практике. Одно дело уметь находить любые две вещи, у которых есть столкновение, и совсем другое - уметь находить столкновение для определенного открытого текста. Например, если вы хотите подделать определенное сообщение, бесполезно иметь возможность совершать экзистенциальную подделку - вам нужно другое сообщение, которое хэшируется на ту же вещь, что и сообщение, которое вы перехватили.
Адриан Петреску
@Adrian Petrescu: Не могли бы вы дать ответ и, возможно, подробнее остановиться на нем? Добавьте такие вещи, как, например, когда каждый (вы предоставляете ситуацию для атаки прообразом, но не для атаки столкновением) лучше всего подходит?
Томас Оуэнс

Ответы:

27

Я могу мотивировать разницу для вас сценариями атаки.

В первой атаке прообраза мы просим противника, учитывая только , найти m или некоторый m такой, что H ( m ) = H ( m ) . Предположим , что веб - сайт магазинов { ¯u сек е р п а м е , Н ( р ы с ш о г d ) } в вместо его баз данных { ¯u сек еЧАС(м)мм'ЧАС(м')ЧАС(м){UsерNaме,ЧАС(пassвесорd)} . Веб-сайт все еще может проверить подлинность пользователя, приняв его пароль и сравнив H ( i n p u t ) = ? Н ( р ы ы ш о г д ) (с вероятностью 1 / 2 л в течение некоторого большого п для ложных срабатываний). Теперь предположим, что эта база данных утечка или иным образом компрометируется. {UsерNaме,пassвесорd}ЧАС(яNпUT)знак равно?ЧАС(пassвесорd)1/2NNПервая атака с прообразом - это ситуация, когда злоумышленник имеет доступ только к дайджесту сообщения и пытается сгенерировать сообщение, хэширующее с этим значением.

Во второй атаке прообраз , мы даем противнику больше информации. В частности, мы не только даем ему но и даем ему m . Рассмотрим хеш-функцию H ( m ) = m dЧАС(м)м где p и q - большие простые числа, а d - открытая постоянная. Очевидно, что дляпервой атаки прообразэто становится проблемой RSA и считается трудным. Тем не менее, в случаевторой прообразной атакиобнаружение столкновения становится легким. Если задать m = m p q + m , H ( m p q + m ) = ( m p q + m ) dЧАС(м)знак равномdмодификацияпQпQdм'знак равномпQ+м . И вот противник обнаружил столкновение практически без вычислений.ЧАС(мпQ+м)знак равно(мпQ+м)dмодификацияпQзнак равномdмодификацияпQ

Мы хотели бы, чтобы односторонние хэш-функции были устойчивы к второстепенным атакам из-за схем цифровой подписи, и в этом случае считается общедоступной информацией и передается (через уровень косвенности) с каждой копией документа. Здесь злоумышленник имеет доступ как к и к . Если злоумышленник может предложить вариант исходного документа (или совершенно новое сообщение) такой, что он может опубликовать свой документ, как если бы он был исходным подписавшим.д о с у м е н т Н ( д о с у м е н т ) д ' Н ( д ' ) = Н ( д о с у м е н т )ЧАС(dосUмеNT)documenTЧАС(dосUмеNT)d'ЧАС(d')знак равноЧАС(dосUмеNT)

Атака столкновения позволяет Противнику еще больше возможностей. В этой схеме мы просим противника (могу ли я назвать его Бобом?) Найти любые два сообщения и такие что . Из-за принципа «голубиных отверстий» и парадокса дня рождения даже «идеальные» хэш-функции квадратично слабее для атак коллизий, чем атаки прообразов. Другими словами, с учетом непредсказуемой и необратимой функции дайджеста сообщений которой для грубой силы требуется времени, столкновение может всегда можно найти в ожидаемое время .м 2 Н ( м 1 ) = Н ( м 2 )м1м2ЧАС(м1)знак равноЧАС(м2) O ( 2 n ) O ( s q r t ( 2 n ) ) = O ( 2 н / 2 )е({0,1}*)знак равно{0,1}NО(2N)О(sQрT(2N))знак равноО(2N/2)

Боб может использовать столкновительную атаку в своих интересах разными способами. Вот одно из самых простых: Боб обнаруживает коллизию между двумя двоичными файлами и ( ), так что b является допустимым исправлением безопасности Microsoft Windows, а является вредоносным ПО. (Боб работает для Windows). Боб посылает свое исправление безопасности по цепочке команд, где за хранилищем они подписывают код и отправляют двоичный файл пользователям Windows по всему миру, чтобы исправить ошибку. Теперь Боб может связываться и заражать все компьютеры Windows по всему миру с помощью и подписи, которую Microsoft вычислила длябб'H(b)=H(b)bbб, Помимо сценариев атак такого рода, если считается, что хеш-функция устойчива к столкновениям, эта хеш-функция также с большей вероятностью будет устойчивой к прообразам.

Росс Снайдер
источник
Это прекрасно объяснено. Намного больше математики, чем я искал, но я очень ценю это усилие - я следовал за тобой до конца. Спасибо.
Томас Оуэнс
И вау. Одноклассник РИТ.
Томас Оуэнс
1
Как дела Томас? Я думаю, что у вас была физика с моим другом Аланом Микинсом. Рад видеть RIT людей здесь! Также спасибо за то, что приняли ответ.
Росс Снайдер
Вполне нормально. Если вы собираетесь быть в кампусе осенью и заинтересованы в безопасности, возможно, мы сможем наверстать упущенное лично. Этим летом я занимался прикладной защитой (применяя стенографию, стеганализацию, шифрование с открытым ключом, цифровые подписи) и хотел бы услышать о теоретической стороне (насколько мне это интересно - у меня нет время или математический фон, чтобы пройти через много статей по этому вопросу).
Томас Оуэнс
rws1236@cs.rit.edu
Росс Снайдер
2

Атаки со столкновением могут быть намного проще, но в случае успеха гораздо менее полезными.

Юкка Суомела
источник
1

Проблема, которую Росс упоминает как проблему дискретного журнала, на самом деле является совершенно другой проблемой, проблемой RSA, которая гораздо больше связана с вычислительными корнями, чем с дискретным журналом.


источник
2
Это, безусловно, правда! К сожалению. Первоначально я использовал проблему дискретного журнала, а затем отредактировал детали схемы. Хороший улов. Не уверен, что это составляет новый ответ - было бы, вероятно, более уместно оставить как комментарий под моим ответом.
Росс Снайдер