Дилемма, поиск в хешированном поле, когда никакой другой информации не известно

У меня дилемма. У меня есть поле hashedX, которое является хешированным/соленым значением, и соль сохраняется в той же строке в базе данных mysql, что является обычной практикой.

hashedX      saltX
------       ------
hashed1      ssai3
hashed2      woddp
hashed3      92ofu

Когда я получаю inputX, мне нужно знать, соответствует ли оно какому-либо из значений в hashedX, например hashed1 hashed2 или hashed3. Так что обычно я брал свои входные данные, хэшировал/солил их и сравнивал со значениями hashedX. Псевдокод:

$hashed_input = hash ($input with $salt );
select * from tablename where $hashed_input is hashedX

Проблема в том, что я не знаю, какое saltX мне нужно, чтобы добраться до $hashed_input, прежде чем я смогу сделать select.

Я мог бы просмотреть строки базы данных одну за другой, попробовать эту соль на своем входе, а затем проверить, соответствует ли ввод, хешированный/солёный с этой солью, hashedX той же строки. Если у меня есть 100 000 записей, я предполагаю, что это будет мучительно медленно. Я понятия не имею, насколько медленно, так как я не очень хорошо разбираюсь в базах данных.

  • Есть ли лучший способ сделать это, чем выбирать все строки, перебирать их, использовать соль этой строки для ввода хэша, а затем снова сравнивать с хешированным значением в БД?

mysql encryption php hash
person cooper    schedule 07.07.2010    source источник

Ответы (3)


arrow_upward
3
arrow_downward

Если это возможно (зависит от вашей хеш-формулы), определите сторону базы данных MySQL User Defined Function для формулы hash (см. СОЗДАТЬ ФУНКЦИЮ). Таким образом, вы сможете получить свои результаты одним простым запросом:

SELECT hashedX, saltX FROM tablename WHERE UDFhash(input, saltX) = hashedX ;
person kriss    schedule 07.07.2010
comment
Ой. Это может немного улучшить производительность, но не решает фундаментальную проблему, а именно то, что сложность задачи составляет O (N) для размера таблицы, что противоречит цели использования базы данных/хэша. - person Slartibartfast; 11.07.2010
comment
@slartibartfast: от этого никуда не деться. Это действительно фундаментальная проблема — учитывая, что хеш-алгоритмы являются односторонними, O(N) является точной нижней границей сложности любого решения этой проблемы. - person Borealid; 11.07.2010
comment
@Borealid: ну, могут быть способы, если у нас есть некоторые ограничения на пространство значений соли. Тогда O(card(salt)) становится возможной другой нижней границей, совместимой с индексированным поиском. - person kriss; 12.07.2010

arrow_upward
1
arrow_downward

Вы не указываете, какой алгоритм хэширования вы используете в PHP. MySQL поддерживает хеш-алгоритмы MD5 и SHA1 как встроенные функции. :

SELECT ...
FROM tablename 
WHERE SHA1(CONCAT(?, saltX)) = hashedX;

Алгоритмы SHA2 поддерживаются в MySQL 5.5, но в настоящее время они доступны только в предварительной бета-версии. См. http://dev.mysql.com/doc/refman/5.5/en/news-5-5-x.html для выпусков.

person Bill Karwin    schedule 07.07.2010
comment
В этом случае вам может понадобиться написать UDF, как предлагает @kriss. - person Bill Karwin; 08.07.2010

arrow_upward
1
arrow_downward

Есть ли лучший способ сделать это, чем выбирать все строки, перебирать их, использовать соль этой строки для ввода хэша, а затем снова сравнивать с хешированным значением в БД?

Да. Гораздо лучший способ.

Обычно соль используется только для предотвращения именно того, что вы пытаетесь сделать. Так что либо вы не хотите использовать соль, либо не хотите выполнять такой поиск.

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

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

Если вы делаете что-то новое/креативное, пожалуйста, опишите, что это такое.

person Slartibartfast    schedule 11.07.2010