0
$\begingroup$

Let's suppose that for a crypto protocol a 32-byte-to-32-byte one-way function is needed. Proposals are:

  1. $\textrm{sha256}(x)$

  2. $\textrm{hmac}(\textrm{sha256}, x, x)$

  3. $\textrm{hmac}(\textrm{sha256}, x, f(x))$, where $f$ is a 32-byte-to-32-byte function whose inverse is easy to compute, e.g. bytewise reverse (whose inverse is itself).

Are #2 and #3 any harder to reverse than #1 (plain SHA-256)? Is there an even harder to reverse proposal?

I understand that if the attacker has access to a generic method with which it's possible to reverse any 32-byte-to-32-byte function, then #1, #2 and #3 are equally easy to reverse, and thus they are equally secure.

Let's suppose that in the future someone finds a fast way to compute the inverse of SHA-256 on 32-byte inputs, but there is no other fast generic reversing method is available. (The attacker is highly motivated to reverse SHA-256, because doing so can possibly break many crypto protocols.) This doesn't help finding the inverse of #2 or #3, because they have an outer SHA-256 call whose input is 64 bytes.

$\endgroup$
  • $\begingroup$ Which HMAC are you using? $\endgroup$ – Elias Dec 2 '17 at 10:23
  • $\begingroup$ @Elias: HMAC: en.wikipedia.org/wiki/Hash-based_message_authentication_code . Do you have a better recommendation? $\endgroup$ – pts Dec 2 '17 at 14:40
  • $\begingroup$ HMAC is a construction. You need to specify which hash function you use. I assume you mean HMAC-SHA256? $\endgroup$ – Elias Dec 2 '17 at 19:52
  • $\begingroup$ @Elias: Yes, I explicitly mention $\textrm{hmac}(\textrm{sha256}, \ldots)$ in the question. $\endgroup$ – pts Dec 3 '17 at 0:04
  • $\begingroup$ Ah, I didn't understand your syntax there. I thought that was HMAC applied to some SHA256 output. $\endgroup$ – Elias Dec 3 '17 at 10:05
2
$\begingroup$

(2) and (3) are expected to cost slightly more to invert than (1), no matter what the distribution on $x$ might be, because the only known preimage search algorithms treat them as black boxes to be evaluated forward and search more or less by guessing and checking (optimized with rainbow tables or quantum computers).

The expected cost of any such algorithm is the cost of evaluating the function, times the expected number of times you must evaluate it. The cost of evaluating (2) and (3) is the same, but they both cost about twice what (1) costs. You can make things much costlier by using a modern password hash such as scrypt or argon2.

However, if the only possible values of $x$ are the strings red and blue with equal probability, then the difference in cost is negligible. The adversary has a 50-50 chance of getting it right in one try.

So a much more important question is: How are you using this in your application? How does it fit into the protocol? What security properties do you hope to achieve by it? What costs do you hope to impose on an adversary trying to break the system?

If the distribution on $x$ has >=128 bits of entropy, or if there are actually two inputs of which one is a secret with >=128-bit entropy and the other maybe has low entropy, there's no reason to try to raise the costs of evaluating the function by iterating SHA-256 or using scrypt or argon2. On the other hand, if you're storing password hashes, then you should absolutely use something designed for password hashes that raises the area*time cost and thwarts attackers with high levels of parallelism.

$\endgroup$
0
$\begingroup$

Disclaimer: I'm not an expert.

I think this is security-by-obscurity. When you have a transformation of x->y where they are the same size, in theory the "address space" of the possible answers is $2^{256}$ results.

This is the same regardless of what you will use since the underlying transformation is based on SHA256, it means that if it "cracked", the only difference between your options will be extra steps that obscure the actual mathematical base of it all.

In short: I don't think it matters.

$\endgroup$
  • $\begingroup$ Does your reasoning explain that #2 is not any better than #1 if the extra value of obscurity is 0 and only SHA-256 gets cracked? I'm not convinced about this, could you please elaborate why? I can't (yet) see how a crack for SHA-256 can easily be applied to crack #2. $\endgroup$ – pts Dec 2 '17 at 10:12
  • $\begingroup$ I understand that if the attacker has access to a generic crack, with which it's possible to reverse any 32-byte-to-32-byte function, then #1, #2 and #3 are equally easy to reverse. $\endgroup$ – pts Dec 2 '17 at 10:14
  • $\begingroup$ That's my personal understanding. Since the main "transformation" done is SHA256 and HMAC is effectively concat + more rounds of SHA256, the extra rounds will not exactly help since all the attacker have to do is perform the reversal a few more times. $\endgroup$ – LiraNuna Dec 2 '17 at 19:12
  • $\begingroup$ If you look at the definition of HMAC, you'll see that it calls the hash (SHA-256) on longer (64-byte) inputs in our case. So if the attacker has a crack for 32-byte-to-32-byte SHA-256 only, it's not useful for cracking HMAC-SHA-256. Given that I still don't understand your reasoning. $\endgroup$ – pts Dec 3 '17 at 0:10

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.