SHA256 Scheduler?

[Reclaim3r]

What is it pretty much. I've wrapped my head around the four functions ( five if you count the Modulo 32 ) and compression to a degree ( padding and splitting or "chunking" as I like to call it).
What is this "Message Scheduler"?

I've been looking through the NIST documents on SHA256 and I see something called a "message scheduler" not sure what that is 
Any ideas or explanations?

[1714972592]

1714972592

[1714972592]

1714972592

[1714972592]

1714972592

[1714972592]

1714972592

[DeathAndTaxes]

SHA-256 involves 64 rounds per block (512 bit input) and each block is broken into eight 32 bit words.  The message schedule refers to the movement of the words through the algorithm.



Word A for round n becomes word B for round n+1 is part of the message schedule.

[Reclaim3r]

SHA-256 involves 64 rounds per block (512 bit input) and each block is broken into eight 32 bit words.  The message schedule refers to the movement of the words through the algorithm.



Word A for round n becomes word B for round n+1 is part of the message schedule.

So the data from the previous round just gets shifted? And what exact are Wt and Kt? From what I can gather, they are where you put the initialization values the NSA supplies.

[DeathAndTaxes]

k is an array of static initialization value and remains the same for all hashes.  It was chosen by NIST but it is a 'nothing up my sleeve number' with a decent selection criteria.  It would be difficult for those constants to affect the security of the hash.  You would have to believe that there is some relationship between the fractional portion of the first 64 sequential cube roots, that NIST was aware of that weakness and nobody in the crypto community has discovered that weakness since SHA-2 was released.

w is initialized from the the current block before the 64 rounds so it varies from message to message and even block to block.  The algorithm for the generation of the w array comes from SHA-2 but the input is the message to be hashed.

Both are 64 value arrays.  In each round the value injected into "a" will change so it serves the purpose of preventing round collisions which could undermine the security of a hashing function.  It is't exactly accurate but it might help to think of them as entropy injectors.  The t is the 0-index value for the current round so only one value is used each round and each round has a different value (i.e. for round 1 w[0] and k[0] is used for round 64 w[63] and k[63] is used).

Code:

Initialize array of round constants:
(first 32 bits of the fractional parts of the cube roots of the first 64 primes 2..311):
k[0..63] :=
   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

So the data from the previous round just gets shifted?

It is mostly shifted with the exception of e and a. So for each of the 64 rounds

Code:

h = g
g = f
f = e
e = d + h + Ch(e,f,g) + Sum1(e) + w[t] + k[t]
d = c
c = b
b = a
a = h + Ch(e,f,g) + Sum1(e) + w[t] + k[t] + Sum0(a) + Maj(a, b, c)

Note all addition is mod 2^32 so overflows "wrap around".  There are a number of ways in which the SHA-2 algorithm can be optimized for performance but when learning it is useful to look at the reference design.

[Reclaim3r]

Since Bitcoin uses a Double SHA256, I've heard you can "carry over" data. And why 64 rounds? Is that a standard?
I realized the more rounds you have, the harder it gets to "reverse".

[Reclaim3r]

The scheduler also appears to have the same two functions as this "Expander" which I have no clue what it's for.

[hhanh00]

Yes, the expander part is the message schedule.

- First, the message is padded.
- Hashing starts with a predefined value as the intermediate hash
- then it takes a block of message input (64 bytes) and it expands it to an array of 64 x 4 bytes. It is called the message schedule.
- then it runs 64 times the same bit manipulation function (the compression function) on the intermediate hash value. Each time is called a round and it uses one element of the message schedule `Wt` and one predefined constant `Kt`.
- After 64 rounds are finished, it goes to the next message block.
- Once the message is consumed, the intermediate hash is the result.

Each little rectangle with an arrow in the expander contains one element of Wj. It's basically a buffer of 16 x 4 bytes. The first 16 elements are the same as the input message block.
The rest is defined as Wj = o1(Wj-2) + Wj-7 + o2(Wj-15) + Wj-16. The expander calculates one element of Wj that it feeds into the compression function. In the next round, the buffer shifts and one new Wj gets calculated.

[Reclaim3r]

Why does it need to be expanded if the input has already been compressed/padded?

You state that is expands it into an array of 64 x 4 bytes which turns into the message schedule.

From what I'm seeing, the data in the message scheduler is also part of the data you're compressing but it is somehow separate from the "compressor" as labeled in the diagram.
This "Expander", which is part of the message scheduler, takes in "Wt", a chunk of data from the message schedule and "Kt", a predefined constant. I assume I understand this correctly?

[DeathAndTaxes]

It isn't compressed and then expanded.  It is 'expanded' and then compressed.

The W[t] value comes from the block input however the block is only 512 bits and SHA-256 uses 32 bit words.  The block input provides sixteen words but there are 64 rounds.  The first 16 round inputs (w[0] to w[15]) are directly copied from the block input and the 'expander' is the process of expanding those 16 words into the other 48.  When the expander is complete there are 64 round inputs one for each round of the compressor function.

Honestly all the documents and diagrams make this seem much more grandiose and complex than it really is.  The pseudocode from wikipedia does a good job of describing the whole algorithm.  The expander portion

Code:

    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
        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

That is it.  The 'expander' is simply the algorithm used to turn 16 words (32 bit each) into 64 words (32 bit each).  Nothing more.  Why 64?  Because there are 64 rounds and injecting a new unique value each round prevents round collisions.  This portion of the code executes once for each 512 bit block of the message.  It executes just prior to the 64 rounds of the compressor function.  When the 64 rounds are complete the next block is processed (first expanded into 64 w values and then compressed).

[hhanh00]

Why does it need to be expanded if the input has already been compressed/padded?

You state that is expands it into an array of 64 x 4 bytes which turns into the message schedule.

From what I'm seeing, the data in the message scheduler is also part of the data you're compressing but it is somehow separate from the "compressor" as labeled in the diagram.
This "Expander", which is part of the message scheduler, takes in "Wt", a chunk of data from the message schedule and "Kt", a predefined constant. I assume I understand this correctly?

These diagrams have to be read as if everything executes in parallel because that's what the hardware will do. Each box contains one word (= 4 bytes) and on the next clock tick, every arrow is 'executed' and it repeats. It's not a description of the algorithm that someone will use to write code but it shows how to do it in hardware. It is better for finding the critical paths, i.e. the paths that take the longest time because they involve more steps.

[Reclaim3r]

I notice that a lot of these diagrams show the expander as a seperate component to the compressor ( which is understandable )
However, I keep getting confused between the diagrams I see in official documents and this one



I hate to ask these seemingly simple questions but if I'm understanding this right, Kt are the predefined constants and Wt is derived from the inputted data. They get combined each round. right?

[hhanh00]

Yes

[Reclaim3r]

Wt is derived from the inputted data, which gets expanded by the expander and Kt are just the constants. One constant is used per 64 rounds.

Would it be detrimental if you failed to perform 64 rounds?

[hhanh00]

Kinda. SHA-2 hasn't been cracked (i.e nothing better than brute force) but versions with a reduced number of rounds have. It's not very important because it's not the full SHA-2 and even there the complexity is still much too high for a practical crack. Of course, if you only perform a few rounds you are dead.

[DeathAndTaxes]

Would it be detrimental if you failed to perform 64 rounds?

Possibly. Everything else being equal more rounds is better than less.  It is a compromise between computing time and security.  More rounds won't help however if the algorithm is cryptographically flawed.  However if you change anything, you have 'designed' a new hashing algorithm. SHA-256 is deterministic; for a given input there is only one valid SHA-256 hash.

'Rolling your own' cryptography is almost universally a bad idea.

Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can't break. It's not even hard. What is hard is creating an algorithm that no one else can break, even after years of analysis. And the only way to prove that is to subject the algorithm to years of analysis by the best cryptographers around.

[Reclaim3r]

Does Bitcoin just use the standard 64 rounds or does it require less?

[hhanh00]

Does Bitcoin just use the standard 64 rounds or does it require less?

It wouldn't be SHA-2 if it used fewer rounds.

[Reclaim3r]

How does the padding work?

I had another question, not sure if its related, but Avalon documentation shows they do some form of preprocessing before sending it to the actual ASIC to "improve efficiency".
Is it padding or something to do with expansion?

[Schleicher]

These six values do not depend on the nonce, so they can be precalculated once, outside of the nonce loop.

[Reclaim3r]

Values as in inputs?

I know they denote SHA256 as having 8 inputs with A-H, each capable of taking in 32 bits. Inputs A and E require processing but everything else just gets shifted over.