Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Recently I've been trying to implement some Bitcoin-related code, and I've stumbled upon a weird concept, a SHA-256 "midstate". Some explanation is given here.

The general concept is that Bitcoin relies on performing SHA hashing of a 128 byte data chunk many times, but only the second half of that chunk changes. This is why the concept of "midstate" is used. As I understand it, in order to perform SHA on 128 bytes of data, one needs to divide the hashing into operations on first and second 64 bytes of the data. As results of first hashing are constant, one would save them as this "midstate", and before hashing the changed second half of bytes, one would restore the "midstate" instead of calculating it again.

Can anyone explain how would I calculate this "midstate" having a library that calculates a whole SHA-256 hash, or alternatively which libraries support calculating of something like that?

share|improve this question
1  
For details about which libraries can be used out-of-the-box, I suggest posting a specific question on StackOverflow instead. That part of your question seems off-topic here. –  Henrick Hellström Feb 16 '12 at 7:39

2 Answers 2

up vote 8 down vote accepted

SHA-256 uses an internal compression function $f$ which takes two inputs, of size 512 and 256 bits respectively, and outputs 256 bits. Hashing works like this:

  1. Input message $M$ is first padded by appending between 129 and 640 bits (inclusive), resulting into a padded message $M'$ whose length (in bits) is a multiple of 512.

  2. $M'$ is split into $n$ 512-bit blocks $M_1$, $M_2$,... $M_n$ (each block has length 64 bytes).

  3. Set $X_0$ (a 256-bit value) to a conventional initial value (which is specified in the SHA-256 standard, section 5.3.3).

  4. Process each block in due sequence, by computing $X_i = f(M_i, X_{i-1})$ for all $i$ from $1$ to $n$.

  5. The hash value is $X_n$.

The $X_i$ values can be seen as the successive contents of a state variable $X$ (indeed, when you have computed $X_i$, you can discard $X_{i-1}$ since that value will not be used thereafter).

Your "midstate" is $X_1$: that's the contents of the "state" after having processed the first block. Since all your 128-byte messages begin with the exact same 64-byte header, all the hash computations formally begin by processing the same block $M_1$, with the same $X_0$ (the conventional initial value), resulting in the same $X_1 = f(M_1, X_0)$. You would like to "restart" each computation from that value $X_1$ directly, to avoid recomputing it again and again.

Doing that over an existing library implementing SHA-256 may or may not be easy, depending on what facilities that library offers. For a basic SHA-256 library, there are two possible issues:

  • The library may refuse to output $X_1$, because it would insist on computing hash values over a padded message only; you want to have the output of $f$ over a given $M_1$ block without padding.

  • The library may refuse to start a new computation starting with the $X_1$ you provide instead of the conventional initial value $X_0$.

Some libraries offer a bit more. For instance, consider sphlib. With that library, there are two ways to achieve what you seek:

  • The implementation works over a context structure (of type sph_sha256_context) which represents the current state. You can thus begin a computation by processing the header, and then clone the context to make many hash computations which start from that exact point. It would look like this:
sph_sha256_context sc;

sph_sha256_init(&sc);
sph_sha256(&sc, header, 64);
for (/* all 128-byte messages */) {
        sph_sha256_context sc2;
        unsigned char second_half[64];
        unsigned char out[32];

        /* set second_half[] to the second half of the 128-byte message */
        sc2 = sc;
        sph_sha256(&sc2, second_half, 64);
        sph_sha256_close(&sc2, out);
        /* SHA-256 output is in out[] */
}
  • sphlib offers an sph_sha256_comp() function which implements exactly the compression function $f$. You can use it to compute SHA-256 "manually", block by block, starting from any state value $X$ you wish. You would have to take care of encoding issues (SHA-256 is big-endian throughout, use sph_dec32be() and sph_enc32be() to do that properly and portably) and padding. If all your messages have length exactly 128 bytes, then padding is always a full 64-byte block, consisting in a byte of value 0x80, followed by 61 bytes of value 0x00, and then two bytes of value 0x04 0x00. Expressed in 16 32-bit words, first word has numerical value 0x80000000, followed by 14 words of value zero, then a final word of value 0x00000400.

For heavy hash crunching (I understand that's the point), your best bet is still probably to extract the inner loop from an opensource implementation, and integrate it directly in your code, so as to avoid any overhead from the library API. You also probably want to avoid heavy encoding/decoding, and work over 32-bit words directly (while SHA-256 takes as input a bit sequence, it soon converts it to a sequence of 32-bit words and works over that). I invite you to do your own SHA-256 implementation, working from the standard: it is not hard, that standard is reasonably clear, and it will grant you enough knowledge on how SHA-256 works to optimize your code (even if you end up reusing parts of some other implementation).

share|improve this answer
1  
If the goal is to optimize performance as far as possible, it's worth pointing out that SHA-256 performs its arithmetic operations in big endian byte order. If the compression function (SHACAL in Davies-Meyer mode) performs a bswap on the internal state at the beginning and the end, that step can be omitted and performed on the last block only, provided that the initial state is adjusted accordingly. –  Henrick Hellström Feb 19 '12 at 8:28

The SHA-256 algorithm works by applying an encryption function in Davies-Meyer mode and Merkle-Damgård chaining. Merkle-Damgård works by first dividing the message to-be-hashed into chunks. In the case of SHA-256 these chunks are 64 octets long. Because Merkle-Damgård chaining is used, the internal state after processing the first 64 octet chunk depends only on the algorithm itself and the value of that first 64 octet chunk. If the latter is also fixed for several messages to-be-hashed, this internal state can be pre-calculated to save processing time. Subsequent messages can be hashed by starting with the "midstate" and processing only the following chunks of the padded message.

A "midstate" can be calculated if you have a SHACAL2 cipher implementation and implement the Davies-Meyer step and Merkle-Damgård padding and chaining yourself. It is not uncommon for hash algorithm implementations to already have implemented support for this.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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