Google CTF 2019 Crypto challenges writeup

Code can be found here

Quantum Key Distribution

Two of the three crypto challenges this CTF were kinda different from the standard, they both gave very detailed descriptions of the challenge but used very odd/unknown systems. This challenge basically boiled down to “can you understand quantum cryptography?”

So let’s get into it. https://en.wikipedia.org/wiki/BB84

BB84 has the following steps:
1. Alice generates random 512 bit numbers a and b
2. Alice sends the qubits, with the ith qubit being the encoding of the ith bit of a under the basis determined by the ith bit of b
3. Bob recieves said qubits and measures each qubit under a random basis
4. Alice and Bob exchange the list of bases that they used
5. They discard any bits where they used different bases and take the remaining bits as the shared key
6. They can then do some other thing to account for possible mistakes/disruptions but that doesn’t apply here

Now lets compare that to the instructions given by the challenge, we see that the steps are kinda out of order. We send Bob (the satellite) the basis and the qubits at the same time and it responds with it’s basis and an “announcement”. If we computute the shared secret then we see that it’s not the same as the announcement but does have the same bit length.

Hmmmmm. The page is vague with it’s language and it’s description of the announcement, using the words “shared secret” and “key” and “encrypted secret” kinda randomly.

Let’s think about this from a meta perspective then. The qubits and the basis that we send the server are randomly generated, so the shared secret is random, but we know that the challenge is to find a hex key that decrypts the AES-CBC encrypted flag. Also we see that the announcement that we get back is different every time.

Hmmmmmmm. So we can guess that the “announcement” we get back is the key we want mixed together with the shared secret. We can generate the shared seceret ourselves since the satellite returns the basis it used, but how did they combine the key with the shared secret? We see that they’re the same bit length so why not try XOR?

Run it a few times and we see that the result of announcement XOR shared_secret is constant! We have our key!

CTF{you_performed_a_quantum_key_exchange_with_a_satellite}

Reversing Cellular Automata

The second of the two weird systems. This one is very straightforward though, “just” reverse a step in the cellular automata.

Here is the rule in question.

It generates the nth bit by looking at the left (n-1), center (n), and right (n+1) bits. And rule 126 was chosen because of how it generates that bit. If LCR are all 0’s or all 1’s then the nth bit is 0, otherwise it’s 1.

Naive attempt #1:
Well we can just make a list of lists, where the nth entry in the big list is a list of all possible triplets centered at the nth bit, then zip them all together. If the resulting bit is 0 then the possible triplets are 0,0,0 and 1,1,1 etc.

Run it and what happens? Python spits out a MemoryError…
Let’s just do a quick calculation to see how many elements are in that big list
3027636133969523175486328123886577647616
Oh…

Naive attempt #2:
Ok lets try incorporating the previous bit into the calculation. But then we run into a problem.

If the output bit was “1” and the last bit was “0”, that leaves us with three possible choices, the triplet could be 010, 001, or 011. We can try to keep track of all of these but we can only start excluding them once we finish a full loop around, and even so we have so many elements in the list that python chugs and itertools can’t make the combinations for us.

This approach doesn’t seem like a good idea, let’s try something else.

Less naive attempt #3:
Let’s look at the patterns generated from rule 126 https://www.wolframalpha.com/input/?i=rule+126+random+initial+conditions

Huh, we see lots of upsidedown triangles. If we consider the rule itself it makes sense. Groups of bits tend to “move” towards each other since something like 100 will result in 110 potentially. Also lines of 111111 become 1000001 which then begin to move towards each other, forming the upsidedown triangles we see.

So using what we know of the patterns can we look at the pattern from 66de3c1bf87fdfcf and backtrack? Assume that each sequence of 0’s was generated by a line ofe 1’s and seperated 1’s are part of an upsidedown triangle? The answer is no. It doesn’t work. The assumptions end up creating a pattern that isn’t even a valid previous state. So at this point I had been at it for a few hours so I went for a walk and immediately figured it out. It was so obvious.

Finally the successful attempt, attempt #4:

Brute force. We can just brute force previous states and keep the ones that step into the obtained step.

The key itself is 64 bits long, so brute force on the entire key is impossible. But cellular automata are not hashing functions. Normally a hash function cannot be realistically brute forced because a 1 bit change in the input results in a completely different hash.

But with the cellular automata a 1 bit change on one side of the input only affects a small local area, the 3 neighbouring bits that will use it in it’s calculation. This means we can split the key into 6 10ish bit long segments with some overlap, apply the automata to all the numbers between 0 and 2¹⁰-1 and keep track of all the states that match our desired segment, and then merge the patterns together. This takes time 6 * 2¹⁰ instead of 2⁶⁴!

One important part to consider is that when stepping this automata we need to not consider the outermost bits, because we don’t want to find solutions where the wrap around neighbours are impactful since the substrings are gonna be concatenated together later. Did that sentence make sense? Probably not. Try it for yourself and you’ll see what I mean.

So use python’s itertools to generate the list of all the combinations of the solutions we found for each segment, merge the segments together, and validate them by checking that the next state for them is 66de3c1bf87fdfcf.

Now we have a list of around 10,000 potential keys, which is actually reasonable. I wrote a short bash script and looped through until I found a key that didn’t result in a bad decrypt, however the encryption scheme doesn’t actually check the integrity of the entire message, it only checks that the padding is ok before deciding that the decrpytion worked, which just made things a bit more complicated, but eventually the script finds the flag!

CTF{reversing_cellular_automatas_can_be_done_bit_by_bit}

PS: Guessing from the flag I don’t think I did this challenge in the intended way, but whatever! Flag is flag!

Reality

A more classic kind of CTF crypto problem, just a confusing hint and a port to netcat to. Let’s break down the information we have.

Connecting to the port gives us:
1. An encrypted flag
2. Three “coefficients” that are pairs of real numbers with 500 decimal places of precision, the first is small and the second is around 10⁴⁰
3. A message: “You need 5 coefficients to decrypt the flag, here’s 3”

Huh, weird. Let’s look closely at the challenge, the name is “reality” and the description mentions someone called “Shamir”. Who is Shamir? This of course refers to Adi Shamir one of the creators of RSA (He’s the S in RSA). But we have a bunch of real numbers, while RSA uses exclusively integer rings. Hm, let’s keep looking.

Googling his name we find something called Shamir’s Secret Sharing, which is a secret sharing scheme where everyone is given a coefficient and n-people need to be present to generate the secret. This works by using the fact that you need k points to uniquely define a k-1th order polynomial (if you’re not sure why this is true, consider taking k derivatives of a k-1th order polynomial and trying to work backwards using integration), and if you have less than k points you have an infinite number of possible k-1th order polynomials that cross those points.

So seems to be the challenge, we have 3 coefficients, now we just need the last two. But how? We have literally an infinite number of possible polynomials that could all be the secret.

As usual with these CTF problems one must look and see what is different from the usual, and use that to guide the way. The obvious weird thing is the massive amount of precision with the numbers that we are given and the title “Reality”. Hmm, reality, real numbers? Maybe the precision is somehow making the secret sharing system insecure? The system usually works by giving each member a pair of an integer n and the coefficient for xⁿ so the system we have here is definitely different.

I didn’t have a clue where to go from there, but resident genius Robert Xiao had an idea immediately. Can we make this into a lattice problem? More specifically a closest vector problem where the solution is the desired coefficients? This might work because the massive amount of decimal precision!

The problem we’re interested for this challenge is called the closest vector problem (CVP). It boils down to this: Given a matrix A and a vector v, what vector x, with the constraint that x is made up of integers, results in the Ax that is closest to v and what is that “closest vector” vector Ax?

We want our closest vector problem to solve for the integer coefficients that make up the polynomial. Here’s our equations, we know that it’s in this form because the challenge said we needed 5 coefficients to decode the flag.

\begin{equation} y_1 = c_0 + c_1 x_1 + c_2 x_1^2 + c_3 x_1^3 + c_4 x_1^4 \\ y_2 = c_0 + c_1 x_2 + c_2 x_2^2 + c_3 x_2^3 + c_4 x_2^4 \\ y_3 = c_0 + c_1 x_3 + c_2 x_3^2 + c_3 x_3^3 + c_4 x_3^4 \\ \end{equation}

Now into a matrix,

\begin{equation} A=
\begin{bmatrix} 1 & x_1 & x_1^2 & x_1^3 & x_1^4 \\
1 & x_2 & x_2^2 & x_2^3 & x_2^4 \\ 1 & x_3 & x_3^2 & x_3^3 & x_3^4 \\ 1 & 0 & 0 & 0 & 0 \\ \end{bmatrix} \end{equation}

The goal vector,

\begin{equation} v=
\begin{bmatrix} y_1 \\
y_2 \\ y_3 \\ c_0 \\ \end{bmatrix} \end{equation}

Remember CVP finds integer valued x such that \(Ax=v\). So given this we expect that the CVP will find \begin{equation} x=
\begin{bmatrix} c_0 \\
c_1 \\ c_2 \\ c_3 \\ c_4 \\ \end{bmatrix} \end{equation}

and return us a vector that is close to (and hopefully close enough so that c0 will be valid)
\begin{equation} res=
\begin{bmatrix} y_1 \\
y_2 \\ y_3 \\ c_0 \\ \end{bmatrix} \end{equation} which we can extract the secret, c0, out from.

The problem is that we don’t know what c0 is, so we can’t give use the goal vector as written. The solution I ended up using was to guess and make it insignificant, ie multiply everything in the matrix and the y’s by a large scaling factor so that the algorithm “doesn’t care as much” about the difference between our guessed c0 and what we want it to return, the actual c0.

Another solution could be to invert the matrix and multiply in the [y1,y2,y3] vector but I only just thought of that.

So that’s the general idea, I ended up adding a few more rows onto the matrix to get the CVP function from fpyll to work, but eventually I got there.

So now we have a massive int, c0. How to decrypt the flag? This was basically just trial and error, I eventually noticed that it was about right to be converted into 16 bytes, which is the key length that is required for the encryption scheme that they used in the earlier challenges (AES-CBC).

And it worked! AES-CBC with the key being c0 and IV being just b’’s resulted in our flag!

CTF{h0w-r3al-is-y0ur-Re4l-4Real}