# SHA-256 Animation

An animation of the SHA-256 hash function in your terminal.

I used this code to help me make a video to explain how SHA-256 works.

## Usage

Just run the `sha256.rb`

script with the data you want to see hashed.

```
# simple
ruby sha256.rb abc
# hash binary or hex data by using `0b` or `0x` prefixes
ruby sha256.rb 0b01100001
ruby sha256.rb 0xaabbccdd
# speed up or step through the animation (optional)
ruby sha256.rb abc normal # default
ruby sha256.rb abc fast
ruby sha256.rb abc enter
```

You can also run the individual functions used in SHA-256 by passing in binary strings as arguments:

```
ruby shr.rb 11111111111111110000000000000000 22
ruby rotr.rb 11111111111111110000000000000000 22
ruby sigma0.rb 11111111111111110000000000000000
ruby sigma1.rb 11111111111111110000000000000000
ruby usigma0.rb 11111111111111110000000000000000
ruby usigma1.rb 11111111111111110000000000000000
ruby ch.rb 11111111111111110000000000000000 11110000111100001111000011110000 00000000000000001111111111111111
ruby maj.rb 11111111111111110000000000000000 11110000111100001111000011110000 00000000000000001111111111111111
```

You can do double-SHA256 (e.g. Bitcoin) by using `hash256.rb`

. This script accepts *hex data* (e.g. block headers, transaction data) by default.

```
ruby hash256.rb 0100000000000000000000000000000000000000000000000000000000000000000000003ba3edfd7a7b12b27ac72c3e67768f617fc81bc3888a51323a9fb8aa4b1e5e4a29ab5f49ffff001d1dac2b7c # genesis block header
```

## How does SHA-256 work?

The NIST specification contains a precise explanation of SHA-256. The following is essentially a visualised summary of that document.

### 1. Definitions

The official specification begins with a number of definitions, but seeing as this is a simplified explanation, all I want you to know is:

`bit`

=`0`

or`1`

(the smallest unit of storage on a computer)`word`

= 32 bits

Also, bitwise operations use the following symbols:

```
OR = |
XOR = ^
AND = &
NOT = ~
```

### 2. Operations

SHA-256 uses four basic bitwise operations on `words`

.

`shr.rb`

)

Right Shift (
SHR^{n}(x) = x >> n

Move bits a number of positions to the right. The bits shifted off the right-hand side are lost.

`rotr.rb`

)

Rotate Right (
ROTR^{n}(x) = (x >> n) | (x << 32-n)

Move bits a number of positions to the right, and place the shifted bits on the left-hand side. This can also be referred to as a *circular right shift*.

`xor.rb`

)

Exclusive Or (
x ^ y ^ z

The `XOR`

bitwise operator takes two input bits, and outputs a `1`

if *only one* of them is a `1`

. This is useful for getting a *balanced representation of multiple bits* when merging them together via multiple `XOR`

operations.

`add.rb`

)

Addition (
(v + w + x + y + z) % 2^{32}

This is standard integer addition, but we constrain the result to a 32 bit number by taking the result **modulus 2 ^{32}**.

### 3. Functions

The operations above can be combined to create functions.

The first four functions are named using the Greek symbol **Sigma** (lowercase `σ`

and uppercase `Σ`

). This is for no particular reason, it’s just so we can give names to some combined operations.

I like to think of these as the “rotational” functions.

`sigma0.rb`

)

σ0 (
σ_{0}(x) = ROTR^{7}(x) ^ ROTR^{18}(x) ^ SHR^{3}(x)

`sigma1.rb`

)

σ1 (
σ_{1}(x) = ROTR^{17}(x) ^ ROTR^{19}(x) ^ SHR^{10}(x)

`usigma0.rb`

)

Σ0 (
Σ_{0}(x) = ROTR^{2}(x) ^ ROTR^{13}(x) ^ ROTR^{22}(x)

`usigma1.rb`

)

Σ1 (
Σ_{1}(x) = ROTR^{6}(x) ^ ROTR^{11}(x) ^ ROTR^{25}(x)

The last two functions of **Choice** and **Majority** accept three different inputs.

`ch.rb`

)

Choice (This function uses the `x`

bit to **choose** between the `y`

and `z`

bits. It chooses the `y`

bit if `x=1`

, and chooses the `z`

bit if `x=0`

.

```
Ch(x, y, z) = (x & y) ^ (~x & z)
```

`maj.rb`

)

Majority (This function returns the **majority** of the three bits.

```
Maj(x, y, z) = (x & y) ^ (x & z) ^ (y & z)
```

`constants.rb`

)

4. Constants (
K_{t}= ∛primes(first 32 bits of fractional part)

SHA-256 uses sixty four constants `K`

to help with mixing up the bits during the main hash computation. These constants are generated by taking the _{t}**cube root** of the first sixty four **prime numbers**.

The *fractional parts* of these cube roots are irrational (they go on forever), so they make for a good selection of random bits to use at constants. This is better than using specifically chosen constants, as this makes it less likely that the hash function has been designed with a back-door.

Anyway, to get *32 bits* from these numbers, we take the fractional part and multiply it by 2^{32}, and use the resulting *integer* as the constant.

Now that we’ve defined the functions and constants we’re going to use, the next step is to *prepare the message* for hashing.

`message.rb`

)

5. Message (
As you may have noticed, SHA-256 operates on the individual *bits* of data. So we before we can hash any data, we first of all need to convert it to its binary representation (`1`

s and `0`

s).

For example when hashing a *string*, we convert each character to its corresponding number in the ASCII table. These numbers are converted to binary, and it’s this binary data that we use as the input to the hash function.

`padding.rb`

)

6. Padding (
The SHA-256 hash function works on data in 512-bit chunks, so all messages need to be *padded* with zeros up to the nearest multiple of 512 bits.

Furthermore, to prevent similar inputs from hashing to the same result, we separate the message from the zeros with a `1`

bit, and also include the size of the message in the last 64 bits of the padding.

**NOTE:** This method of separating the message with a `1`

and including the message size in the padding is known as **Merkle–Damgård strengthening** (MD strengthening).

`blocks.rb`

)

7. Message Blocks (
After the message has been padded, we cut it in to equal 512-bit **message blocks** `M`

to be processed by the hash function. (There is only one message block for this example message, so the animation above isn’t very interesting.)^{i}

Each of these message blocks can also be further split in to 16 words `M`

(^{i}_{j}`512 / 32 = 16 words`

), which will come in handy in just a moment.

Now that we have padded our message and cut it in to equal chunks, we put *each of the message blocks* through the main hash function.

`schedule.rb`

, `expansion.rb`

)

8. Message Schedule (For each message block we create a sixty-four word **message schedule** `W`

._{t}

The first sixteen words of this message schedule are constructed from the message block.

W_{t}= M^{i}_{t}(for 0 ≤ t ≤ 15)

This is then *expanded* to a total of sixty four words by applying rotational functions to some of the words *already in the schedule*.

W_{t}= σ_{1}(W_{t-2}) + W_{t-7}+ σ_{0}(W_{t-15}) + W_{t-16}(for 16 ≤ t ≤ 63)

`initial.rb`

)

9. Initial Hash Value (The hash function begins by setting the **initial hash value** `H`

in the ^{0}*state registers* (`a`

, `b`

, `c`

, `d`

, `e`

, `f`

, `g`

, `h`

).

H^{0}= √primes(first 32 bits of fractional part)

Like the constants, the initial hash value uses the fractional part of the **square root** of the first eight **prime numbers**. This gives us a random set of bits that we can use as a platform to begin the hash computation.

### 10. Compression Function

This is the heart of the hash function.

For each word in the message schedule, we use the current values in the state registers to calculate two new **temporary words** (`T`

and _{1}`T`

)._{2}

`t1.rb`

)

Temporary Word 1 (
T_{1}= Σ_{1}(e) + Ch(e, f, g) + h + K_{t}+ W_{t}

This temporary word takes the next **word in the message schedule** along with the next **constant from the list**. These values added to a `Σ`

rotation of the _{1}*fifth* value in the state register, the `choice`

of the values in the *last three* registers, and the value of the *last* register on its own.

`t2.rb`

)

Temporary Word 2 (
T_{2}= Σ_{0}(a) + Maj(a, b, c)

This temporary word is calculated by adding a `Σ`

rotation of the _{0}*first* value in the state register to a `majority`

of the values in the *first three* registers.

`compression.rb`

)

Compression (
After calculating the two temporary words, we shift each value in the state registers down one position, and update the following registers:

- The
*first*value in the state register becomes`T`

+_{1}`T`

._{2} - The
*fifth*value in the state register has`T`

added to it._{1}

This is one “round” of compression, and is repeated for every word in the message schedule.

After we have compressed the entire message schedule, we **add** the resulting hash value to the initial hash value we started with. This gives us the final hash value for this message block.

If there are further message blocks to be processed, the current hash value will be used as the *initial hash value* in the next compression.

**NOTE:** This process of applying a compression function to each message block and using the output as the input for the next compression is known as the **Merkle–Damgård construction**.

`final.rb`

)

11. Final Hash Value (
We will be left with eight 32-bit values in the state registers after applying the compression function to each message block.

The final hash value is just the *concatenation* of these eight 32-bit values to produce a 256-bit **message digest**. For compactness this message digest is usually shown in hexadecimal.

## Notes

- This isn’t the prettiest code I’ve ever written.
- These scripts redraw the entire terminal screen for every frame of the animation, so the display can become disjointed at faster speeds.
- All of the actual code for calculating SHA-256 hashes can be found in
`sha256lib.rb`

, all of the other files are animations. - I decided not to include the individual animations for
`expansion.rb`

,`t1.rb`

,`t2.rb`

in the main`sha256.rb`

animation. This is to help speed up the flow of the animation. - In terms of security; I believe the
**Sigma**functions help with the*diffusion of bits*, and the**Choice**and**Majority**functions give the hash function it’s*one-wayness*due to being*nonlinear*. The**addition modulus 2**is also^{32}*nonlinear*.^{1}

## Testimonials

that’s dope – esky33

## Links

- FIPS 180-4 – The official specification for the SHA-2 family of hash functions, including SHA-256.
- SHA-256 Examples – A couple of official hash examples to check your implementation with.
- Security Analysis of SHA-256 and Sisters – A paper by Henri Gilbert and Helena Handschuh explaining some security details about SHA-256.

### Footnotes

*1: Cryptography For Developers, Simon Johnson (pg. 218)*