2
\$\begingroup\$

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;
}
\$\endgroup\$
3
\$\begingroup\$
  • 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.

\$\endgroup\$
  • \$\begingroup\$ Thank you. I like the sha256_update cleanup, and had planned a revisit. The difficulty I find depends on how min is implemented. If implemented as a macro, subtraction gives rise to a warning of comparison between signed and unsigned types. If implemented as a function, then a type specific min is needed. I have settled for uint8_t chunk = DGST256 - c->blklen; followed by an if (chunk > msglen) chunk = msglen;, but am left wondering whether or how to improve branch prediction of the test? That gets rid of the req (required) and off (offset) mirror. The while is cleaner. \$\endgroup\$ – David C. Rankin Dec 30 '17 at 23:33
  • \$\begingroup\$ @DavidC.Rankin Your implementation of min looks good. I don't think you should worry about branch prediction. It seems to be peanuts compared to the amount of work done by sha256hashblock. If you are OK with gcc specifics, __builtin_expect(msglen > chunk, 1) may help. Of course, profiling is necessary. \$\endgroup\$ – vnp Dec 30 '17 at 23:51
  • \$\begingroup\$ I disagree that struct ctx_t member uint64_t msglen; should be size_t. That should remain uint64_t. OTOH in sha256_update (ctx *c, const uint8_t *msg, const uint64_t msglen) should use size_t msglen \$\endgroup\$ – chux Jan 2 '18 at 19:31
2
\$\begingroup\$

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 229 even though c->msglen is 64-bit.

Suggested alternative code to use byte lengths up to 261.

// (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?
\$\endgroup\$
  • \$\begingroup\$ Thanks @chux. The sha256d is just because I already had the sha256 from pdfcrack in the same directory when I started monkeying with implementing the sha256_update. uint64_t -> size_t change was made there (and it all places where it represented a length as suggested in the first response). I like your cleanup on indexes between 63-56. I've been profiling a bit the suggested changes from both responses, and the only thing I've run into is the original avoids a memcpy by using indexing in the for loop which is lost when implementing the other suggested while. I'll keep at it. \$\endgroup\$ – David C. Rankin Jan 2 '18 at 23:43
  • \$\begingroup\$ And whether it makes a whole lot of sense or not, the objective was to avoid exposing struct ctx_t and only expose an opaque pointer. Personally exposing the struct doesn't give me a whole lot of heartburn, but the goal was to keep as much of the hashing behind the scene. Thanks again for your input. \$\endgroup\$ – David C. Rankin Jan 2 '18 at 23:49
  • \$\begingroup\$ A way to expose the the size requirement is to union-ize with a unsigned char array. The public sees the boring unsigned char[magic_number]; while code sees both. More on that later. \$\endgroup\$ – chux Jan 2 '18 at 23:52
  • \$\begingroup\$ I think I got it -- that's about a brilliant solution that I didn't think of... And your CR?, just initials for the name at the end of the comment. \$\endgroup\$ – David C. Rankin Jan 3 '18 at 0:37
  • \$\begingroup\$ I thought I had it... My thought was to create a union along the lines of union foo { uint8_t bytes[sizeof (struct ctx_t)]; struct ctx_t ctx; };, but that continues to require full exposure of struct ctx_t to avoid the incomplete type issue. Where doeth my thinking go awry? \$\endgroup\$ – David C. Rankin Jan 3 '18 at 8: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.