SHA256, a by The Books Implementation

One can find several SHA256 implementations on the internet, but usually they are not well commented, they have tricky and hard to understand code. In this post I decided to implement SHA256 “by the books”, and by that I mean I implement SHA256 as close as I can to what is described in the FIPS PUB 180-4.

Where Can I Find the FIPS Publication?

The latest FIPS publications are available for free. FIPS stands for FEDERAL INFORMATION PROCESSING STANDARDS PUBLICATION and the SHA series is part of its publications.

What Changed Between FIPS Revisions 180-1 180-2 180-3 and 180-4

The current SHA256 specification is in the document FIPS PUB 180-4, which is version 4 of the specification. I was curious to know what changed between these versions, fixes maybe?

Version Description
FIPS PUB 180-1 From 1995. it introduces SHA1
FIPS PUB 180-2 From 2002. it introduces SHA256, SHA384 and SHA512
FIPS PUB 180-3 From 2008. it introduces SHA224 (newer standard for smaller hash…)
FIPS PUB 180-4 From 2015. Allows padding to be added later. Added SHA512/224 and SHA512/256 and a correction on when the parity function in SHA1 should apply

How This Implementation is Commented

The source code makes references to the FIPS specification and uses the same variable names, explanations, when needed, are added. For instance, here is how the specification explains the SHA256 constants:

fips180-4-sha256-constants

And there is how the code comments it, note the array is also named k:


// FIPS PUB 180-4 -- 4.2.2
//
// "These words represent the first thirty-two bits of the fractional parts of
//  the cube roots of the first sixty-four prime numbers"
//
// For instance, first prime number is 2
//  Cube root of 2 is 2 exp(1/3) = 1.2599210498948731647672106072782
//  Fractional part = 0.2599210498948731647672106072782
//  Then the tricky step, we need to get the fractional part of the maximum 32 bit number.
//  Why is that? Think this way, if the fractional part is 0, then the number we want is 0,
//  if the fractional part is 0.99999..., then the number we want is 0xFFFF.FFFF
//  if the fractional part is 0.5, then the number we want is 1/2 of 0xFFFF.FFFF
//  So:
//  0.2599210498948731647672106072782 x 0xFFFFFFFF=1116352408.580543430848315846637=0x428A2F98
//  0x428A2F98 is the first constant
//  
static const uint32_t k[64] =
{
    0x428A2F98, 0x71374491, 0xB5C0FBCF, 0xE9B5DBA5, 0x3956C25B, 0x59F111F1, 0x923F82A4, 0xAB1C5ED5,
    0xD807AA98, 0x12835B01, 0x243185BE, 0x550C7DC3, 0x72BE5D74, 0x80DEB1FE, 0x9BDC06A7, 0xC19BF174,
    0xE49B69C1, 0xEFBE4786, 0x0FC19DC6, 0x240CA1CC, 0x2DE92C6F, 0x4A7484AA, 0x5CB0A9DC, 0x76F988DA,
    0x983E5152, 0xA831C66D, 0xB00327C8, 0xBF597FC7, 0xC6E00BF3, 0xD5A79147, 0x06CA6351, 0x14292967,
    0x27B70A85, 0x2E1B2138, 0x4D2C6DFC, 0x53380D13, 0x650A7354, 0x766A0ABB, 0x81C2C92E, 0x92722C85,
    0xA2BFE8A1, 0xA81A664B, 0xC24B8B70, 0xC76C51A3, 0xD192E819, 0xD6990624, 0xF40E3585, 0x106AA070,
    0x19A4C116, 0x1E376C08, 0x2748774C, 0x34B0BCB5, 0x391C0CB3, 0x4ED8AA4A, 0x5B9CCA4F, 0x682E6FF3,
    0x748F82EE, 0x78A5636F, 0x84C87814, 0x8CC70208, 0x90BEFFFA, 0xA4506CEB, 0xBEF9A3F7, 0xC67178F2
};

Lets now take a look on some aspects of SHA256.

The Constants, Ahh The Constants

There is always a lot of concerns when constants are used. Here is an example where constants were used as a backdoor, the Dual_EC_DRBG Random Number Generator have indeed a backdoor on its constants. Part of the linked text:

What Shumow and Ferguson showed is that these numbers have a relationship with a second, secret set of numbers that can act as a kind of skeleton key. If you know the secret numbers, you can predict the output of the random-number generator after collecting just 32 bytes of its output

The constants used on SHA algorithms are the Nothing Up My Sleeve Numbers.

Lets go back to SHA-256, what are those constants? There are two sets of constants in the SHA256 implementation. The k array of 64 words that are the cube root of first 64 primes, this is described above. The other set is the initial hash value, described below:


    // FIPS PUB 180-4 -- 5.3.3
    //
    // Initial hash value
    // "These words were obtained by taking the first thirty-two bits of the fractional parts of the square
    //  roots of the first eight prime numbers"
    //
    // For instance, first prime number is 2
    //  Square root of 2 is 2 exp(1/2) = 1.4142135623730950488016887242097
    //  Fractional part = 0.4142135623730950488016887242097
    //  Then the tricky step, we need to get the fractional part of the maximum 32 bit number.
    //  Why is that? Think this way, if the fractional part is 0, then the number we want is 0,
    //  if the fractional part is 0.99999..., then the number we want is 0xFFFF.FFFF
    //  if the fractional part is 0.5, then the number we want is 1/2 of 0xFFFF.FFFF
    //  So:
    //  0.4142135623730950488016887242097 x 0xFFFFFFFF=1779033703.5378858225296820112509=0x6A09E667
    //    0x6A09E667 is the first word in the initial hash value
    context->h[0] = 0x6A09E667;
    context->h[1] = 0xBB67AE85;
    context->h[2] = 0x3C6EF372;
    context->h[3] = 0xA54FF53A;
    context->h[4] = 0x510E527F;
    context->h[5] = 0x9B05688C;
    context->h[6] = 0x1F83D9AB;
    context->h[7] = 0x5BE0CD19;
 

SHA-256 Functions

SHA256 functions, from the specification:

fips180-4-sha256-functions

MAJ is the Majority function, with 3 input bits, the result is 1 if at least two out of the three input bits are 1 or 0 otherwise.

It is implemented out of logical operations, no if is used:


#define MAJ(x, y, z) (((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z)))   
 

Majority true table:

X Y Z MAJ
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

Note this is a one way function, which means it is impossible to figure out X,Y and Z out of the MAJ result. It also compresses 3 bits into one bit.

CH is the Choice function, the result is a choice made by input x on inputs y and z. If x is one, then output assumes the same value as y, z is chosen when x is zero. Like the majority function, it is a one way function, that compresses 3 bits into 1 bit and its implementation only uses logical operators.


#define CH(x, y, z) (((x) & (y)) ^ (~(x) & (z)))  
 

Choice function true table:

X Y Z CH
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1

There are 4 sigma functions, upper case sigma function 0, upper case sigma function 1, lowerr case sigma function 0, and lower case sigma function 0. These functions just scrambles its input. They take one input word and also output one word. SHR is a shift right operator and ROTR is a rotate operator, the difference between them being the shift loses bit 0 when the shift happens while the ROTR does not lose bits as bit0 that would be lost is inputted again in bit 31.

Testing It

A non exhaustive test is done by trying to replicate an example provided by NIST, where abc is used as input and the expected output is:


BA 78 16 BF 8F 01 CF EA 41 41 40 DE 5D AE 22 23 B0 03 61 A3 96 17 7A 9C B4 10 FF 61 F2 00 15 AD
 

Lets run it:

sha256-on-abc

To get clarifications on above dump messages, look at Debugging Webassembly With Print-Statements

The Source Code at Last

For the debug module source code (debug-wasm.c and .h), look at Debugging Webassembly With Print-Statements.

Compiling it:


emcc sha256.c debug-wasm.c -O1 -s MODULARIZE=1 -s WASM=1 -o sha256.js  

Start EMSCRIPTEN server:


emrun --no_browser --port 8080 .

Point your browser to: http://localhost:8080/sha256.html

The sha256.c File


 
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <endian.h>
#include <emscripten.h>

#include "sha256.h"
#include "debug-wasm.h"

// FIPS PUB 180-4 -- Figure 1
// Process in 512 bits blocks
#define SHA256_BLOCK_SIZE (512/8)

// Simple min function
#define MIN(a,b) (((a)<(b))?(a):(b))
 
// FIPS PUB 180-4 -- 4.1.2
#define CH(x, y, z) (((x) & (y)) ^ (~(x) & (z)))
#define MAJ(x, y, z) (((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z)))
#define SHR32(x, n) (x >> n)
#define ROR32(x, n) ((x >> n) | (x << (32 - n)))
#define SIGMA_UPPER_0(x) (ROR32(x, 2) ^ ROR32(x, 13) ^ ROR32(x, 22))
#define SIGMA_UPPER_1(x) (ROR32(x, 6) ^ ROR32(x, 11) ^ ROR32(x, 25))
#define SIGMA_LOWER_0(x) (ROR32(x, 7) ^ ROR32(x, 18) ^ SHR32(x, 3))
#define SIGMA_LOWER_1(x) (ROR32(x, 17) ^ ROR32(x, 19) ^ SHR32(x, 10))
 
static void Sha256_ProcessBlock(sha256Context *context);

// Helper function, simple test on our SHA256 implementation
EMSCRIPTEN_KEEPALIVE void sha256Test(void)
{
    unsigned char shaInput[3]={'a','b','c'};
    unsigned char shaOutput[SHA256_DIGEST_SIZE];
     
    DBG_DUMP(DEBUG_WASM_DEBUG, shaInput, sizeof(shaInput), "%s", "Input");
    
    Sha256_Compute(shaInput, sizeof(shaInput), shaOutput);
    
    DBG_DUMP(DEBUG_WASM_DEBUG, shaOutput, sizeof(shaOutput), "%s", "shaOutput");
    
}

// FIPS PUB 180-4 -- 4.2.2
//
// "These words represent the first thirty-two bits of the fractional parts of
//  the cube roots of the first sixty-four prime numbers"
//
// For instance, first prime number is 2
//  Cube root of 2 is 2 exp(1/3) = 1.2599210498948731647672106072782
//  Fractional part = 0.2599210498948731647672106072782
//  Then the tricky step, we need to get the fractional part of the maximum 32 bit number.
//  Why is that? Think this way, if the fractional part is 0, then the number we want is 0,
//  if the fractional part is 0.99999..., then the number we want is 0xFFFF.FFFF
//  if the fractional part is 0.5, then the number we want is 1/2 of 0xFFFF.FFFF
//  So:
//  0.2599210498948731647672106072782 x 0xFFFFFFFF=1116352408.580543430848315846637=0x428A2F98
//  0x428A2F98 is the first constant
//  
static const uint32_t k[64] =
{
    0x428A2F98, 0x71374491, 0xB5C0FBCF, 0xE9B5DBA5, 0x3956C25B, 0x59F111F1, 0x923F82A4, 0xAB1C5ED5,
    0xD807AA98, 0x12835B01, 0x243185BE, 0x550C7DC3, 0x72BE5D74, 0x80DEB1FE, 0x9BDC06A7, 0xC19BF174,
    0xE49B69C1, 0xEFBE4786, 0x0FC19DC6, 0x240CA1CC, 0x2DE92C6F, 0x4A7484AA, 0x5CB0A9DC, 0x76F988DA,
    0x983E5152, 0xA831C66D, 0xB00327C8, 0xBF597FC7, 0xC6E00BF3, 0xD5A79147, 0x06CA6351, 0x14292967,
    0x27B70A85, 0x2E1B2138, 0x4D2C6DFC, 0x53380D13, 0x650A7354, 0x766A0ABB, 0x81C2C92E, 0x92722C85,
    0xA2BFE8A1, 0xA81A664B, 0xC24B8B70, 0xC76C51A3, 0xD192E819, 0xD6990624, 0xF40E3585, 0x106AA070,
    0x19A4C116, 0x1E376C08, 0x2748774C, 0x34B0BCB5, 0x391C0CB3, 0x4ED8AA4A, 0x5B9CCA4F, 0x682E6FF3,
    0x748F82EE, 0x78A5636F, 0x84C87814, 0x8CC70208, 0x90BEFFFA, 0xA4506CEB, 0xBEF9A3F7, 0xC67178F2
};

// FIPS PUB 180-4 -- 5.1 & 5.1.1
// To ensure data is multiple of 64 bytes, extra processing is done inside Sha256_Final()
//  
//
static const uint8_t padding[64] =
{
    0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
};
 
// Function to be used when the message to be SHA256ed is presented in **one** buffer
//  data and len -> are the input buffer
//  digest -> Points to a buffer to be populated with SHA256 result
// 
void Sha256_Compute(const void *data, size_t len, uint8_t *digest)
{
    sha256Context Context;
    
    Sha256_Init(&Context);
    Sha256_Update(&Context, data, len);
    Sha256_Final(&Context, digest);
}

// Initial function to be used when the message to be SHA256ed is passed in parts.
//  The padding is not possible at this step because the message to be SHA256ed is unknown.
//
//  context -> Pointer to the context structure that holds info needed to perform SHA256 on a partial message.
//
void Sha256_Init(sha256Context *context)
{
    // FIPS PUB 180-4 -- 5.3.3
    //
    // Initial hash value
    // "These words were obtained by taking the first thirty-two bits of the fractional parts of the square
    //  roots of the first eight prime numbers"
    //
    // For instance, first prime number is 2
    //  Square root of 2 is 2 exp(1/2) = 1.4142135623730950488016887242097
    //  Fractional part = 0.4142135623730950488016887242097
    //  Then the tricky step, we need to get the fractional part of the maximum 32 bit number.
    //  Why is that? Think this way, if the fractional part is 0, then the number we want is 0,
    //  if the fractional part is 0.99999..., then the number we want is 0xFFFF.FFFF
    //  if the fractional part is 0.5, then the number we want is 1/2 of 0xFFFF.FFFF
    //  So:
    //  0.4142135623730950488016887242097 x 0xFFFFFFFF=1779033703.5378858225296820112509=0x6A09E667
    //  0x6A09E667 is the first word in the initial hash value
    context->h[0] = 0x6A09E667;
    context->h[1] = 0xBB67AE85;
    context->h[2] = 0x3C6EF372;
    context->h[3] = 0xA54FF53A;
    context->h[4] = 0x510E527F;
    context->h[5] = 0x9B05688C;
    context->h[6] = 0x1F83D9AB;
    context->h[7] = 0x5BE0CD19;
 
    // No bytes in the buffer
    context->size = 0;
    
    // No data was processed so far
    context->totalSize = 0;
}
 
// This function accepts a partial message to be SHA256ed. It can be called as many times
//  as needed.
//
//  context -> Pointer to the context structure that holds info needed to perform SHA25 on partial message.
//  data and len -> are the input buffer
//  digest -> to be populated with SHA256 result
//
void Sha256_Update(sha256Context *context, const void *data, size_t len)
{
    // Process this incoming message
    while(len > 0)
    {
        // Calculate how many bytes to process at this pass
        // Process 64 bytes at a time (one SHA256 block), but account for
        // data already present in the context buffer
        size_t n = MIN(len, 64 - context->size);
 
        // Copy the data to the buffer
        memcpy(context->buffer + context->size, data, n);
 
        // Update context
        context->size += n;
        context->totalSize += n;
        
        // Update pointer into the message
        data = (uint8_t *) data + n;
        
        // Update remaining bytes to process
        len -= n;
 
        // Only process if the 64 bytes buffer is full
        if(context->size == 64)
        {
            // Process this block and empty the buffer
            Sha256_ProcessBlock(context);
            context->size = 0;
        }
    }
}
 
// Final function to be used when the message to be SHA256ed is passed in parts
//
//  context -> Pointer to the context structure that holds info needed to perform SHA256 on partial message.
//  digest -> Points to a buffer to be populated with SHA256 result
//
 void Sha256_Final(sha256Context *context, uint8_t *digest)
 {
    // FIPS PUB 180-4 -- 5
    //
    // Padding:
    //
    // 5.1 Padding the Message
    // The purpose of this padding is to ensure that the padded message is a multiple of 512 or 1024
    // bits, depending on the algorithm. Padding can be inserted before hash computation begins on a
    // message, or at any other time during the hash computation prior to processing the block(s) that
    // will contain the padding
    //
    // 5.1.1 SHA-1, SHA-224 and SHA-256
    // Suppose that the length of the message, M, is l bits. Append the bit “1” to the end of the
    // message, followed by k zero bits, where k is the smallest, non-negative solution to the equation
    // l + 1 + k = 448mod512 . Then append the 64-bit block that is equal to the number l expressed
    // using a binary representation. For example, the (8-bit ASCII) message “abc” has length
    // 8x3 = 24, so the message is padded with a one bit, then 448 - (24 + 1) = 423 zero bits, and then
    // the message length, to become the 512-bit padded message
    // The length of the padded message should now be a multiple of 512 bits.
    // 
 
    // Length of the original message before padding, in bits
    uint64_t l = context->totalSize * 8;
    size_t k = 0;
 
    // Pad the message so that its length is congruent to 448 modulo 512
    if( l%512 < 448)
       k = 448 - l%512;
    else
       k = 512 + 448 - l%512;
 
    DBG_LOG(DEBUG_WASM_DEBUG, "l:%d\n", l);
    DBG_LOG(DEBUG_WASM_DEBUG, "k:%d\n", k);
 
    // Append padding, note that the final 64 bits are not here yet...
    // Done this way so it won't need to create a padding array with the exact
    // number of bits needed for padding
    Sha256_Update(context, padding, k/8 /* k is a counter of bits */);
 
    // Final 64 bits, append the length of the original message
    context->w[14] = htobe32((uint32_t) (l >> 32));
    context->w[15] = htobe32((uint32_t) l);
 
    // Now the digest is calculated
    Sha256_ProcessBlock(context);
 
    // Convert from host byte order to big-endian byte order
    for(size_t i = 0; i < 8; i++) context->h[i] = htobe32(context->h[i]);
 
    // Copy the result to the user provided buffer
    if(digest != NULL) memcpy(digest, context->digest, SHA256_DIGEST_SIZE);
 }
 
 
// FIPS PUB 180-4 -- 6.2
//
// Process a block
//
void Sha256_ProcessBlock(sha256Context *context)
{
    uint32_t w[64];     // Message schedule
 
    // 1. Prepare the message schedule, {Wt}
    for(size_t t = 0 ; t <= 63 ; t++)
    {
        if( t<=15 )
            w[t] = betoh32(context->w[t]);
        else
            w[t] = SIGMA_LOWER_1(w[t-2]) + w[t-7] + SIGMA_LOWER_0(w[t-15]) + w[t-16];
    }
 
    //DBG_DUMP(DEBUG_WASM_DEBUG, w, sizeof(w), "%s", "w");

    // 2. Initialize the eight working variables, a, b, c, d, e, f, g, and h,
    // with the (i-1)st hash value:
    uint32_t a = context->h[0];
    uint32_t b = context->h[1];
    uint32_t c = context->h[2];
    uint32_t d = context->h[3];
    uint32_t e = context->h[4];
    uint32_t f = context->h[5];
    uint32_t g = context->h[6];
    uint32_t h = context->h[7];
  
    // 3. Loop 64 times
    for(size_t t = 0; t <= 63; t++)
    {
        //DBG_LOG(DEBUG_WASM_DEBUG, "t=%d\n", t);
        
        // Calculate T1 and T2
        uint32_t temp1 = h + SIGMA_UPPER_1(e) + CH(e, f, g) + k[t] + w[t];
        uint32_t temp2 = SIGMA_UPPER_0(a) + MAJ(a, b, c);
 
        // Update working registers
        h = g;
        g = f;
        f = e;
        e = d + temp1;
        d = c;
        c = b;
        b = a;
        a = temp1 + temp2;
    }
 
    // 4. Compute the ith intermediate hash value H(i):
    context->h[0] += a;
    context->h[1] += b;
    context->h[2] += c;
    context->h[3] += d;
    context->h[4] += e;
    context->h[5] += f;
    context->h[6] += g;
    context->h[7] += h;
}

The sha256.h file:


#ifndef _SHA256_H
#define _SHA256_H
 
#include <stdint.h>

// FIPS PUB 180-4 -- Figure 1
// SHA256 outputs 256 bits digest
#define SHA256_DIGEST_SIZE (256/8)
 
// A context is needed in order to allow processing pieces of data
//  
typedef struct
{
    union
    {
        // Current digest. It is an union so we can access it as bytes or 32 bit words
        uint32_t    h[SHA256_DIGEST_SIZE/4];
        uint8_t     digest[SHA256_DIGEST_SIZE];
    };
    
    // SHA256 only runs on 64 bytes blocks, data is added to this buffer and
    // a SHA256 pass runs once this buffer is full
    union
    {
       uint32_t     w[16];
       uint8_t buffer[64];
    };
    
    // Number of bytes in the above buffer
    size_t size;
    
    // Total Number of bytes processed so far.
    uint64_t totalSize;
} sha256Context;
 
// SHA256 related functions
void Sha256_Compute(const void *data, size_t length, uint8_t *digest);
void Sha256_Init(sha256Context *context);
void Sha256_Update(sha256Context *context, const void *data, size_t length);
void Sha256_Final(sha256Context *context, uint8_t *digest);
 
#endif

and the sha256.html file


<html>
<head>
  <meta charset="UTF-8">
  <script type="text/javascript" src="sha256.js"></script>
  <script>
    Module()
    .then(function(instance){
        var exports = instance['asm']; // the .js file puts the exports in the 'asm' field
        // Add button listener, calls Webassembly's sha256Test() when clicked
        var button = document.getElementById('sha256Button');
        button.addEventListener('click', function() {
            exports._sha256Test();
        }, false);
      }
  );
  </script>
</head>
<body>
  <input type="button" id="sha256Button" value="click here to run SHA256(abc)"/>
</body>
</html>

This webassembly implementation of SHA256 is one more step into getting a tetris game with Webassembly.


Leave a message below. Webassembly is evolving rapidly, please let me know if this post got outdated.

Enjoyed this post?

Don't miss new posts: Share it with your friends:

You may also like...

5 Responses

  1. Johnc223 says:

    Spot on with this writeup, I actually believe this website needs a great deal more attention. Ill probably be returning to read through more, thanks for the info! caegedddeaae

  2. thank you for sharing with us, I believe this website genuinely stands out : D.

  1. May 11, 2018

    […] 5、[文章]SHA256 的实现 […]

  2. May 11, 2018

    […] 5、[文章] SHA256 的实现 […]

  3. May 12, 2018

    […] 5、[文章] SHA256 的实现 […]

Leave a Reply

Your email address will not be published. Required fields are marked *