Википедия определяет вторую атаку прообразом как:
учитывая фиксированное сообщение m1, найдите другое сообщение m2, такое что hash (m2) = hash (m1).
Википедия определяет атаку столкновением как:
найдите два произвольных разных сообщения m1 и m2, таких что hash (m1) = hash (m2).
Единственное отличие, которое я вижу, состоит в том, что во второй атаке с прообразом m1 уже существует и известен атакующему. Однако это не кажется мне значительным - конечная цель по-прежнему состоит в том, чтобы найти два сообщения с одинаковым хешем.
Каковы существенные различия в том, как осуществляется вторая атака прообраз и атака столкновений? Каковы различия в результатах?
(Кроме того, я не могу пометить этот вопрос должным образом. Я пытаюсь применить теги «криптографическая безопасность перед столкновением изображений», но у меня недостаточно репутации. Может кто-то применить соответствующие теги?)
источник
Ответы:
Я могу мотивировать разницу для вас сценариями атаки.
В первой атаке прообраза мы просим противника, учитывая только , найти m или некоторый m ′ такой, что H ( m ′ ) = H ( m ) . Предположим , что веб - сайт магазинов { ¯u сек е р п а м е , Н ( р ы с ш о г d ) } в вместо его баз данных { ¯u сек еЧАС( м ) м м' ЧАС( м') ЧАС( м ) { У ев е т п м е , Н( Р ы ы ш о г д) } . Веб-сайт все еще может проверить подлинность пользователя, приняв его пароль и сравнив H ( i n p u t ) = ? Н ( р ы ы ш о г д ) (с вероятностью 1 / 2 л в течение некоторого большого п для ложных срабатываний). Теперь предположим, что эта база данных утечка или иным образом компрометируется. { U сек й г п м е , р ы ы ш о г д} ЧАС( Я п р у т ) = ? ЧАС( Р ы ы ш о г д) 1 / 2N N Первая атака с прообразом - это ситуация, когда злоумышленник имеет доступ только к дайджесту сообщения и пытается сгенерировать сообщение, хэширующее с этим значением.
Во второй атаке прообраз , мы даем противнику больше информации. В частности, мы не только даем ему но и даем ему 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 d м'= m p q+ м . И вот противник обнаружил столкновение практически без вычислений.ЧАС( м р д+ м ) = ( м р д+ м )dмодификацияр д= мdмодификацияр д
Мы хотели бы, чтобы односторонние хэш-функции были устойчивы к второстепенным атакам из-за схем цифровой подписи, и в этом случае считается общедоступной информацией и передается (через уровень косвенности) с каждой копией документа. Здесь злоумышленник имеет доступ как к и к . Если злоумышленник может предложить вариант исходного документа (или совершенно новое сообщение) такой, что он может опубликовать свой документ, как если бы он был исходным подписавшим.д о с у м е н т Н ( д о с у м е н т ) д ' Н ( д ' ) = Н ( д о с у м е н т )ЧАС( до с у м е н т ) document ЧАС( до с у м е н т ) d' ЧАС( д') = H( до с у м е н т )
Атака столкновения позволяет Противнику еще больше возможностей. В этой схеме мы просим противника (могу ли я назвать его Бобом?) Найти любые два сообщения и такие что . Из-за принципа «голубиных отверстий» и парадокса дня рождения даже «идеальные» хэш-функции квадратично слабее для атак коллизий, чем атаки прообразов. Другими словами, с учетом непредсказуемой и необратимой функции дайджеста сообщений которой для грубой силы требуется времени, столкновение может всегда можно найти в ожидаемое время .м 2 Н ( м 1 ) = Н ( м 2 )м1 м2 ЧАС( м1) = H( м2) O ( 2 n ) O ( s q r t ( 2 n ) ) = O ( 2 н / 2 )е( { 0 , 1 }*) = { 0 , 1 }N O ( 2N) O ( s qт т ( 2N) ) = O ( 2н / 2)
Боб может использовать столкновительную атаку в своих интересах разными способами. Вот одно из самых простых: Боб обнаруживает коллизию между двумя двоичными файлами и ( ), так что b является допустимым исправлением безопасности Microsoft Windows, а является вредоносным ПО. (Боб работает для Windows). Боб посылает свое исправление безопасности по цепочке команд, где за хранилищем они подписывают код и отправляют двоичный файл пользователям Windows по всему миру, чтобы исправить ошибку. Теперь Боб может связываться и заражать все компьютеры Windows по всему миру с помощью и подписи, которую Microsoft вычислила дляб б' ЧАС(b)=H(b′) b′ b′ b , Помимо сценариев атак такого рода, если считается, что хеш-функция устойчива к столкновениям, эта хеш-функция также с большей вероятностью будет устойчивой к прообразам.
источник
Атаки со столкновением могут быть намного проще, но в случае успеха гораздо менее полезными.
источник
Проблема, которую Росс упоминает как проблему дискретного журнала, на самом деле является совершенно другой проблемой, проблемой RSA, которая гораздо больше связана с вычислительными корнями, чем с дискретным журналом.
источник