Midnightsun CTFは毎年いくつか独自色の強い問題が出るな、という印象だったのですが、今年はBackupシリーズのcryptoがひどかった印象があります。その他AVRマイコンなどの組み込みに関連する問題が出るのはいつもどおりという感じ。
私は純粋cryptoを2問通しました。どちらもsolve数が二桁前半で、簡単というほどではないが難しい問題ではない、という感じでの面白い問題でした。なんとかチームメイトに怒られない程度の貢献はできたかな。
ocat_024
u = getrandbits(512) p = next_prime(1337 * u + getrandbits(300)) q = next_prime(2021 * u + getrandbits(300)) n = p * q sage: n 376347864369130929314918003073529176189619811132906053032580291332225522349124770927556541528827257242440708492473086949335591022991715583608318595770643139658398940858358366788472884935226392323475683663699450192657590965945792699658618476121298301964814904817629813971114882401961638885452623305901569855693667669 sage: e 310766221758298615381202293330340201483059349618898159596286032329366528507960364515724537815587119639645241427449290559721282531962504187828968370246921804939126848756614691757878117709116273156365166616707032588454229002048939764035908902821773289938766897121298435864096976179239412103595971947786698704390414999 sage: round(log(d, 2)) 376 sage: Zmod(n)(int.from_bytes(flag, 'big'))^e 303959676149267585825046248298946771045524761540948385119310381022731003152171453295355624619013005255259014408962058282203132797411290952180380162699236575669681289832696809724483816916203823843359489329046259936011464869397208487809073597880729992617105037777911285154649450892121090200338517719744860831555514222
となっているRSAの問題です。加えて、が比較的小さいことが分かっています。
まず第一に注目するのは素数が独特な構造になっていることです。これは過去にConfidence CTF 2019 TeaserでReally Suspicious Acronymとして出題されている形式で、が共通しており、のサイズが比較的小さいことからと近似ができるので、 という近似ができます。この近似によりの上位210ビット程度を求めることができます。
しかしこれだけの情報では、Coppersmith's methodを用いた素因数分解には不足です。そこでが比較的小さいというヒントから、を使って立式していきます。
ですから、を先程近似した値と真の値との差を用いてと表して以下の式が成り立ちます。
さらにをとります。
式(△)において、未知変数は であり、は素因数の未知の部分なので300bit程度、また であることから、の大きさは最大でも376bit程度になります。一方は1000bit以上ありますから、は剰余多項式(△)の比較的小さな整数根になっていると言えそうです。したがってCoppersmith's methodによっての具体的な値を求められるかもしれません。多変数多項式の小さい根を求める実装としては、 defund/coppersmith が優れています。これを使ってを求めることができれば、を計算しフラグを求められそうです。
# https://raw.githubusercontent.com/defund/coppersmith/master/coppersmith.sage import itertools from sage.rings.polynomial.multi_polynomial_sequence import PolynomialSequence def small_roots(f, bounds, m=1, d=None): if not d: d = f.degree() R = f.base_ring() N = R.cardinality() f /= f.coefficients().pop(0) f = f.change_ring(ZZ) G = PolynomialSequence([], f.parent()) for i in range(m+1): power = N^(m-i) * f^i for shifts in itertools.product(range(d), repeat=f.nvariables()): g = power for variable, shift in zip(f.variables(), shifts): g *= variable^shift G.append(g) B, monomials = G.coefficient_matrix() monomials = vector(monomials) factors = [monomial(*bounds) for monomial in monomials] for i, factor in enumerate(factors): B.rescale_col(i, factor) B = B.dense_matrix().LLL() B = B.change_ring(QQ) for i, factor in enumerate(factors): B.rescale_col(i, 1/factor) B = B.change_ring(ZZ) H = Sequence([], f.parent().change_ring(QQ)) for h in B*monomials: if h.is_zero(): continue H.append(h.change_ring(QQ)) I = H.ideal() if I.dimension() == -1: H.pop() elif I.dimension() == 0: V = I.variety(ring=ZZ) if V: roots = [] for root in V: root = map(R, map(root.__getitem__, f.variables())) roots.append(tuple(root)) return roots return [] n = 376347864369130929314918003073529176189619811132906053032580291332225522349124770927556541528827257242440708492473086949335591022991715583608318595770643139658398940858358366788472884935226392323475683663699450192657590965945792699658618476121298301964814904817629813971114882401961638885452623305901569855693667669 e = 310766221758298615381202293330340201483059349618898159596286032329366528507960364515724537815587119639645241427449290559721282531962504187828968370246921804939126848756614691757878117709116273156365166616707032588454229002048939764035908902821773289938766897121298435864096976179239412103595971947786698704390414999 c = 303959676149267585825046248298946771045524761540948385119310381022731003152171453295355624619013005255259014408962058282203132797411290952180380162699236575669681289832696809724483816916203823843359489329046259936011464869397208487809073597880729992617105037777911285154649450892121090200338517719744860831555514222 p_ = int(sqrt(n * 1337/2021)) q_ = int(sqrt(n * 2021/1337)) PR.<r, t_> = PolynomialRing(Zmod(e)) f = 1 + k_*n - t_*(p_ + q_ + r) + t_ for ans in small_roots(f, [2^300, 2^377]): r = int(ans[0]) phi = n - (p_ + q_ + r) + 1 d = int(pow(e, -1, phi)) m = pow(c, d, n) print(m)
求まりました。
dbcsig_64434
from hashlib import sha256 def keygen(password): while True: p = 2 * random_prime(2 ^ 521) + 1 if p.is_prime(proof=False): break base, h = 3, password for i in range(256): h = sha256(h).digest() x = int.from_bytes(h * 2, "big") return base, p, pow(base, x, p), x def sign(message, priv): h = int(sha256(message).hexdigest(), 16) k = next_prime(int.from_bytes( sha256(message + priv.to_bytes(128, "big")).digest() + sha256(message).digest(), "big" )) r = int(pow(g, (k - 1) / 2, p)) s = int(Zmod((p - 1) / 2)(-r * priv + h) / k) return r, s g, p, pub, priv = keygen(b"[redacted]") r, s = sign(b"blockchain-ready deterministic signatures", priv)
(配布ソースコード中に存在した、問題と直接関係ないコメントを省略しています)
独自のデジタル署名アルゴリズムのようですが、プログラムはいわゆるDSAのそれと似通っています。目的はを求めることで、に加えて、平文から求められるが分かっています。
このアルゴリズムを観察すると、2つ特徴的な部分が見つかります。まず1つ目は秘密鍵の構造で、int.from_bytes(h * 2, "big")
のように、256bitの値を2回繰り返して並べることで512bitの値を作っています。値の大きさは512bitありますが、情報量としては256bitのものと等価と考えられます。2つめはの値で、こちらも256bitの値を2つ並べて作られていますが、上位256bitが全くわからない一方、下位256bitは でありおよその値が分かっています。
式をたてて整理してみます。そもそものDSAアルゴリズムでは (ただしここでです)がなりたち、それは今回も同様です。ここで, と表しつつ、移項して式を整理すると次のような形になります。
ここで未知数はで、はそれぞれ256bitの値です。はどのくらいかわかりませんが、だいたい1000を超えることはないでしょう。他方、は521bit程度の値であり未知数と比較して大きいですから先ほどと同様にCoppersmith's methodが適用できそうです。
# https://raw.githubusercontent.com/defund/coppersmith/master/coppersmith.sage ... from hashlib import sha256 g = 3 p = 403564885370838178925695432427367491470237155186244212153913898686763710896400971013343861778118177227348808022449550091155336980246939657874541422921996385839128510463 pub = 246412225456431779180824199385732957003440696667152337864522703662113001727131541828819072458270449510317065822513378769528087093456569455854781212817817126406744124198 r = 195569213557534062135883086442918136431967939088647809625293990874404630325238896363416607124844217333997865971186768485716700133773423095190740751263071126576205643521 s = 156909661984338007650026461825579179936003525790982707621071330974873615448305401425316804780001319386278769029432437834130771981383408535426433066382954348912235133967 message = b"blockchain-ready deterministic signatures" h = int(sha256(message).hexdigest(), 16) q = (p-1) // 2 # assert q.is_prime ???????? PR.<d_, k_, a> = PolynomialRing(Zmod(q)) f = 2^256 * s * k_ + s * (h + a) + r * (d_ + 2^256 * d_) - h roots = small_roots(f, [2^256, 2^256, 1000], d=4, m=4) for root in roots: dval = Integer(root[0]) dval = dval * 2^256 + dval if pow(g, dval, p) == pub: print("[+] found: {}".format(dval)) break else: print("[-] wrong: {}".format(dval))
できました。ところで、この問題のkeygen
に従って値が作られていればは最大でも522bit程度の値で安全素数になると思ったのですが、実際にはは557bitあり、また安全素数ではありませんでした。これは一体どういうことでしょうか 🤔