Can you find the round keys?
We got a modified SHA256 in this task. The first 8 round constants are replaced by 8 random values, and our goal is to recover those 8 round constants with only one output hash and its input.
- Subtract the IV from the output
- Undo last 56 rounds
- Recover round constants from 8 to 1 by propagating the error the first round.
The overall structure of SHA256 looks like this:
def sha256(inp): padded = pad(inp) # pad to multiple of 64 bytes blocks = chunk(padded) # split each 64 bytes blocks state = IV for block in blocks: w = compute_w(block) s = compression(state, w, ROUND_KEYS) state = [(x + y) & 0xffffffff for x, y in zip(state, s)]
In this task, our input has only one block, so the for loop only runs once. Also, we know what the input is, so we have all those
The last step can be reversed by subtraction:
state = [(x - y) & 0xffffffff for x, y in zip(state, IV)]
Next, the compression function is:
def compression(self, state, w, round_keys): for i in range(64): state = self.compression_step(state, round_keys[i], w[i]) return state def compression_step(self, state, k_i, w_i): a, b, c, d, e, f, g, h = state s1 = self.rotate_right(e, 6) ^ self.rotate_right(e, 11) ^ self.rotate_right(e, 25) ch = (e & f) ^ (~e & g) tmp1 = (h + s1 + ch + k_i + w_i) & 0xffffffff s0 = self.rotate_right(a, 2) ^ self.rotate_right(a, 13) ^ self.rotate_right(a, 22) maj = (a & b) ^ (a & c) ^ (b & c) tmp2 = (tmp1 + s0 + maj) & 0xffffffff tmp3 = (d + tmp1) & 0xffffffff return (tmp2, a, b, c, tmp3, e, f, g)
It won't be too hard to write its inverse by changing order of instructions and terms:
def decompression_step(self, state, k_i, w_i): tmp2, a, b, c, tmp3, e, f, g = state maj = (a & b) ^ (a & c) ^ (b & c) s0 = self.rotate_right(a, 2) ^ self.rotate_right(a, 13) ^ self.rotate_right(a, 22) tmp1 = (tmp2 - s0 - maj) & 0xffffffff d = (tmp3 - tmp1) & 0xffffffff s1 = self.rotate_right(e, 6) ^ self.rotate_right(e, 11) ^ self.rotate_right(e, 25) ch = (e & f) ^ (~e & g) h = (tmp1 - s1 - ch - k_i - w_i) & 0xffffffff return a, b, c, d, e, f, g, h
The last 56 round constants is same as standard SHA256, so we can undo those rounds with the inverse function above.
The problem is: how to reveal those secret round keys?
Linear property of first 8 rounds
In decompression_step, we can notice that
k_i is only used to calculate
h. If we use a wrong round constant in
h will be incorrect. All values from
g is still valid. Furthermore, the error in
h is the difference between the real round constant and the constant we use.
Consider the last round (i.e. round 8), If we use 0 as the round constant to undo this round, Only
h is incorrect, and the difference to the real one is the secret constant we want.
Next, consider round 7,
g and all values from
f is valid. Values after
h will be rubbish, but it doesn't matter.
Keep undoing those rounds with round constant 0, the error will be propagate to
a, and the difference between our
a in IV will be the last secret constant we want !!!
With this secret constant, we can undo round 8. And use same tricks again to make the error of round 7's constant propagate to
b and so on.
You can found the script at here.