Sorry about that. I just wanted to make sure I knew W and K like the back of my hand. Thank you for all the help. I am extremely grateful for it. Sorry if it was really troublesome.
Topic: SHA256 Scheduler? (Read 3172 times)
Both w and k are 64 element arrays. The w[t] element is used each round where t is the current round {0...63}. The diagram indicates just that. It simply omits rounds 2 to 62 because all the rounds are identical and it would make the diagram massive otherwise. Diagrams seem to not be your thing did you look at the pseudocode I linked to. It describes it in very 'english like' syntax. The SHA-2 family really isn't that complex. ECDSA on the other hand ...
http://en.wikipedia.org/wiki/SHA-2#Pseudocode
Specifically "a = h + Ch(e,f,g) + Sum1(e) + w[t] + k[t] + Sum0(a) + Maj(a, b, c)" So on round 0 w[0] and k[0] is used, on round 1 w[1] and k[1] is used ... on round 63 w[63] and k[63] is used.
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 = atic
a = h + Ch(e,f,g) + Sum1(e) + w[t] + k[t] + Sum0(a) + Maj(a, b, c)
http://en.wikipedia.org/wiki/SHA-2#Pseudocode
Specifically "a = h + Ch(e,f,g) + Sum1(e) + w[t] + k[t] + Sum0(a) + Maj(a, b, c)" So on round 0 w[0] and k[0] is used, on round 1 w[1] and k[1] is used ... on round 63 w[63] and k[63] is used.
I understand what is going on with K here, its the constants that the NSA provided.
I also notice that W does not go to each round. Is their a formula/rule for when W gets inputted?
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.
Yes. a and e for the first 3 rounds are precalculated because they don't change when you change the nonce in the block header.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.
It's part of the speed optimization.
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.
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.
These six values do not depend on the nonce, so they can be precalculated once, outside of the nonce loop.
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?
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?
Does Bitcoin just use the standard 64 rounds or does it require less?
It wouldn't be SHA-2 if it used fewer rounds.
Does Bitcoin just use the standard 64 rounds or does it require less?
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.
Quote from: Bruce Schneier
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.
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.
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?
Would it be detrimental if you failed to perform 64 rounds?
Yes
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?
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?
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. 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?
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
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).
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).
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?
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?
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.
- 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.
The scheduler also appears to have the same two functions as this "Expander" which I have no clue what it's for.
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".
I realized the more rounds you have, the harder it gets to "reverse".
Jump to: