ASIS CTF Quals 2023 - renamiara

Recently, I have participated in Asis CTF Quals 2023. Although I can only solve one challenge, which is renamiara, through this challenge I have learned a little more about math and gained a little experience about the way that I should approach a problem. Because this is the most recent flag of mine, I want to share the solution and all my thinking process. This will be a super fast write-up and I hope you like it.

Renamiara

This is the link to the challenge renamiara.py

First, the server will give us a banner with "greetings and welcome" to the challenge and tell us that this is a real-world's discrete log problem (I don't think so :P)

If we enter "y" then the fun begin. If we enter "n" then …

ans = sc().decode().strip().lower()
if ans == 'y':
    NBIT = 32
    STEP = 40

    pr(border, "In each step solve the given equation and send the solution for x, y", border)
    c = 1
    while c <= STEP:
        nbit = NBIT * c
        p = getPrime(nbit)
        pr(border, f'p = {p}')
        pr(border, 'First send the base g: ')
        g = sc().strip().decode()
        pr(border, 'Send the solutions for pow(g, x + y, p) = x * y, as x and y:')
        xy = sc().strip().decode().split(',')
        try:
            g, x, y = [int(_) for _ in [g] + xy]
            print(g,x,y)
        except:
            die(border, 'Given number is not correct! Bye!!')
        if (x >= p-1 or x <= 1) or (y >= p-1 or y <= 1) or x == y:
            die(border, "Kidding me!? Your solutions must be smaller than p-1 and x ≠ y :(")
        if g <= 2**24 or g >= p-1:
            die(border, "Kidding me!? Please send the correct base :P")
        if pow(g, x + y, p) ==  x * y % p:
            if c == STEP:
                die(border, f"Congratulation! the flag is: {flag}")
            else:
                pr(border, "Good job, try to solve the next level!")
                c += 1
        else:
            die(border, "Try harder and be smarter to find the solution!!")
elif ans == 'n':
    pr(border, 'Bye!!')
else:
    pr(border, 'Please send a valid answer! Bye!!')

From the code of the challenge, we can see that this challenge will contain 40 sub-problems with the variable c being raised by 1 each time we complete 1 level (in this case, the prime p = getPrime(32*c) will be bigger). If we got to level 40, we could have the flag. So our way to solve all the sub-problems will be harder and harder, right? We will know later.

The server gave us

$p$, and our job is to find

$g,x,y$ to make the equation below valid.

$$g^{x+y}\mathrm{\%}p=xy\mathrm{\%}p$$

We can only input

$x,y$ for

$x\in range(1,p-1)$,

$y\in range(1,p-1)$ and

$x\ne y$

if (x >= p-1 or x <= 1) or (y >= p-1 or y <= 1) or x == y:
    die(border, "Kidding me!? Your solutions must be smaller than p-1 and x ≠ y :(")

Also, we can only input

$g$ for

$g\in range(2^{24},p-1)$

if g <= 2**24 or g >= p-1:
    die(border, "Kidding me!? Please send the correct base :P")

So from here, I have come up with many weird solutions, like brute forcing the pair

$(x,y)$ such that

$x\in range(1,p-1)$ and

$y=p-x$ that satisfies the equation at level 1 to see if there is any relation between

$x,y$ and

$g$ (I choose

$g=2^{24}+1$), but it takes longer than I thought, so I changed my approach.

Another approach of mine is to solve the equation with my crypto-challenge legendary ultimate tool, CASIO fx-580VN X the calculator (You didn't read wrong :P They work like magic sometimes) with small

$g$ (like

$g=2$) for computation test for random

$x$ to have

$y$, but I know this just for testing and then move on to the next idea.

After some thought, from the equation above, I have:

$$g^{x+y}\mathrm{\%}p=xy\mathrm{\%}p<=>\frac{g^{x+y}}{x\ast y}\equiv 1(modp)$$

From Fermat little theorem we have:

$$g^{p-1}\equiv 1(modp)withpisprime$$
Linked those two together, I have to make

$$\frac{g^{x+y}}{x\ast y}=g^{p-1}$$
To do that, first I came up with another weird solution is to find a pair

$(x,y)$ to make

$x+y=p-1$ and

$inverse(x+y,p)=1$, another brute force solution . But I remember that I can change the variable

$g$, so this leads me to my final solution for this challenge.

So my solution is to make

$x+y=p$ and

$(x\ast y)\mathrm{\%}p=g$. Hence,

$$\frac{g^{x+y}}{x\ast y}=\frac{g^p}{g}=g^{p-1}$$
We will pick a random

$x$ (I choose constant

$x=2^{24}$) and

$y=p-x$, and formed

$g=(x\ast y)\mathrm{\%}p$. Below is my code to solve this challenge first attempt:

from Crypto.Util.number import inverse
from pwn import *

io = remote('45.153.241.194', 31337)
# receive the greetings
for i in range(6):  
    print(io.recvline())
# yes
io.sendline(b'y')

# make the same attack for 40 levels
for i in range(40):
    # receive instruction msg or "next level" msg
    print(io.recvline())
    # receive p
    p = io.recvline()
    p = int(p.decode()[5:],10)
    print(io.recvline())
    print(p)
    x = 2**24 
    y = p-x
    g =pow(x*y,1,p)
    # send g
    io.sendline(str(g).encode())
    print(io.recvline())
    # send x,y
    io.sendline((str(x)+","+str(y)).encode())

io.interactive()

By the time I ran this code, it was working well for all my attempts to get the flag. But I remember that

$g$ have to be in

$range(2^{24},p-1)$, so maybe add another while loop to find random

$x$ make pair

$(x,p-x)$ that

$(x\ast (p-x))\mathrm{\%}p\in range(2^{24},p-1)$ if

$g\notin range(2^{24},p-1)$ to make sure

$g$ is valid before send

$g,x,y$ to the server.

Conclusion

To sum up, this challenge was the easiest in the crypto category. I have learned that I should not approach a challenge with a brute-force solution instead of examining the math behind it first, and I shouldn't forget any detail that could lead me to the solution (I don't remember the

$g$ at the time; only focus on

$x$ and

$y$). But this challenge didn't take me long to solve, and I'm really glad that I could solve it

I'm still really naive about crypto challenges, so my explanation could be unprecised. Other unsolved challenges still remain unsolved for me. I'm really curious about others' challenge solutions, but I will come back to it later if I can find a way to solve it. And finally, I hope that you will enjoy reading this little Sonic write-up of mine. Thanks you for reading, and have an A1 day!

#KienSD