Why Reversing Sha256 Is Hard

sha256 is an algorithm that modifies eight 32 bit integers in place and returns a new set of 8 integers. The starting 8 integers are always the same:

// first 32 bits of the fractional parts (the decimals) of
// the square roots of the first 8 primes
h0 := uint32(0x6a09e667)
h1 := uint32(0xbb67ae85)
h2 := uint32(0x3c6ef372)
h3 := uint32(0xa54ff53a)
h4 := uint32(0x510e527f)
h5 := uint32(0x9b05688c)
h6 := uint32(0x1f83d9ab)
h7 := uint32(0x5be0cd19)

The digest for the letter ‘a’

ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb

is just the concatenation of the 8 calculated integers.

h0 := uint32(0xca978112)
h1 := uint32(0xca1bbdca)
h2 := uint32(0xfac231b3)
h3 := uint32(0x9a23dc4d)
h4 := uint32(0xa786eff8)
h5 := uint32(0x147c4e72)
h6 := uint32(0xb9807785)
h7 := uint32(0xafee47bb)

Reversing a sha256 hash would mean performing calculations to get back to the original 8 values of h0..h8. Because sha256 incorporates parts of the message in to its calculation, we would also reveal the message in the process.

let’s simplify the task by just trying to reverse h0. We can look at the steps taken to arrive at h0 by following the specification¹ backwards. h0 is the addition of the previous value of h0 and a calculated variable a. What was the previous value of h0? We have no idea! We’ve already hit a road block before we began!

This can be simplified further. h0 + a happens once for each 512 bits in the message schedule. For messages smaller than 512 bits, we can assume h0 is the initial value 0x6a09e667. We’ll guess the message is smaller than 512 bits. This let’s us turn our attention to reversing the variable a. It gets calculated as such:

func rightRotate(value uint32, shift uint) uint32 {
	return (value >> shift) | (value << (32 - shift))
}

// the 64th iteration of the sha256 algorithm, which gives the final value of `a`
s1 := rightRotate(e, 6) ^ rightRotate(e, 11) ^ rightrotate(e, 25)
ch := (e & f) ^ ((^e) & g)

temp1 := h + s1 + ch + uint32(k[63]) + uint32(w[63])

s0 := rightRotate(a, 2) ^ rightRotate(a, 13) ^ rightRotate(a, 22)
maj := (a & b) ^ (a & c) ^ (b & c)
temp2 := s0 + uint32(maj)

a = temp1 + temp2

We’ve stumbled in to a endless maze of misdirection! We have to know all of the previous values of a, b, c, e, f, g and h along with the 32 bit value in the message schedule w at index 63. Ignoring the 8 variables a..g, Let’s consider finding just the value of w[63]. That was originally calculated as:

s0 := rightRotate(w[48], 7) ^ rightRotate(w[48], 18) ^ (w[48] >> 3)
s1 := rightRotate(w[61], 17) ^ rightRotate(w[61], 19) ^ (w[61] >> 10) 
w63 = w[47] + s0 + w[56] + s1

and following the specification of the algorithm, to know w[48] we need to know w[33], and to know w[33] we need to know w[18], and to know w[18], we need to know w[2] which is potentially a 32 bit chunk of the original message!

It doesn’t end here, even if we guessed these values, we would have to guess them 63 more times and hope that values h0...h8 align with their initially instantiated values. Remember, we’ve simplified this so that only 1 block is involved. There could be multiple blocks! Essentially, whether brute forcing forwards or backwards, you must guess the original message.