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.
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
prompts the user to enter a number of keys in hex, seperated with a comma
and makes sure the number of keys entered is 8
compares the keys entered by the user to the actual secret keys used n the sha256_with_secret_round_keys function
if they all match, then it prints Good job, here's a flag:, along with the flag
if not, then it prints Sorry, that's not right.
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.
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.
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.
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
adds them together
takes it mod p
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:
CTF{sHa_roUnD_k3Ys_caN_b3_r3vERseD}This was an RSA challenge where you had to break the prime generation function. We see that the function
Generates a 64 bit number
Does a logical OR with 0xc000000000000001 on it
Then, for 16 rounds:
Sets the chunk to s
Multiplies s by a constant a (0xe64a5f84e2762be5)
Then, if the number generated is prime, it returns it
I got s1*s2 by getting the upper and lower bits of n and applying modinv
We can represent p as [x][xa][xa^2]... where each [] is 64 bits long or p = x64^15 + ax64^14...
Multiplying it with q would give (kek how do i represent this) [0 ][1 ][2 ]... ... [30][31] <- chunk indexes (64 bits long) [xy ] ... ... [xya^30] [xya ]... [xya^29] [xya ]... [xya^29] since its n = xy64^30 + 2xya64^30 ... + 2xya^29*64^1 + xya^30
We can get upper and lower bits of n to get upper and lower bits (with modinv of a) of xy like this. however since theres a 2 coefficient on 2xya*64^30 this value is bit shifted and leaks into the last upper bits of xy. this gives 2 values what xy could be (one where the the bit is subtracted and one where it isnt). which are 0xab802dca026b182578adce5060bd0eb1 or 0xab802dca026b182478adce5060bd0eb1
Script below to gen s1*s2 (bit removal hasnt happened yet)
I factored these numbers and generated (kind of) all the 64 bit factors for both of these 128 bit numbers, and then tried using them as s in order to get the primes p and q. 0xab802dca026b182478adce5060bd0eb1 has no 64 bit factors, so it had to be 0xab802dca026b182578adce5060bd0eb1. The 64 bit factors of that number are [17323093358088416319, 11957115919933039605, 15301219884532198649, 14589535238740003363, 10091363333161070837, 14567509746395306455, 15648764542394866359, 15625139955456876315, 14898389259854230905, 14898389259854230905, 15625139955456876315, 15648764542394866359, 14567509746395306455, 10091363333161070837, 14589535238740003363, 15301219884532198649, 11642633479736017985, 9423396846760527157, 9883074741724455311, 13159516333377194255, 12330536802058217123] I then modified the gen_prime function to, if it wasn't prime, don't repeat, since these s's should generate a prime without having to do anything. This resulted in the 2 factors p and q, and then we used this to decrypt the flag.
CTF{__donald_knuths_lcg_would_be_better_well_i_dont_think_s0__}