Zenn
🐡

justCTF 2020 - 25519

2021/02/01に公開
CTF
crypto
easy
tech

問題概要

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
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はもっと頑張りたいです。

Discussion