[tum ctf 2016] hiecss - crpyto

[참조] https://github.com/dqi/ctf_writeup/blob/master/2016/tumctf/hiecss/README.md

여기 번역, 또는 따라하기

문제

#!/usr/bin/env python3 import gmpy2 from Crypto.Hash import SHA256 e = 65537 order = 'Give me the flag. This is an order!' def sqrt(n, p): if p % 4 != 3: raise NotImplementedError() return pow(n, (p + 1) // 4, p) if pow(n, (p - 1) // 2, p) == 1 else None # just elliptic-curve addition, nothing to see here def add(q, a, b, P, Q): if () in (P, Q): return (P, Q)[P == ()] (Px, Py), (Qx, Qy) = P, Q try: if P != Q: lam = (Qy - Py) * gmpy2.invert(Qx - Px, q) % q else: lam = (3 * Px ** 2 + a) * gmpy2.invert(2 * Py, q) % q except ZeroDivisionError: return () Rx = (lam ** 2 - Px - Qx) % q Ry = (lam * Px - lam * Rx - Py) % q return int(Rx), int(Ry) # just elliptic-curve scalar multiplication, nothing to see here def mul(q, a, b, n, P): R = () while n: if n & 1: R = add(q, a, b, R, P) P, n = add(q, a, b, P, P), n // 2 return R def decode(bs): if len(bs) < 0x40: return None s, m = int(bs[:0x40], 16), bs[0x40:] if s >= q: print('\x1b[31mbad signature\x1b[0m') return None S = s, sqrt(pow(s, 3, q) + a * s + b, q) if S[1] is None: print('\x1b[31mbad signature:\x1b[0m {:#x}'.format(S[0])) return None h = int(SHA256.new(m.encode()).hexdigest(), 16) if mul(q, a, b, e, S)[0] == h: return m else: print('\x1b[31mbad signature:\x1b[0m ({:#x}, {:#x})'.format(*S)) if __name__ == '__main__': q, a, b = map(int, open('curve.txt').read().strip().split()) for _ in range(1337): m = decode(input()) if m is not None and m.strip() == order: print(open('flag.txt').read().strip())  break

[아이디어]

q, a, b = map(int, open('curve.txt').read().strip().split())

ECC 를 이용한 문제, q, a, b를 읽어서 처리하고 있음, 처음에 q, a, b가 뭔지 몰라서 온갖 삽질을 하고 다녔음. 그러다가 인터넷에서 찾음, 깔끔하게 정리되어 있음

q : 보통은 p라고 많이 쓰는데, 소수이며 모듈러로 사용함

a, b : 계수라고 하나 뭐 하여튼. y^2 = x^3 + a*x  + b 에서 a와 b를 말함, ECC는 a, b 가 전부임, y^2 와 x^3에는 계수가 없기 때문임

그러므로 q, a, b를 구하면 될 것 같음. 당연한거 아님? 그러나 당연하지 않음. 그 뒤에도 알아야 할 것이 태산같이 많음

h = int(SHA256.new(m.encode()).hexdigest(), 16)  if mul(q, a, b, e, S)[0] == h:

 여기에서는 입력하는 메시지의 SHA256 를 구해서 mul(q, q, b , e, S) 함수와 비교함 그러니까 m을 공격자가 입력하는 값이므로 q, a, b만 알면 h를 구할 수 있을 것 같음

k = gmpy2.invert(n, l)

가장 짧을 글자이지만 어려운 개념이 들어있음 우선 l 이 어려움. l은 q, a, b를 구한 다음, 한번더 계산해야 하는 값임. 영어로는 order 라고 불리며, 어려운 말로 쓰이면 '순환군의 갯수'  정도, ECC 패어링에서 생성하는 전체의 갯수. 이 갯수를 구하는 것이 이 문제를 푸는 핵심임. order 를 구한 다음 e의 값의 역(reverse)를 구해서 푸는 문제임

[q 구하기]

가장 쉬운 문제, 왜냐면 문제에서 갈켜주고 있기 때문이 바이너리 검색으로 구할 수 있음

 

H=0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff L=1 m=H+L//2 buf="%064x"%m buf+=orderpad p.sendline(buf) recvbuf = p.recv() print recvbuf k=0 while True:   k+=1   if recvbuf.find(":")>=0:     print "q is bigger "     L=m+1   else:     print "q is smaller or equal"     H=m   print (k,hex(m))   if H-L<=1:     print ('deff',H-L)     break   m=(H+L)//2   buf="%064x"%m   buf+=orderpad   p.sendline(buf)   sleep(0.1)   recvbuf = p.recv()   print recvbuf

m=0x247ce416cf31bae96a1c548ef57b012a645b8bff68d3979e26aa54fc49a2c296+1 buf="%064x"%m buf+=orderpad p.sendline(buf) recvbuf = p.recv() print recvbuf k=0 while True:   k+=1   if recvbuf.find(":")>=0:     print "q is bigger "   else:     print "q is smaller or equal"   print (k,hex(m))   break

이렇게 q의 값을 쉽게 구함

[a와 b 구하기]

이것도 쉬움, 왜냐면 2원 1차 연립 방정식이기 때문임

ECC 의 일반항이 이거인데, y^2 = x^3 + a*x  + b 

문제에서 3, 6의 값을 보내면 사인값이 틀렸다고 하면서 해당되는 y의 값을 출력해줌

for i in range(3,20):   print 'i=',i   buf="%064x"%i   buf+=orderpad   p.sendline(buf)   recvbuf = p.recv()   print recvbuf

요렇게 데이터를 보내면, 서버에서 해당되는 값을 보내줌, 그래서 방정식을 풀 수 있음

q = 0x247ce416cf31bae96a1c548ef57b012a645b8bff68d3979e26aa54fc49a2c297 x1=0x3 y1=0x493589ba9df3a079e9bfb83e0037cd6a6d5b89fc37dd7c1759df8f601c4a1cc x2=0x6 y2=0x2179f35ed018406b3a98072c5577a80c7b1c9feb78f480bbbc0f8adda7f8a542 #b = y1**2 - a*x1 #b = y2**2 - a*x2 b =( y1**2 * 2 - y2**2 ) % q a1 = (y1**2 - x1**3 - b) / x1 a2 = (y2**2 - x2**3 - b) / x2    print 'b=',hex(b%q) print 'a1=',hex(a1%q) print 'a2=',hex(a2%q)

[order 구하기]

위에서 a, b, q값을 구했으므로, h를 쉽게 구할 수 있을 것 같음, 물론 문제 계산에서는 6만몇번 돌려서 값을 구했는데 .... 그러나 실제 몇번 돌려야 하는지 계산해 보면 지림. 몇번 계산해야 하는가는 order 값을 구해서 e 값의 역(reverse)를 구해야 함. 우선은 order 를 구해야 함

sage: a = 0xb3b04200486514cb8fdcf3037397558a8717c85acf19bac71ce72698a23f635 sage: b = 0x12f55f6e7419e26d728c429a2b206a2645a7a56a31dbd5bfb66864425c8a2320 sage: q = 0x247ce416cf31bae96a1c548ef57b012a645b8bff68d3979e26aa54fc49a2c297 sage: E = EllipticCurve(GF(q), [a,b]) sage: E.order() 16503925798136106726026894143294039201930439456987742756395524593191976084900

설명에는 order 를 구하기 위하여 sage를 사용했다라는 달랑 한줄만 나옴. 그러나 여기에도 조금 깊은 설명이 필요함 우선 sage를 python를 기반으로 하는 cython을 이용하여 만든 수학계산 함수 모음 정도됨. python 이 스크립트 언어이기 때문에 느린 단점을 바이너리로 만들어서 커버침. 설명하면 지루하고 . 인터넷에보면 sage 를 어떻게 설치해야 하는가 설명이 잘 나와있음 . 검색어 : sagemath

위에서 잠깐 설명했듯이 order를 알아야 역(reverse)를 구하고 우리가 만든 임의의 값을 넣어서 해쉬값(mac)을 위조할 수 있음. sage 에서 미리 order 구하는 함수를 만들어 놓았음. 그래서 동일하게 값을 입력하면 order 를 구해줌. 자 이제 다 구했음 이제 답을 입력해 볼 차례임

q = 0x247ce416cf31bae96a1c548ef57b012a645b8bff68d3979e26aa54fc49a2c297 a = 0xb3b04200486514cb8fdcf3037397558a8717c85acf19bac71ce72698a23f635 b = 0x12f55f6e7419e26d728c429a2b206a2645a7a56a31dbd5bfb66864425c8a2320 def bf(i):    p=remote('localhost',8888)    log.success(i)    curve = libnum.ecc.Curve(a, b, q)    orderpad = 'Give me the flag. This is an order!'+' '*i    h = int(hashlib.sha256(orderpad).hexdigest(), 16)    H = curve.check_x(h)[0]    n = 65537    l = 16503925798136106726026894143294039201930439456987742756395524593191976084900    # Multiplicative inverse    k = gmpy2.invert(n, l)    Q = curve.power(H, k)    msg = '%064x' % Q[0]     msg += orderpad    p.sendline(msg)    buf = p.recv()    print (buf) for i in range(10):    try:      bf(i)    except:      print 'sleep...'      sleep(0.5)

다 온줄 알았지만 보야할 것이 좀더 있음 우선 (로컬서버에 socat으로 띄우는 것은 다 아니까 생략) 여기 쯤 오면 libnum.ecc.Curve(a, b, q) 내용은 대충 감이 와야 함  ECC 를 만들어 주는 함수임. curve.check_x(h)[0] 패어링 함수. x에 h를 넣고 y를 계산해 주는 함수. H는 ECC 패어링이 생김, 당연함.k = gmpy2.invert(n, l) 이거는 역을 구하는 함수임 invert 함수 자체가 나머지 1이 생기는 곱셉의 역, 뭐 그정도 구하는 함수임. 그래서 내가 만든 H 패어링에 k를 곱하면 해쉬가 동일하게 만들어짐. 그러나 처음하면 에러남. 왜냐면 패어링이 q 보다 큰 값으로 생김. ECC 는 패어링이 q 보다 반드시 작아야 함. 그래서 에러가 남. ' ' 스페이스 패딩을 몇개 넣으면 키가 출력됨

w00t@LiLi-SuperCom:~/Desktop/ctf/muhen/crypto/hiecss$ python ans.py [+] Opening connection to localhost on port 8888: Done [+] 4 hxp{H1dd3n_Gr0uP_0rD3rz_4r3_5uPP0s3D_t0_B3_k3p7_h1DD3n!}

ECC에 대한 개념만 있으면 풀이방법이 쉽게 생각나는 문제임(문제 였음)