Когда вредно хешировать25.11.2019 21:48

Предисловие

Данный текст будет являться одной из переписанных глав для учебного пособия по защите информации кафедры радиотехники и систем управления, а также, с этого учебного кода, кафедры защиты информации МФТИ (ГУ). Полностью учебник доступен на github (см. также draft releases). На Хабре планирую выкладывать новые «большие» куски, во-первых, чтобы собрать полезные комментарии и замечания, во-вторых, дать сообществу больше обзорного материала по полезным и интересным темам.

Надёжная криптографическая хеш-функция обеспечивает преобразование открытого текста в текст заданной длины. При этом обеспечивается «стойкость»: сложность в восстановлении первого и второго прообразов. Или, говоря простым языком про первое свойство, сложность получения такого текста, значение хеш-функции для которого будет равно заданному.

Под сложностью восстановления понимается тот факт, что для нахождения первого прообраза [надёжной криптографической хеш-функции] требуется совершить в среднем не менее $2^{n-1}$ операций хеширования, где $n$ — количество бит в выходе криптографической хеш-функции. Взяв современную хеш-функцию с большим размером выхода (начиная от 256 бит) разработчик информационной системы уверен, что восстановить исходные данные по значению хеш-функции нельзя. Чаще всего он прав.

Но есть важный набор случаев, когда несмотря на надёжность хеш-функции восстановление прообраза или даже исходного текста не представляет проблемы. Это случай, когда использовать хеш-функцию бессмысленно. Это случай, когда количество вариантов исходного текста поддаётся перебору.
Пример: номер телефона. Разных номеров телефона с префиксом »+7» и 10 цифрами составляет $10^{10} \approx 2^{33}$ . Современные устройства, оптимизированные для перебора значений хеш-функций перебирают миллионы хешей в секунду. Значит, подсчёт значений хеш-функций для всех возможных номеров телефонов с префиксом составляет не более нескольких секунд.

Пример: номер кредитной карты (PAN, payment card number). Часто номер карты маскируют, открывая первые 4 (6) и/или последние 4 цифры, а остальные скрывая. Всего цифр на карте 16. Можно ли хешировать номера карт с целью скрыть их от злоумышленника? Нет. Если злоумышленник получил 8 цифр из 16 (первые 4 и последние 4), а также значение хеш-функции от полного номера карты, то восстановить полный номер он сможет менее чем за секунду. Для этого ему потребуется перебрать всего $10^{8} \approx 2^{26}$ вариантов номера.

Интересен пример с адресом электронной почты. Казалось бы, что по значению надёжной хеш-функции невозможно восстановить оригинальный адрес. Количество разных вариантов из 8 латинских букв и 10 цифр уже даёт $36^8 \approx 2^{41}$ вариантов названий почтовых ящиков без учёта разных доменов почтовых служб (@mail.ru, @gmail.com, etc.). Если брать и другие разрешённые символы, а также удлинить адрес, вариантов ещё больше. Но… До 2006 года работал проект «Blue Frog» («голубая лягушка»), который предлагал своим пользователям защиту от спама. Он использовал автоматическое уведомление провайдеров о рассылаемом с их серверов спаме, что заставляло распространителей рекламы отказаться от рассылки спама как минимум на те адреса, которые являлись участниками проекта. Чтобы понять, принадлежит ящик участнику или нет, распространялся файл со списком значений криптографической хеш-функции от каждого адреса почтового ящика участника.

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

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

Возможные решения для описанных случаев.

Хешировать не сами значения, а конкатенацию исходного значения и некоторого секрета, который хранится отдельно. Например, не в таблице базы данных (вместе со значениями хеш-функций), а в конфигурации сервера приложений. С аналогичным успехом вместо хеширования можно использовать функцию блочного шифрования на некотором секретном ключе.
Использовать такие хеш-функции, которые являются не только надёжными, но и медленными в вычислении. Как для криптоаналитика, так и для легального пользователя. Примером таких функций являются PBKDF2, bcrypt, scrypt, Argon2, для которых при вызове функции мы дополнительно указываем количество итераций хеширования. Однако если увеличение длины выхода хеш-функции всего на один бит (из 256 или 512) увеличивает сложность атаки криптоаналитика на двоичный порядок (в два раза), то увеличение количества итераций для хеш-функции PBKDF2 в два раза увеличит сложность атак также только в два раза. То есть получение значения хеш-функции даже легальным пользователем становится затратно с точки зрения вычислительных ресурсов и затраченной энергии.

Послесловие

Автор будет благодарен за фактические и другие замечания к тексту.