This challenge involved reversing the sha256 hash function where there were unknown keys.
Unlike some of my other writeups where I reverse everything there is in a pretty logical order, I want to walk through how I personally solved the challenge, since I did it in a rather strange order.
Reversing challenge.py
I obviously had to start by taking a look at the challenge.py file first, since it had the main functions and what was happening.
We see that challenge.py
starts by calling the generate_random_round_keys with parameter of 8
calls the sha256_with_secret_round_keys with the round keys and our message, which if we look is 'Encoded with random keys', and is constant
prints the hex result of sha256_with_secret_round_keys
So, we need to deduce the keys used in the sha256 function when we know the message and the hash created by that message with the keys.
If we take a look at the generate_random_round_keys function, we see it just generates a 32 bit number n times, where n is the number passed to the function, more specifically, it generates a number between 0 and 256 4 times and concatenates the numbers together. Nothing vulnerable here.
Then, we look at the sha256_with_secret_round_keys function.
We see that it just calls the sha.sha256 function on the message, along with the round keys that were generated.
It seems that the sha.sha256 is imported and given to us in the sha256.py file, so we need to go have a look at that.
The sha256.py file
This file seems to be the actual crypto part of the challenge.
Taking a quick look at the program, I deduced that it performs 64 rounds of the compression function on our padded message.
Since we know the message and it stays constant, we can use the given compute_w function to generate the w for our message.
We also know the k values, so we can just use those.
Reversing a round with all values
My first goal was to try and figure out how to reverse a round of one of these functions.
We can take a closer look at the compression function, and see that
only 2 values actually change, which are d and h, the rest are just shifted right by 1 place.
We also see that, because of this, we can calculate quite a few variables mentioned, 4 to be exact, which are s1, ch, maj and s0, using the given functions.
Now, we need to figure out what d and h are, from tmp2 and tmp3.
We know that:
Each of these are then taken mod 4294967296 (referring this to p from now on).
Rewriting these, we get
Now, we know tmp2 and tmp3, so we and in the case of tmp2, we can just subtract all our known values and take that mod p to get h
Then, since we know h, we can then carry on to work out d, subtracting all the values from tmp3 and taking that mod p to get d.
So now we know how to reverse a round in the case where we know all the previous values, and also the k_i and w_i values.
I wrote a messy function in python to do this:
Now, once I had this done, I thought I had solved the challenge, and that the goal was to recover the initial state of the hash function, since there were 8 keys, and so I was suprised when it didn't work.
Not over yet :/
Taking another look at the script however, we can see that the keys generated are used as the first 8 k values, however the rest remain unchanged, and the state is constant.
Knowing this, if we know the initial state and the fact that values each round are shifted right by one, we generate this table: (using sample values here)
Now, at the time I didn't realise this, but my getprev function was able to recover the entirety of the first half of the table, since I believe that the first half of the values aren't affected by the second half, while the second half are.
So, now we know the entirety of the first 4 columns of the table.
However, there are still 4 32 bit numbers which we don't know.
Since we know the initial state, we should probably only look at the initial state and the one after it, since we have more values, and if we are able to work out the 5th value in that second row, it basically becomes the exact same problem on each row.
The important thing to notice here is that the only place where k_i is used at all is when calculating tmp1, and so we can calculate all the other values except tmp1 (and therefore tmp2 and tmp3).
We can then get our equations from before:
Since we know everything for tmp1 except for k_1, I'm going to write a new equation:
temp = h + s1 + ch + w_i
Then we can rewrite the equations:
Now, we can work out what our new variable temp is, since all the values we have, and then we can also easily calculate k_i since we know tmp2, and so we just subtract (temp + s0 + maj) from tmp2 to get k_i, which we then use to calculate tmp3!
We then fill in our table in the four cells where tmp3 is used, and then repeat for the next row, since we know all values again (apart from k_i of course!)
Again, another messy python function to solve:
Once we have our solution matrix, I made another function just to get the k_i values and output them.
After all the rounds, we see a line in the sha256 function before the state gets returned to the player:
This basically
takes x from the current state and y from the initial state
This is once again very easy to reverse, we just take our outputted hash, subtract each number of the initial state from it, and then mod p once again.
Now we have all the steps done, we just need to put it all together.
Final solve script:
Flag: CTF{sHa_roUnD_k3Ys_caN_b3_r3vERseD}