Коллизия хэшей
Что такое Коллизия хэшей?
Коллизия хэшейДва разных входа, дающих одинаковое значение криптографического хэша; ломает гарантии целостности, уникальности и подписи, зависящие от функции хэширования.
Коллизия хэшей — это пара разных входов, дающих одинаковый выход. Поскольку хэш-функции сжимают произвольные данные до фиксированной длины, коллизии существуют математически, но безопасный хэш делает их вычислительно недостижимыми. Общая граница дней рождения означает, что перебор коллизии стоит лишь около 2^(n/2) операций (2^128 для SHA-256), поэтому «сломанной» называют функцию, у которой математические сокращения резко снижают эту стоимость.
Важны два класса. Коллизия с одинаковым префиксом дописывает блоки к общему префиксу; куда опаснее коллизия с выбранным префиксом, которая стартует с двух произвольных осмысленных префиксов и всё равно совпадает — именно она подделывает сертификаты и ключи.
Реальные взломы: Wang и соавторы нашли практические коллизии MD5 в 2004 году; в 2008 году Sotirov, Stevens и др. создали поддельный сертификат УЦ, а в 2012 году шпионская вредоносная программа Flame применила новую коллизию MD5 с выбранным префиксом, чтобы подделать сертификат Microsoft Terminal Server Licensing и подписывать вредонос от имени Microsoft. SHA-1 пал под SHAttered от Google/CWI в 2017 году (около 2^63 работы), а затем под SHA-1 is a Shambles авторства Leurent и Peyrin в 2020 году, подделавшим сертификацию ключа PGP (GnuPG CVE-2019-14855, исправлено в 2.2.18).
Защита: отказаться от MD5 и SHA-1 для любого применения в безопасности и перейти на SHA-256, SHA-3 или BLAKE2/BLAKE3 согласно выводу SHA-1 из употребления в NIST.
flowchart TD
A[Атакующий выбирает два префикса P1 и P2] --> B[Поиск коллизии вычислить блоки почти-коллизии]
B --> C{Хэш P1 плюс блоки равен хэшу P2 плюс блоки}
C -->|Нет| B
C -->|Да| D[Безобидный документ D1 и вредоносный D2 имеют один хэш]
D --> E[Жертва подписывает или доверяет D1]
E --> F[Подпись или доверие переносится на D2]
F --> G[Поддельный сертификат ключ или бинарник принят]● Примеры
- 01
Пара PDF SHAttered (2017) от Google и CWI с одинаковым SHA-1.
- 02
Flame (2012) использовала коллизию MD5 с выбранным префиксом для подделки сертификата Microsoft Terminal Server.
● Частые вопросы
Что такое Коллизия хэшей?
Два разных входа, дающих одинаковое значение криптографического хэша; ломает гарантии целостности, уникальности и подписи, зависящие от функции хэширования. Относится к категории Криптография в кибербезопасности.
Что означает Коллизия хэшей?
Два разных входа, дающих одинаковое значение криптографического хэша; ломает гарантии целостности, уникальности и подписи, зависящие от функции хэширования.
Как защититься от Коллизия хэшей?
Защита от Коллизия хэшей обычно сочетает технические меры и операционные практики, как описано в определении выше.