Indexing a SHA hash in place of a VARCHAR

Question

In Is it a good idea/approach to index a VARCHAR column? the concept was using VARCHAR as the column.

I was wondering, if we store the SHA-1 hash or SHA-256 hash (if I am paranoid) as a BINARY(20) column and index on that column.

Performing a SHA-1 computation on a short string is fast enough on the application side and we just query by the SHA value instead.

Likely I am thinking the length of the VARCHAR would hover around 10 to 30 characters with some going longer but lower probability.

Answer 1

This question has the [Performance] tag so I suspect that you may be thinking of a hash index. In SQL Server, the maximum key length for nonclustered indexes is 1700 bytes. It is not possible to create a nonclustered index with a long string column as a key column. For example, for the following table:

DROP TABLE IF EXISTS #HASH_INDEX_DEMO;

CREATE TABLE #HASH_INDEX_DEMO (
    ID BIGINT NOT NULL,
    BIG_COLUMN_FOR_U VARCHAR(8000) NOT NULL,
    SMALL_COLUMN VARCHAR(10) NOT NULL
);

INSERT INTO #HASH_INDEX_DEMO WITH (TABLOCK)
SELECT RN, REPLICATE(CHAR(65 + RN % 26), (RN % 43) * (RN % 119)), 'SMALL'
FROM 
(
    SELECT ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) RN
    FROM master..spt_values t1
    CROSS JOIN master..spt_values t2
) q;

Attempting to create this index:

CREATE INDEX I ON #HASH_INDEX_DEMO (BIG_COLUMN_FOR_U);

Fails with this error:

Msg 1946, Level 16, State 3, Line 19 Operation failed. The index entry of length 1701 bytes for the index 'I' exceeds the maximum length of 1700 bytes for nonclustered indexes.

If you need to do an equality search on that column then the query optimizer must do a table scan. For example, the following query takes about 0.6 seconds on my machine:

SELECT ID, SMALL_COLUMN
FROM #HASH_INDEX_DEMO
WHERE BIG_COLUMN_FOR_U = 'A'
OPTION (MAXDOP 1);

One alternative is to create a hash index on the column and to perform the equality search on both the hash index and the column itself. CHECKSUM() is probably the best choice because you don't need any cryptographic security for this and a small number of collisions is acceptable. You primary want something small and fast. The code below adds a computed column and creates an index on that column:

ALTER TABLE #HASH_INDEX_DEMO ADD BIG_COLUMN_FOR_U_CHECKSUM AS CHECKSUM(BIG_COLUMN_FOR_U);

CREATE INDEX I ON #HASH_INDEX_DEMO (BIG_COLUMN_FOR_U_CHECKSUM);

The query below returns the same results as the initial query but SQL Server is able to use the index. It finishes in 0.01 seconds on my machine.

SELECT ID, SMALL_COLUMN
FROM #HASH_INDEX_DEMO
WHERE BIG_COLUMN_FOR_U_CHECKSUM = CHECKSUM('A') AND BIG_COLUMN_FOR_U = 'A'
OPTION (MAXDOP 1);

Hash indexes are a good choice when the key length is too long to allow for a nonclustered index or disk space is at an absolute premium. In your question you estimate that the length of the column will be about 10 to 30 characters to the added complexity probably isn't worth it for your scenario.

Answer 2

the length of the VARCHAR would hover around 10 to 30 characters with some going longer

If the data is averaging around 20 bytes or more per record then you are not saving any space therefore not reducing page accesses when searching for values, so there is almost certainly no benefit from doing this so you are adding complication to your application(s) for no gain.

In fact you will be using extra space as you'll need to store the original value as well as the hash result, potentially slowing queries needing key lookups or performing scans, unless you expect a lot of duplicate values in which case you could store the actual values de-duplicated in another table.

You will also lose the ability to perform any sort of range queries using the index (for instance WHERE name LIKE 'D%') which may be an issue depending on the data being stored, and also lose the ability to sort by that data using the index (again, depending on the data this may not be needed).

Answer 3

If you are really paranoid you wouldn't be using SHA at all, as SHA is designed to be a fast executing hash algorithm and fast to be brute-forced on CPU and or very fast on GPU's (millions of hashes per second), Also huge rainbow tables exists...you should be considering blowfish/twofish/Threefish/Argon as those algorithms are designed to run (very) slow on GPU's making brute-forcing pretty much impossible.

I would not even consider adding a hashed column in a index as databases are designed to return as quick as possible, as one the worse things you can do to check 'a' = 'abdgahsdgdu' which is to "fast" to return false the database does the same more or less under the hood, Which opens up a (possible) Timing attack related attack. - raymond-nijland

Using a hash this way could actually reduce data length/pattern related timing attack vectors, because the lookup & comparison times are going to be more consistent. But the database is not the right layer to be dealing with that anyway, IMO. - david-spillett

Very true the application needs to that simply use SELECT password FROM users WHERE user_name = '<username>' and use a time safe hash compare function to be safe, where username is safe to be indexed. - raymond-nijland

Answer 4

I can think of one additional benefit but it is mostly due to limitations of JPA, Spring and MySQL.

MySQL defaults to case insensitive unless you use MySQL specific constructs like BINARY in columnDefinition or utf8mb4_bin thus causing portability / sorting issues. In which case the workaround was to create an index column containing the SHA-1 which will not be translated by JPA/Spring/Hibernate/MySQL.