How to mitigate risk of leaking information of a user not found in database during login

Question

As far as I understand the process of logging someone into your system goes like this:

1) The user which wants access transmits credentials to your system (typically login - being a unique identifier - and password)

2) The system uses the login to retrieve the account information from a database comprising a passwordhash to compare against.

3) If a user was found, the transmitted password is hashed and the hash is compared against the hashed password from the DB.

4a) If both match access is granted

4b) If both do not match access is declined

Whereby the process of (2) leaks the information of a login existing in your system or not (via time).

---

My question is twofold:

a) Is this risk of leaking the information worth mitigating?

and more interesting:

b) How to mitigate that risk?

Answer 1

Timing step 2 does leak information. In order for it not to, you'd need a database implementation where hits and misses take the same amount of time.

It is probably more important, though, that you run step 3 unconditionally. If a username is not in the database, then use a dummy value for the salt and execute your password hash using the same configuration you use for real accounts.

Step 2 would probably require more than one login request to "average out" noise from timing data. Conditionally executing step 3 would make timing attacks trivial.

I'm not familiar with real world database implementations. (Or their indexing options.) My guess is that no major DB supports a constant time indexing mode. There might be indexing options that are closer than others to being constant time.

Hash-table-based indexing schemes that don't use bloom filters or caches might be one of the least bad options. Perhaps there is some type of index that will only ever do one disk seek for any key lookup.

Hit and miss times after the disk-seek will still vary, but then hopefully it won't vary by much. Precise timing then might be made more difficult by other unpredictable sources of timing variability. (Seek times, server load, or network conditions, for example.)