justCTF 2020 - 25519

문제 개요

One time signatures, so you can spend your coins only once.
Please solve the task locally first and reach our server only for the flag :)

nc c25519.nc.jctf.pro 1337

https://ams3.digitaloceanspaces.com/justctf/6f7420f1-b591-47a0-98f2-40fd097c33de/task.sage

task.sage

#!/use/bin/env sage

from sys import exit
from hashlib import sha256


FLAG = open('./flag.txt').read()

ec = EllipticCurve(GF(2**255-19), [0, 486662, 0, 1, 0])
p = ec.order()
ZmodP = Zmod(p)
G = ec.lift_x(9)

ha = lambda x: x if isinstance(x, int) or isinstance(x, Integer) else product(x.xy())
hashs = lambda *x: int.from_bytes(sha256(b'.'.join([b'%X' % ha(x) for x in x])).digest(), 'little') % p


def hashp(x):
    x = hashs((x))
    while True:
        try:
            return ec.lift_x(x)
        except:
            x = hashs((x))


def keygen():
    x = randint(1, p-1)
    P = x * G
    return x, P


def verify(signature, P, m):
    I, e, s = signature
    return e == hashs(m, s*G + e*P, s*hashp(P) + e*I)


if __name__ == "__main__":
    x, P = keygen()
    m = randint(1, p-1)
    print(x, P, m)

    spent = set()
    for i in range(8):
        Ix = int(input('I (x): '))
        Iy = int(input('I (y): '))
        I = ec(Ix, Iy)
        e = int(input('e: '))
        s = int(input('s: '))
        if verify((I, e, s), P, m) and I not in spent:
            print('ok')
            spent.add(I)
        else:
            print('nope')
            exit(1)

    print(FLAG)

이름 그대로 Curve 25519에 대한 질문인 것 같습니다.

해설

이 문제에서 다음과 같은 조건을 설정하였다.

타원 곡선 y^2 = x^3+48662x^2+x를 사용합니다.G는 이 타원 곡선의 기점이고, G는x=9. Wikipedia 딱 봐도 자릿수 p가 엄청 커요.

서버 액세스 시 x, P 및 임의 수 m을 제공합니다.여기에는 P=xG의 관계성이 있다.

이 상태에서 8회 이하의 처리를 반복한다.돌파할 수 있다면 깃발을 주시오.

매개변수로 타원 커브의 점 I=(I x, I y) 및 정수 e, s가 필요합니다.

I는 아직 중복되지 않았으며 e=Hs(m,sG+eP,sHp(P)+eI)가 충족되는지 확인합니다.여기는 H입니다.s 프로그램hashs, Hp는 hashp입니다.

2 판정에 사용된 목록에 I 추가

언뜻 보기에는 자유도가 높지만 산열 함수는 상당히 번거로운 인상을 준다.조건식에는'양쪽에 e가 존재한다'는 것이 있기 때문에 잃어버리지 않으면 전진할 수 없다.
따라서 sG+eP =\alphaG, sH-p(P)+eI=\beta G와 매개변수(\alpha,\beta)를 추가해 보십시오.

P=xG(s+ex)G=\alphaG, 즉 s+ex=\alpha.이것은\alpha, 베타가 해시 값을 확정하고 e를 얻은 다음에 s가 필요하다는 것을 나타낸다.

두 번째 공식은 남은 자유도 I를 정하는 데 사용되며, I=e^{-1}(\beta G-sH p(P)) 변형이 있으면 I를 구한다.

즉, 필요한 절차는 다음과 같다.

0~p-1 사이의 무작위 수\alpha, 베타 생성

e=H_s(m,\alpha G,\beta G)에서 e

구하기

s+ex=\alpha에 따라 s

를 구하다

I\equive ^{-1}(\beta G-sH p(P))(\modp)에서 I를 구합니다.p가 적어도 짝수이기 때문에 e의 역원을 얻지 못할 수 있습니다. 이때 1에서 다시 시작합니다

다음 프로그램은 I의 중복을 특별히 고려하지 않았지만 충돌이 발생하지 않아 기본적으로 통과할 수 있다(생각 없음)
solve.py

from hashlib import sha256
from sage.all import *
import pwn

ec = EllipticCurve(GF(2**255-19), [0, 486662, 0, 1, 0])
p = ec.order()
ZmodP = Zmod(p)
G = ec.lift_x(Integer(9))

ha = lambda x: x if isinstance(x, int) or isinstance(x, Integer) else product(x.xy())
hashs = lambda *x: int.from_bytes(sha256(b'.'.join([b'%X' % ha(x) for x in x])).digest(), 'little') % p

def hashp(x):
  x = hashs((x))
  while True:
    try:
      return ec.lift_x(x)
    except:
      x = hashs((x))

io = pwn.remote("c25519.nc.jctf.pro", 1337)
line = io.recvline().decode('utf-8').split()
x = int(line[0])
P = x * G
m = int(line[-1])

# required: I(Ix, Iy), s, e
for _ in range(8):
  while True:
    try:
      a = randint(0, p - 1)
      b = randint(0, p - 1)
      e = hashs(m, a*G, b*G)
      s = a - e*x
      I = inverse_mod(e, p) * (b*G - s*hashp(P))
      print(io.recvuntil("I (x):").decode('utf-8'), I.xy()[0])
      io.sendline(str(I.xy()[0]).encode('utf-8'))
      print(io.recvuntil("I (y):").decode('utf-8'), I.xy()[1])
      io.sendline(str(I.xy()[1]).encode('utf-8'))
      print(io.recvuntil("e:").decode('utf-8'), e)
      io.sendline(str(e).encode('utf-8'))
      print(io.recvuntil("s:").decode('utf-8'), s)
      io.sendline(str(s).encode('utf-8'))
      break
    except:
      pass
io.interactive()

sage@7d301c35aaf1:/tmp/25519$ python3 solve.sage
[+] Opening connection to c25519.nc.jctf.pro on port 1337: Done
I (x): 15173548547438417837958538934901226118009749756988789082285890307420506692795
 I (y): 56010349933474948589592027095481854451317796359560057433094116023175606374790
 e: 43081426461778073251499005572182999111754544017489573471475548538573001097637
 s: -225427771218132659323468449082112079082542799329884737617792361341164430160707770336746244318540309044763701281261585437307840570453082186386951568079861
 ok
...(省略)
I (x): 42783616650181984940055861578652434892199983643867742392490150628181143704860
 I (y): 4512726711869550603856915854493443762971126203518057901457635611931940804164
 e: 39473473736355715013237497914980618017872847794800280213346620493410343326331
 s: -206548806235997260660213694695955550140095474232589479026997243191911072360145415465891454905282956075072096388288781547483892779920488241579757111479959
[*] Switching to interactive mode
 ok
jCTF{th1s_g4me_st0p_on1y_onc3}

[*] Got EOF while reading in interactive

감상

상당히 긴 시간 "해시 어떡해... 양쪽에 e가 있으면 안 되지 않나요?"이런 시간을 사용하고 있다.Crypto는 더 열심히 하고 싶어요.