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)

名前通り、Curve25519に関する問題のようです。

解説

この問題では、以下のような条件が設定されています。

• 楕円曲線$y^2=x^3+48662x^2+x$を使用している。$G$はこの楕円曲線上の基点で、$G_x=9$。Wikipedia見ると分かりますが、位数$p$がとても大きいです。
• サーバーアクセス時に$x$と$P$、乱数$m$が与えられる。ここで、$P=xG$という関係性がある。
• この状態で、以下のプロセスを8回繰り返す。突破できればフラグをくれる。
  1. パラメータとして、楕円曲線上の点$I=(I_x, I_y)$と整数$e$、$s$が要求される。
  2. $I$がまだこの繰り返しの中で未使用であり、かつ$e=H_s(m, sG+eP, sH_p(P)+eI)$を満たしているかチェック。ここで、$H_s$はプログラム上におけるhashs、$H_p$はhashpです。
  3. $I$を2の判定で用いる既出リストに追加

一見かなり自由度が高そうですが、ハッシュ関数がかなり邪魔な印象です。条件式で「両辺に$e$が存在する」ということから、これを無くさないことには先に進めません。

ということで、$sG+eP=\alpha G$、$sH_p(P)+eI=\beta G$とパラメータ$(\alpha, \beta)$を追加してみましょう。

• $P=xG$より$(s+ex)G=\alpha G$、つまり$s+ex=\alpha$。これは$\alpha$、$\beta$によりハッシュ値が確定して$e$が求まり、その後に$s$が求められることを示します。
• 2つ目の式は残った自由度の$I$を確定するために使用し、$I=e^{-1}(\beta G-sH_p(P))$と変形すると$I$が求まります。

つまり、必要な手順としては以下の通りです。

1. $0$~$p-1$の間の乱数$\alpha$、$\beta$を生成する
2. $e=H_s(m, \alpha G, \beta G)$から$e$を求める
3. $s+ex=\alpha$より$s$を求める
4. $I\equiv e^{-1}(\beta G-sH_p(P))(\mod p)$から$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はもっと頑張りたいです。