manykey

题目

from ecdsa import SigningKey
import secrets
sk = SigningKey.generate()
pk = sk.verifying_key

message = secrets.token_bytes(16)
print("Hello,", message.hex())
sig = sk.sign(message)
print(sig.hex())

print("Here's my public key")
print(pk.to_der().hex())

print("What was my private key again? (send me DER-encoded hex bytes)")
der = bytes.fromhex(input(""))

sk2 = SigningKey.from_der(der)
vk2 = sk2.verifying_key


assert sk2.privkey.secret_multiplier * sk2.curve.generator == vk2.pubkey.point
assert vk2.verify(sig, message)

with open("flag") as f:
    flag = f.read()
    print(flag, sk2.sign(flag.encode()))

题目对随机消息进行ECDSA签名。我们需要构造一个恶意的密钥对，使得服务器生成的签名通过验证。

我的解答

第一眼看上去觉得根本不可能，因为这似乎要求我们在NIST-P-192求解ECDLP——除非——我们可以指定的不止密钥对？

查阅from_der()的文档：它允许我们控制曲线参数，甚至不要求是named_curve，这意味着我们可以选取一条容易求解ECDLP的曲线。

曲线参数有什么要求？从源码来看from_der()的限制并不多，主要是验签这边：https://github.com/tlsfuzzer/python-ecdsa/blob/a4a8acddb9876c66240bdfcbe23fdd5b26c5e9c0/src/ecdsa/ecdsa.py#L184

def verifies(self, hash, signature):
    """Verify that signature is a valid signature of hash.
    Return True if the signature is valid.
    """

    # From X9.62 J.3.1.

    G = self.generator
    n = G.order()
    r = signature.r
    s = signature.s
    if r < 1 or r > n - 1:
        return False
    if s < 1 or s > n - 1:
        return False
    c = numbertheory.inverse_mod(s, n)
    u1 = (hash * c) % n
    u2 = (r * c) % n
    if hasattr(G, "mul_add"):
        xy = G.mul_add(u1, self.point, u2)
    else:
        xy = u1 * G + u2 * self.point
    v = xy.x() % n
    return v == r

对于$G$的阶数$n$和给定的签名$(r,s)$，这里要求了$r,s\in[1,n-1]$，而，这就决定了要生成一个$n>max\{r,s\}$，也就是192bit；同时这个阶数$n$必须足够特殊，使得ECDLP容易求解（可以阅读https://wstein.org/edu/2010/414/projects/novotney.pdf）。这里选择生成一个smooth的$n$。

（接下来纯属自己乱搞，不知道有没有更优雅的方式）

ns = []

while len(ns) < 1997:
    n = product(random_prime(2^17) for _ in range(12))
    if n.nbits() == 192:
        ns.append(n)
    
print(max(ns))
# 6276558150548653530270409953235291693375654678911154305751

在[巅峰极客2023]Rosita题解中，我们提到了一个生成曲线参数的工具，它可以"Generate a curve with given ORDER (using Complex Multiplication)"。

$ ./ecgen --fp --order 6275087238293041911103993524901500956130003182535550430701 192
[
{
    "field": {
        "p": "0xffeaf7b927898195b22567a985dfd2bf7d208b790a3e4985"
    },
    "a": "0x09c469d6ff8634f3b71bb3cb849decec29935c6541720194",
    "b": "0x15461cf4ad64c1238ddce9799e5e9585d3f44418d8f161c0",
    "order": "0xffeaf7b927898195b22567a8745015f83ffa2d56273feded",
    "subgroups": [
        {
            "x": "0xdc886e9594657e3f80c9b85f4b95f7b532cd130b0dbd450d",
            "y": "0xa5a8098d3c738a39656c8bbd2eda286a1450d60083fad517",
            "order": "0xffeaf7b927898195b22567a8745015f83ffa2d56273feded",
            "cofactor": "0x1",
            "points": [
                {
                    "x": "0x25fd563a3321b262f103c45519634122f18d0f4f551a3973",
                    "y": "0x667cccc4508136c1d3b31f45b896f635ecef7563342a365b",
                    "order": "0x201d"
                },
                {
                    "x": "0xf6cb5eb59ce39bedc04392a0ceb1bc1781646ee80a129677",
                    "y": "0x9722efe459b529a10388ab6fb7a0133dc70269d18dfa5caa",
                    "order": "0x808f"
                },
                {
                    "x": "0x3cd49f6e05dea375f7f3c33b72f6a786691e107fa556a22d",
                    "y": "0xf8b5113a141d790a874a22c8b401f9d754a815280af15e7d",
                    "order": "0x8d79"
                },
                {
                    "x": "0x165dbc47e6a881b85024a43fc73ae8442b400e2e4448d9f4",
                    "y": "0x7502d7190e96193cf56bcd9155d41227e3a2878817d72e5f",
                    "order": "0x112b7"
                },
                {
                    "x": "0xcdafa19225719ad52ea7d7bb0f4cee36677e99ccef809e38",
                    "y": "0x5b029e68b554252079e740b6196062f636c5ee1edbec50b9",
                    "order": "0x138a7"
                },
                {
                    "x": "0xdd8d11a4343013ef42b2f6f9c997e56126f17e684e335bc1",
                    "y": "0xf896dd21e18f02462d521c51d474c8a22ca03fc726825e33",
                    "order": "0x1516d"
                },
                {
                    "x": "0x629099cedf16b0dc99ee599d05b22a738f9eed18622e09bb",
                    "y": "0xdd66bd076e5879ecf112ab3d01d886c95aa4d207c3328186",
                    "order": "0x16949"
                },
                {
                    "x": "0x8c17f7c5c49e1427876c7a850afabb10ae0c8ea61ae725a4",
                    "y": "0x6b4c83a1099578dd8c58e2645b9c8e8652514ba79344f2c7",
                    "order": "0x177df"
                },
                {
                    "x": "0x4bfd6b80147cdf8546bee49e3b675e452ddfd7ea635f57d9",
                    "y": "0x6fb1f105bf9275898843a7f64deb92e604b1458ad38c7964",
                    "order": "0x18895"
                },
                {
                    "x": "0x93aa36dc2bd9fdd120d43da7d503522f692e7e31a6a13e1e",
                    "y": "0x19a6635e6aaae8131ca6c6c3324f8f3cbb19516fed4e163c",
                    "order": "0x19bad"
                },
                {
                    "x": "0xd1fbc8e8a654d646877e5c8052138c64ddfe954412b4e0da",
                    "y": "0x6afe114ae0c7744dc890f47681218342188e08da52837ec1",
                    "order": "0x1c675"
                },
                {
                    "x": "0x7c87e2e33319a11f53233dc6ac3c8f59cfd1105bba029f66",
                    "y": "0xecbd7104f22d60ddfd3480ef61a3c6c7ee52efe1828850aa",
                    "order": "0x1d521"
                }
            ]
        }
    ]
}]

然后就是翻文档翻源码，搞懂怎么把参数提取出来，做完ECDLP再塞回去，这个python-ecdsa库里面的椭圆曲线操作用起来相当蛋疼。。

缝缝补补最后得到一个可以用的解题脚本如下（不能保证点在曲线上，需要多跑几次）：

from sage.all import *
from pwn import *
from hashlib import sha1
from ecdsa.keys import SigningKey, VerifyingKey
from ecdsa.ellipticcurve import CurveFp, PointJacobi
from ecdsa.curves import Curve

n = 6275087238293041911103993524901500956130003182535550430701
p = 0xFFEAF7B927898195B22567A985DFD2BF7D208B790A3E4985
a = 0x09C469D6FF8634F3B71BB3CB849DECEC29935C6541720194
b = 0x15461CF4AD64C1238DDCE9799E5E9585D3F44418D8F161C0
EC = EllipticCurve(GF(p), [a, b])
assert EC.order() == n
G = EC.gens()[0]

io = remote("manykey.chal.irisc.tf", 10102)
io.readline()

# get msg -> z
msg = io.readline().decode().split()[1]
z = int(sha1(bytes.fromhex(msg)).hexdigest(), 16)

# get sig -> r, s
sig = io.readline().decode()
r = int(sig[:48], 16)
s = int(sig[48:], 16)

# get pk
pk = bytes.fromhex(io.read().decode().splitlines()[1])
pk = VerifyingKey.from_der(pk)

# solve ECDLP
kG = EC.lift_x(GF(p)(r))
k = G.discrete_log(kG)
d = (s * k - z) * inverse_mod(r, n) % n
Q = d * G
u1 = z * inverse_mod(s, n)
u2 = r * inverse_mod(s, n)
P = u1 * G + u2 * Q

# traslate sagemath into python-ecdsa
EC_ecdsa = CurveFp(p, a, b)
G_ecdsa = PointJacobi(
    EC_ecdsa, x=G.xy()[0], y=G.xy()[1], z=1, order=G.order(), generator=True
)

EC_ecdsa = Curve("1997", curve=EC_ecdsa, generator=G_ecdsa, oid=None)
sk = SigningKey.from_secret_exponent(secexp=d, curve=EC_ecdsa)
vk = sk.verifying_key

payload = sk.to_der().hex().encode()
io.sendline(payload)
io.interactive()
# irisctf{key_generating_machine}