3
$\begingroup$

Is it possible to optimize/precalculate some results in SHA-256 if the input starts with fixed values? My input is always 1111||message. Can I precalculate the 1111 in SHA-256 to save some cycles?

$\endgroup$
5
$\begingroup$

You can't completely precalculate 1111, however, you can completely precalculate messages that have a length multiple of 512. The reason is simple, SHA-256 uses 512-bit message block per compression, i.e. the compression function of SHA-256 uses 512-bit message inputs and 256-bit previous hash values.

$$C:\{0,1\}^{256}\times \{0,1\}^{512} \to \{0,1\}^{256}$$

and

$$H_i= C(H_{i-1},m_i)$$ where each $m_i$ has 512-bit lenght and $H_0$ is the IV.


per comment below

To be honest, my input is 32-Byte ones || 32-Byte X || 32-Byte Y, what exactly do I have to precalculate with X is not constant?

32-Byte makes 256 bits, therefore you cannot completely precalculate one compression. However, still, you can pre-compute some rounds of the compression function it that helps;

The SHA-256 uses a block cipher with 64 rounds and each round uses the message as a key and you can calculate 8 rounds of the next compression call. The key $W_i$ for round $i$ is formed by the message words $M_t$ of the block is formed by;

$$W_i = \begin{cases}M_t^{(i)} & 0 \leq t \leq 15 \\ \sigma_0^{256} W_{t-2} + W_{t-7} + \sigma_1^{256}W_{t-15} + W_{t-16} & 16 \leq t \leq 63 \end{cases}$$

With the 32-byte you can precalculate only 8 rounds of the compression function. The Y has no such options since at the beginning of the rounds the previous hash value from the previous compression function is needed.


using $11..11$ as a full block:

There is one way, though not effective, one can calculate $H'=C(H_0,11..11)$. This will require padding. Now you can use this $H'$ as the $IV$ for the $\operatorname{SHA256'}$; That is

$$H_i= C(H_{i-1},m_i)$$ where each $m_i$ has 512-bit lenght and $H_0$ is the $H'$ then your real message becomes as

$$11..11 \mathbin\| padding_1 \mathbin\| X \mathbin\| Y \mathbin\| padding_2$$

$\endgroup$
5
  • $\begingroup$ to be honest, my input is 32-Byte ones || 32-Byte X || 32-Byte Y, what exactly do I have to precalculate in the SHA256 function? $\endgroup$
    – alice03
    Feb 15 at 19:36
  • $\begingroup$ the problem is, X is not constant $\endgroup$
    – alice03
    Feb 15 at 19:51
  • $\begingroup$ @alice03 it should be done now. $\endgroup$
    – kelalaka
    Feb 15 at 19:58
  • $\begingroup$ thanks, do you know if it is also possible to optimize SHAKE128 with this method? $\endgroup$
    – alice03
    Feb 18 at 1:13
  • $\begingroup$ @alice03 yes, and very little advantage, again. Well, since 11.11 is not private, See the updated method that may fit you. $\endgroup$
    – kelalaka
    Feb 18 at 8:00

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.