[ASIS CTF Quals 2023] Renamiara, Refactor

13th place with team CyberSpace lol!!

Renamiara

chall

#!/usr/bin/env python3

from Crypto.Util.number import *
import sys
from flag import flag

def die(*args):
	pr(*args)
	quit()

def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()

def sc():
	return sys.stdin.buffer.readline()

def main():
	border = "|"
	pr(border*72)
	pr(border, " Greetings and welcome to the Renamiara cryptography challenge! The ", border)
	pr(border, " objective of this mission is to tackle an exceptionally difficult  ", border)
	pr(border, " and unique discrete logarithm problem in the real world. Are you   ", border)
	pr(border, " prepared and willing to take on this challenge? [Y]es or [N]o?     ", border)
	pr(border*72)


	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]
			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!!')

if __name__ == '__main__':
	main()

주어진 소수$p$에 대하여 $g, x, y$ 를 주어진 범위를 만족하도록 적절하게 설정해서
$g^{x+y} ≡ xy \ (mod \ p)$ 가 되도록 하면 되는 간단한 문제이다.

exploit code

from pwn import *

r = remote("45.153.241.194", 31337)

for _ in range(6):
    r.recvline()

r.sendline(b"Y")

for _ in range(40):
    r.recvline()
    r.recv(5)
    p = int(r.recvline().strip())

    x = 2
    y = p-2
    g = p-4

    r.recvline()
    r.sendline(str(g).encode())
    r.recvline()
    r.sendline(str(x).encode() + b"," + str(y).encode())
r.interactive()

ASIS{_An07H3r_F1XeD_PoInt5_f0r_DLP!!}

Refactor

chall

#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

def pgen(nbit):
	x, y = 0, 1
	while True:
		u, v = getRandomRange(1, 110), getRandomRange(1, 313)
		x, y = u * x + 31337 * v * y, v * x - u * y
		if x.bit_length() <= nbit // 2 and x.bit_length() <= nbit // 2:
			p = x**2 + 31337 * y**2 | 1
			if isPrime(p) and p.bit_length() >= nbit:
				return p
		else:
			x, y = 0, 1

def encrypt(msg, pkey):
	e, n = pkey
	m = bytes_to_long(msg)
	c = pow(m, e, n)
	return c

p, q = [pgen(1024) for _ in '__']
pkey = (31337, p * q)

c = encrypt(flag, pkey)

print(f'n = {p * q}')
print(f'c = {c}')

주목해야할 부분은 $x', \ y' = u x + 31337 v y, \ v x - u y$ 이다. 식을 조금 쓰다보면

임을 알 수 있다. 따라서 $p$는 (합성수) | 1 형태이므로 1이 무조건 더해짐을 알 수 있다. 여기서 취약점이 발생한다.

가 되고, $q-1$도 마찬가지이다. 따라서

꼴이 된다. 여기서 가능한 $f(u_i, v_k)$ 의 수가 적으므로, 이들을 모두 곱하면 $k * phi(n)$ 을 얻을 수 있다. (여기까지 해놓고, 인수분해를 못해서 팀원의 도움을 받았다 ;;)
https://gist.github.com/ddddavidee/b34c2b67757a54ce75cb 을 참조하여 인수분해를 한 뒤, $flag$는 $p$보다 작으니 $c$의 $p$에 대한 nth_root 중에 하나가 $flag$가 될 것이다.

exploit code (sage)

from Crypto.Util.number import *

n = 15354257069173285781905276045639014609593379926482050489113547339117588412057832262093892509606681500550900795674355198875730897090963848584014735402479257641196755288572505568604616504895577156519599359709585689487167929035277328860394887100644352498762646576634768748203691626550604902474991908656069443025123380468043304218262437495617397923826383876725820263637369772201236276175774820781740263113457945850397866995318921153304724846886489062447149970082086628646772837892015556355384776002878980523779509899708723447721484662031731419684247739500573264103203416815345858413217500504527510275599764791910780108801
c = 11319719392368830772976523857976369154729855326260479489071566552409492905894844561614086707874832191432242950123964961582894044688274348653418226595519872495639236324552876924940961325755770656445013054487327399663358245181836741250528901918846037855858412978924591011941242779828600098063462814300900861180897010043498668688944295535981632815932395145673684660722012731208682402231321184600968865557231738026003707732466182970622224802483189066444000715061144732475930157185474148162121034705457395021374353689284243509307079898846581316271587575615363632603786729853488699442091342820074301120194843407072588515822
e = 31337

kphi = 1
for i in range(1, 110):
    for j in range(1, 313):
        kphi *= (i**2 + 31337*j**2)

kphi *= (e**2)
#p, q = RecoverPrimeFactors(n, e, kphi)
p = 105715818457627742408000131791581803263118020835149667693668608571225154488542137271980297710919424371195402388949605652963443885828295675739336380180535922174255090993167178687171710340954123691292788509909056718088095296632705467715389346937487380451649168395395364160870163074624211881977798989971456000001
q = 145240866439751106761526504646813835228951225415298127295768132296855432307480970631514914164555160238156330813406764237749011856096707865906390209767144608883077674672614160939250714495850533446106123780228787492172102563126918589380263861525132111853963871071073064030554599628460085909232957963526524108801

for i in GF(p)(c).nth_root(e, all = True):
       if b"ASIS" in long_to_bytes(int(i)):
              print(long_to_bytes(int(i)).decode())

ASIS{P0lL4rd5_p-1_Al9oR!7Hm_gg!!}

Refactor은 과정은 간단해 보이지만, 삽질을 생략해서 그렇다. 나름 재밌는 문제였던 것 같다..