TL;DR

  • $(g^x)G = P$となるような$x$を求める問題
  • $x$はそこまで大きくないのでBaby-Step Giant-Stepアルゴリズムの要領で平方分割すれば上手く求められる

Prerequisite

  • ECDSA
  • Baby-Step Giant-Stepアルゴリズム

Writeup

次のようなスクリプトが動いている(PoW用のスクリプトも添付されるが略)。

import hashlib
import hmac
import os

flag = open("flag.txt", "rb").read()
p = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
a = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC
b = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
E = EllipticCurve(Zmod(p), [a, b])
G = E(0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296,
      0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5)


# RFC 6979 section 2.3.2
def bits2int(b, q):
  res = int.from_bytes(b, 'big')
  blen = res.bit_length() 
  qlen = q.bit_length()
  return res >> (blen - qlen) if qlen < blen else res


# RFC 6979 section 2.3.3
def int2octets(x, q):
  rlen = ceil(q.bit_length()/8)
  return int(x % q).to_bytes(rlen, 'big')


# RFC 6979 section 3.2
def generate_k(hash_func, h, q, x, kp = b""):
  qlen = q.bit_length()//8
  hlen = hash_func().digest_size

  v = b"\x01" * hlen
  k = b"\x00" * hlen
  dgst = hmac.new(k, digestmod=hash_func)
  to_hash = v + b"\x00" + int2octets(x, q) + int2octets(h, q)
  to_hash += kp # Additional data described per variant at section 3.6 (k')
  dgst.update(to_hash)
  k = dgst.digest()

  v = hmac.new(k, v, hash_func).digest()
  dgst = hmac.new(k, digestmod=hash_func)
  to_hash = v + b"\x01" + int2octets(x, q) + int2octets(h, q)
  to_hash += kp # Additional data described per variant at section 3.6 (k')
  dgst.update(to_hash)
  k = dgst.digest()

  v = hmac.new(k, v, hash_func).digest()
  while True:
    t = b""
    while len(t) < qlen:
      v = hmac.new(k, v, hash_func).digest()
      t += v
    k = bits2int(t, q)

    if 1 <= k < q:
      return k

    k = hmac.new(k, v + b"\x00", hash_func).digest()
    v = hmac.new(k, v, hash_func).digest()


def sign(h, q, x, kp = b""):
  print("Signing %x..." % h)
  k = generate_k(hashlib.sha256, h, q, x, kp)
  x1, y1 = (k*G).xy()
  r = Integer(x1)
  s = Integer((h + r*x)*inverse_mod(k, q) % q)
  return r, s


def verify(h, q, r, s, P):
  print("Verifying %x..." % h)
  u1 = h * inverse_mod(s, q) % q
  u2 = r * inverse_mod(s, q) % q
  x1, x2 = (u1*G + u2*P).xy()
  return x1 == r


def get_signature(q, x, kp = b""):
  try:
    h = int(input("hash (hex): "), 16)
  except:
    return False

  if h == int(hashlib.sha256(flag).hexdigest(), 16):
    print("Nonono!")
    return False

  return sign(h, q, x, kp)


def verify_signature(q, P):
  try:
    h = int(input("hash (hex): "), 16)
    r = int(input("r: "))
    s = int(input("s: "))
  except:
    return False
  return verify(h, q, r, s, P)


def verify_password(q, x, kp):
  try:
    password = int(input("password: "))
  except:
    return False
  h = int(hashlib.sha256(flag).hexdigest(), 16)
  return password*E.lift_x(sign(h, q, x, kp)[0]) == G


def menu():
  print()
  print("1- Get signature")
  print("2- Verify signature")
  print("3- Read flag")
  print("4- Exit")
  try:
    option = int(input())
  except:
    return -1
  return option
end


def main():
  q1 = 2 * 2 * 2 * 2 * 3 * 71 * 131 * 373 * 3407
  q2 = 17449 * 38189 * 187019741 * 622491383 * 1002328039319 * 2624747550333869278416773953
  q = int(next_prime(q1*q2))
  x = int(pow(7, q2 * randint(1, p), q))
  P = x*G
  kp = os.urandom(32) # Extra data

  print("\nWelcome! What's your plan for today?")
  while True:
    option = menu()
    if option == 1:
      signature = get_signature(q, x, kp)
      print(signature)
    elif option == 2:
      print("Correct!") if verify_signature(q, P) else print("Wrong!")
    elif option == 3:
      print(flag.decode()) if verify_password(q, x, kp) else print("Wrong!")
    elif option == 4:
      print("Bye!")
      return
    else:
      print("Invalid option!")
      return


main()

ある楕円曲線が定義されて、その上でECDSAで署名/検証が出来る。nonceの生成はRFCに則っているようなのでここに脆弱性があるとは考えにくい。

また、2つの合成数$q_1, q_2$に対して$q_1q_2$より大きくて最も近い素数を$q$としているが、実は$q = q_1q_2+1$であり、加えてこの問題で使われる楕円曲線の位数である(SageMathで確認)。

ECDSAの署名鍵$x$は未知の乱数$y$を用いて、$x \equiv (7^{q_2})^y \mod q$という形をしており、7は$\mathbb F_q^*$の原始根であるから(これもSageMathで確認)、$x$の位数は$q_1$であり、これはそこまで大きく無い。

最終的にフラグの署名時に使われたnonceを$k_0$とおいて、$z(k_0G) = G$、すなわち$zk_0 \equiv 1 \mod q$となるような$z$を求めればフラグが開示される。なお、$G$はECDSAで用いられるベースポイントである。

フラグに関する情報が全く得られなくて「どこから解くんだ...?」と思っていたが(ここでカンニングポイント1)、非常に簡単な見落としがあり、3- Read flagで呼ばれているverufy_password()と、その中で呼ばれているsign()の処理を読むと、sign()が呼ばれたところで署名されるメッセージであるhを出力しているのでフラグのハッシュ値は判明する。したがって、これを1- Get signatureで送ると、フラグのハッシュ値に対する署名が判明し...ない。これは86行目から87行目にかけてのif文で入力がフラグのハッシュ値かどうかをチェックし、そうであるなら即座にreturnしているからである。

しかしこのフィルターはフラグのハッシュ値に対して$q$を足した値を送ることで容易にバイパス出来る。nonceの生成や計算上では$q$で割った余りで考えているが、フラグのハッシュ値との照合時はそうではないので当然このハッシュ値は異なるはずである。

これで手持ちの情報としてフラグのハッシュ値$h$とその署名$r,s$が手に入った。この署名で使われたnonceを$k$とおくと、$P \coloneqq kG$のx座標である$r$が手に入ったので、$P$と$-P$を計算することが出来る(但しどちらかは判別出来ない)。これらを用いると次のような関係にある。ここで$g \equiv 7^{q_2} \mod q$とおいた。

$$ \left(\frac hs\right) G + \left(\frac rs g^y\right) G = P $$

これをいい感じに変形すると次のようになる。

$$ g^yG \equiv \left(\frac sr\right)P - \left(\frac hr\right) G $$

以下、$Q \coloneqq \left(\frac sr\right)P - \left(\frac hr\right) G$とする。

さて、$q = q_1q_2+1$より、$\mathbb F_q^*$の位数は$q-1 = q_1q_2$であり、$g \equiv 7^{q_2} \mod q$であったから、$g$の位数は$q_1$である。この値はそこまで大きくない事を考えると、Baby-Step Giant-Step Algorithmの要領で$y$を求められそうな予感がする。

具体的には$m \coloneqq \lceil \sqrt {q_1} \rceil$とおいて、$y = im+j$のように$y$を$m$で割ると次のようになる。

$$ g^{im}(g^{j}G) = Q $$

両辺に$g^{-im} \bmod q$を掛けると、$g^jG =g^{-im}Q$が成り立つ。そこで、事前に$g^jG$を全通り計算して格納しておき(時間、空間計算量は共に$O(\sqrt {q_1}) = O(m)$)、後は$g^{-im}Q$を全ての$i$について計算した点が、$g^jG$の計算結果の中に含まれる場合は、$i,j$が求まったことになり、したがって$y=im+j$と$x$が求められたことになる。

と、思いきやSageMathのEllipticCurveを使う実装では点の加算/スカラー倍が遅く、$g^jG$のキャッシュも、照合も到底終わりそうにない。PoW用の添付ファイルによれば、PoW終了後に問題スクリプトを起動しているが、そのタイムアウトは2400秒となっており、それには間に合いそうに無いぐらい遅い。

ここで途方に途方に暮れてカンニングした(2回目)結果、考え方はだいたい同じだったが、fastecdsaというライブラリを使っていた。点の加算/スカラー倍をこれに変えた結果、速度がだいぶ改善され、現実的な時間で終了するようになった。

後は$k_0 \equiv \frac{h+rx}{s} \mod q$であるので、$z \equiv \frac{s}{h+rx} \mod q$を計算して3- READ flagで提出すればフラグが得られる。

Code

※何故か成功する場合としない場合がある、謎

from pwn import remote
from tqdm import tqdm
from fastecdsa.curve import Curve
from fastecdsa.point import Point
from math import sqrt, ceil
from xcrypto.mod import mod_sqrt

import pickle
import os

p = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
a = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC
b = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
q1 = 2 * 2 * 2 * 2 * 3 * 71 * 131 * 373 * 3407
q2 = 17449 * 38189 * 187019741 * 622491383 * 1002328039319 * 2624747550333869278416773953
q = q1*q2 + 1
gx, gy = (0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296,
      0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5)
EC = Curve("curve", p, a, b, q, gx, gy)
G = Point(gx, gy, curve=EC)

g = 7
_g = pow(g, q2, q)

def choice(c):
    sc.recvuntil(b"4- Exit\n")
    sc.sendline(str(c).encode())


def read_flag(password):
    choice(3)
    sc.recvuntil(b"password: ")
    sc.sendline(str(password).encode())
    sc.recvuntil(b"Signing ")
    h = int(sc.recvuntil(b"...\n")[:-4], 16)

    res = sc.recvline()

    return (h, res)


def get_sig(msg):
    choice(1)
    sc.recvuntil(b"hash (hex): ")
    sc.sendline(hex(msg).encode())
    sc.recvline()

    sig = eval(sc.recvline())

    return sig

sc = remote("localhost", 13337)
h, _ = read_flag(114514)
print(h)
r,s = get_sig(h+q)
print(r)
print(s)

m = ceil(sqrt(q1))
print(m)
assert m**2 >= q1

y1, y2 = mod_sqrt(EC.evaluate(r), p)

P1 = Point(r, y1, curve=EC)
P2 = Point(r, y2, curve=EC)

Q1 = s * pow(r, -1, q) * P1 - h * pow(r, -1, q) * G
Q2 = s * pow(r, -1, q) * P2 - h * pow(r, -1, q) * G

point_dict_file = "./point_dict"
if os.path.isfile(point_dict_file):
    with open(point_dict_file, "rb") as f:
        d = pickle.loads(f.read())
else:
    d = {}
    lhs = G
    for j in range(m):
        if j % 10000 == 0:
            print(j)
        d[(lhs.x, lhs.y)] = j
        lhs = _g * lhs

    with open(point_dict_file, "wb") as f:
        f.write(pickle.dumps(d))

print("[+] Creating Table is done")

g_m_inv = pow(_g, -m, q)
rhs1 = Q1
rhs2 = Q2
x = None
for i in range(m):
    if i % 10000 == 0:
        print(i)
    t = (rhs1.x, rhs1.y)
    if t in d:
        print("[+] Found!!")
        j = d[t]
        y = i*m + j
        break

    t = (rhs2.x, rhs2.y)
    if t in d:
        print("[+] Found!!")
        j = d[t]
        y = i*m + j
        break

    rhs1 = g_m_inv * rhs1
    rhs2 = g_m_inv * rhs2

if y is not None:
    print(y)
    x = pow(_g, y, q)
    z = s * pow(h + r*x, -1, q) % q
    print(z)

    h, res = read_flag(z)
    print(res)
    sc.interactive()

print("[+} End")

Flag

ローカルでやっただけなので無し

Resources