[CONFidence CTF 2019 Teaser] Bro, do you even lift? writeup

문제

---

분석

두 개의 파일이 주어진다.

lift.sage는 syntax가 python 비슷..한것이 뭔가 알고리즘을 하나 정의하고 있는 듯 보이고

out.txt는 그 알고리즘이 실행된 후의 출력값처럼 보인다.

flag = int(open('flag.txt','r').read().encode("hex"),16)
ranges = int(log(flag,2))
p = next_prime(ZZ.random_element(2^15, 2^16))
k = 100
N = p^k
d = 5
P. = PolynomialRing(Zmod(N), implementation='NTL')
pol = 0
for c in range(d):
    pol += ZZ.random_element(2^ranges, 2^(ranges+1))*x^c
remainder = pol(flag)
pol = pol - remainder
assert pol(flag) == 0

print(p)
print(pol)

35671
12172655049735206766902704703038559858384636896299329359049381021748*x^4 +
11349632906292428218038992315252727065628405382223597973250830870345*x^3 +
9188725924715231519926481580171897766710554662167067944757835186451*x^2 +
8640134917502441100824547249422817926745071806483482930174015978801*x +
170423096151399242531943631075016082117474571389010646663163733960337669863762406085472678450206495375341400002076986312777537466715254543510453341546006440265217992449199424909061809647640636052570307868161063402607743165324091856116789213643943407874991700761651741114881108492638404942954408505222152223605412516092742190317989684590782541294253512675164049148557663016927886803673382663921583479090048005883115303905133335418178354255826423404513286728

코드실행 결과, 수(p)와 다항식 하나 ( f(x) )가 출력되었다.

코드 분석을 해봤을때 f(flag) = 0 mod p^n 으로 생각된다.

cf) 반복문으로 pol (polynomial)을 형성하는 부분을 봤을때,

flag와 같은 비트의 수가 계수로 사용됨을 알 수 있다.

이 때, $x^4$, $x^3$, $x^2$, $x$의 계수 네 개는 모두 223 bit이다.

따라서, 우리가 찾고자 하는 flag도 223-bit number라는 것을 알 수 있다.

---

EXPLOIT

이때, 수학적으로 $f(x) \equiv 0\,mod\,p^n$이고 p가 prime number이면

$f(x) \equiv 0 \,mod\, p$ 임은 자명하다.

연속적으로, $f(x) \equiv 0 \,mod \,p^2$ , $f(x) \equiv 0 \,mod \,p^3$ ...등등도 항상 성립한다.

따라서 우리는 flag값을 순차적으로 찾아낼 수가 있다.

---

FL4G

$f(t_0) \equiv 0\, mod\, p$ 인 $t_0$를 찾아내면,

$flag \equiv t_0\, mod \,p$

즉, $ flag = Xp + t_0 $

그 다음으로,

$ f(t_1 p + t_0) \equiv 0\,mod\,p^2$ 인 $t_1$을 찾아낸다.

같은 방법으로 $t_2$, $t_3$, $t_4$, ... 를 찾아내어 

$mod p^n$ 상에서의 최종 flag 값을 찾아낼 수 있다.

※주의 : $t_0$으로 가능한 값이 25020, 27020 두 가지가 발생한다. 이 때 25020을 선택하여 flag 값을 구하면 해당 값이 223bit가 아니다. 즉, 우리가 원하는 flag가 아니다. $t_0$값을 27020으로 설정하고 flag 값을 끝까지 구하면 223bit짜리 우리가 원하는 flag를 얻을 수 있다.

아래는 flag 구하는 코드 실행 장면 (코드 첨부함)

code.py