# Secure Hash Algorithm SHA-256

CS 463 Lecture, Dr. Lawlor

The core of SHA-256 is a round-based bit mixing function applied to a 256-bit block of data.

Each round consists of bit mixing between eight integers or "state variables", here named a-h.

// SHA-256 round function:
... load Wi from the data, or mixed from data in later rounds ...

// Mixing
h += (ror(e,6)^ror(e,11)^ror(e,25)) + (g^(e&(f^g))) + K[i] + Wi; // "Ch"
d += h;
h += (ror(a,2)^ror(a,13)^ror(a,22)) + ((a&b)|(c&(a|b))); // "Maj"

// Cyclic shift of variables:
UInt32 old_h=h;
h=g; g=f; f=e; e=d; d=c; c=b; b=a; a=old_h;

This is repeated for 64 rounds per block of the message.  The value of the output hash is just the sum of the ending values of the a-h variables after running each block.

Here's the full code.  Note we might need to buffer up message data until we accumulate each full block to hash, and the special work at the end of the message (add a one bit, pad with zeros to the end of the block, and add message length in bits).  This takes about 600 nanoseconds per block, or a little under 2 million short hashes per second (per core of a Sandy Bridge machine).
```/*
SHA-256 Hash in C++

2013-02-19 : Orion Lawlor : Public domain
2010-06-11 : Igor Pavlov : Public domain
http://cpansearch.perl.org/src/BJOERN/Compress-Deflate7-1.0/7zip/C/Sha256.c
This code is based on public domain code from Wei Dai's Crypto++ library.
*/
#include <string.h> /* for size_t and memset (to zero) */
#include <string> /* for std::string */

/*
This class computes SHA256 message digests.
*/
class SHA256 {
public:
/* This type needs to be at least 32 bits, unsigned */
typedef unsigned int UInt32;
/* This is the type of the data you're processing */
typedef unsigned char Byte;

/* This is the data type of a message digest. */
class digest {
public:
enum {size=32}; // bytes in a message digest
SHA256::Byte data[size]; // binary digest data

// Equality.  This is useful for "if (cur==target)" tests.
bool operator==(const digest &other) const {
for (int i=0;i<size;i++)
if (data[i]!=other.data[i])
return false;
return true;
}

// Less-than.  This is mostly useful for std::map<SHA256::digest, ...>
bool operator<(const digest &other) const {
for (int i=0;i<size;i++)
if (data[i]<other.data[i])
return true;
else if (data[i]>other.data[i])
return false;
return false;
}

// Convert digest to an ASCII string of hex digits (for printouts)
std::string toHex() const;
};

/* External Interface */
SHA256(); // constructor.  Sets up initial state.

// Add raw binary message data to our hash.
//  You can call this repeatedly to add as much data as you want.
void add(const void *data, size_t size);

// Finish this message and extract the digest.
// Resets so you can add the next message, if desired.
SHA256::digest finish(void);

~SHA256(); // destructor.  Clears out state and buffered data.

/* Internal Interface (public, for debug's sake) */
// This is the internal state of the hash.
UInt32 state[8];

// This is how many message bytes we've seen so far.
size_t count;

// This buffers up to a whole block of data
Byte buffer[64];

// Reset to initial values.
void init();

// Process the finished block of data in "buffer"
void block();
};

/* This is the *really* easy version: given a string as input, return the digest as output.
std::cout<<"SHA-256: "<<SHA256_digest(someString).toHex()<<"\n";
*/
inline SHA256::digest SHA256_digest(const std::string &src) {
SHA256 hash;
return hash.finish();
}

/************** Bit twiddling and round operations for SHA256 *************/

/* Define bit rotate operations.  These work like:
UInt32 ror(UInt32 value,UInt32 bitcount)
*/
#ifdef _MSC_VER /* Windows bit rotate from standard library */
#  include <stdlib.h>
#  define rol(x, n) _rotl((x), (n))
#  define ror(x, n) _rotr((x), (n))
#else /* portable (Linux, Mac, etc) bit rotate */
#  define rol(x, n) (((x) << (n)) | ((x) >> (32 - (n))))
#  define ror(x, n) (((x) >> (n)) | ((x) << (32 - (n))))
#endif

/* These are the round keys, one per round. */
static const SHA256::UInt32 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
};

/* This sets up the Sha256 initial state, at the start of a message. */
void SHA256::init()
{
state[0] = 0x6a09e667;
state[1] = 0xbb67ae85;
state[2] = 0x3c6ef372;
state[3] = 0xa54ff53a;
state[4] = 0x510e527f;
state[5] = 0x9b05688c;
state[6] = 0x1f83d9ab;
state[7] = 0x5be0cd19;
count = 0;
}
SHA256::SHA256() {
init();
}

unsigned int ROUND_COUNT=64; // HACK

/* This adds another block of data to our current state.
This is our main transforming/mixing function. */
void SHA256::block()
{
unsigned i;

UInt32 KWi[64]; // Per-round key + work data

// First part of W is just the incoming message data */
#define s0(x) (ror(x, 7) ^ ror(x,18) ^ (x >> 3))
#define s1(x) (ror(x,17) ^ ror(x,19) ^ (x >> 10))
UInt32 W[16]; // Work buffer: 0-15 are straight from the data
for (i = 0; i < 16; i++) {
W[i]=
((UInt32)(buffer[i * 4    ]) << 24) +
((UInt32)(buffer[i * 4 + 1]) << 16) +
((UInt32)(buffer[i * 4 + 2]) <<  8) +
((UInt32)(buffer[i * 4 + 3])); // big-endian 32-bit load
KWi[i]=W[i]+K[i];
}

// The rest of W is a scrambled copy of the original data
for (;i<ROUND_COUNT;i++)
{
W[i&15] += s1(W[(i-2)&15]) + W[(i-7)&15] + s0(W[(i-15)&15]);
KWi[i] = W[i&15]+K[i];
}

UInt32 a,b,c,d,e,f,g,h; /* local copies of state, for performance */
a=state[0]; b=state[1];  c=state[2];  d=state[3];
e=state[4]; f=state[5];  g=state[6];  h=state[7];

// This is the main data transform loop
for (i = 0; i < ROUND_COUNT; i++) {
// SHA-256 round function:
// Mixing
h += (ror(e,6)^ror(e,11)^ror(e,25)) + (g^(e&(f^g))) + KWi[i]; // "Ch"
d += h;
h += (ror(a,2)^ror(a,13)^ror(a,22)) + ((a&b)|(c&(a|b))); // "Maj"

// Cyclic shift of variables:
UInt32 old_h=h;
h=g; g=f; f=e; e=d; d=c; c=b; b=a; a=old_h;
}

// Add result back into state array
state[0]+=a; state[1]+=b;  state[2]+=c;  state[3]+=d;
state[4]+=e; state[5]+=f;  state[6]+=g;  state[7]+=h;

/* Wipe temporary variables, for paranoia */
memset(W, 0, sizeof(W));
memset(KWi, 0, sizeof(KWi));
}

// Add raw binary message data to our hash.
void SHA256::add(const void *data, size_t size)
{
const Byte *dataptr=(const Byte *)data;
UInt32 curBufferPos = (UInt32)count & 0x3F; /* location within last block */
while (size > 0)
{
buffer[curBufferPos++] = *dataptr++; // copy next byte of data
count++; // message got longer
size--; // user data got shorter
if (curBufferPos == 64) // we have one whole block finished
{
curBufferPos = 0;
block();
}
}
}

/* End Sha256 processing, and write out message digest. */
SHA256::digest SHA256::finish(void)
{
size_t lenInBits = (count << 3); // i.e., times 8 bits per byte
UInt32 curBufferPos = (UInt32)count & 0x3F; // 0x3f is mask to wrap around to buffer size
unsigned i;
buffer[curBufferPos++] = 0x80; // standard specifies "add a one bit...
while (curBufferPos != (64 - 8)) // ...then pad with zeros to end of block"
{
curBufferPos &= 0x3F;
if (curBufferPos == 0)
block();
buffer[curBufferPos++] = 0; // zero out rest of block
}

// Finally, add message length, in bits, as big-endian 64 bit number
for (i = 0; i < 8; i++)
{
buffer[curBufferPos++] = (Byte)(lenInBits >> 56);
lenInBits <<= 8;
}

block(); // transform last block (including length)

// Copy state out as big-endian integers.
SHA256::digest output;
for (i = 0; i < 8; i++)
{
output.data[i*4+0] = (Byte)(state[i] >> 24);
output.data[i*4+1] = (Byte)(state[i] >> 16);
output.data[i*4+2] = (Byte)(state[i] >> 8);
output.data[i*4+3] = (Byte)(state[i]);
}

init(); // reset for next trip around

return output;
}

SHA256::~SHA256()
{
// To keep from leaving any sensitive data lying around, zero out our buffers.
memset(state,0,sizeof(state));
count=0;
memset(buffer,0,sizeof(buffer));
}

std::string SHA256::digest::toHex() const
{
std::string ret="";
for (int i=0;i<size;i++) {
const char *hexdigit="0123456789abcdef";
ret+=hexdigit[(data[i]>>4)&0xf]; // high 4 bits
ret+=hexdigit[(data[i]   )&0xf]; // low 4 bits
}
return ret;
}

/***** Actual user code ****/
std::string str="!";
int digest_short() { return SHA256_digest(str).data[0]; }

int foo(void) {
print_time("hash time",digest_short);

std::cout<<SHA256_digest("0").toHex()<<"\n";
return 0;
}```

(Try this in NetRun now!)

## Differential Cryptanalysis Resistance

Here's a very weakened version of SHA-256 using *zero* rounds, showing the hash of each the digits 0-9.  Because we don't touch the original data (that happens in the rounds), the output is constant.  Collision city!

```d413ccce76cf5d0a78dde6e44a9fea74a21ca4fe360ad1183f07b356b7c19a32

Using one round, there are only two localized places with differences, where the data was added in.
```d413ccce76cf5d0a78dde6e46e97d7dca21ca4fe360ad1183f07b35688695566
By the second round, these differences are spread to parts of the next integer:
```d413ccce76cf5d0ad92cb5606e97d7dca21ca4fe360ad118d546c95188695566
By the third round, another integer is changed:
```d413ccce69df2c09d92cb5606e97d7dca21ca4fe9699b51bd546c95188695566
d413ccceebde983d572055616f97d7dca21ca4fee677b4b353fa714e89695566
d413ccce6bff0b91d72475617097d7dca21ca4feb84b5e71d3be795a8a695566
d413cccefdbc7be55939155e7197d7dca21ca4fe5e991720569321538b695566
d413ccce7d9c6a99d93d355e7297d7dca21ca4fe098b8ab2e65768ff8c695566
d413cccefc1e5d4d5730d55f7397d7dca21ca4fe7914b40f650b10fc8d695566
d413ccce7bbcca21d734f55f7497d7dca21ca4fea93e168be4cf19088e695566
d413ccce721ce8cd6189956c7597d7dca21ca4fed915bd1d6fe3c1118f695566
d413cccef33cb999e18db56c7697d7dca21ca4fee59e3517efa808fd90695566
d413ccce747d0a655f81556d7797d7dca21ca4fe3dcf9a8c6e5bb0fa91695566```
By the fourth round, it's more changes than not:
```75a08fe669df2c09d92cb5606e97d7dc7bc4d2959699b51bd546c95188695566
d5bc67ffebde983d572055616f97d7dcfaffcf8de677b4b353fa714e89695566
c3a868676bff0b91d72475617097d7dc7c598f28b84b5e71d3be795a8a695566
a282c861fdbc7be55939155e7197d7dc520180d45e991720569321538b695566
67eddb9e7d9c6a99d93d355e7297d7dcdd855095098b8ab2e65768ff8c695566
40f7842afc1e5d4d5730d55f7397d7dcaa3442fe7914b40f650b10fc8d695566
c8336d4d7bbcca21d734f55f7497d7dc99f846dda93e168be4cf19088e695566
a47c01f1721ce8cd6189956c7597d7dcfdeeed45d915bd1d6fe3c1118f695566
cccb013af33cb999e18db56c7697d7dc701c5e04e59e3517efa808fd90695566
e689646c747d0a655f81556d7797d7dc1ace14c43dcf9a8c6e5bb0fa91695566```
By the fifth round, only a few places haven't been touched yet.  These are hit by the sixth round.
```75a08fe669df2c09d92cb5606a7d15517bc4d2959699b51bd546c95141e2fbdc
d5bc67ffebde983d572055611675742ffaffcf8de677b4b353fa714e491f4cc5
c3a868676bff0b91d72475618b86d5a57c598f28b84b5e71d3be795aafeb4646
a282c861fdbc7be55939155e9d5833c5520180d45e9917205693215381b0cd4e
67eddb9e7d9c6a99d93d355e4c362b80dd855095098b8ab2e65768ffdc275793
40f7842afc1e5d4d5730d55fd6fcccf9aa3442fe7914b40f650b10fc9f9c717e
c8336d4d7bbcca21d734f55fa3a8aea299f846dda93e168be4cf1908a93f0df4
a47c01f1721ce8cd6189956c8281c9abfdeeed45d915bd1d6fe3c11130e3f80b
cccb013af33cb999e18db56c4d0a19d8701c5e04e59e3517efa808fdba51fb94
e689646c747d0a655f81556d410de3681ace14c43dcf9a8c6e5bb0fac2fec706```
(Try this in NetRun now!)

With all 64 rounds, changing a single bit of the input changes everything:
```5feceb66ffc86f38d952786c6d696c79c2dbc239dd4e91b46729d73a27fb57e9