0
$\begingroup$

I've been to https://docs.google.com/spreadsheets/d/1mOTrqckdetCoRxY5QkVcyQ7Z0gcYIH-Dc0tu7t9f7tw/edit#gid=1194752368, http://www.righto.com/2014/09/mining-bitcoin-with-pencil-and-paper.html, and https://en.wikipedia.org/wiki/SHA-2#Pseudocode (the pseudocode is for sha256)

The use of those links, not withstanding, I cannot create the 'W' values beyond the first 16 values. Everything I read is complex beyond my understanding.

In a very simplistic and step by step example, how do I get the 'w' values for SHA256?

$\endgroup$
  • $\begingroup$ Do you know what a rightrotation and a rightshift on 32 bit words is? and xor? Then you can just follow the recursion, a simple loop. $\endgroup$ – Henno Brandsma Mar 23 '18 at 13:41
  • $\begingroup$ Xor and "bitshift", yes. The other(s), no. $\endgroup$ – Mine Mar 23 '18 at 20:04
  • $\begingroup$ See here to implement right rotation in python. $\endgroup$ – Henno Brandsma Mar 23 '18 at 20:42
  • $\begingroup$ I see, the "rotation" is the same as a bit shift, but the bits that normally fall off and disappear merely reappear at the other end (instead of it being just filled up with zeros in the case of a bitshift). Okay, I know that, I just didn't know that was the term for it. Still don't know how to get all the W values. $\endgroup$ – Mine Mar 23 '18 at 22:29
  • $\begingroup$ Are you writing this for fun/learning, or because you need to hash something with sha256? I ask because python comes with with sha256 out of the box via hashlib.sha256, so if you just need to use sha256 on something then you're going about it the long/wrong way. $\endgroup$ – Ella Rose Mar 23 '18 at 23:13
2
$\begingroup$

In SHA-256, $W$ is a vector of 64 values $W_i$ each 32-bit, collectively forming an expanded form of the input to a compression step. Said input is a 512-bit sub-block of the message to be hashed par SHA-256 after that message was padded. The $W_i$ depend only on said input.

$W_0$ to $W_{15}$ are said input, formatted as 32-bit words. $W_{16}$ to $W_{63}$ are computed from these by applying for $i$ from 16 to 63 the recurrence defined by FIPS 180-4 section 6.2.2 as (within a reordering of terms): $$W_i\gets W_{i-16}\;\tilde+\;\sigma_0(W_{i-15})\;\tilde+\;W_{i-7}\;\tilde+\;\sigma_1(W_{i-2})$$ where $\;\tilde+\;$ is addition with truncation of the result to 32-bit.

In the above expression, $\sigma_0$ and $\sigma_1$ are 32-bit functions of a 32-bit argument defined by FIPS 180-4 section 4.1.2 as: $$\begin{align} \sigma_0(x)&\gets(x\ggg\,\,\,7)\oplus(x\ggg18)\oplus(x\gg\,\,\,3)\\ \sigma_1(x)&\gets(x\ggg17)\oplus(x\ggg19)\oplus(x\gg10) \end{align}$$ where $\oplus$ is bitwise-XOR, $\ggg$ is right-rotation of a 32-bit word (also known as right-rotate-no-carry or right-circular-shift), $\gg$ is right-shift of a 32-bit word (also known as right-logical-shift).

For example, to compute $W_{16}$, we

  1. apply the function $\sigma_0$ to $W_1$ (right-rotating that value by 7 and 18 bits, right-shifting it by 3 bits, then combining the resulting three 32-bit values by XOR);
  2. apply the function $\sigma_1$ to $W_{14}$ (right-rotating that value by 17 and 19 bits, right-shifting it by 10 bits, then combining the resulting three 32-bit values by XOR);
  3. add $W_0$, $W_9$, and the two above results, truncating the result to 32-bit.

Note: the reason for using shift rather than rotate for one of the terms of $\sigma_0$ and $\sigma_1$ is discussed here.

Note: often (including in almost any careful hardware implementation) it is kept only the chronologically last obtained 16 values of $W$, evolving as the compression rounds are performed per the transformation: $$W_i\gets W_i\;\tilde+\;\sigma_0(W_{(i+1\bmod16)})\;\tilde+\;W_{(i+9\bmod16)}\;\tilde+\;\sigma_1(W_{(i+14\bmod16)})$$

| improve this answer | |
$\endgroup$
0
$\begingroup$

Following the wiki code: we have a message block of $512$ bits (or $64$ bytes) that you're dealing with. We see those as $16$ words of $32$ bits each. These are W[0],..., W[15], in order.

Then e.g. W[16] = W[0] ^ f_1(W[1]) ^ W[9] ^ f_2(W[14]) where f_1(w) transforms the word w into ror(w,7)^ror(w,18)^(w>>3) where ror is implemented as in the link in my comment above, and f_2(w) = ror(w,17)^ror(w,19)^(w>>10) Then W[17] is the same with all indices moved up 1, etc. So : W[17] = W[1] ^ f_1(W[2]) ^ W[10] ^ f_2(W[15]) and next W[18] = W[2] ^ f_1(W[3]) ^ W[11] ^ f_2(W[16]), etc.

So W[16],....., W[63] are all computed based on the previously computed W[i] in a way that mixes up the bits, and we get a 4-fold expansion of the message block words that are used as starting values.

Conceptually, what's happening in this hash function (and others like this) is that we're using a block cipher $E(m,k)$ (often called the "transform" function in code implementations) with block size (for $m$) of 256 bits (8 words) and keysize (for $k$) of 512 bits. To handle a message with blocks $m_0,m_1, m_2, \ldots, m_N$ (where the last block(s) have padding and a total length) is to define $h_0$ to be a fixed block, and then computing $h_1 = E(h_0,m_0) + h_0$ (message block addition happens per word, modulo $2^{32}$), $h_2 = E(h_1, m_1) + h_1$, etc. up to $h_{N+1} = E(h_N, m_N) + h_N$ and then $h_{N+1}$ is the final hash. Adding the input to the cipher output makes the result irreversible (which is what we want with hash functions).

The $E$ function uses a message block as key, and the computation of the $W$ words is its key schedule: it creates round keys for the block cipher (which has 64 rounds for SHA-256 and uses one $W$ word per round, this is the last big loop in the Wikipedia pseudo code).

I think the pseudo code can quite well be translated into pure Python, using a good ror function, of course.

It would help if you can tell where your code no longer gives the right result as compared to the spread sheet links. And it's more of a stackoverflow question if it's about code itself, IMHO.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Its not so much the code, its about what is done. I don't really fully understand your provided explanation (as an example). Its not that my code doesn't give the right answers, its I literally don't know how to code for the W part past the first 16 W's. The first two links I gave were very good at explaining things, up until the W's. $\endgroup$ – Mine Mar 23 '18 at 23:21
  • $\begingroup$ Considering you're the only one who has tried to answer this so far, I'd like to be more specific. For example, in your answer, how do I get, specifically, W[16]. How do I get W[17], how do I get W[18]? I've gotten the impression that W[16] and W[17] are different from W[18]...and on. I'm not worried so much about the exact programming code, but understanding how it works such that I could write the code myself. $\endgroup$ – Mine Mar 24 '18 at 4:31
  • $\begingroup$ @Mine added some conceptual explanation. The expansion of the W's is a straightforward loop in i. Ever programmed a Fibonacci sequence (or some such recursive sequence?) $\endgroup$ – Henno Brandsma Mar 24 '18 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.