The Internals of SHA 256 Algorithm

 I came across this excellent video, explaining how the SHA-256 algorithm works internally. I had always been excited to understand how a real-world hashing algorithm works internally. SHA-256 is one of the most popular hashing algorithms, so after getting my hands on that video, I knew I had to try and implement this on my own. This feels like once in a lifetime opportunity. So here I am after having implemented the algorithm on my own and feeling confident understanding how SHA-256 works. I want to pass on that same confidence to the readers of this blog (probably including me in a few months :D) along with code snippets. So, lets dive right into it...

Basic Operations

There are some basic operations that the SHA-256 algorithm builds on top of. Here is a list of those:

1. Shift Right - Shifts the bits of the original number pos bits to the right, dropping of things that slide of the end.

2. Rotate Right - Rotates pos bits in the original number. Very similar to shift but instead of dropping things off the end, it wraps them at the beginning (in a circular fashion)

3. σ0 (lowerSigma0) - Combination of rotations and shifts defined above.

4. σ1 (lowerSigma1) - Another combination of rotation and shifts.

5. Σ0 (upperSigma0) - Combination of rotations.

6. Σ1 (upperSigma1) - Another combination of rotations.

7. Choice - Given three binary numbers x, y, z, depending on the bits of x, choses the corresponding bit in y if x bit is 1, or the corresponding bit in z if x bit is 0.

8. Majority - The result contains the majority bit out of each bit of x, y and z.

The SHA-256 Algorithm

The above picture shows the various steps of the SHA-256 algorithm. This is the SHA256 algorithm in code that I implemented:

Here is each of the steps broken down:

1. Convert the original message (usually string) in the binary format. (If the string is "abc", it gets converted to 011000010110001001100011, where first 8 bits are "a" (96 ASCII), next 8 are "b" (97 ASCII) and next 8 are "c" (98 ASCII).

2. Pad the binary message in such a way that the total number of bits in the padded message are a multiple of 512. Also, 65 bits of the padded message are reserved. A bit "1" is added right after the original message as a separator. Then there are a bunch of zeroes, and the last 64 bits encode the length of the original message.

3. Now that the message length is a multiple of 512, we just break it into message blocks which are 512 bits in length each.

4. Next step is to process each message block one by one and create a message schedule out of each block eventually compressing each of the message schedule.

5. In order to create a message schedule, we break down the 512 bit message block into 16 words of 32 bits each. However, a message schedule consists of 64 words. This is where the basic operations we defined above come into play. We use some combination of those to generate the remaining 48 words. At the end of all of this, we have transformed a 512-bit message block into 64, 32 bits word message schedule.

6. Now comes the heart of the SHA-256 algorithm, the compression stage. Now that we have 64 words of 32 bits size with us, we need to merge them in some way. SHA-256 does that by merging them down to 8, 32-bit hash values. These hash values are initialized as below:

They might look intimidating (anything in hexadecimal looks intimidating to me :D) but these are just the square roots of the first 8 primes. (Their fractional part, to be precise)

And these hash values, are the ones that store the final result after processing each message block. As shown in the block diagram above, the updated hash values after each step are used as an input in the next step. The square root of first 8 primes is the initial hash value with which all this process starts.

7. This process of creating a message schedule and compressing it is repeated for each message block. And the final hash values, generated after processing the last message block gives us the SHA-256 hash. We convert each hash value into the 8-length hexadecimal equivalent and concatenate all of them to generate the 64-length SHA-256 hash. 

And that is how the SHA-256 algorithm works. Here is the full C++ source code for the algorithm:

	#include<bits/stdc++.h>
	using namespace std;
	#define INT_BITS 32
	uint32_t init_hash_values[8];
	uint32_t hash_values[8];
	void initHashValues() {
	init_hash_values[0] = 0x6a09e667;
	init_hash_values[1] = 0xbb67ae85;
	init_hash_values[2] = 0x3c6ef372;
	init_hash_values[3] = 0xa54ff53a;
	init_hash_values[4] = 0x510e527f;
	init_hash_values[5] = 0x9b05688c;
	init_hash_values[6] = 0x1f83d9ab;
	init_hash_values[7] = 0x5be0cd19;
	for (int i = 0; i < 8; i++) {
	hash_values[i] = init_hash_values[i];
	}
	}
	array<uint32_t, 64> K = {
	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
	};
	uint32_t shiftRight(uint32_t orig, int pos) {
	return orig >> pos;
	}
	uint32_t rotateRight(uint32_t orig, int pos) {
	return (orig >> pos) | (orig << (INT_BITS - pos));
	}
	uint32_t lowerSigma0(uint32_t orig) {
	uint32_t rotr7 = rotateRight(orig, 7);
	uint32_t rotr18 = rotateRight(orig, 18);
	uint32_t shr3 = shiftRight(orig, 3);
	return rotr7 ^ rotr18 ^ shr3;
	}
	uint32_t lowerSigma1(uint32_t orig) {
	uint32_t rotr17 = rotateRight(orig, 17);
	uint32_t rotr19 = rotateRight(orig, 19);
	uint32_t shr10 = shiftRight(orig, 10);
	return rotr17 ^ rotr19 ^ shr10;
	}
	uint32_t upperSigma0(uint32_t orig) {
	uint32_t rotr2 = rotateRight(orig, 2);
	uint32_t rotr13 = rotateRight(orig, 13);
	uint32_t rotr22 = rotateRight(orig, 22);
	return rotr2 ^ rotr13 ^ rotr22;
	}
	uint32_t upperSigma1(uint32_t orig) {
	uint32_t rotr6 = rotateRight(orig, 6);
	uint32_t rotr11 = rotateRight(orig, 11);
	uint32_t rotr25 = rotateRight(orig, 25);
	return rotr6 ^ rotr11 ^ rotr25;
	}
	uint32_t choice(uint32_t x, uint32_t y, uint32_t z) {
	uint32_t res = 0;
	for (int i = 0; i < 32; i++) {
	if ((1 << i) & x) {
	res = res | ((1 << i) & y);
	} else {
	res = res | ((1 << i) & z);
	}
	}
	return res;
	}
	uint32_t majority(uint32_t x, uint32_t y, uint32_t z) {
	uint32_t res = 0;
	for (int i = 0; i < 32; i++) {
	int cnt0 = 0, cnt1 = 0;
	if ((1 << i) & x) cnt1++; else cnt0++;
	if ((1 << i) & y) cnt1++; else cnt0++;
	if ((1 << i) & z) cnt1++; else cnt0++;
	if (cnt1 > cnt0) res = res | (1 << i);
	}
	return res;
	}
	string stringToBinary(string str) {
	string res = "";
	for (int i = 0; i < str.size(); i++) {
	bitset<8> b(str[i]);
	res += b.to_string();
	}
	return res;
	}
	string pad(string str) {
	int n = str.size();
	int finalLen = n + 1 + 64; // 1 separator and 64 bits for size
	int closestMul = 512;
	while (closestMul < finalLen) {
	closestMul += 512;
	}
	string res = str;
	res += "1";
	bitset<64> sz(n);
	int zeroes = closestMul - n - 1 - 64;
	while (zeroes--) {
	res += "0";
	}
	res += sz.to_string();
	return res;
	}
	vector<string> toMsgBlock(string paddedStr) {
	vector<string> msgBlocks;
	int start = 0;
	int sz = 512;
	while (start < (int)paddedStr.size()) {
	string thisBlock = "";
	for (int i = start; i < min(start + sz, (int)paddedStr.size()); i++) {
	thisBlock += paddedStr[i];
	}
	msgBlocks.push_back(thisBlock);
	start = start + 512;
	}
	return msgBlocks;
	}
	string intToBinary(int num) {
	bitset<32> n(num);
	return n.to_string();
	}
	string addStringBinary(string s1, string s2) {
	int carry = 0;
	string sum = "";
	for (int i = 31; i >= 0; i--) {
	int a = s1[i] - '0';
	int b = s2[i] - '0';
	int res = (a + b + carry);
	carry = res >= 2 ? 1 : 0;
	res = res % 2;
	sum = to_string(res) + sum;
	}
	return sum;
	}
	vector<string> createMessageSchedule(string messageBlock) {
	int start = 0;
	int sz = 32;
	vector<string> messages;
	while (start < 512) {
	string msg = "";
	for (int i = start; i < start + 32; i++) {
	msg += messageBlock[i];
	}
	messages.push_back(msg);
	start = start + 32;
	}
	for (int i = 16; i < 64; i++) {
	string f1 = intToBinary(lowerSigma1(stoul(messages[i - 2], 0, 2)));
	string f2 = messages[i - 7];
	string f3 = intToBinary(lowerSigma0(stoul(messages[i - 15], 0, 2)));
	string f4 = messages[i - 16];
	string sum1 = addStringBinary(f1, f2);
	string sum2 = addStringBinary(f3, f4);
	string newMsg = addStringBinary(sum1, sum2);
	messages.push_back(newMsg);
	}
	return messages;
	}
	void compress(vector<string> messageSchedule) {
	for (int i = 0; i < (int) messageSchedule.size(); i++) {
	uint32_t message = stoul(messageSchedule[i], 0, 2);
	uint32_t constWord = K[i];
	uint32_t temp1 = upperSigma1(hash_values[4]) + choice(hash_values[4], hash_values[5], hash_values[6]) + hash_values[7] + message + constWord;
	uint32_t temp2 = upperSigma0(hash_values[0]) + majority(hash_values[0], hash_values[1], hash_values[2]);
	// shift all hash values down by 1
	for (int i = 7; i >= 0; i--) {
	hash_values[i] = hash_values[i - 1];
	}
	hash_values[0] = temp1 + temp2;
	hash_values[4] += temp1;
	}
	for (int i = 0; i < 8; i++) {
	hash_values[i] += init_hash_values[i];
	}
	}
	void processMessageBlocks(vector<string> messageBlocks) {
	for (int i = 0; i < (int) messageBlocks.size(); i++) {
	string thisBlock = messageBlocks[i];
	vector<string> thisSchedule = createMessageSchedule(thisBlock);
	compress(thisSchedule);
	for (int i = 0; i < 8; i++) {
	init_hash_values[i] = hash_values[i];
	}
	}
	}
	string getFinalHash() {
	string res = "";
	char hex_string[8];
	for (int i = 0; i < 8; i++) {
	sprintf(hex_string, "%X", hash_values[i]);
	string hexConst(hex_string);
	for (int j = 0; j < 8; j++) {
	hexConst[j] = tolower(hexConst[j]);
	}
	res += hexConst;
	}
	return res;
	}
	string sha256(string str) {
	string binStr = stringToBinary(str);
	string paddedStr = pad(binStr);
	vector<string> messageBlocks = toMsgBlock(paddedStr);
	processMessageBlocks(messageBlocks);
	string finalHash = getFinalHash();
	return finalHash;
	}
	int main() {
	initHashValues();
	string hash = sha256("abc");
	cout << hash << endl;
	}

view raw sha256.cpp hosted with ❤ by GitHub

I hope, this post gives you confidence around the SHA-256 algorithm and maybe even the motivation to implement it yourself (probably improving over my quick and kind of dirty implementation) in the programming language of your choice.