Инъективны ли криптографические хеши при определенных условиях?

Question

извините за длинный пост, у меня есть вопрос об общих криптографических алгоритмах хеширования, таких как семейство 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, посещенный пользователем (например, путем использование предварительно вычисленной таблицы значений хеш-функции для «общих» значений compont, таких как «www»).

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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

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

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

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

Answer 3

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

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