Блог

извините за длинный пост, у меня вопрос об общих криптографических алгоритмах хеширования, таких как семейство SHA, MD5 и т. Д.

В общем, такой алгоритм хеширования не может быть инъективным, поскольку фактический созданный дайджест обычно имеет фиксированную длину (например, 160 бит в SHA-1 и т. Д.), Тогда как пространство возможных сообщений, подлежащих обработке, Практически бесконечно.

Однако, если мы создаем дайджест сообщения, длина которого не превышает длину сгенерированного дайджеста, каковы свойства обычно используемых алгоритмов хеширования? Могут ли они быть инъективными в этом ограниченном пространстве сообщений? Существуют ли алгоритмы, которые, как известно, приводят к коллизиям даже в сообщениях, длина битов которых короче длины битов созданного дайджеста?

На самом деле я ищу алгоритм, обладающий этим свойством, т. Е. Который, По крайней мере в принципе, может генерировать сталкивающиеся хэши даже для коротких входных сообщений.

Справочная информация: У нас есть плагин для браузера, который для каждого посещенного веб-сайта отправляет запрос серверу, спрашивающий, принадлежит ли веб-сайт одному из наших известных партнеров. Но, конечно, мы не хотим шпионить за нашими пользователями. Итак, чтобы затруднить создание какой-либо истории посещений, мы фактически отправляем не посещенный URL, а дайджест хэша (в настоящее время SHA-1) некоторой очищенной версии. На стороне сервера у нас есть таблица хэшей хорошо известных URI, которая сопоставляется с полученным хэшем. Здесь мы можем жить с определенной долей неопределенности, поскольку считаем невозможность отслеживать наших пользователей функцией, а не ошибкой.

По очевидным причинам эта схема довольно нечеткая и допускает ложные срабатывания, а также несоответствие URI, которое должно быть.

Итак, прямо сейчас мы рассматриваем возможность изменения генерации отпечатков пальцев на что-то, что имеет большую структуру, например, вместо хеширования полного (очищенного) URI, мы могли бы вместо:

1. разделите имя хоста на компоненты по адресу «.» и хэшируйте их по отдельности
2. проверьте путь к компонентам в «.» и хэшируйте их по отдельности

Объедините полученные хэши в значение отпечатка пальца. Пример: хеширование «www.apple.com/de/shop » использование этой схемы (и использование Adler 32 в качестве хэша) может привести к «46989670.104268307.41353536/19857610/73204162 «.

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

Итак, прямо сейчас я ищу алгоритм хэширования / дайджеста, который имеет высокую частоту коллизий (Adler 32 серьезно рассматривается) даже для коротких сообщений, так что вероятность того, что данный компонентный хэш будет уникальным, невелика. Мы надеемся, что дополнительная структура, которую мы вводим, предоставляет нам достаточно дополнительной информации, чтобы улучшить поведение сопоставления (т. Е. Снизить Частоту ложных срабатываний / ложных отрицаний).

Я не верю, что хэши гарантированно будут инъективными для сообщений того же размера, что и дайджест. Если бы они были, они были бы биективными, в которых отсутствовала бы точка хэша. Это говорит о том, что они также не являются инъективными для сообщений меньшего размера, чем дайджест.

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

Например, выбрасывание 159 бит хэша SHA-1 даст вам довольно высокую частоту столкновений. Возможно, вам не захочется выбрасывать так много.

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

Вместо этого, как насчет отправки списка URL-адресов плагину при запуске, а затем, чтобы он просто отправил обратно один бит, указывающий, посещает ли он URL-адрес в списке? Если вы не хотите отправлять URL-адреса явно, отправляйте хэши (не пытаясь максимизировать коллизии). Если вы хотите сэкономить место, отправьте фильтр Блума.

Поскольку вы готовы смириться с частотой ложных срабатываний (то есть случайных сайтов, занесенных в белый список, хотя на самом деле это не так), фильтр Блума может оказаться как раз тем, что нужно.

Каждый клиент загружает фильтр Блума, содержащий весь белый список. Тогда клиенту не нужно каким-либо иным образом взаимодействовать с сервером, и нет никакого риска шпионажа.

При 2 байтах на URL частота ложных срабатываний будет ниже 0,1%, а при 4 байтах на URL-адрес — ниже 1 на 4 миллиона.

Загрузка всего фильтра (и, возможно, его регулярные обновления) — это большие затраты на пропускную способность. Но предположим, что в нем есть миллион URL-адресов (что мне кажется довольно много, учитывая, что вы, вероятно, можете применить некоторые правила для канонизации URL-адресов перед поиском), это загрузка размером 4 МБ. Сравните это со списком из миллиона 32-битных хэшей: тот же размер, но частота ложных срабатываний будет где-то около 1 к 4 тысячам, так что фильтр Блума выигрывает в компактности.

Я не знаю, как плагин связывается с сервером, но я сомневаюсь, что вы можете выполнить HTTP-транзакцию намного меньше 1 КБ — возможно, меньше с поддерживающими подключениями. Если обновления фильтра происходят реже, чем одно на 4k посещений URL-адреса данным пользователем (или меньшее число, если URL-адресов меньше миллиона или вероятность ложного срабатывания превышает 1 на 4 миллиона), это может привести к использованию меньшей пропускной способности, чем текущая схема, и, конечно, к большим утечкам меньше информации о пользователе.

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

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

У меня сложилось впечатление, что вам действительно нужна криптография с открытым ключом, когда вы предоставляете посетителю открытый ключ, используемый для кодирования URL-адреса, и расшифровываете URL-адрес с помощью секретного ключа.

Реализации JavaScript есть немного везде.