9 minutes
My Solution to Curta Puzzle 8 Groovy Fruit (Punch) Fiesta
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 fruitthemed 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, apple
and banana
must be coprime, and hence milkshake
is a modular multiplicative inverse function.
We know punch
is prime because it has no factors. This can be checked with sagemath.


apple
and 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 s
from 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 punch
, hence 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 apple
and 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 y
s, 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.
This was quite the torture. Thank you, cts🌸 and Curta.
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.