“Почти что коллизия” и хеш-функции

Предположим, найдены два различных сообщения, для которых значения (криптографической) хеш-функции отличаются только в одном байте (то есть, всего несколько близких битов различаются). Пусть разрядность хеш-функции 256 бит, то есть 32 байта. Заметьте: тут важна и локализация отличий – не просто несколько битов, но ещё и в одном байте. Что именно обнаружение таких сообщений означает для хеш-функции? Как ни странно, но, без прочих обстоятельств, – практически ничего нового, кроме того, что хеш-функцию, эмпирически, станут считать менее стойкой: то, что два сообщения с описанным свойством существуют – и так было известно.

Другое дело, если предъявлен метод, позволяющий быстро находить пары сообщений с близкими значениями хеш-функции. Тогда, конечно, хеш-функция перестаёт быть действительно криптографической. Однако и в случае предъявления метода возникают всякие оговорки. Близки ли входные сообщения из пары? (Кстати, тут можно вспомнить, про нужные в некоторых задачах хеш-функции (не криптографические) с “хорошей” локализацией, – LSH.) Если близки, то как метод поиска таких сообщений связан с алгоритмом хеш-функции? Можно ли успешно отыскать сообщение, парное к заданному? Известны ли свойства получающихся разбиений? Поднимается ли структура разбиений в алгоритм поиска их представителей (то есть, можно ли формулу разбиений)? В общем, много уточнений.

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

На поиске близких значений хеш-функций, например, построена схема доказательства работы в протоколе цифровой валюты Биткойн (и далеко не только там). В биткойн-сети узлы должны подбирать входные массивы так, чтобы значение хеш-функции от них было меньше заданного порога (параметр “сложности”), это означает, что несколько старших байтов записи подряд должны быть нулевыми. То есть, все использованные значения хеш-функций (SHA-256) совпадают по нескольким последовательным крайним байтам. Эта ситуация, конечно, отличается от описанной в предыдущем абзаце, но только тем, что тут совпадает меньшее количество байтов (в исходной идее требуется различие, максимум, в одном байте). При этом, в случае с биткойнами, довольно велика вероятность того, что в ходе работы сети “майнеров” либо уже были обнаружены полноценные коллизии SHA-256, либо такие коллизии будут обнаружены в течение нескольких лет (если ничего не изменится кардинально, конечно). Это так не только по причине парадокса дней рождения, но и из-за возможных дефектов SHA-256. Другое дело, что такие коллизии вряд ли кто-то заметил – объёмов памяти для хранения всех перебираемых значений нет в принципе.

Адрес записки: https://dxdt.ru/2024/04/05/12726/

Похожие записки:



Далее - мнения и дискуссии

(Сообщения ниже добавляются читателями сайта, через форму, расположенную в конце страницы.)

Написать комментарий

Ваш комментарий:

Введите ключевое слово "S751G" латиницей СПРАВА НАЛЕВО (<--) без кавычек: (это необходимо для защиты от спама).

Если видите "капчу", то решите её. Это необходимо для отправки комментария ("капча" не применяется для зарегистрированных пользователей). Обычно, комментарии поступают на премодерацию, которая нередко занимает продолжительное время.