Инъективны ли криптографические хеши при определенных условиях?
Извините за длинный пост, у меня есть вопрос об общих криптографических алгоритмах хеширования, таких как семейство SHA, MD5 и т. д.
В общем, такой алгоритм хеширования не может быть инъективным, поскольку фактический создаваемый дайджест обычно имеет фиксированную длину (например, 160 битов в SHA-1 и т. Д.), Тогда как пространство возможных сообщений, подлежащих дайджесту, практически бесконечно.
Тем не менее, если мы создадим дайджест сообщения, который длится не более, чем сгенерированный дайджест, каковы свойства обычно используемых алгоритмов хеширования? Могут ли они быть инъективными в этом ограниченном пространстве сообщений? Существуют ли алгоритмы, которые, как известно, создают коллизии даже для сообщений, длина битов которых меньше, чем длина битов создаваемого дайджеста?
Я на самом деле ищу алгоритм, который обладает этим свойством, т. Е. Который, по крайней мере в принципе, может генерировать коллизирующие хэши даже для коротких входных сообщений.
История вопроса: у нас есть плагин для браузера, который для каждого посещаемого веб-сайта отправляет запрос на сервер, спрашивающий, принадлежит ли веб-сайт одному из наших известных партнеров. Но, конечно, мы не хотим шпионить за нашими пользователями. Итак, чтобы затруднить создание некоторой истории просмотра, мы на самом деле не отправляем посещенный URL, а хеш-дайджест (в настоящее время SHA-1) какой-то очищенной версии. На стороне сервера у нас есть таблица хешей известных URI, которая сопоставляется с полученным хешем. Здесь мы можем жить с определенной степенью неопределенности, поскольку считаем, что не можем отслеживать наших пользователей как функцию, а не как ошибку.
По понятным причинам эта схема довольно нечеткая и допускает ложные срабатывания, а также несоответствующие URI, которые должны иметь.
Итак, прямо сейчас мы рассматриваем возможность изменения генерации отпечатка пальца на что-то, что имеет большую структуру, например, вместо хеширования полного (очищенного) URI, мы могли бы вместо этого:
- разделите имя хоста на компоненты в "." и хеши тех, кто индивидуально
- проверьте путь к компонентам в "." и хеши тех, кто индивидуально
Объедините полученные хеши в значение отпечатка пальца. Пример: хэширование "www.apple.com/de/shop" с использованием этой схемы (и использование Adler 32 в качестве хэша) может привести к "46989670.104268307.41353536/19857610/73204162".
Однако, поскольку такой отпечаток имеет большую структуру (в частности, по сравнению с простым дайджестом SHA-1), мы могли бы случайно снова упростить вычисление фактического URI, посещенного пользователем (например, с использованием предварительно вычисляемая таблица значений хеш-функции для "общих" значений compont, таких как "www").
Итак, сейчас я ищу алгоритм хеширования / дайджеста, который имеет высокую частоту коллизий (серьезно рассматривается Adler 32) даже для коротких сообщений, так что вероятность уникальности хэша данного компонента является низкой. Мы надеемся, что дополнительная структура, которую мы навязываем, предоставляет нам достаточно дополнительной информации, чтобы улучшить поведение сопоставления (то есть снизить частоту ложных срабатываний / ложных отрицаний).
3 ответа
Я не верю, что хэши гарантированно будут инъективными для сообщений того же размера, что и дайджест. Если бы они были, они были бы биективны, в которых не было бы точки хеша. Это говорит о том, что они не являются инъективными для сообщений меньше, чем дайджест.
Если вы хотите поощрять коллизии, я предлагаю вам использовать любую хеш-функцию, которая вам нравится, а затем выбрасывать биты, пока она не столкнется достаточно.
Например, отбрасывание 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 КБ - возможно, с помощью соединений keep-alive. Если обновления фильтра выполняются реже, чем один раз на 4 тыс. Посещений URL-адреса данным пользователем (или меньшее число, если существует менее миллиона URL-адресов или более 1 на 4 миллиона ложных положительных вероятностей), это может привести к уменьшению пропускной способности. чем текущая схема, и, конечно, утечки гораздо меньше информации о пользователе.
Это не работает так же хорошо, если вам требуется, чтобы новые URL-адреса были внесены в белый список немедленно, хотя я полагаю, что клиент может по-прежнему подключаться к серверу при каждом запросе страницы, чтобы проверить, изменился ли фильтр, и, если это так, загрузить патч обновления.
Даже если фильтр Блума слишком велик для полной загрузки (возможно, в тех случаях, когда у клиента нет постоянного хранилища, а объем ОЗУ ограничен), я думаю, что вы все равно можете ввести некоторую сокрытие информации, если клиент вычислит, какие биты Блума Фильтр это нужно видеть, и просить тех с сервера. С помощью комбинации кэширования в клиенте (чем выше доля фильтра, который вы кэшировали, тем меньше битов нужно запрашивать и, следовательно, тем меньше вы говорите серверу), запрашивая окно вокруг фактического бита, который вас интересует (поэтому вы не указываете серверу, какой именно бит вам нужен), а клиент, запрашивающий ложные биты, которые ему на самом деле не нужны (скрыть информацию в шуме), я полагаю, вы могли бы скрыть, какие URL вы посещаете. Тем не менее, потребуется некоторый анализ, чтобы доказать, насколько это действительно работает: шпион будет стремиться найти шаблон в ваших запросах, который связан с просмотром определенного сайта.
У меня сложилось впечатление, что вам действительно нужна криптография с открытым ключом, когда вы предоставляете посетителю открытый ключ, используемый для кодирования URL, и расшифровывает URL с помощью секретного ключа.
Реализации JavaScript немного повсюду.