Насколько легко подделать файл, хешированный тремя функциями: CRC32, MD5 и SHA-1?

Файл-A хэшируется с помощью CRC32, MD5 и SHA-1.

Насколько легко создать фальшивый файл-B, который имеет те же хэши, что и файл-A? CRC32, MD5 и SHA-1?

Может ли средний ПК с графическим процессором вычислить тройную коллизию хэшей файла-А? И сколько времени это займет?

Насколько легко создать поддельный файл-b с теми же хэшами, что и файл-а? crc32, md5 и sha1?

В криптографических кругах это известно как проблема «второго прообраза».

С CRC32 это просто; просто возьмите исходное сообщение и добавьте (то есть xor) несколько смещенных копий полинома CRC, и это не изменит хэш. Если у вас нет исходного файла-а (у вас есть только хеш), то создание файла-b потребует одновременного решения 32 логических уравнений, что лишь немного сложнее.

С MD5 и SHA-1 нет известного практического способа. В обоих случаях лучший подход, который у нас есть, состоит в том, чтобы попробовать огромное количество произвольных файлов-b, пока мы не наткнемся на один с ожидаемым хешем — это невыполнимый объем работы в обоих случаях.

Что известно о MD5 и SHA-1, так это о том, как создать два разных файла с одним и тем же хэшем. Однако эти методы требуют возможности указать оба файла и не применяются, если один из файлов уже задан.

Может ли средний компьютер с графическим процессором вычислить тройное столкновение хэшей файла-а?

Неизвестно, как это сделать (на практике, например, до того, как солнце превратится в красного гиганта...)

Как пишет poncho, мы не знаем, как практически найти второй прообраз для SHA1 или MD5, не говоря уже о том, чтобы он совпадал с обоими.

Однако мы знаем, как находить столкновения. Из-за особенностей конструкции MD мы можем легко преобразовать коллизии в множественные коллизии. Это означает, что мы можем создать много сообщений, которые будут конфликтовать, так много, что мы можем создать много коллизий SHA-1 (более широкий хеш) и получить остальные с помощью атаки на день рождения. как описано здесь: Насколько сложно создать одновременную коллизию MD5 и SHA1?

Таким образом, второй прообраз этих троих кажется нам неподвластным. Но коллизия SHA-1 и MD5 будет стоить $2^{67}$ операции. Мы можем сделать это снова 16 раз, чтобы построить множественное столкновение для обоих. и найти коллизию также для CRC32 (или любого 32-битного хеша, даже сильного). Это составит общую стоимость $2^{71}$ для создания двух сообщений, которые сталкиваются во всех трех хэшах. Но это будет, когда злоумышленник выбирает оба сообщения, а не одно из них. Это далеко за пределами возможностей одного мощного ПК, но не за пределами возможностей национального государства или мегакорпорации.