Incremental sha256sum computation

Question

I ran across an interesting computation for a sha256sum that did not rely on the openssl or crypto libraries pdfcrack/sha256.c. The only difficulty with either of the functions (sha256 and sha256f) was they required the total number of bytes be provided. That makes for rather large allocation when wanting a sum for large files. OpenSSL provides for a final sha256sum based on intermediate calculations using less than the entire number of bytes allowing for a small fixed buffer to be used and the sum computed by calling SHA256_Update on the individual buffers that make up a file, and then a final call to SHA256_Final to compute the final sum.

Starting with the pdfcrack/sha256.c file, out of curiosity rather than any real need, I decided to see if that code could be split in a manner that would allow final sha256sum to be computed from incremental portions of input in a way similar to how it is handled in openssl. This code followed.

Similar to OpenSSL, a context struct is provided to hold the intermediate working values for the sum. This ended up being more of a necessity than any desire to do something similar. The reason being, limiting access to intermediate values through an opaque pointer pretty much dictated the approach. The remainder was just chasing what a sha256sum was down the rabbit-hole to figure out how the total function could be split into intermediate calculations, and then accounting for partial blocks of data from input, etc.

What I am looking for is comments on whether my use of the context struct makes sense in the way it is handled, whether there may be some way around having to dynamically allocate the context behind the scenes (I haven't come up with any, and since there is only a single allocation and free, it isn't a big performance concern). I would also like comment on the static hdefault used to store the final sum if for some reason the user provides a NULL pointer as a parameter (that tweak was borrowed directly from openssl, I originally had the functions as void rather than returning a pointer, but that approach made more sense) Any other general comments are welcome as well. Just note the macros and the sha256hashblock were pretty much straight pulls from the pdfcrack file.

The header and source file for the sha256sum implementation is provided below. A short driver file follows that mimics what sha256sum does from the command line. A gcc compile string would be:

$ gcc -Wall -Wextra -pedantic -Wshadow -std=c11 -Ofast sha256d.c \
  -o sha256fread sha256fread.c

sha256d.h

#ifndef _SHA256_DCR_H_
#define _SHA256_DCR_H_

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

#define HASHL256 32

typedef struct ctx_t ctx;

ctx *sha256_init (void);
void sha256_update (ctx *c, const uint8_t *msg, const uint64_t msglen);
uint8_t *sha256_final (ctx *c, uint8_t *hash);
void sha256_free (ctx *c);

uint8_t *sha256 (const uint8_t *msg, const uint64_t msglen, uint8_t *hash);

#endif /** _SHA256_DCR_H_ */

sha256d.c

#include "sha256d.h"

enum { HBLK256 = 8, DGST256 = 64 }; /* block & digest size */

struct ctx_t {  /** context for intermediate computations */
    uint8_t blk[DGST256],   /* storage for sha block */
            blklen;         /* stored block length */
    uint32_t h[HBLK256];    /* working variables */
    uint64_t msglen;        /* total message length */
};

/** sha256 computation macros */
#define ROTR(x, n) (( x >> n ) | ( x << (32 - n)))

#define Choice(x, y, z) ( z ^ ( x & ( y ^ z )))
#define Majority(x, y, z) (( x & y ) ^ ( z & ( x ^ y )))

#define Sigma0(x) (ROTR(x, 2) ^ ROTR(x, 13) ^ ROTR(x, 22))
#define Sigma1(x) (ROTR(x, 6) ^ ROTR(x, 11) ^ ROTR(x, 25))

#define sigma0(x) (ROTR(x, 7) ^ ROTR(x, 18) ^ (x >> 3))
#define sigma1(x) (ROTR(x, 17) ^ ROTR(x, 19) ^ (x >> 10))

#define ROUND(a,b,c,d,e,f,g,h,k,data)           \
  h += Sigma1(e) + Choice(e, f, g) + k + data;      \
  d += h;                       \
  h += Sigma0(a) + Majority(a ,b ,c);

/** sha256 sha2 algorithm providing update to 'blk' */
static void sha256hashblock (const uint8_t *blk, uint32_t *hash) {
    uint32_t W[64];
    uint32_t A, B, C, D, E, F, G, H;
    int i;

    /* 1. Prepare the message schedule */
    for (i = 0; i < 16; ++i) {
        W[i] = ((unsigned)blk[i*4    ] << 24)
            | ((unsigned)blk[i*4 + 1] << 16)
            | ((unsigned)blk[i*4 + 2] << 8)
            |  blk[i*4 + 3];
    }
    for (; i < 64; ++i) {
        W[i] = sigma1(W[i-2]) + W[i-7] + sigma0(W[i-15]) + W[i-16];
    }

    /* 2. Initialize the eight working variables */
    A = hash[0];
    B = hash[1];
    C = hash[2];
    D = hash[3];
    E = hash[4];
    F = hash[5];
    G = hash[6];
    H = hash[7];

    /* 3. Compression loop unrolled */
    ROUND(A, B, C, D, E, F, G, H, 0x428a2f98, W[ 0]);
    ROUND(H, A, B, C, D, E, F, G, 0x71374491, W[ 1]);
    ROUND(G, H, A, B, C, D, E, F, 0xB5C0FBCF, W[ 2]);
    ROUND(F, G, H, A, B, C, D, E, 0xE9B5DBA5, W[ 3]);
    ROUND(E, F, G, H, A, B, C, D, 0x3956C25B, W[ 4]);
    ROUND(D, E, F, G, H, A, B, C, 0x59F111F1, W[ 5]);
    ROUND(C, D, E, F, G, H, A, B, 0x923F82A4, W[ 6]);
    ROUND(B, C, D, E, F, G, H, A, 0xAB1C5ED5, W[ 7]);
    ROUND(A, B, C, D, E, F, G, H, 0xD807AA98, W[ 8]);
    ROUND(H, A, B, C, D, E, F, G, 0x12835B01, W[ 9]);
    ROUND(G, H, A, B, C, D, E, F, 0x243185BE, W[10]);
    ROUND(F, G, H, A, B, C, D, E, 0x550C7DC3, W[11]);
    ROUND(E, F, G, H, A, B, C, D, 0x72BE5D74, W[12]);
    ROUND(D, E, F, G, H, A, B, C, 0x80DEB1FE, W[13]);
    ROUND(C, D, E, F, G, H, A, B, 0x9BDC06A7, W[14]);
    ROUND(B, C, D, E, F, G, H, A, 0xC19BF174, W[15]);
    ROUND(A, B, C, D, E, F, G, H, 0xE49B69C1, W[16]);
    ROUND(H, A, B, C, D, E, F, G, 0xEFBE4786, W[17]);
    ROUND(G, H, A, B, C, D, E, F, 0x0FC19DC6, W[18]);
    ROUND(F, G, H, A, B, C, D, E, 0x240CA1CC, W[19]);
    ROUND(E, F, G, H, A, B, C, D, 0x2DE92C6F, W[20]);
    ROUND(D, E, F, G, H, A, B, C, 0x4A7484AA, W[21]);
    ROUND(C, D, E, F, G, H, A, B, 0x5CB0A9DC, W[22]);
    ROUND(B, C, D, E, F, G, H, A, 0x76F988DA, W[23]);
    ROUND(A, B, C, D, E, F, G, H, 0x983E5152, W[24]);
    ROUND(H, A, B, C, D, E, F, G, 0xA831C66D, W[25]);
    ROUND(G, H, A, B, C, D, E, F, 0xB00327C8, W[26]);
    ROUND(F, G, H, A, B, C, D, E, 0xBF597FC7, W[27]);
    ROUND(E, F, G, H, A, B, C, D, 0xC6E00BF3, W[28]);
    ROUND(D, E, F, G, H, A, B, C, 0xD5A79147, W[29]);
    ROUND(C, D, E, F, G, H, A, B, 0x06CA6351, W[30]);
    ROUND(B, C, D, E, F, G, H, A, 0x14292967, W[31]);
    ROUND(A, B, C, D, E, F, G, H, 0x27B70A85, W[32]);
    ROUND(H, A, B, C, D, E, F, G, 0x2E1B2138, W[33]);
    ROUND(G, H, A, B, C, D, E, F, 0x4D2C6DFC, W[34]);
    ROUND(F, G, H, A, B, C, D, E, 0x53380D13, W[35]);
    ROUND(E, F, G, H, A, B, C, D, 0x650A7354, W[36]);
    ROUND(D, E, F, G, H, A, B, C, 0x766A0ABB, W[37]);
    ROUND(C, D, E, F, G, H, A, B, 0x81C2C92E, W[38]);
    ROUND(B, C, D, E, F, G, H, A, 0x92722C85, W[39]);
    ROUND(A, B, C, D, E, F, G, H, 0xA2BFE8A1, W[40]);
    ROUND(H, A, B, C, D, E, F, G, 0xA81A664B, W[41]);
    ROUND(G, H, A, B, C, D, E, F, 0xC24B8B70, W[42]);
    ROUND(F, G, H, A, B, C, D, E, 0xC76C51A3, W[43]);
    ROUND(E, F, G, H, A, B, C, D, 0xD192E819, W[44]);
    ROUND(D, E, F, G, H, A, B, C, 0xD6990624, W[45]);
    ROUND(C, D, E, F, G, H, A, B, 0xF40E3585, W[46]);
    ROUND(B, C, D, E, F, G, H, A, 0x106AA070, W[47]);
    ROUND(A, B, C, D, E, F, G, H, 0x19A4C116, W[48]);
    ROUND(H, A, B, C, D, E, F, G, 0x1E376C08, W[49]);
    ROUND(G, H, A, B, C, D, E, F, 0x2748774C, W[50]);
    ROUND(F, G, H, A, B, C, D, E, 0x34B0BCB5, W[51]);
    ROUND(E, F, G, H, A, B, C, D, 0x391C0CB3, W[52]);
    ROUND(D, E, F, G, H, A, B, C, 0x4ED8AA4A, W[53]);
    ROUND(C, D, E, F, G, H, A, B, 0x5B9CCA4F, W[54]);
    ROUND(B, C, D, E, F, G, H, A, 0x682E6FF3, W[55]);
    ROUND(A, B, C, D, E, F, G, H, 0x748F82EE, W[56]);
    ROUND(H, A, B, C, D, E, F, G, 0x78A5636F, W[57]);
    ROUND(G, H, A, B, C, D, E, F, 0x84C87814, W[58]);
    ROUND(F, G, H, A, B, C, D, E, 0x8CC70208, W[59]);
    ROUND(E, F, G, H, A, B, C, D, 0x90BEFFFA, W[60]);
    ROUND(D, E, F, G, H, A, B, C, 0xA4506CEB, W[61]);
    ROUND(C, D, E, F, G, H, A, B, 0xBEF9A3F7, W[62]);
    ROUND(B, C, D, E, F, G, H, A, 0xC67178F2, W[63]);

    /* 4. Compute the intermediate hash value */
    hash[0] += A;
    hash[1] += B;
    hash[2] += C;
    hash[3] += D;
    hash[4] += E;
    hash[5] += F;
    hash[6] += G;
    hash[7] += H;
}

/** sha256_init initializes the context used for
 *  intermediate hash calculations for DGST256
 *  sized blocks.
 */
ctx *sha256_init (void)
{
    ctx *c = malloc (sizeof *c);
    if (!c) {
        perror ("sha256_init() error: memory exhausted");
        return NULL;
    }

    memset (c->blk, 0, DGST256);
    c->blklen = 0;
    c->msglen = 0;

    (c->h)[0] = 0x6a09e667;
    (c->h)[1] = 0xbb67ae85;
    (c->h)[2] = 0x3c6ef372;
    (c->h)[3] = 0xa54ff53a;
    (c->h)[4] = 0x510e527f;
    (c->h)[5] = 0x9b05688c;
    (c->h)[6] = 0x1f83d9ab;
    (c->h)[7] = 0x5be0cd19;

    return c;
}

/** sha256_update updates the context 'c' with hash for 'msg'
 *  of 'msglen' size. used to allow sha2 sum calculation for
 *  large files without requiring memory allocation to hold
 *  entire file. can be called for any size msglen.
 */
void sha256_update (ctx *c, const uint8_t *msg, const uint64_t msglen)
{
    uint8_t req = DGST256 - c->blklen,
            off = DGST256 - req;
    uint64_t i;

    c->msglen += msglen;

    if (msglen < req) {  /* handle update less than full blk */
        memcpy (&(c->blk)[c->blklen], msg, msglen);
        c->blklen += msglen;
        return;
    }

    if (c->blklen) {    /* if partial block from last update */
        memcpy (&(c->blk)[c->blklen], msg, req);
        sha256hashblock (c->blk, c->h);
    }

    msg += off;     /* no need to preserve original ptr here */
    for (i = 0; i + DGST256 <= msglen; i += DGST256)
        sha256hashblock (msg + i, c->h);

    c->blklen = msglen - i;
    memcpy (c->blk, msg + i, c->blklen);
}

/** sha256_final provides final padding of context blk
 *  before computing final sha256sum. 'hash' must be of
 *  sufficient size to store the HASHL256 (32) byte sum.
 *  if hash is 'NULL', static storage in 'hdefault' is
 *  used. a pointer to the final sha256sum is returned.
 */
uint8_t *sha256_final (ctx *c, uint8_t *hash)
{
    static uint8_t hdefault[HASHL256];
    uint32_t i;

    if (hash == NULL)
        hash = hdefault;

    /* pad the message and update context blk */
    (c->blk)[(c->blklen)++] = 0x80;
    if (c->blklen > 56) {
        while (c->blklen < DGST256)
            (c->blk)[(c->blklen)++] = 0;

        sha256hashblock (c->blk, c->h);
        c->blklen = 0;
    }
    while (c->blklen < 56)
        (c->blk)[(c->blklen)++] = 0;

    (c->blk)[56] = 0;
    (c->blk)[57] = 0;
    (c->blk)[58] = 0;
    (c->blk)[59] = 0;
    (c->blk)[60] = (uint8_t)(c->msglen >> 21);
    (c->blk)[61] = (uint8_t)(c->msglen >> 13);
    (c->blk)[62] = (uint8_t)(c->msglen >> 5);
    (c->blk)[63] = (uint8_t)(c->msglen << 3);
    sha256hashblock (c->blk, c->h);

    /* fill hash from final working variable values */
    for (i = 0; i < HBLK256; ++i) {
        hash[i*4]     = (uint8_t)((c->h)[i] >> 24);
        hash[i*4 + 1] = (uint8_t)((c->h)[i] >> 16);
        hash[i*4 + 2] = (uint8_t)((c->h)[i] >> 8);
        hash[i*4 + 3] = (uint8_t)(c->h)[i];
    }

    return hash;    /* copy to hash */
}

/** sha256_free free memory allocated to context */
void sha256_free (ctx *c)
{
    if (c)
        free (c);
}

/** sha256 computes sha256sum from bytes in 'msg'.
 *  'msglen' provides the number of bytes in 'msg',
 *   and the final sha256sum is stored in 'hash' and 
 *   a pointer returned, or if 'hash' is NULL, the
 *   static array 'hdefault' is used as storage for
 *   the sha256sum. on error a sha256sum of all zeros
 *   is returned.
 */
uint8_t *sha256 (const uint8_t *msg, const uint64_t msglen, uint8_t *hash)
{
    ctx *c = NULL;
    static uint8_t hdefault[HASHL256];

    if (hash == NULL)
        hash = hdefault;

    if (!(c = sha256_init()))
        return hdefault;
    sha256_update (c, msg, msglen);
    sha256_final (c, hash);
    sha256_free (c);

    return hash;
}

sha256fread.c

A short example file that mimics sha256sum use from the command line. Just give it a filename or redirect stdin to it.

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

#include "sha256d.h"

#ifndef BUFSIZ
#define BUFSIZ 8192
#endif

int main (int argc, char **argv) {

    uint8_t i, hash[HASHL256] = "";
    ctx *c = sha256_init();     /* sha context initialization */
    FILE *fp = argc > 1 ? fopen (argv[1], "rb") : stdin;

    if (!c)     /* validate context allocated */
        return 1;

    if (!fp) {  /* validate file open for reading */
        fprintf (stderr, "error: file open failed '%s'.\n", argv[1]);
        return 1;
    }

    for (;;) {  /* read input in BUFSIZ chunks, updating hash in ctx */
        uint8_t buf[BUFSIZ] = "";
        int64_t nread = fread (buf, 1, BUFSIZ, fp);
        if (ferror (fp)) {
            perror ("read error occurred");
            return 1;
        }
        sha256_update (c, buf, nread);
        if (nread < BUFSIZ)         /* if last chunk read, exit loop */
            break;
    }
    if (fp != stdin) fclose (fp);   /* close file if not stdin */

    sha256_final (c, hash);         /* compute final sha256sum  */
    sha256_free (c);                /* free context, ~138 bytes */

    for (i = 0; i < HASHL256; i++)      /* output sha256sum */
        printf ("%02" PRIx8, hash[i]);
    printf ("  %s\n", fp == stdin ? "-" : argv[1]);

    return 0;
}

Answer 1

• Each length (especially msglen) shall be declared size_t rather than uint64_t.

• There is no reason to const-qualify msglen.

• Computation of

  uint8_t req = DGST256 - c->blklen,
          off = DGST256 - req;
  

  looks strange. DGST256 - req == DGST256 - (DGST256 - c->blklen) == c->blklen. I recommend shorter and cleaner

  uint8_t off = c->blklen;
  

• I also recommend to streamline the sha256_update logic. As written, it is very hard to follow. Consider something along the lines of

  void sha256_update (ctx *c, const uint8_t *msg, size_t msglen)
  {
      c->msglen += msglen;
  
      while (msglen > 0) {
          uint8_t chunk = min(DGST256 - c->blklen, msglen);
  
          memcpy(&c->blk[c->blklen], msg, chunk);
  
          msg += chunk;
          msglen -= chunk;
          c->blklen += chunk;
  
          if (c->blklen < DGST256) {
              return;
          }
  
          sha256hashblock (c->blk, c->h);
          c->blklen = 0;
      }
  }
  

• To address your direct concerns, your handling of ctx is perfectly reasonable. On the other hand, I would prefer sha256_final to assume that hash parameter is always valid.

Answer 2

I am looking for is comments on whether my use of the context struct makes sense in the way it is handled, whether there may be some way around having to dynamically allocate the context behind the scene

The usual work-around it to expose struct ctx_t to provide space. Yet what OP is doing is fine.

Any other general comments are welcome as well.

Code curiously unnecessarily limits the length to 2²⁹ even though c->msglen is 64-bit.

Suggested alternative code to use byte lengths up to 2⁶¹.

// (c->blk)[56] = 0;
...
// (c->blk)[63] = (uint8_t)(c->msglen << 3);

uint64_t bit_len = c->msglen;
bit_len *= 8;  // 8 bits per byte
// I like doing the above in 2 lines in case `c->msglen` is narrowed.

for (index = 63; index >= 56; index--) {
  (c->blk)[index] = (uint8_t)bit_len;
  bit_len /= 256;
}

---

It is not clear c->blklen is always in the range [0...63] when (c->blk)[(c->blklen)++] = 0x80; is executed. I'd expect cleaner code in sha256_update() that shows this.

---

if() not needed.

   // if (c)
     free (c);

---

Alternative code that I find clearer

// ctx *c = NULL;
....
// if (!(c = sha256_init()))
//    return hdefault;

ctx *c = sha256_init();
if (c == NULL) {
    return hdefault;
}

---

Use size_t rather than uint64_t to prevent accessing outside array range.

// uint8_t *sha256 (const uint8_t *msg, const uint64_t msglen, uint8_t *hash)
uint8_t *sha256(const uint8_t *msg, size_t msglen, uint8_t *hash)

---

Insure at least 32-bit math. unsigned may be 16 bit.

// W[i] = ((unsigned)blk[i*4    ] << 24)
W[i] = ((uint32_t)blk[i*4    ] << 24)
// or 
W[i] = ((uint_fast32_t)blk[i*4    ] << 24)

---

No need to save a few bytes. Let blklen be unsigned rather than uint8_t.

---

Pedantic code would check for overflow in sha256_update()

if (msglen > (UINT64_MAX/8 - c->msglen)) Oops();

---

Unclear why code uses different names sha256d.h and SHA256_DCR_H. I'd expect SHA256D_H

// file sha256d.h
#ifndef _SHA256_DCR_H_  // why CR?