Рейтинг:2

Существует ли квантовый алгоритм для поиска коллизий SHA256?

флаг in

Насколько я понимаю, сеть Биткойн можно рассматривать как суперкомпьютер ищет коллизии SHA256. Он еще не нашел ни одного (март 2022 г.). Кроме того, в эпоху постквантовой криптографии вы сможете реверсировать хэши SHA256.

Но в случае обнаружения хэш-коллизий, есть ли уже предложенный алгоритм?

poncho avatar
флаг my
«Кроме того, в эпоху постквантовой криптографии вы сможете реверсировать хэши SHA256» — не могли бы вы рассказать об этом — если вы знаете квантовый алгоритм, который может реально вычислять прообразы хэшей SHA256, это было бы большой новостью (и в любом случае, если вы можете вычислить прообразы SHA256, найти коллизии легко...)
fgrieu avatar
флаг ng
Вы можете видеть в биткойнах то, что хотите, но нет, это не поиск коллизий SHA-256. Он генерирует значения SHA-256, которые могут конфликтовать. Но он рассматривает только мелкую дробь с некоторым редким произвольным свойством и отбрасывает все остальные, в которых наиболее вероятны коллизии (если таковые имеются). Что правда, так это то, что он все еще довольно далек от того, чтобы сгенерировать достаточное количество SHA-256, чтобы коллизия в любом случае была вероятной, поэтому не имеет значения, что она _не_ ищет коллизии.
Рейтинг:4
флаг sa

В 2009 году DJ Bernstein написал одну из первых статей на эту тему. доступна здесь:

В аннотации указано:

Текущие предложения по аппаратному обеспечению факторизации специального назначения станет устаревшим, если будут построены большие квантовые компьютеры: решето числового поля масштабируется гораздо хуже, чем квантовый алгоритм Шора для факторизация. Станет ли все специализированное криптоаналитическое оборудование устарели в постквантовом мире? Квантовый алгоритм Брассарда, Хойера и Тэппа часто заявлено о снижении стоимости $b$-битовые хеш-коллизии от $2^{b/2}$ к $2^{b/3}.$ В этой статье анализируется алгоритм Брассарда — Хейера — Таппа и показывается, что у него принципиально худшее соотношение цена-качество, чем у классического схемы хеш-коллизии ван Оршота-Винера, даже при оптимистичных предположениях относительно скорости квантовых компьютеров.

Совсем недавно Хосоямада и Сасаки сообщили о частичном прогрессе в CRYPTO 2021 в версиях SHA-256 и SHA-512 с уменьшенным числом раундов, см. здесь; также может быть общедоступная версия на сервере препринтов iacr.org. Редактировать: Слайды и разговор доступны здесь

В аннотации указано:

В этой статье мы впервые изучаем специализированные атаки квантовых столкновений на SHA-256 и SHA-512. Атаки достигают 38 и 39 шагов соответственно, что значительно улучшает классические атаки на 31 и 27 шагов. Обе атаки используют структуру предыдущей работы, которая преобразует множество столкновений с полусвободным запуском в столкновение с двумя блоками и быстрее, чем обычная атака, в метрике стоимости компромисса между временем и пространством. Мы наблюдаем, что количество требуемых полусвободных столкновений может быть уменьшено в квантовой настройке, что позволяет нам преобразовать предыдущие классические 38- и 39-ступенчатые полусвободные столкновения в столкновение. Идея наших атак проста и применима и к другим криптографическим хеш-функциям.

kelalaka avatar
флаг in
Алгоритм Брассарда и др. требует $\приблизительно 2^{85}$-времени и -пространства, что делает его невозможным в пространстве. Да, уменьшенная версия может быть быстрее, чем классические атаки, однако раунды всегда проблематичны.

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.