Ща темку тебе интересную покажу…

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

То есть для каждого нового файла, оно считает MD5 и ищет его в базе, если такого хеша нет, значит файл новый.

Звучит пиздец банально. Ну дак вот.

В какой-то момент ты обнаруживаешь 2 файла, с разным содержимым, но с одним и тем же хешем. Да ёб твоб мать! А как такое возможно?

Возможно!

MD5 ― это криптографическая хеш-функция, придуманная в 1991 году Рональдом Ривестом. Её задача — брать произвольные данные и сжимать их в 128-битное число (32 hex-символа).

Как эта поебота работает описывать не буду, если интересно погугли, там это уже на 100500 разжевали и в рот положили.

Вернемся к баранам:

Создаём пару текстовых файлов:

printf 'TEXTCOLLBYfGiJUETHQ4hAcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak' > a.txt

printf 'TEXTCOLLBYfGiJUETHQ4hEcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak' > b.txt

Содержимое отличается одним символом (22 символ): В a.txt это A (ASCII 65, 0x41), в b.txt — E (ASCII 69, 0x45).

Проверим, что так оно и есть:

xxd -g 1 a.txt | sed -n '1,2p'
xxd -g 1 b.txt | sed -n '1,2p'

xxd создаёт представление указанного файла или данных, прочитанных из потока стандартного ввода, в виде шестнадцатеричных кодов.

Либо сразу выводим различия:

cmp -l a.txt b.txt

22 101 105

• 22 → позиция (22-й байт в файле)
• 101 (восьмеричное) → 0o101 = 65 (десятичное) = 0x41 = 'A'
• 105 (восьмеричное) → 0o105 = 69 (десятичное) = 0x45 = 'E'

cmp — утилита, которая сравнивает два файла побайтово и сообщает о первом отличии, если оно есть.

Ага, видим разницу.

Едем дальше, считаем MD5:

md5sum a.txt b.txt

И видим:

faad49866e9498fc1719f5289e7a0269  a.txt
faad49866e9498fc1719f5289e7a0269  b.txt

Вот это нихуясебе! Наверное md5sum гличнулся…

Проверяем по другому:

openssl dgst -md5 a.txt b.txt

MD5(a.txt)= faad49866e9498fc1719f5289e7a0269
MD5(b.txt)= faad49866e9498fc1719f5289e7a0269

Да нет, все правильно… Хеш одинаковый для разных файлов.

И что это всё значит?

Это наглядная коллизия и практическая атака на MD5 алгоритм.

На первый взгляд кажется, что «достаточно поменять один байт и можно случайно попасть в коллизию». Но на деле случайно это практически невозможно провернуть (вероятность ≈ 1 к 2^128).

То, что я показал в примере с A → E — это синтетическая пара, созданная криптографами специально с использованием дифференциального криптоанализа MD5.

То есть кто-то заранее просчитал, какой именно байт нужно поменять, чтобы скомпенсировать все внутренние изменения в состояниях MD5.

Практическая атака (2004–2008)

• В 2004 году Ван Сяоюнь с коллегами показали первую реальную коллизию для MD5 за считанные часы.
• В 2008 году был создан поддельный сертификат SSL с использованием MD5-коллизии (огромный скандал).

Вот с тех пор MD5 окончательно считается небезопасным.

Коллизии можно находить и создавать целенаправленно, поэтому не рекомендую использовать MD5 для проверки целостности, подписей, сертификатов и т.п.

Для этих задач лучше бери проверенный SHA-256 или что-то посильнее.

Вот такие пироги. Изучай!

Комментарии