Атака прообраза

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

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

сопротивление прообразу : практически для всех заранее заданных выходных данных вычислительно невозможно найти какой-либо входной сигнал, который хеширует этот выходной результат; т.е., учитывая $y$ , трудно найти $x$ такой, что $h (x) = y$ . ^{[ 1 ]}
сопротивление второго прообраза : для указанного входа вычислительно невозможно найти другой вход, который дает тот же результат; т. е. при заданном $x$ трудно найти второй входной сигнал $x' \neq x$ такой, что $h (x) = h (x')$ . ^{[ 1 ]}

Их можно сравнить с сопротивлением столкновению , при котором вычислительно невозможно найти любые два различных входных сигнала $x$ , $x',$ которые хэшируют один и тот же выходной сигнал; то есть такой, что $час (Икс) знак равно час (Икс')$ . ^{[ 1 ]}

Устойчивость к столкновениям подразумевает устойчивость ко второму прообразу. Сопротивление второму прообразу подразумевает сопротивление прообразу только в том случае, если размер входных данных хеш-функции может быть существенно (например, в 2 раза) больше, чем размер выходных данных хеш-функции. ^{[ 1 ]} И наоборот, атака по второму прообразу подразумевает атаку коллизией (тривиально, поскольку, помимо $x'$ , $x$ уже известен с самого начала).

Примененные атаки на прообразы

По определению, идеальная хэш-функция такова, что самый быстрый способ вычислить первый или второй прообраз — это атака методом перебора . Для $n$ -битного хеша эта атака имеет временную сложность $2. н$ , что считается слишком большим для типичного выходного размера $n$ = 128 бит. Если такая сложность — лучшее, чего может достичь злоумышленник, то хеш-функция считается устойчивой к прообразу. Однако есть общий результат: квантовые компьютеры выполняют атаку структурированного прообраза в ${\sqrt {2^{n}}}=2^{\frac {n}{2}}$ , что также подразумевает второй прообраз ^{[ 2 ]} и, таким образом, столкновение.

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

Все известные на данный момент практические или почти практические атаки. ^{[ 3 ]}^{[ 4 ]} на MD5 и SHA-1 являются коллизионными атаками . ^{[ 5 ]} В общем, атаку столкновением легче организовать, чем атаку прообраза, поскольку она не ограничена каким-либо заданным значением (для столкновения можно использовать любые два значения). Временная сложность атаки перебором столкновений, в отличие от атаки прообраза, составляет всего $2^{\frac {n}{2}}$ .

Ограниченные космические атаки прообразов

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

Типичным примером является использование хешей для хранения данных проверки пароля для аутентификации. Вместо хранения открытого текста паролей пользователей система контроля доступа хранит хэш пароля. Когда пользователь запрашивает доступ, отправленный им пароль хешируется и сравнивается с сохраненным значением. Если сохраненные данные проверки будут украдены, у вора будут только хэш-значения, а не пароли. Однако большинство пользователей выбирают пароли предсказуемым образом, и многие пароли достаточно коротки, чтобы можно было протестировать все возможные комбинации при использовании быстрых хэшей, даже если хэш имеет рейтинг защищенности от атак на прообразы. ^{[ 6 ]} специальные хеши, называемые функциями получения ключей Для замедления поиска были созданы . См. раздел «Взлом пароля» . Чтобы узнать о методе предотвращения проверки коротких паролей, см. соль (криптография) .

См. также

Атака на день рождения
Криптографическая хэш-функция
Сводка безопасности хеш-функции
Дружелюбие к головоломкам
Радужный стол
Случайный оракул
RFC 4270 : Атаки на криптографические хэши в интернет-протоколах

Ссылки

^ Jump up to: ^а ^б ^с ^д Рогауэй, П.; Шримптон, Т. (2004). «Основы криптографических хеш-функций: определения, последствия и разделение устойчивости к прообразу, устойчивости к второму прообразу и устойчивости к столкновениям» (PDF) . Быстрое программное шифрование . Конспекты лекций по информатике. Том. 3017. Шпрингер-Верлаг. стр. 371–388. дои : 10.1007/978-3-540-25937-4_24 . ISBN 978-3-540-22171-5 . Проверено 17 ноября 2012 г.
^ Дэниел Дж. Бернштейн (12 ноября 2010 г.). «Квантовые атаки на Blue Midnight Wish, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Shabal, SHAvite-3, SIMD и Skein» (PDF) . Университет Иллинойса в Чикаго . Проверено 29 марта 2020 г.
^ Брюс Мортон; Клейтон Смит (30 января 2014 г.). «Почему нам нужно перейти на SHA-2» . Совет безопасности центра сертификации .
^ «Блог Google Online Security: объявляем о первой коллизии SHA1» . Проверено 23 февраля 2017 г.
^ «MD5 и перспективы» . 01 января 2009 г.
^ Гудин, Дэн (10 декабря 2012 г.). «Кластер из 25 графических процессоров взламывает любой стандартный пароль Windows менее чем за 6 часов» . Арс Техника . Проверено 23 ноября 2020 г.

[crypto-hash-def-1] Jump up to: ^а ^б ^с ^д Рогауэй, П.; Шримптон, Т. (2004). «Основы криптографических хеш-функций: определения, последствия и разделение устойчивости к прообразу, устойчивости к второму прообразу и устойчивости к столкновениям» (PDF) . Быстрое программное шифрование . Конспекты лекций по информатике. Том. 3017. Шпрингер-Верлаг. стр. 371–388. дои : 10.1007/978-3-540-25937-4_24 . ISBN 978-3-540-22171-5 . Проверено 17 ноября 2012 г.

[2] Дэниел Дж. Бернштейн (12 ноября 2010 г.). «Квантовые атаки на Blue Midnight Wish, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Shabal, SHAvite-3, SIMD и Skein» (PDF) . Университет Иллинойса в Чикаго . Проверено 29 марта 2020 г.

[3] Брюс Мортон; Клейтон Смит (30 января 2014 г.). «Почему нам нужно перейти на SHA-2» . Совет безопасности центра сертификации .

[4] «Блог Google Online Security: объявляем о первой коллизии SHA1» . Проверено 23 февраля 2017 г.

[5] «MD5 и перспективы» . 01 января 2009 г.

[6] Гудин, Дэн (10 декабря 2012 г.). «Кластер из 25 графических процессоров взламывает любой стандартный пароль Windows менее чем за 6 часов» . Арс Техника . Проверено 23 ноября 2020 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]