Account Leak

Uncrackable password? I thought this was a CTF; get me my friends minecraft password pls <3

nc tjc.tf 31601

Here’s the Python source:

1
#!/usr/local/bin/python3.10 -u
2

3
import time
4
from Crypto.Util.number import getPrime, getRandomInteger, getRandomNBitInteger
5

6
flag = open("flag.txt").read().strip()
7
p = getPrime(512)
8
q = getPrime(512)
9

10
sub = getRandomInteger(20)
11

12
# hehe u cant guess it since its random :P
13
my_password = getRandomNBitInteger(256)
14

15
n = p*q
16
c = pow(my_password, 65537, n)
17
dont_leak_this = (p-sub)*(q-sub)
18

19

20
def gamechat():
21
    print("<Bobby> i have an uncrackable password maybe")
22
    print(f"<Bobby> i'll give you the powerful numbers, {c} and {n}")
23
    print("<Bobby> gl hacking into my account")
24
    print("<Bobby> btw do you want to get my diamond stash")
25
    resp = input("<You> ")
26
    if (resp.strip() == "yea"):
27
        print("<Bobby> i'll send coords")
28
        print(f"<Bobby> {dont_leak_this}")
29
        print("<Bobby> oop wasnt supposed to copypaste that")
30
        print("<Bobby> you cant crack my account tho >:)")
31
        tic = time.time()
32
        resp = input("<You> ")
33
        toc = time.time()
34
        if (toc-tic >= 2.5):
35
            print("<Bobby> you know I can reset my password faster than that lol")
36
        elif (resp.strip() != str(my_password)):
37
            print("<Bobby> lol nice try won't give password that easily")
38
        else:
39
            print("<Bobby> NANI?? Impossible?!?")
40
            print("<Bobby> I might as wel give you the flag")
41
            print(f"<Bobby> {flag}")
42
    else:
43
        print("<Bobby> bro what, who denies free diamonds?")
44
    print("Bobby has left the game")
45

46

47
gamechat()

Seems like another RSA challenge. We’re provided a leak equivalent to (p-sub)(q-sub), where sub is a random 20-bit integer. Well, we can actually do a bit of math to turn this leak into knowledge of phi(n), i.e. Euler’s totient, which will allow us to decrypt the password ciphertext and get the flag:

$leak = n - sub*(p + q - sub)$

$n - leak = sub*(p + q - sub)$

$(n - leak)//sub = p + q - sub$

$p + q = (n - leak)//sub + sub$

$phi = (p-1)(q-1) = pq - (p + q) + 1 = n - (p + q) + 1$

Now, in order to get sub, we can just brute-force it, knowing that it is a factor of $n - leak$

1
from pwn import *
2
from sympy.ntheory import factorint
3
from Crypto.Util.number import *
4

5
r = remote('tjc.tf', 31601)
6
r.recvuntil(b', ')
7
res = r.recvline().decode("ascii").split(' ')
8
c = int(res[0])
9
n = int(res[-1])
10
r.sendlineafter(b'<You> ', b'yea')
11
r.recvline()
12
leak = int(r.recvline().decode('ascii')[:-1].split()[-1])
13

14
sub = -1
15
for i in range(1<<19, 1<<20): # 50% chance for it to be 20 bits long
16
    if (n - leak) % i == 0:
17
        print(i)
18
        sub = i
19
        break
20

21
assert sub.bit_length() == 20
22

23
p_plus_q = (n - leak)//sub + sub
24
phi = n - p_plus_q + 1
25
d = inverse(65537, phi)
26
pt = pow(c, d, n)
27
r.sendlineafter(b'<You> ', str(pt).encode())
28
r.interactive()

1
tjctf{h3y_wh3r3_d1d_my_d1am0nds_g0_th3y_w3r3_ju5t_h3r3}