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