Hashing items of different Bytes but same length would enable a timing attack?

Question

I am following this paper which comes highly recommended as a secure Registration/Login system over TLS which uses client side computation for the Password Processing Function (PPF). What my main question is about is how the design prevents account enumeration (an attacker finding out if usernames are valid on the server).

To summarise the final solution in Section 4:

On the server, each valid user has a different $v$ which is generated by a CSPRNG and is at least 128-bits of random data.

For login, if the user exists, it computes the salt as:

hash( username || domain-name || $v$ ).

If the user does not exist, it computes the salt as:

hash( username || domain-name || $σ$ )

Where σ is a server secret value of 128 bits of random data.

The point of this is that a salt is always returned, regardless of whether the username is valid or not. This prevents an attacker from making many queries to figure out everyone's usernames and it also prevents timing attacks as the computation is always done server side and it takes the same time.

However in the system we have, we do not have usernames so we are replacing the username here with the user's email address instead. Also we have another requirement where our support team needs to change user's email addresses on their behalf if they lose access to them. The design in the paper would appear not to work in that case because the salt is then based on the email address, and hence the PPF computation is also tied to it. So if the user changes their email then their previous salt is no longer valid and they need to re-do the PPF computation which is a nuisance. Also it's much worse if the support team changed the user's email because then they would definitely be locked out of their account.

So my thoughts to resolve this for valid users is to have the salt calculated as:

Salt = hash( domain-name || padding || $v$ )

And for invalid users the salt would be calculated as:

Salt = hash( email || domain-name || padding || $σ$ )

So for this to work, emails would be limited to maximum 80 characters. Then the length of email + domain-name + padding would always be 100 Bytes. And for valid users the domain name + padding would also always be 100 Bytes. The padding character could just be a 'P' and everything is always padded to 100 Bytes.

So my main questions:

1. Is it possible for an attacker to do a timing attack on the network request with the server to check if an email is valid/invalid?

2. Will there be a give-away (detectable) timing difference between hashing the email || domain-name || padding, vs hashing just domain-name || padding if they're both 100 Bytes in length? I.e. does hashing different characters make the computation take longer or go faster.

Answer 1

It is a bad idea to use any user information of host information to generate a salt. Salt should be random.

Use password stretching. Depending on tools available to you considers bcrypt, scrypt, argon2. Then no matter if user exists or not the password stretching can take (depending configuration) substantial time. It will be safe against timing attacks.

Since the stretched password hash will not depend on user ID, your users will be able to change their IDs (whatever you use as ID - email, user name or anything else) as often as they want. When user ID changes, it will not bve necessary to recalculate the password hash.

Answer 2

Notice that since your database is already storing your value $v$, you have to do a database look-up to recover the value $v$ before performing the client-side work.

This means that you could also easily "recover" the corresponding client's id (or better a hash thereof) along the way (and if it does not exist return a PRF value defined by the email used).

You can also simply completely discard the username part altogether, since it does not really add any entropy to the whole, in my opinion... But that is probably another discussion. (To have the same effect, since you already have to lookup the $v$ value in your database, it could be replaced with the hash of the user's id and a nonce, for instance, enabling us to have different value at each call, leaking no information... And then this could also directly be included in the $v$ value.)
My point is "the username could be something else than the username or email, without much troubles and without compromising on security".

Now, to address your questions:

1. Could an attacker perform a timing attack on your server to know whether a given user exists or not?
   Most certainly, yes, since you have to recover the said $v$ value in your database to send his salt to your user. This is partially addressed in the paper, since if the look-up fails, then a salt is still computed and sent to the user. However notice that the look-up itself is probably a process which is taking $\mathrm{O}(\log(n))$ and as such it can be timed and the failed lookups would require more time on average that when the user exists... Except if you anticipated it and use an hash-table to index your users (which allows to search in constant time). I am not familiar with databases software, but I believe that this is not the case usually, however one can probably build such a table using a key-value store and hashes as keys... But I'd better ask someone else than me about database design first.

2. Modern hash functions are generally implemented without branching and using constant-time instructions, this means that for the same given length, the hash's speed should be constant. So there shouldn't be any problem if you take a modern hash function such as SHA256, SHA3 or BLAKE2.

Finally, notice that letting the server re-compute the salt on every login is costly in term of computing power and that it serves no security goals. The salt can be stored in the database without any problem. As Thomas Pornin put it in his excellent answer (which you should read) on Security.SE:

Salts are not meant to be secret; otherwise we would call them keys. You do not need to make salts public, but if you have to make them public (e.g. to support client-side hashing), then don't worry too much about it. Salts are there for uniqueness. Strictly speaking, the salt is nothing more than the selection of a specific hash function within a big family of functions.

The linked paper says it explains why the salt shall be recomputed by the server at each attempt, but in the end I couldn't find any rationale in the paper explaining this. I do not advice to do so, since it could somehow lead to CPU (D)DoS attacks. Be also careful not to let the client-side decide the cost of the PPF used, since this could also lead to CPU exhaustion.

Answer 3

The solution is to compute the fake salt for an unknown user on every attempt, but only return it if the user is invalid. Otherwise return the salt looked up directly (do not hash the “real” salt with the username).

You can even do this all the way down at the database layer to make it as constant time as possible.

So you could have a database stored procedure named getUserSalt(@email) which does the following

1. Trims white space and lowercases the username/email. This is done as usernames are not case sensitive in most applications, so we need to return the same fake salt for all case variations of an email address.
2. Computes the fake salt fS for a non-existent user as fS=SHA256(server_secret||email) trimmed to your normal salt length (say 16 bytes)
3. Looks up the real salt rS for the email address with a SQL query
4. If rS is null, the user doesn’t exist, and return the fake salt fS to the application (which sends it to the user). Otherwise return rS.

Step #4 is not truly constant time, but it is a single branch. You could perform null checks in your SQL lookup query, but then that query would not be constant time. In any case, this single branch is unlikely to be exploitable from a timing perspective.