The latest Curta CTF puzzle was a tough one, with less people solving than the other puzzles. I had the pleasure of being one of the solvers.
Curta puzzles require players to generate a
_start value by plugging their addresses into the provided
generate function, then find a unique
_solution that only works for their address. Here is the complete puzzle:
Who doesn’t like a fruit punch? It seems like a delicious challenge. You blend the fruits and make a smoothie or a milkshake out of them xD
I spent some time trying to understand the operations; however, it appeared to be difficult to wrap my head around. First of all, the
blender function is a recursive loop. And it seems to change the order of arguments at each call. Then, at the end of the function, there is another operation that makes some juice?? Well, it took more than a bit to understand what the operations do. But understanding them did not help; it only confused me more.
Only after paying more attention to the purpose of the
punch variable did the curtain lift from my eyes.
punch is solely used in taking the modulus of other variables. So it was clear we are concerned with modular arithmetics here. I opened my Moonmath Manual. Well, now it became clear. The
blender function is just an extended Euclidean algorithm. I had actually written an implementation of it in Solidity, but mine was an unoptimized version solely written for learning purposes. That and the fruit-themed naming combined caused me to take ashamedly too much time to realize the truth.
So, what is the extended Euclidean algorithm? It takes two integers (x, y) and returns their greatest common denominator (gcd) and two other variables (s and t), that satisfy
gcd(x, y) = s * x + t * y.
Other things I noticed are that
punch is a prime number modulus,
banana must be coprime, and hence
milkshake is a modular multiplicative inverse function.
punch is prime because it has no factors. This can be checked with sagemath.
banana must be coprimes because they have to be “
yummy”, meaning their gcd has to be 1.
milkshake returns a multiplicative inverse because it performs the following operation.
In this operation, the second argument returned is
gcd(x, y) = s * x + t * y. When we take the modulus
y on both sides,
t * y vanishes. If the reasoning here is not clear, you should read about the computational rules of modular arithmetics. Since we know
y here, is prime, x and y are coprime, and
gcd(x,y) is 1. So
1 %% y == 1. And
s * x + t * y %% y == s * x. Given these
1 == s * x. Hence,
s is the multiplicative inverse of
x in mod punch arithmetic.
Now it appears that we have all we need to solve this (or do we???).
So this operation is performed in mod punch, and we know
milkshake(x) returns the modular inverse of
x in mod punch.
_start is our constant,
cherry is just
1, and we want to solve for
banana. I will rewrite this in simple math so we can forget about all that fruit stuff:
All the above insight was to necessary to make the following change to the above congruence:
This is actually almost the solution. However, I made the mistake of consulting to GPT4, which adamantly insisted that the equation cannot be simplified and I must resort to brute forcing. Unfortunately, brute forcing is not possible in mod 906459278810089239293436146013992401709! This is strangely the place I got stuck the longest. I have spent many hours reading about elliptic curves, trying to actually understand what this is and how to solve it.
I was not going to give up. I knew I could not trust a dumb GPT bot, so I finally took the pen and paper and expanded the equation as much as I can. Then I tried it with a known value of
y. I realized there has to be a solution for
x for most
ys, because some of the solutions submitted so far had used very low
y values. So with the assumption that I can use any
y and that I should solve for
x, I worked to bring the congruence to a more useful state.
Now this looks solveable. It has to be, we just have one unknown. Finally I realized sage math can solve this congruence. I was relieved. Also I did not need to expand the equation that much, as sagemath could handle that too (yes I made GPT4 write the sage script after I begged it to forgive me for the insults).
Here, I knew that most solutions will cause revert in the contract. I believe it was due to
require(appleJuice_ > 0); check. So the contract would not accept all the solutions generated by above, but that’s fine. I just got few hundred solutions, and assumed the contract would accept at least one. I used the following helper script to get list of possible solutions.
Once I had the possible solutions, I copied them to my foundry test file as an array, and ran the test until a solution was accepted.
Addendum: The intended solution
After Phase 1 was over, cts posted the intended solution on Discord.
From this, we can see that we can define an elliptic curve from a cubic equation. Then pick any point on this point and the inverse of it leads to the solution after filtering possible solutions based on the constraints.
It is fun to see how elegant the intended solution is against the hacky job I did.