Optimizing SHA-256 implementation for fixed input prefix

Question

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?

Answer 1

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$$