writeups/2021/corctf/dividing_secrets

dividing_secrets

by haskal

crypto / 434 pts / 121 solves

I won't give you the secret. But, I'll let you divide it.

nc crypto.be.ax 6000

provided files: server.py

solution

inspecting the server script... it seems to be using a 512 bit prime p and taking a random number g to the power of the secret flag message x mod p. in order to crack this you'd need to come up with an efficient solution for the Discrete Log Problem

luckily, the server also lets you divide the exponent by an arbitrary input number up to 64 times (that's 512/8 for those who are paying attention, which suggests taking a character-by-character approach). the exploit concept is to use the division to shift x all the way to 8 bits, then try to guess what those 8 bits are by trying all 256 possible values. then, once that is known, move on to the next 8 bits using the known segment and combining it with another round of 256 guesses

it looks kinda like this

# start by doing x >> 504
# (this is the same as x / (2**504))
position = 504
top_bits = 0

while True:
    # send off the next guess
    r.recvuntil("number> ")
    r.sendline(str(2**position))
    h = int(r.recvline().decode())
    # guess every possible character
    for i in range(256):
        if pow(g, (top_bits << 8) | i, p) == h:
            # once it is found, move on
            sys.stdout.write(chr(i))
            top_bits = (top_bits << 8) | i
            position -= 8
            break

running the exploit.py script should produce

[+] Opening connection to crypto.be.ax on port 6000: Done
g 3163314640353309966974084350140065528835797402483351605270276213160985733919488025191658477221550585332241782718778635951464919000972247044376608291073497
p 9937890065686116796205186685937536971919686769106263396090623316690565375989826956720662974087853527508968612312091794142094431426690835778526649323968253
enc 5829222177042077791091257368279368382423357539393247444397252396260207162571334610710294330374985463989052071335431112395334343144642068220012344459731980
corctf{qu4drat1c_r3s1due_0r_n0t_1s_7h3_qu3st1on8852042051e57492}[*] Closed connection to crypto.be.ax port 6000
Traceback (most recent call last):
.....
...
  File "/usr/lib/python3.9/site-packages/pwnlib/tubes/sock.py", line 58, in recv_raw
    raise EOFError
EOFError