Understanding SHA256 (for dummies)

[irukandji]

So, with the SHA256 process (?) we can take any string of words and numbers and *do something* to it and we get a 256 string of ones and zeroes .Small changes to the input give an unrelated new string/key.

This can also be converted to other forms/keys (?) 

Hopefully I got that right.
My questions is....What do we do to the original set of words and numbers?    What is the process?

If t is difficult to explain, then, is there a good analogy or way to explain it?

Thanks

[NotATether]

There is some pseudocode of SHA256 on Wikipedia at https://en.wikipedia.org/wiki/SHA-2#Pseudocode, I will try to explain what that does.

First of all the digest size of SHA256 is obviously 256 bytes; this is the length of the output of the SHA256 function.

Second, the string, which can be an arbitrary byte array like an executable program, gets a single 1 bit appended at the end, the enough zeros to make the total length a multiple of 512, and is then split into 512-bit chunks.

The digest function of SHA256 is applied 64 times (rounds) and transforms 256 bits (split into 8 32-bit ints) into 256 bits, also split into 8 32-bit ints.

With each 512-bit chunk, you take a large 2048-bit buffer array to use as temporary space, put the first 512-bit chunk at the beginning of the array and apply a transformation on each group of 512 bits, moving further along the buffer after each iteration. Eventually all 2048 bits of the buffer "w" are transformed.

I paste the relevant code snippet from the pseudocode below:

Code:

(message is the input with a 1 and enough 0s appended)
Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
    create a 64-entry message schedule array w[0..63] of 32-bit words
    (The initial values in w[0..63] don't matter, so many implementations zero them here)
    copy chunk into first 16 words w[0..15] of the message schedule array

    Extend the first 16 words into the remaining 48 words w[16..63] of the message schedule array:
    for i from 16 to 63
        (You don't have to understand what this does except that it overwrites the 32-bit integers between w[i-16] to w[i])
        (w is array of 32-bit ints)
        s0 := (w[i-15] rightrotate  7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift  3)
        s1 := (w[i- 2] rightrotate 17) xor (w[i- 2] rightrotate 19) xor (w[i- 2] rightshift 10)
        w[i] := w[i-16] + s0 + w[i-7] + s1

The 8 32-bit variables that are used in the hashing are the hashes, these are appended together to make the 256-bit digest for each round.

At first they are initialized with "first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19" (they are written in binary, and not decimal format. This is the math behind how to derive sqrt(2) in binary for example.):

Code:

h0 := 0x6a09e667
h1 := 0xbb67ae85
h2 := 0x3c6ef372
h3 := 0xa54ff53a
h4 := 0x510e527f
h5 := 0x9b05688c
h6 := 0x1f83d9ab
h7 := 0x5be0cd19

Then the  digest algorithm takes these initial hash values, "w" and another set of constants "k" to make new "h" values which are then added to h0,h1,...h7. So after one round of SHA256 completes, you have 8 different "h" values. All 64 rounds are applied for each chunk in succession.

There is also "k", which is just an array of 64 32-bit round constants, they are first initialized as the (according to wikipedia) "first 32 bits of the fractional parts of the cube roots of the first 64 primes 2..311". They are not changed after each round, they remain constant and the same. It's too big to paste here but it's in the article.

Graphical explanation of the digest process from bitcoinwiki.org, which shows where the chunks are inserted and transformed:


(Source: https://en.bitcoinwiki.org/wiki/SHA-256)


Again, none of this is my own work, I'm not the source for it, this explanation was derived from the Wikipedia article I linked above.

[odolvlobo]

This video shows the SHA-256 process very clearly: Mining Bitcoin with pencil and paper