13
$\begingroup$

Let $H$ be a cryptographically secure hash function, like SHA256. The output of $H$ is $N$ bytes long, with $N$ usually in the order of $32$ for commonly used hash functions.

Now, be $X$ a string, I can compute $Y = H(X)$, which is a sequence $Y_0, \ldots, Y_{N-1}$ of bytes. Now, I was wondering: is there any way to have some $H^{(i)}$ so that $\forall X,\; H^{(i)}(X) = H(X)_i$ (i.e., a function that extracts the $i$-th byte of $H(X)$) but so that computing $H^{(i)}$ is faster than computing $H$, then extracting the $i$-th byte?

In other words, if I want to just compute one byte of $H$, can I avoid carrying out some computations and save some CPU?

(I hope not. If not, is there a proof for this?)

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ I'm pretty sure it's a common security assumption (which hasn't failed us so far) that short-cutting the hash is impossible. $\endgroup$
    – SEJPM
    Commented Oct 26, 2016 at 14:36
  • $\begingroup$ It probably depends on how much faster and if you want this property for all $i$. Certainly if $H(X)$ can at best computed in time $T$, there is no way that $H^{(i)}(X)$ could be faster than $T/N$ for all $i$ ... because otherwise you could just use the $H^{(i)}$ functions to compute $H$. However, they maybe certain bytes that can be computed slightly faster. $\endgroup$
    – Guut Boy
    Commented Oct 26, 2016 at 14:57
  • $\begingroup$ Please define what you mean by "cryptographically secure". The answer depends on the precise definition. Do you mean "behaves like a random oracle"? Or do you mean "one-way and collision-resistant"? The question will have two different answers, depending on which you mean. $\endgroup$
    – D.W.
    Commented Oct 26, 2016 at 18:56
  • 5
    $\begingroup$ If there was a significant reduction, bitcoin miners would already be using it. $\endgroup$
    – k-l
    Commented Oct 26, 2016 at 23:54

3 Answers 3

Reset to default
19
$\begingroup$

For SHA-256, given its structure, the savings achievable when computing a single byte of the output is small. Argument: the computation consists of 64 rounds in cascade (or several times that for input of at least 56 bytes); full diffusion is achieved after 8 rounds, therefore all but the last 7 rounds must be computed in full (and then a large fraction of the rest, varying with which byte is kept), therefore savings are (much) less than 7/64 on the rounds, and a little extra operation on the output (worth less than 8 32-bit additions). Thanks to tylo for reporting that diffusion is much slower than I stated.

This is largely true for all common hash functions, but we can not generalize to any hash function. It is easy to construct a hash function of cost about proportional to the width needed (but somewhat inefficient, or insecure).

Improve this answer
$\endgroup$
5
  • $\begingroup$ That's what I wanted to hear. $\endgroup$
    – Matteo Monti
    Commented Oct 26, 2016 at 14:56
  • 1
    $\begingroup$ Actually, in the cascade most of the variables are just shuffled around. Only two of them depend on the entire previous round. But that's a minor detail, and even then the saving is ranging from nothing at all (working variable $A$ requires the execution of the full round) to 2 rounds (for variables $C$ and $H$). In the end it doesn't change much, though. $\endgroup$
    – tylo
    Commented Oct 26, 2016 at 15:18
  • $\begingroup$ @tylo: Looking at it more carefully, I now believe that A has no way to influence H before performing 7 rounds; and then I'm not sure that's quite full diffusion, so I added an extra round to err on the safe side. $\endgroup$
    – fgrieu ♦
    Commented Oct 26, 2016 at 19:25
  • 1
    $\begingroup$ @fgrieu Yes, it's a little more complex than 0-2 rounds, but looking at "half rounds" (calculation of $E$ but not $A$) and comparing them to full rounds would actually require looking into more details even. About the example with $A$ influencing $H$: you're right, that $A$ itself needs 7 roundsfor that, but from that round you do need $E$, so that the saving isn't the full round. $\endgroup$
    – tylo
    Commented Oct 27, 2016 at 9:50
  • 1
    $\begingroup$ @tylo: I think we can safely conclude that the achievable saving is much less than 7/64 and call it a day ! $\endgroup$
    – fgrieu ♦
    Commented Oct 27, 2016 at 9:57
7
$\begingroup$

There are definitely secure hash functions for which it is possible to calculate certain bytes fairly quickly.

There are some concatenation constructions (SHA-1(X)||MD5(X)) for which this is blatantly obvious.

While they do exist for password hashing, I am not aware of any requirements for computation time for cryptographic hash functions in general. It should therefore be possible to construct one that can calculate small parts faster than the entire function value.

Improve this answer
$\endgroup$
5
  • $\begingroup$ The question here is not to build a broken scheme, we assume that $H$ is secure, and we would like to know if it is possible to short cut some computations in order to target some parts of the output. $\endgroup$
    – Biv
    Commented Oct 26, 2016 at 15:14
  • 3
    $\begingroup$ Yes, but from the fact that H is cryptographically secure (i.e. collision and preimage resistant) it does not follow that there is no faster way to calculate the entire H(X) or parts of H(X). $\endgroup$
    – Elias
    Commented Oct 26, 2016 at 15:17
  • $\begingroup$ There could for example simply be a more efficient implementation of the entire algorithm for computing H. This does not influence the cryptographic strength. $\endgroup$
    – Elias
    Commented Oct 26, 2016 at 15:19
  • 2
    $\begingroup$ I don't know why this answer is down voted. It appears to be correct, and it answers the question. The question was "are we guaranteed that...?" and the answer is "no; here's a counterexample". That's a perfectly valid answer. @Biv, I disagree; a counterexample (what you call "building a broken scheme") is a perfectly acceptable way to demonstrate that a particular statement is false. Note that the concatenation construction is secure, under at least one standard definition of security for hash functions. $\endgroup$
    – D.W.
    Commented Oct 26, 2016 at 19:01
  • $\begingroup$ +1 to counteract the (in this case unjustified) kneejerk reaction that some people automatically downvote answers that suggest MD5(). Perhaps replacing that example with ( SHA3(X) || Argon2(X) ) would have prevented those (unjustified) downvotes. $\endgroup$
    – David Cary
    Commented Oct 27, 2016 at 20:46
3
$\begingroup$

As SEJPM said, one of the common security assumption for a hash function is that there is no way to retrieve the hash but to calculate the whole function. In other word there should be no short-cutting.

Let us have a look of how we could accelerate calculation. This could be done either by trying to reduce the numbers of iterations over the message and by tweaking the main function.

Considering the 2 mains constructions schemes we have two cases:

In both case the message has to be completely absorbed in order to retrieve the hash. So no way to cheat on that part, we will need to process the whole message.

Why is this necessary ? Because each bit of the message has an influence on the hash. If it wasn't the case it would pose some serious security threat: the difficulty to forge a hash would be less complex.

However, we know that a hash function is composed of a round function applied multiple times. Can we simplify this process and have a tweaked round function that compute only the desired bits ?

It could be an idea, but you will notice that after few rounds, the bits that you are targeting depends on full states. E.g. for MD5, $19$ rounds (over the $64$) implies a full propagation of a modified bit (source code). Therefore the you need to compute the exact full state for the $64 - 19 = 45$ iterations left of the round function.

Therefore you during the main absorption phase you won't be able to cheat and only after fully absorbed the message, you will have to do $45$ normal rounds before using your $19$ tweaked ones. This surely is not a significant gain of speed.

Also notice that the number of operations (without considering the data provenances) will be relatively similar.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ "one of the common security assumption for a hash function is that there is no way to retrieve the hash but to calculate the whole function" - No, that's not a common assumption. There are two standard assumptions for modeling hash functions: (a) the random oracle model, or (ii) one-way + collision-resistant. I don't think either one necessarily implies that there's no speedup; certainly one can easily construct hash functions where there is a speedup but that satisfy (ii). $\endgroup$
    – D.W.
    Commented Oct 26, 2016 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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