ふるつき

v(*'='*)v かに

LINE CTF 2021 babycrypto4 writeup

LINE CTF は cryptoに関しては満足行くクオリティの問題はありませんでした……。

overview

secp160r1上のECDSAに関する次の20 x 4個のパラメータが与えられます*1。左からr, s, kの上位16bit, hash(m) です。このときにいわゆる秘密鍵dを求めよ、という問題です。

0x92acb929727872bc1c7a5f69c1c3c97ae1c333e2 0xe060459440ebc11a7cd811a66a341f095f5909e5 0xef2b0000 0x68e548ef4984f6e7d05cbcea4fc7c83393806bbf
0xb0f5df566a323de9c9449b925d29b84a607c6b5d 0x84e39e417e47b4fcaf344255103c61ecaaec4129 0xc1c00000 0x1a79e7b0308805508d79f2600a01e70d4f56559e
0xc90081698382f98c817a137db22f11a846d699fe 0x2f8fbb7e74b789cd762b30930ef21862a5fd68ee 0x841b0000 0x95e3302e197be4d8335cf0d17cc70860ea5317f7
0x9d84669314b014bc83f3ac53ddcf3c9536c940b1 0x8b1a69d6e9d75f1698144badc7b93f9a2347839d 0xa1c90000 0xc7af08154a154ac8c58eb14380955834093b3863
0x96d5439a01f47e92be9ff40bee1fecb033b70d3f 0x1c23660695d16bf03ef40e5ef53bdc92a5d348e7 0x816e0000 0x9d3f0dc80e962b9377ed22de66d6421457bcaf5d
0x3ea39f6c446918690b395ba181f6d5d08444897a 0x4478e239338ec6652815d03b8decb2d4f58beaba 0x9d050000 0x478e00e6191477e6cdd17a29719d96d02e5e8960
0xbd1cbcd26fb6cb41878ec155fb2506534e803c97 0xd732fbda187222d85e9a14243b007cc25e1b6b7c 0x445a0000 0x2493379cf90246fe7316963c65f28cd9b0a6ecd4
0x727f7f05a9096beb6d5f65acce6fe42ec3a07dc9 0x8511715efb01ff83b04fe82fb7535dc7de40abef 0x91d0000 0x6ce034dddd5470034068c5146fae4dd039aacaf6
0x513ed0e15f8f3405bf0083a2186926fe60ccb65e 0x28892ebcc428f2a566b39a2dbe03ec436641c948 0x879d0000 0xfe4e2564369a23e07efbf82d01c5ae7e72cd8105
0xebf3e23fbe73c5f50032c8e4a3d8359fef203a03 0xa5b79ae6f8ed237a05b4325c02b8dfe7b9ff5aa7 0x98950000 0x762309f98ebac533fece5321736fc6ba95d8382b
0xc49cdbf6ec3b73188238291fa960675a099b74a0 0xeabb1e7dcd20115a47b94ecfe8780f676e237437 0x287a0000 0x523ea75c4310ac1ac64fa28cc5047b7223e8da0b
0x9e8a731a26f509793e2b8778cd75b518549ab9c8 0x27be029029db9d62cdb729bc592cb0a4e6168bf3 0xebc80000 0x9f0e9e95661f5e93c90b72af0dce38c673c7ef16
0xa74159f377749ad36efc28f9c7608a6758009af 0xa3ce2671944b01f633265a6458ce2cca8b72eda6 0x574c0000 0x16e12f9dece23681927be002d24a0e4e6ed3ae7e
0xcb0a427a05b3e3dcb18a1bb66f9340d2a0c721ab 0x4a242cca295c6018f4a65d1fadbdb45731cccd7a 0x23f40000 0xd7e0a09d8aed604bc1fda1f1965c4a8bf6b58621
0x5dc440585c88e75da002f941520867add07f93ef 0x3612124de46659ef7d79d46f1eb05707e313b84d 0x65850000 0xca6547a9e3f08bd36f700b7282a36033250971ad
0x6e009a8f5138a5b94d4e81b5f2a07ee29b413b39 0x8b3c33c15dca93248f840324d540b7956251d1e0 0xb4f80000 0xe916da678253ff7b31453ba1ec709eb909b37c5d
0x5091314db6155d7a96c1b19098ca235cf86d1f77 0x2c62bf21452a2b326e8db27fb3345e10c63b2821 0x452c0000 0x31dd06dcf95fb04a734149eed64b7b99a575d56e
0x2f6eed036a46ca6e309d8d7292bd3b0796607fcc 0x63b4524f47dcde603426c48bbb2f308bc474e5ce 0x63780000 0xe108d036a12b4f15cc9af89688d26634c5dfc32a
0x247ca1d3450a85612e6176ea5dfec4aeb90e2a3f 0x66b1f9f04e284e28f44402f1ca7803c90786d9c2 0x48a0000 0xd58c608cc4d3adfc131c73cccff952c1d310a1e0
0xab04fc0c4981b047622c786662091f7efbbbd807 0xa2853851df0aaed34dc972bcf7d7d5ffbbc2b401 0x9d040000 0x5bdd98b548b8b0f48a56fb4c41e6d09bf8bd1b0e

solution

いわゆるnonceであるkの上位16bitがわかっているのでこれを利用するのかな、と思うところですが、そもそも32bitのkでは小さすぎるので、半分が与えられていようがいまいが変わらず解けます。

(EC)DSAでは s \equiv (h + rd)k^{-1} \mod n ですから、これを展開して変形すると k - s^{-1}rd  - s^{-1}h \equiv 0 \mod n になります。いくつかのインスタンスを考えて、インスタンスごとに異なる値に添え字をつけると

 k_i - s_u^{-1}r_id  - s_i^{-1}h_i \equiv 0 \mod n

となります。このとき、 k_i, d がそれぞれ未知数で、 r_i, s_i, h_iはそれぞれ既知です。

一方、Hidden Number Problemは以下の式で t_i, a_i既知、 x_i, y未知に未知数を求める問題で、 x_iの最大値がある程度小さい時には、CVPを解いて x_i, yがそれぞれ求めることができます。

 x_i - t_iy + a_i \equiv 0 \mod p

2つの式を見比べてみると、 k_i \leftrightarrow x_i,  s_i^{-1}r_i \leftrightarrow t_i,  d \leftrightarrow y,  a_i \leftrightarrow -s_i^{-1}h_i という対応づけができそうです。そして、 x_iに対応する k_iは最大でも 2^{33} - 1 と小さいですから、CVPを解くことで k_i, xを求められそうです。今回は埋め込み法(embedded technique)と呼ばれる形のSVPを解くことでCVPを解いています。

from hashlib import sha1
import random

# https://neuromancer.sk/std/secg/secp160r1
p = 0xffffffffffffffffffffffffffffffff7fffffff
K = GF(p)
a = K(0xffffffffffffffffffffffffffffffff7ffffffc)
b = K(0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45)
E = EllipticCurve(K, (a, b))
G = E(0x4a96b5688ef573284664698968c38bb913cbfc82, 0x23a628553168947d59dcc912042351377ac5fb32)
E.set_order(0x0100000000000000000001f4c8f927aed3ca752257 * 0x01)

n = int(E.order())

dataset = []
with open("output.txt") as f:
    lines = f.read().strip().split("\n")
    for l in lines:
        # r_, s_, k_, h_ = [int(x, 16) for x in l.split(" ")]
        dataset.append( [int(x, 16) for x in l.split(" ")] )


r, s, k, h = zip(*dataset)
N = 20 # randint(2, 20) # len(h)
print("N = {}".format(N))
t = [r[i] * inverse_mod(s[i], n) % n for i in range(N)]
u = [(h[i] * inverse_mod(-s[i], n) % n) % n for i in range(N)]

nonce_max = 2**32

B = matrix(QQ, N + 2, N + 2)
B.set_block(0, 0, matrix.identity(N) * n)
B.set_block(N, 0, matrix(QQ, 1, N, t))
B.set_block(N+1, 0, matrix(QQ, 1, N, u))
B[N,N] = nonce_max / n
B[N+1,N+1] = nonce_max

L = B.LLL()
for row in list(L):
    k1 = int(abs(row[0]))
    if k1 != 0 and k1 != nonce_max and k1 < nonce_max:
        x = (k1*s[0] - h[0]) * inverse_mod(r[0], n) % n
        kk = (k1 >> 16) << 16
        print(k1, x, kk in k)
        print(int(x)*G)

この問題では k_iがかなり小さいので、3インスタンス程度あればHNPが解けます。

*1:もともと問題文ではsecp160k1となっていましたが、正しくはsecp160r1のようでした。この間違いのアナウンスなしに解いたThe Duckはすごい