Loading...
Loading...
Loading...
Loading...
Loading...
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__}For this challenge, we are provided with a short Verilog program, and a C++ wrapper for it using the Verilator library. Verilog is a language that is used to describe hardware and abstract it into a program. check.sv
This was my first time using Verilog, so most of the challenge involved learning the syntax. The C++ wrapper program essentially reads in one character at a time, up to 100, then runs the open_safe routine and checks its result. I realized it was likely a password checker, with our input being transformed in some way to result (if correct) in a 56 bit decimal (3008192072309708). If it reached this, we are sent the flag. Here's my understanding of the verilog.
I initially attempted to manually step back from the final expected bits, but my unfamiliarity with Verilog syntax and conventions led to a different result every time. At this point, I decided to invest time into installing Verilator, allowing me to build the binary for myself; which would be needed to check my flag. The largest advantage though was the ability to add debugging statements in.
Using this, I could see how my data was transformed. I sent test pieces of data, starting at 0b0000001, and doing a binary shift left each iteration; this was to give me recognisable patterns to work from.
We were able to get the states of the memory, magic and kittens arrays after entering each character.
From here, we can just manually work out where all the bits are after getting a test case:
dddfffffffgggggggccccccceeeeeeehhhhhhhddddaaaaaaabbbbbbb
Then, we can use this on our compare string to get the binary we want:
00110111 01001100 01101111 01011000 00100101 00101010 01011111 1111000 (converted to 8-bit)
And then simply decode this to get the password 7LoX%*_x, which we enter on the remote to get the flag!
CTF{W4sTh4tASan1tyCh3ck?}Statically linked binary - it mmaps a RWX region, reads the length of shellcode from us, then reads that much data from stdin into the mmaped region. It then installs some strict seccomp and executes our shellcode. The goal is to read a file - /home/user/flag. However. read is BANNED. In fact, this seccomp is a whitelist not a blacklist, and few useful things are allowed. For our purposes, we'll use open, lseek and write.
First, the binary forks. The child process does some sort of loop in which it continuously reads 4 bytes out of /home/user/flag and checks it against CTF{.The parent reads the shellcode, installs seccomp and runs the shellcode. Since the seccomp is done after forking, the child does not inherit seccomp. This means we can begin to hijack the memory of the child from the parent in our shellcode, and force the child to do things that we cannot. The binary prints the PID of the child, so we can use /proc/<pid>/mem. 1. Build "/proc/<pid>/mem" on the stack using push and mov 2. open this file 3. lseek it so that we can write to the read function of the child process 4. Build shell popping shellcode on the stack 5. write shell popping shellcode to the read() function 6. To prevent the parent process exiting before the shell has time to pop, use jmp $ to continually jump to the current RIP, keeping it alive 7. This works, and a shell is popped. From there, we cat flag to get the flag.
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}