0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It is easy to find a pair. Just pass "abc", hash("abc") for example. $\endgroup$ – user253751 Jan 15 at 11:39
  • $\begingroup$ @user253751 the key is unique to each user and 50 char and the user_id has 10 chars.. $\endgroup$ – kelalaka Jan 15 at 14:34
  • $\begingroup$ If it has to be 10 chars than "abcdefgh", hash("abcdefgh") is a valid pair $\endgroup$ – user253751 Jan 15 at 14:39
  • $\begingroup$ @user253751 the OP has defined a hash function that uses a key for each user. It requires a key. It is not a good way to define a function, though. $\endgroup$ – kelalaka Jan 15 at 14:54
  • $\begingroup$ Only the validate method is public, the hash method is private. And the key in hash method is the same for every user. $\endgroup$ – icetroid Jan 16 at 1:31
1
$\begingroup$

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)

$\endgroup$
  • 1
    $\begingroup$ [reposted with correction]: due to data-timing dependency of String comparison in most contexts, an adversary able to invoke validate(String user_id, String hash) with control of the hash input, and time execution, can find hash(user_id) with mere thousands of calls. validate will return true for this hash input. This does not seem a disastrous issue in the context. $\endgroup$ – fgrieu Jan 15 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.