Запросить сервер на наличие записи, при этом сервер не знает точно, для какой записи запрашивался

Question

Я думал о таких услугах, как pwnedlist.com и shouldichangemypassword.com и фундаментальная проблема с ними - доверие.

То есть пользователь должен верить, что эти службы не собираются собирать отправленные запросы.

Pwnedlist.com предлагает опцию отправки хэша SHA-512 запроса пользователей, который является шагом вперед, но все же теряет информацию, если запрос существует в базе данных. То есть вредоносная служба будет знать, что указанный адрес электронной почты действителен (см. Также: почему вы никогда не должны нажимать на ссылки отказа от подписки в спам-письме).

Я пришел к следующему решению:

1) Вместо того, чтобы пользователь сам вычислял и отправлял хеш, хеш (я буду использовать намного более простой md5 в моем примере) вычисляется с помощью клиентского JavaScript:

md5("user@example.com") = "b58996c504c5638798eb6b511e6f49af"

2) Теперь вместо передачи всего хэша в виде запроса на сервер передаются только первые N битов:

GET http://remotesite.com?query=b58996

3) Сервер отвечает всеми хешами, существующими в его базе данных, которые начинаются с тех же N битов:

{
"b58996afe904bc7a211598ff2a9200fe",
"b58996c504c5638798eb6b511e6f49af",
"b58996443fab32c087632f8992af1ecc", 
...etc... }

4) Javascript на стороне клиента сравнивает список хэшей, возвращаемых сервером, и сообщает пользователю, существует ли ее адрес электронной почты в БД. Поскольку в ответе сервера присутствует «b58996c504c5638798eb6b511e6f49af», электронная почта существует в базе данных - сообщите пользователю!

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

Что ТАК думает об этом решении? Важно, кто-нибудь знает о каких-либо существующих примерах или обсуждении этой техники?

ПРИМЕЧАНИЕ. Как pwnedlist.com, так и shouldichangemypassword.com, по-видимому, управляются авторитетными людьми / организациями, и у меня нет оснований полагать иначе. Это больше мыслительное упражнение.

Answer 1

Такие службы, как pwnedlist.com, работают с общедоступной информацией.По определению каждый имеет доступ к этим данным, поэтому попытка защитить их - спорный вопрос.Злоумышленник просто загрузит его из The Pirate Bay .

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

Вам гораздо лучше с Bloom Filter .Это позволяет вам создать черный список пропущенных данных без возможности получения простого текста.Это связано с тем, что грубая сила, основанная на перестановках, скорее всего, обнаружит столкновения, чем реальный простой текст.Поиск и вставка - это классная сложность O (1), и сама таблица занимает гораздо меньше места, возможно, на 1/10 000 от пространства, которое она использует при использовании традиционной базы данных sql, но это значение является переменной в зависимости от частоты ошибок, которую вы указали,