TCTF/0CTF 2022 Crypto real_magic_dlog

Posted on Edited on In ,

Problem description

Based on HITCON 2021 "magic dlog". According to its author @lyc, the intended solution is "Finding Smooth Integers in Short Intervals Using CRT Decoding".

proof of work

1
2
3
4
5
6
7
8
9
10
11
def proof_of_work(self):
    random.seed(urandom(8))
    proof = ''.join([random.choice(string.ascii_letters + string.digits + '!#$%&*-?') for _ in range(20)])
    digest = sha256(proof.encode()).hexdigest()
    self.dosend('sha256(XXXX + {}) == {}'.format(proof[4: ], digest))
    self.dosend('Give me XXXX:')
    x = self.request.recv(10)
    x = (x.strip()).decode('utf-8') 
    if len(x) != 4 or sha256((x + proof[4: ]).encode()).hexdigest() != digest: 
        return False
    return True

dlog

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def handle(self):
    try:
        signal.signal(signal.SIGALRM, self.timeout_handler)
        signal.alarm(50)
        if not self.proof_of_work():
            self.dosend('You must pass the PoW!')
            return
        signal.alarm(60)
        magic = urandom(LEN)
        magic_num = bytes_to_long(magic)
        self.dosend(magic.hex())
        self.dosend('P:>')
        P = int(self.request.recv(100).strip(), 16)
        self.dosend('E:>')
        E = int(self.request.recv(100).strip(), 16)
        self.dosend('data:>')
        data = self.request.recv(100).strip()
        num1 = int(data, 16)
        if P >> (384 - LEN * 8) == magic_num and isPrime(P):
            data2 = sha384(data).hexdigest()
            num2 = int(data2, 16)
            if pow(num1, E, P) == num2 % P:
                self.dosend(flag)
            else:
                self.dosend('try harder!!!')
    except TimeoutError:
        self.dosend('Timeout!')
        self.request.close()
    except:
        self.dosend('Wtf?')
        self.request.close()

Solution

proof of work

The proof of work part requires us to break the first 4 chars of a random 8 bytes string. We are given the condition where the SHA-256 of the string is shown.

For example, we are shown something like:

sha256(XXXX + n56#&U856iv#8vI3) == fb3d8b097f094662b84c90fd6faca83a385a075dc2e25f477b379da7408dac19 Give me XXXX:

We can just iterate all the possible combinations since the complexity isn't too large. It's just a PoW anyway.

The interactive code is below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from hashlib import sha256
import socket
from string import digits, ascii_letters
import itertools

# connection
def dosend(sock, msg):
    try:
        sock.sendall(msg.encode('latin-1'))
    except:
        pass
HOST = "202.120.7.219"
PORT = 15555
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
c = s.connect((HOST, PORT))
s.sendall(b"")
resp = s.recv(1024).decode().strip()
digest_compare = resp[35:]
proof_rest = resp[14:30]

# breaking SHA-256 first 4 places
alpha_bet = digits+ascii_letters+"!#$%&*-?"
strlist = itertools.product(alpha_bet, repeat=4)
xxxx = ''
for i in strlist:
    data = i[0] + i[1] + i[2] + i[3]
    data_sha = sha256((data + proof_rest).encode('utf-8')).hexdigest()
    if (data_sha == digest_compare):
        xxxx = data
        break

# send pow
resp = s.recv(1024).decode().strip()
s.sendall(xxxx.encode())

dlog

The expected solution should be from this paper: Finding Smooth Integers in Short Intervals Using CRT Decoding Although, in the description, the challenge mentions that this problem is developed from HITCON 2021 "magic dlog". I searched on the internet and found a solution for HITCON 2021 version. By slightly adjusting the code, the solution can be applied to this challenge.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from Crypto.Util.number import *
from hashlib import *
from gmpy2 import  is_prime
from sage.all import *

LEN = 17
magic_num = int(resp, 16)

for i in range(65536):
    n = magic_num * 2 ** (384 - LEN*8) + i * 2 ** (384 - LEN*8 - 16)
    if is_prime(n + 1):
        f = factor(n)
        if all(p < 2 ** 40 for p, e in f):
            num1 = primitive_root(n+1)
            data = int(num1).to_bytes(2, 'big').hex().encode('latin-1').strip()
            data2 = sha384(data).hexdigest()
            num2 = int(data2, 16)
            e = discrete_log(Zmod(n+1)(num2), Zmod(n+1)(num1))
            if (n+1) >> (384 - LEN * 8) == magic_num and isPrime(n+1): #only for check
                if pow(num1, e, n+1) == num2 % (n + 1): #only for check
                
                    resp = s.recv(1024).decode().strip()
                    print(resp) # P: 
                    s.sendall(hex(n+1).encode('latin-1')) # send P

                    resp = s.recv(1024).decode().strip()
                    print(resp) # e: 
                    s.sendall(hex(e).encode('latin-1')) # send e

                    resp = s.recv(65536).decode().strip()
                    print(resp) # data: 
                    s.sendall(data) # send data

                    resp = s.recv(1024).decode().strip()
                    print(resp) # msg

                    break

We still want to look at how this works.

The challenge first generates a random 17 bytes (136 bits) and converts it to long integer as a magic_num \(m\). We are given the hex of this number and expected to find a proper set of \(\{P,\; E,\; {\rm data}\}\) such that: \[ \begin{aligned} \lfloor {P \over {2^{248}}} \rfloor = m\; ;\\ P \; {\rm is \; prime.} \end{aligned} \] It also means that the first 136 bits of \(P\) should be exactly equal to bits in \(m\). Since \(P\) is prime, \(P-1\) can be \(m \cdot 2^{248} + i\), where \(i \in [2^{247}, 2^{248})\) is an even number.

Here, I learned a trick from the solution. We can actually only iterate the highest 16 bits after 136 bits and let all the rest be 0's. It will make the factorization of \(P-1\) way easier and faster.

Also, there's another condition on this set. Let data2 be hexdigest of sha384 of the input data. num1 and num2 are integer converted from data and data2. The other constraints on \(\{P,\; E,\; {\rm data}\}\) are: \[ \begin{aligned} n_{1}^{E} &\equiv n_{2} \mod P \\ n_{1} &= {\rm int(data, 16)}\\ n_{2} &= {\rm int(sha384(data), 16)} \end{aligned} \] It can be clearly seen that this is a Discrete Logarithm (DL) problem. The core method for this kind of problem is to find a enough smooth \(P\) so that \(E\) can be easily/quickly obtained by calling discrete_log from SageMath (I'll write a sum-up later for these maths/cryptanalysis tools). The smoothness can be restricted by conditioning all factors of rank of \(P\) (which is \(P-1\) since \(P\) is prime) to be no greater than 40 (or 50 if it doens't work).

The detailed explaination can be found here (in Chinese). This kind of algorithm is called Pohlig-hellman. The conditions of applying Pohlig-hellman to find DLP solution in limited time is:

\[g^{x} \equiv a \mod P,\; {\rm g\;is\;the\;primitive\;root\;of\;P.}\] Thus, we can set \(n_{1}\) to be the primitive root of \(P\).

Reference

Hitcon2021 Crypto Writeup 离散对数 Finding Smooth Integers in Short Intervals Using CRT Decoding