How safe is my method

Question

I'm building a website. I have an API which takes 2 parameters: delete_user(user_id, hash).

And there is method to evaluate hash using SHA512:

String hash(String user_id)
{
   String key = "23jfk3jf...343fk";
   return SHA512(user_id + SHA512(key));  
}

And the second method to validate:

bool validate(String user_id, String hash)
{
   if(hash(user_id) == hash)
   {
        return true;
   }
   else return false;
}

1. Every user knows his user_id and the hash value of his user_id.
2. user_id has length K symbols
3. the key in hash method has M symbols
4. hash method is not public to users, but validate method is.

Is it hard for a user to find any pair (String user_id, String hash), for which validate will return true (of course, user_id is not his own account's user_id). Let's say K = 10 and M = 50?

Answer 1

This is the pre-image attack on hash functions, i.e.

• pre-image attack : given a hash value $y$ find a pre-image $x$ such that $y=h(x)$.

  Good designed cryptographic hash functions have $\mathcal{O}(2^{n})$ classical pre-image resistance for $n$-bit output. The classical attack tries all possible input space to find a $x$ that hashes the target hash value. Due to the birthday paradox, we don't expect that all values exist in $2^n$ bit space. Some will occur more than one. This will not change the complexity.

Assuming that you are using base64 encoding to store the values, then each position in the string hash 64 possible character (= is used for padding).

Concentrate on a target user_id, an attacker will search 50 character keyspace to match. $$ \text{hash} \stackrel{?}{=}\operatorname{SHA512}(\text{user_id}, \operatorname{SHA512}(key_i)$$ This will make $64^{50} = 2^{6\cdot 50} = 2^{300}$ This is a huge number to deal with any available computing power. If you are using another encoding, you can adjust the values.

Hash functions are designed to run fast. This will also make an attack time fast if there is any. You can make it slow by making iterations or you can use already existing solutions like HKDF, PBKDF2, etc. They have iterations to increase the attack time.

Your scheme seems fine up besides there are some considerations;

• There is already HMAC (Hash Based Message Authentication Code or keyed-hash message authentication code). It's security proven by Bellare, Mihir (June 2006). New Proofs for NMAC and HMAC: Security without Collision-Resistance under the assumption that the compression function is PRF.

  You can use HMAC with SHA512, too. If the size does not really an issue, you the full output of the HMAC-SHA512, (or your scheme)