Можно ли создать поддельный файл с одинаковыми контрольными суммами, используя два разных алгоритма?

— Это вообще возможно? - да, если общий размер контрольных сумм меньше, чем общий размер файла, избежать коллизий невозможно.

«Возможно ли это на самом деле с текущим оборудованием/программным обеспечением?» - если возможно построить текст, соответствующий заданной контрольной сумме для каждой из используемых контрольных сумм, то да.

См. Википедию о конкатенации криптографических хеш-функций, термин, который также можно найти в Google.

С этой страницы:

«Однако для хеш-функций Меркла-Дамгарда конкатенированная функция настолько же сильна, как и лучший компонент, а не сильнее. Жу отметил, что 2-коллизии приводят к n-коллизиям: если возможно найти два сообщения с одним и тем же хэшем MD5. , фактически не сложнее найти столько сообщений, сколько нужно злоумышленнику с идентичными хэшами MD5. Среди n сообщений с одним и тем же хэшем MD5, вероятно, будет коллизия в SHA-1. Дополнительная работа, необходимая для поиска Коллизия SHA-1 (за пределами экспоненциального поиска дня рождения) является полиномиальной. Этот аргумент резюмируется Финни».

Для наивного ответа нам пришлось бы сделать несколько (неправильных) предположений:

• Алгоритмы хеширования SHA1 и MD5 приводят к равномерному распределению хеш-значений для набора случайных входных данных.
• Оставим в стороне детали алгоритма — случайная входная строка имеет равные шансы получить любое значение хеш-функции.

(В принципе, никаких скоплений и хорошо распределенных доменов.)

Если вероятность обнаружения строки, которая конфликтует с хэшем другого SHA1, равна p1, и аналогично p2 для MD5, наивным ответом будет вероятность найти строку, которая конфликтует с обоими, равна p1*p2.

Однако оба хеша сломаны, поэтому мы знаем, что наши предположения неверны.

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

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

Поэтому я спросил себя, возможно ли создать файл A', который имеет тот же размер, ту же сумму md5 и ту же сумму sha1, что и исходный файл A.

Да, сделайте копию файла.

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

Вы можете думать об этом так:

Если размер файла увеличивается на n, вероятность возможной подделки увеличивается, но вычислительные затраты, необходимые для проверки комбинаций, увеличиваются экспоненциально на 2^n.

Таким образом, чем больше ваш файл, тем больше вероятность того, что найдется подделка, но тем меньше вероятность, что вы ее найдете.

Теоретически да, вы можете иметь это, на практике это адский сговор. На практике никто даже не смог создать сговор SHA1, не говоря уже о MD5 + SHA1 + Size одновременно. Эта комбинация просто невозможна прямо сейчас, не обладая всей мощью компьютера в мире и не запуская его какое-то время.

Хотя в ближайшем будущем мы можем увидеть больше уязвимостей в SHA1 и MD5. А при поддержке более качественного железа (особенно GPU) почему бы и нет.

Теоретически вы могли бы это сделать. На практике, если вы начнете с двух контрольных сумм, предоставленных MD5 и SHA1, и попытаетесь создать файл, который выдаст те же две контрольные суммы, это будет очень сложно (во много раз сложнее, чем создать файл, который выдаст ту же самую контрольную сумму MD5, или контрольная сумма SHA1 отдельно).