Означает ли разбитая бумага Google (первое столкновение для полного SHA-1) создание нового файла с тем же хэшем, что и исходный файл?

У меня есть исходные данные A и хэш H (A) этого A. Возможно ли с помощью разрушенных документов Google создать новые данные B, которые выводят этот H (A)?

++ Я понял, что содержание статьи состоит в том, чтобы дополнить два блока сообщений, чтобы окончательное резюме было одинаковым. Метод, о котором я подумал, заключается в том, можно ли правильно найти M2 (2) «фиктивного файла», чтобы CV2 «исходного файла» и «фиктивного файла» выводились так же, как в методе 1 на фотографии, или сделать только CV2 таким же, как в Method2 через поиск новых M1(2), M2(2).

64-байтовый блок сообщения — это бессмысленные данные. Поэтому файл не должен открываться нормально.

Формат файла не ограничивается PDF.

Нет. То, что вы описали, было бы вторая атака предварительного изображения, тогда как команда Google произвела атаку столкновений. В разрушенном Статья Марка Стивенса и др. «Первое полное столкновение на SHA1». где эти состояния указаны в вашем методе 1, авторы сначала смогли одновременно выбрать $M_1^{(1)}$ и $M_1^{(2)}$ внося небольшие возмущения в одно или другое до тех пор, пока не будет найдена близкая пара значений $CV_1^{(1)}$ и $CV_1^{(2)}$ были произведены. В вашем сценарии $M_1^{(1)}$ будет исправлено и только $M_1^{(2)}$ можно отрегулировать, что значительно усложнит поиск близкого $CV_1$ ценности. Точно так же на втором этапе исследователи смогли возмутить оба $M_2^{(1)}$ и $M_2^{(2)}$ чтобы найти полное столкновение, но в вашем сценарии злоумышленник сможет только настроить $M_2^{(2)}$.

Разница в сложности этих задач такова, что поиск второго прообраза для SHA1, скорее всего, займет примерно $2^{160}$ оценки хэш-функции. Это сродни разнице между вероятность найти в комнате двух человек с одинаковым днем ​​рождения и вероятность найти в комнате кого-то с таким же днем ​​рождения, как у вас.

Более поздняя работа («SHA1 — это руины» Леурана и Пейрина.) показывает, что это возможно для злоумышленника, чтобы взять произвольный файл и добавить данные, которые они контролируют, как в ваш файл, так и в свой файл таким образом, чтобы получить одно и то же значение SHA1 для обоих файлов. Это известно как выбранный префикс-столкновение и это еще более убедительное доказательство того, что SHA1 нужно устареть.

NB: В вашей таблице байтовых значений левые и правые метки обозначены как $M_1^{(2)}$ и я вернулся к обозначению SHAttered paper. Я не уверен в источнике вашей второй таблицы.

Атака Shattered находит другой файл/сообщение B, который имеет тот же хэш SHA-1, что и файл/сообщение A, но только если какой-то раздел данных в A имеет характеристику, которая не может произойти случайно. Для большинства форматов файлов/семантики данных это по-прежнему допускает атаки злоумышленников, которые не могут изменить значение/внешний вид/эффект A, но могут незначительно повлиять на двоичное содержимое A.

У меня есть исходные данные A и хэш H (A) этого A. Возможно ли с помощью разрушенных документов Google создать новые данные B, которые выводят этот H (A)?

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

1. Да, без вычислительных усилий, если A начинается с одного из двух конкретных 320-байтовых значений, которые дала атака Shattered. Мы можем просто заменить одно на другое, чтобы сформировать B с тем же хешем SHA-1. Это можно (среди прочего) использовать для простого создания двух разных допустимых PDF-файлов с немного другим содержимым байтов и совершенно другим внешним видом.
2. Нет, если A меньше примерно 125 байт, при использовании метода Shattered paper, даже с их вычислительными затратами. Но мы должны снизить этот предел примерно до 19 байт, если мы изменим метод и примем увеличение вычислительных усилий в скромный раз (около 250 тысяч) примерно до $2^{81}$ Хэши SHA-1.
3. Да, с вычислительными усилиями Shattered, если противник может выбрать первые 128 байтов A. Это все еще атака Shattered, но она требует значительной работы. Мы можем снизить этот предел до 64 байт, если примем увеличение вычислительных усилий по сравнению с предыдущим пунктом.
4. Да, как расширение 3, если противник знает первое $n$ байтов A и может выбрать следующий $128+(-n\bmod 64)$ байт. И мы должны снизить это до $64+(-n\bmod 64)$ байт с повышенными вычислительными затратами. Это может быть дополнительно расширено до того, что противник выберет около 20 байт информации в любом первом $64\,f$ байтов А со знанием этого раздела А, и дальнейшее увеличение работы не более чем в $f$.
5. Да, как следствие 4, если A готовится способом, находящимся под контролем противника, т.е. если A является документом PDF, изображением PNG, изображением CD/DVD «ISO», возможно, исполняемым файлом, подготовленным с использованием инструментов, созданных злоумышленником. Информацию о цифровых сертификатах см. этот вопрос.
6. Нет, если A проходит тест, предоставленный авторами Shattered, и мы придерживаемся их метода атаки. Но их тест не может защитить от других атак сопоставимой стоимости, и ни один тест не может защитить от атак с незначительно увеличенной стоимостью.
7. Нет, если есть по крайней мере 64 бита энтропии в первых 64 байтах A, которые неизвестны злоумышленнику в то время, когда злоумышленник может влиять на A, для любых возможных вычислительных усилий. Это включает в себя случайный A и цифровые сертификаты, выпущенные центрами сертификации, которые принимают простые меры предосторожности, используя рандомизированные серийные номера в начале сертификата.

Я хочу убедиться, что формат файла не ограничивается PDF.

Атака и расширение Shattered не ограничиваются PDF, см. 3/4/5. Его можно перенести (с некоторыми усилиями) с любым форматом файла без какой-либо внутренней проверки избыточности; то есть большинство. Кроме того, префиксы, аналогичные 1 (специализированные для недорогой подделки PDF), могут быть разработаны для многих форматов, включая JPEG, PNG, GIF, MP4, JPEG2000, формат Portable Excutable и многих других, при этом значительная, но выполнимая работа должна быть выполнена только однажды. Префиксы 1 работают даже с некоторыми существующими форматами файлов, например. аудио и видео для плееров, которые пропускают то, что они не распознают (поскольку вопрос не спрашивает, что разные A и B ведут себя по-разному; этого было бы трудно добиться с префиксами 1 для чего-то не PDF, а стандартный плеер не создан для этой цели).

Если вы сомневаетесь: лучше перестраховаться, чем сожалеть, предположите, что да, атака возможна, и используйте непрерывный и значительно более широкий хэш, чем SHA-1.

(принцип) статьи состоит в том, чтобы дополнить два блока сообщений

Не совсем. это дополнено несколько битов в два последовательный блоков сообщений (каждый по 64 байта), содержимое которых выбирается (со значительной, но выполнимой работой) в зависимости от состояния хэша перед обработкой этих двух блоков сообщений. Следовательно, содержимое этих двух блоков сообщений в A не является произвольным, оно должно совпадать с этими мучительно вычисленными 128 байтами. Такое совпадение не произойдет случайно (например, для случайного A), оно требует некоторого контроля над A и знания состояния хэша перед хешированием этих двух блоков. Такое знание можно получить, зная часть сообщения А перед этими двумя блоками А, которые нужно выбрать, чтобы атака сработала.

Атака, которая работает для произвольного A, будет (второй) атакой прообраза. Такая атака не известна для SHA-1.