0
$\begingroup$

I have a function in which I need to calculate SHA1(common_prefix + random_string). I am calling this function many times so that calculation of SHA1 slows down the performance of the function. As for the all of the calls, I am using a common_prefix, is it possible to tweak SHA1 in a way that it won't calculate the hash for the (common_prefix+random_string), however it does something like a preprocessing for (common_prefix) and using this preprocess(calculated values) to calculate SHA1(common_prefix+random_string)?

Is it somehow possible to do it?

$\endgroup$
  • $\begingroup$ For reference, what are the respective bit lengths for common_prefix and random_string? $\endgroup$ – Paul Uszak Mar 8 '19 at 15:28
  • $\begingroup$ Use blake faster and more secure. $\endgroup$ – kelalaka Mar 8 '19 at 15:55
  • $\begingroup$ You should be extremely careful about using SHA-1! SHA-1 has failed its original security goal of collision resistance. You should use SHA-2, or SHA-3, or BLAKE2, unless you can prove that collision resistance is unnecessary for your application with reference to a design document articulating what your application does with what resources for whom and what its security goals are. $\endgroup$ – Squeamish Ossifrage Mar 8 '19 at 17:02
  • $\begingroup$ This is not intented for the purpose of security. @PaulUszak length of common_prefix is 64 bytes and random_string length will be up to 8-9. $\endgroup$ – user1945535 Mar 8 '19 at 17:04
  • $\begingroup$ Yeh, no. The question was to ascertain whether there is any point in bothering at all with multi-part hashing. Remember that SHAs come in fixed block sizes. $\endgroup$ – Paul Uszak Mar 8 '19 at 17:53
4
$\begingroup$

Yes, you can save effort, if the common prefix is at least one 512-bit block.

Speaking mathematically: For a padded message $m = m_1 \mathbin\| m_2 \mathbin\| \cdots \mathbin\| m_\ell$ of $\ell$ 512-bit blocks, $$\operatorname{SHA1}(m) = f(\cdots f(f(\mathit{iv}, m_1), m_2) \cdots, m_\ell),$$ where $f$ is SHA-1's internal compression function. For example, suppose you have a pair of two-block messages $m_1 \mathbin\| m_2$ and $m_1 \mathbin\| m_2'$ with a common prefix $m_1$ and distinct suffixes $m_2$ and $m_2'$. Then

\begin{align} \operatorname{SHA1}(m_1 \mathbin\| m_2) &= f(f(\mathit{iv}, m_1), m_2), \\ \operatorname{SHA1}(m_1 \mathbin\| m_2') &= f(f(\mathit{iv}, m_1), m_2'), \end{align}

which share the common subexpression $f(\mathit{iv}, m_1)$. If you precompute $h_0 = f(\mathit{iv}, m_1)$, then you can more quickly compute $\operatorname{SHA1}(m_1 \mathbin\| m_2) = f(h_0, m_2)$ and $\operatorname{SHA1}(m_1 \mathbin\| m_2') = f(h_0, m_2')$.

Speaking programmatically: Most implementations of SHA-1 support an init/update/final API. For example, to hash the string hello world with OpenSSL's API you might write:

SHA_CTX ctx;
unsigned char h[20];

SHA1_Init(&ctx);
SHA1_Update(&ctx, "hello", 5);
SHA1_Update(&ctx, " ", 1);
SHA1_Update(&ctx, "world", 5);
SHA1_Final(h, &ctx);

The state of the SHA-1 computation, including buffering to split messages into blocks, is stored in the SHA_CTX object. In some cases, like in OpenSSL, you can copy the context in order to save any effort that had already been done to hash what you've fed into it so far:

SHA_CTX ctx, ctx0, ctx1;
unsigned char h0[20], h1[20];

SHA1_Init(&ctx);
SHA1_Update(&ctx, "Once before a console dreary, while I programmed, weak and weary", 64);

ctx0 = ctx;
SHA1_Update(&ctx0, "\nOver many a curious program which did TECO's buffer fill...", 60);
SHA1_Final(h0, &ctx0);

ctx1 = ctx;
SHA1_Update(&ctx1, "\nO vermin yak urea's pro-Grammy itched dt casbah fur fell...", 60);
SHA1_Final(h1, &ctx1);

The resulting hashes are

  • h0 = b2b36d39d4431b3a57b7c30630bbbde9553b50ae
  • h1 = 2a0dae0548307b4ef33c0f1fedd7cbad2c32d5d8
$\endgroup$
  • $\begingroup$ Thanks for the detailed information. I have tried out this way, however looks like the generated hash is not correct as I checked online. The common_prefix was 64 'a' chars as following: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa. Then I just added a letter 'w'. I used 64 'a' since you said it should be at least 512 bit length. Then the combined was incorrect. Do you know what might cause this? $\endgroup$ – user1945535 Mar 8 '19 at 17:00
  • 1
    $\begingroup$ The SHA-1 hash of the prefix is 0098ba824b5c16427bd7a1122a5a442a25ec644d, and the SHA-1 hash of the prefix with w added to it is 9deba23257f97a734f398132ad537d46b0913b94. If your code isn't computing these, there's a bug in your code. I don't know what code you're using, so I can't say what the bug is! $\endgroup$ – Squeamish Ossifrage Mar 8 '19 at 17:08
  • $\begingroup$ yes there was indeed a bug that I missed related to the size that I need to update. Thanks a lot for the help. $\endgroup$ – user1945535 Mar 8 '19 at 20:45
2
$\begingroup$

SHA-1 processes data in blocks, see the following image: SHA-1 processing

This means that common SHA-1 implementation provide the following three stateful functions:

  • Init() - initialize the state to the IV
  • Update(data) - append data to the input, the state for this may either come from Init or a previous Update call.
  • Final() - computes the actual hash based on the state

Now this means that usually you would compute the SHA1 hash for your data in an object-oriented language as follows:

SHA1 instance(); // C++ notation
instance.Init();
instance.Update(common_prefix)
instance.Update(random_string)
return instance.Final()

Now all you have is to save and copy the internal state after the first Update call and re-use it across your differing instances. Of course be aware that no speedup is to be expected if the common_prefix is less than 512 bit, because in this case the internal compression function isn't invoked and all that happens is that the implementation will buffer the input.

$\endgroup$
  • $\begingroup$ FYI: This works for essentially all modern hash functions, but the threshold will be a different value. $\endgroup$ – SEJPM Mar 8 '19 at 16:16

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.