dxdt.ru: занимательный интернет-журнал

Часто приходится сталкиваться с неверным пониманием того, как криптографические хеш-функции можно применять для “анонимизации” данных и какой эффект можно получить на практике. Связано это с излишне общей трактовкой основного свойства хеш-функций: сложности вычисления аргумента по значению, нахождения прообраза – то есть, сложной обратимости. Из того факта, что только по известному значению хеш-функции нельзя вычислить исходный аргумент, делается вывод, что после применения хеш-функции к исходным данным полностью исчезает различительная способность. Это, конечно, далеко не так.

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

Сложность обращения мешает далеко не всегда. Во многих и многих практических случаях достаточно использовать прямое вычисление хеш-функции, чтобы, перебирая допустимые аргументы на входе, найти подходящий. Если известны ограничения на входные данные, метод оказывается очень эффективным. Чем больше ограничений, тем эффективность выше. В практических случаях – ограничения есть, и не одно. Я обычно привожу в пример домашние адреса из некоторой базы данных с пользователями, где адрес разбит на поля “Улица”, “Номер дома/квартира”. Пусть анонимизирующее значение хеш-функции вычисляется от объединения этих полей для одной записи. Сколько всего есть таких строк с возможными записями домашнего адреса для огромного мегаполиса? Десяток миллионов? Что-то около того. И эти строки можно взять из открытых картографических данных.

По современным вычислительным меркам – проверка десятка миллионов записей по SHA-256 не займёт какого-то существенного времени (вот, например, я посчитал для сравнения: реализация SHA-256 в OpenSSL на Raspberry Pi 5 обрабатывает больше миллиона 1024-байтовых блоков в секунду). Обычно, предлагают очевидные методы защиты: взять вместо SHA-256 специальную медленную хеш-функцию, привязанную к объёму памяти; взять секретный параметр (“соль”), который будет подмешиваться при “анонимизации”. Оба метода – не слишком подходят: требуют кратно больше вычислительных ресурсов и на стороне легитимного “анонимизатора”, требуют управления генерированием и хранением “соли” (так как это не защита от использования предвычисленных данных, “соль” нельзя совсем зафиксировать или передавать вместе с данными, но при этом текущее значение должно быть как-то проиндексировано, поскольку изменение соли приведёт к изменению соответствия в разных версиях анонимизированной таблицы).

Необходимо рассматривать и актуальную “модель угроз” – то есть, знать, от чего пытаемся защитить данные. Рассмотрим другой пример: анонимизация “хешированием” URL, которые посещает пользователь через браузер. На первый взгляд, URL-ы сложнее перебирать (но тоже можно). Однако, если задача состоит в обнаружении факта посещения конкретных URL, то, зная эти URL, определить соответствие труда уже не составляет. Если сторона, принимающая “анонимизированные” URL от браузера, использует какие-то “соли”, то это не мешает данной стороне без проблем самостоятельно обращать значения по списку URL. Ну и, по большому счёту, подсчитать хеш-функции по массиву мыслимых URL – тоже возможно, однако, из-за слишком слабых ограничений на входные данные, ограниченным тут будет успех: представьте, что в URL дописывается псевдослучайная строка из 32 ASCII-символов.

Тем не менее, пример из предыдущего абзаца показывает, что такая схема позволяет с легкостью находить пользователей, посетивших один и тот же URL. Это существенный дефект используемой схемы “анонимизации”: одинаковые значения – отображаются в одинаковые значения, то есть, подобное хеширование вовсе и не удаляет “различительную способность”. Если вернуться обратно к записям адресов пользователей, то это означает, что нетрудно определить пользователей, проживающих вдесятером по одному адресу, даже не нужно ничего перебирать.

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

Адрес записки: https://dxdt.ru/2024/12/27/14538/