CTF

[tum ctf 2016] hiecss - crpyto

goldpapa 2016. 10. 5. 00:03

[참조] 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에 대한 개념만 있으면 풀이방법이 쉽게 생각나는 문제임(문제 였음)