Dilemma, searching a hashed field when no other information is known

Question

I'm having a dilemma. I have a field hashedX that is a hashed/salted value and the salt is saved in the same row in the mysql database as is common practice.

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

When I receive inputX, I need to know if it matches any of the values in hashedX such as hashed1 hashed2 or hashed3. So typically I would take my input, hash/salt it, and compare it to the values of hashedX. Pseudo code:

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

The problem is I don't know which saltX I need to even get to the $hashed_input before I can do any select.

I could go through the database rows, one by one, try that salt on my input, then check if the input as hashed/salted with this salt matches hashedX of that same row. If I have a 100,000 records, my guess is that this would be painfully slow. I have no idea how slow since I'm not that great at databases.

• Is there a better way to do this, than selecting all rows, looping through them, using that row's salt to hash input, then comparing again to the hashed value in the db?

Answer 1

If it is possible (depends on your hash formula) define a MySQL User Defined Function database side for the hash formula (see CREATE FUNCTION). This way you will be able to get your results in one simple request:

SELECT hashedX, saltX FROM tablename WHERE UDFhash(input, saltX) = hashedX ;

Answer 2

You don't specify which hash algorithm you're using in PHP. MySQL supports MD5 and SHA1 hash algorithms as builtin functions:

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

SHA2 algorithms are supported in MySQL 5.5, but this is only available in pre-beta release at this time. See http://dev.mysql.com/doc/refman/5.5/en/news-5-5-x.html for releases.

Answer 3

Is there a better way to do this, than selecting all rows, looping through them, using that row's salt to hash input, then comparing again to the hashed value in the db?

Yes. A much better way.

Typically a salt is only used to prevent exactly what you are trying to do. So either you don't want to use a salt, or you don't want to do this kind of lookup.

If you are checking an entered password against a given user account or object, you should reference the object on the same line that you have the salt and hashed salt+password. Require the account name / object to be referenced when the password is given, then look up the row corresponding to that account name and object and compare the password against that salt + hash.

If you are keeping a record of items that you've seen before, then you should just go with a hash, (or a bloom filter) and forget the salt, because it doesn't buy you anything.

If you're doing something new / creative, please describe what it is.