[ASIS CTF Quals 2023] Renamiara, Refactor

hakid29·2023년 9월 23일
0
post-thumbnail

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()

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

(x,y,g)=(2,p2,p4)(x, y, g) = (2, p-2, p-4)
gx+ygpgp4 (mod p)g^{x+y} ≡ g^p ≡ g ≡ p-4 \ (mod \ p)
xy2(p2)p4 (mod p)xy ≡ 2(p-2) ≡ p-4 \ (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=ux+31337vy, vxuyx', \ y' = u x + 31337 v y, \ v x - u y 이다. 식을 조금 쓰다보면

f(x,y)=x2+31337y2f(x, y) = x^2 + 31337y^2
f(x,y)=f(x,y)f(u,v)f(x', y') = f(x, y)f(u, v)

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

p1=f(x,y)=f(x1,y1)f(u1,v1)=f(x2,y2)f(u1,v1)f(u2,v2)p-1 = f(x, y) = f(x_1, y_1)f(u_1, v_1) = f(x_2, y_2)f(u_1, v_1)f(u_2, v_2)
=....=f(0,1)f(u1,v1)f(u2,v2)....f(uk,vk)=....=f(0, 1)f(u_1, v_1)f(u_2, v_2)....f(u_k, v_k)

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

phi(n)=(p1)(q1)=313372f(u1,v1) ... f(uk,vk)phi(n) = (p-1)(q-1) = 31337^2f(u_1, v_1) \ ... \ f(u_k, v_k)

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

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은 과정은 간단해 보이지만, 삽질을 생략해서 그렇다. 나름 재밌는 문제였던 것 같다..

0개의 댓글