Is it safe to use a secret salted hash of a public id for client to prove ownership of id to a server that knows salt but does not store ids?

Question

I am writing a peering server - the server assigns randomly generated public IDs to users, and I want users to be able to reclaim their ids in the future, but only to be able to claim ids that they have been assigned, not arbitrary ids or ids belonging to other users.

I also want to avoid storing any information on the server after its connection to a user closes.

I have limited knowledge of cryptography, but am thinking that the server can give the users their public ID and a secret produced by salting and hashing the id. To reclaim the id, the user would pass the server both the id and secret, the server would re salt and hash the id and ensure that it matches the provided secret.

Is this safe? If so what hash function is appropriate, and if not is there a better approach?

Thanks!

Answer 1

You could do something fairly simple, such as

$UserSecret = Random()$
$UserID = HMAC(ServerSecret, UserSecret)$

Send the user the two values. When he reconnects, he sends the two values back. If re-calculating $UserID$ with the user's $UserSecret$ gives the same $UserID$ then that proves (to a high degree of certainty) that it's the same person that was given that ID before (assuming the $ServerSecret$ is still secret and the same value as it was originally).

The size of the ID value will need to be sufficiently large that the same ID is unlikely to be handed out to more than one person, since you're not keeping track of which ones have been used previously.

Using HMAC-SHA256 would give large enough values. See the wikipedia entry for HMAC for an explanation of how it works.

You could also use an SRP-style verifier, which could then be used to do an authenticated key exchange as well.

User generates a random value $x$, and sends the server

$Verifier = g^x mod N$

(see SRP for more details on $g$ and $N$)

Establish a secure session using SRP with $x$ and $Verifier$ to generate a key. The server then calculates $UserID = HMAC(ServerSecret, Verifier)$ and sends that to the user. The user saves the $UserID$ and $x$.

Later connections, do the same thing using the saved $x$, but server sends a hash (e.g. SHA256) of $UserID$ to the user. The user verifies that the hash is correct (which authenticates the server), then sends $UserID$ (that it originally got) back to the server to prove it also knows it.

Answer 2

Your design is that the server has a key (which you call the salt, but would have to be secret here) and generates the client's public and secret values using e.g.:

$$p = ID\\ s = H(k|p),$$

where $H$ is some hash function. This seems secure: if an attacker only has access to $p$ they have no chance of generating $s$ without knowing $k$.

However, if $H$ is susceptible to a length extension attack, you would have to make sure all $p$ values are the same size. Therefore, and in case there are other weaknesses in the hash function, it would be better to use HMAC:

$$s = \operatorname{HMAC}_H(k, p)$$

As a MAC it is designed for this kind of purpose. You would have to keep $k$ secret, since an attacker knowing it could generate any $s_i$ from the corresponding $p_i$. Also, an attacker knowing some pair $(p', s')$ would be able to test guesses for $k$ offline so it would need to be a strong key.

---

There's also the alternative construction where you pick a random secret value and use HMAC to generate the public ID:

$$s = r\\ p = \operatorname{HMAC}_H(s, k)$$

The advantage here is that an attacker would be unable to generate the $s$ even if they did know $k$ – i.e. you would be able to make it a public salt rather than a key. (Attackers knowing it would be able to generate their own $(p, s)$ pairs, though.) In that case you should, however, invert the argument order and use $s$ as the HMAC key and $k$ as the message (as above), because HMAC security relies on the key being secret.

The downside is that your IDs would be random numbers (or bitstrings). You couldn't use a chosen public ID like a username, email address or a small integer. Each $s$ would also have to be a strong key, so you would need to generate more strong random numbers than in the first alternative.