1. はじめに

　2025/1/26 12:00 JST ～18:00 に開催された「AlpacaHack Round9 (Crypto)」参加しました。数時間とはいえ、CTF にまとまった時間を投入できたのは久しぶりでした*1。2 完で 6 位。

　最初の 1 問で色々迷走し、時間を使い過ぎてしまった点は大いなる反省点でした。

2. Writeup

AlpacaHackの過去問は常設コンテンツとなるため、フラグの記載は省略します。

2.1. RSAMPC (16 solves)

設問

I calculated the RSA public key using multi-party computation.

以下の 2 ファイルが提供されます。

「chall.py」

import os
from Crypto.Util.number import getRandomRange, getPrime, bytes_to_long

FLAG = os.environ.get("FLAG", "fakeflag").encode()

def additive_share(a):
    t0, t1 = getRandomRange(-2**512, 2**512), getRandomRange(-2**512, 2**512)
    t2 = a-t0-t1
    return t0, t1, t2

def replicated_share(a):
    t = additive_share(a)
    return [(t[i], t[(i+1)%3]) for i in range(3)]

def multiply_shares(sa, sb):
    def mul(t, u):
        return t[0]*u[0]+t[0]*u[1]+t[1]*u[0]
    r = additive_share(0)
    z = [mul(sa[i], sb[i])+r[i] for i in range(3)]
    w = [(z[i], z[(i+1)%3]) for i in range(3)]
    return w

def reconstruct(s):
    return s[0][0] + s[0][1] + s[1][1]

p = getPrime(512)
q = getPrime(512)

sp = replicated_share(p)
sq = replicated_share(q)
print("your share of p:", sp[0])
print("your share of q:", sq[0])

spq = multiply_shares(sp, sq)
print("your share of pq:", spq[0])

n = reconstruct(spq)
assert n == p*q
print("n:", n)

e = 0x10001
c = pow(bytes_to_long(FLAG + os.urandom(127-len(FLAG))), e, n)
print("e:", e)
print("c:", c)

「output.txt」

your share of p: (-384164070196680113629973964276599320736606300184523772854135294036334447818682200607218877531386512793858125339877828582394197679795576991953411880314517, 178776721087372919385257940734429604253240493277094581482580652949038337321961407291832241379559936948198042043881180916670462219794291885959730598632423)
your share of q: (-10504102453855211730773548202462643334445368588122773952797120588540073173181223269420294976331168878842123082669069593895980908615299058089156709125348617, 3324659724832936014805633502878093035237335054058544453532695059432217891926271390882999445452501190449380595220556388508799059755133895886341486877191502)
your share of pq: (880194945859095512548778390949753106113259354062743403885130575509194611686622871911550689148439940097472063798899034574466553154127726867674397008987477001207806315461004286936941315001029394217039765579529660629019466179402060549350587729722354909331590051509695082365313846996923469825646557408789955494, 40388351148875096689764230410867470980240794826105168292967479483809364773078955483003274901375600951153408618729650715655666480989756454152565386666760509805904377793675351489295406907138019316039841793386393194481700178651652081449097569147179108704523020190287922457859082133424057955783092523665228634328)
n: 122269467950798077326822634108968850809243750508493781647505745002863843379348700424238562022365315227978807541070854658246091147872559714237246479088170538196473585543281713624525798244748333546435600544573727499127916535316599284592352755786055339638261774730837681190375466416924715653324305527245715836447
e: 65537
c: 100976267335628681910815317357700490412039872278731196009735781349258998302355802361980783540754919888894607253589239383351290237447746132667260747986281172840910605287343986031579879857474734142154881821962810929745626899955618676413832332521656625264015203959361696843594006345498340544121922011105950850715

検討

　リークされる sp[0] 、sq[0]、spq[0] が何なのかよくわからなかったので、SageMath の数式処理で把握することにしました。「test.sage」


PR.<p,q,tp0,tp1,tq0,tq1,tr0,tr1> = PolynomialRing(ZZ)

tp2 = p - tp0 -tp1
sp = [(tp0,tp1), (tp1,tp2), (tp2,tp0)]
print(sp[0])
#(tp0,tp1)

tq2 = q - tq0 -tq1
sq = [(tq0,tq1), (tq1,tq2), (tq2,tq0)]
print(sq[0])
#(tq0,tq1)

def mul(t, u):
  return t[0]*u[0]+t[0]*u[1]+t[1]*u[0]

tr2 = -tr0-tr1
r = (tr0, tr1, tr2)

z = [mul(sp[i], sq[i])+r[i] for i in range(3)]
spq = [(z[i], z[(i+1)%3]) for i in range(3)]

print(spq[0])
#(tp0*tq0 + tp1*tq0 + tp0*tq1 + tr0, q*tp1 - tp1*tq0 + p*tq1 - tp0*tq1 - tp1*tq1 + tr1)

　spq[0][0]からは良い情報を得られそうにありませんので、spq[0][1]の方を見てみます。

　tp0、tp1、tq0、tq1 は既知ですから、spq[0][1] の未知数は p, q, r[1] の 3つでいずれも 512bit、ということになります。

　最初これを（愚かにも） LLL で処理しようとしたのですが、無理筋でした（未知数が大きすぎ！）。気を取り直して r[1] を "誤差" と見なし、 p （もしくは q）の近似値を求めて総当たりしてみたところ、うまくいきました。想定解法のようです。

解法（ソルバ）

「solve.sage」

from Crypto.Util.number import *
import gmpy2

sp = (-384164070196680113629973964276599320736606300184523772854135294036334447818682200607218877531386512793858125339877828582394197679795576991953411880314517, 178776721087372919385257940734429604253240493277094581482580652949038337321961407291832241379559936948198042043881180916670462219794291885959730598632423)
sq = (-10504102453855211730773548202462643334445368588122773952797120588540073173181223269420294976331168878842123082669069593895980908615299058089156709125348617, 3324659724832936014805633502878093035237335054058544453532695059432217891926271390882999445452501190449380595220556388508799059755133895886341486877191502)
spq = (880194945859095512548778390949753106113259354062743403885130575509194611686622871911550689148439940097472063798899034574466553154127726867674397008987477001207806315461004286936941315001029394217039765579529660629019466179402060549350587729722354909331590051509695082365313846996923469825646557408789955494, 40388351148875096689764230410867470980240794826105168292967479483809364773078955483003274901375600951153408618729650715655666480989756454152565386666760509805904377793675351489295406907138019316039841793386393194481700178651652081449097569147179108704523020190287922457859082133424057955783092523665228634328)
n = 122269467950798077326822634108968850809243750508493781647505745002863843379348700424238562022365315227978807541070854658246091147872559714237246479088170538196473585543281713624525798244748333546435600544573727499127916535316599284592352755786055339638261774730837681190375466416924715653324305527245715836447
e = 65537
c = 100976267335628681910815317357700490412039872278731196009735781349258998302355802361980783540754919888894607253589239383351290237447746132667260747986281172840910605287343986031579879857474734142154881821962810929745626899955618676413832332521656625264015203959361696843594006345498340544121922011105950850715

N = n * sp[1] * sq[1]
b = spq[1] + sp[1]*sq[0] + sp[0]*sq[1] +sp[1]*sq[1]
D = B**2 - 4*N

sqD = int(gmpy2.isqrt(D))
approx_p = ((b + sqD)//2) // sq[1]

for i in range(-100000,100000):
  p = approx_p+i
  if n % p == 0:
    print("found!")
    break

q = n // p
d = pow(e,-1,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))

2.2. addprimes (16solves)

設問

addprimes in PARI/GP is useful for implementing RSA decryption.

以下のファイルが提供されます。「server.sage」

import os
import signal
from sage.misc.banner import require_version
from Crypto.Util.number import getPrime, bytes_to_long

assert require_version(10), "This challenge requires SageMath version 10 or above"

signal.alarm(30)
FLAG = os.environ.get("FLAG", "Alpaca{*** FAKEFLAG ***}").encode()
assert FLAG.startswith(b"Alpaca{")

p = getPrime(512)
q = getPrime(512)
n = p * q
e = 37

print("n:", n)
print("e:", e)

c = int(input("ciphertext: "))
assert 1 < c < n-1
pari.addprimes(p)
m = mod(c, n).nth_root(e)
print("plaintext:", m)

padded_flag = FLAG + os.urandom(127-len(FLAG))
print("encrypted flag:", pow(bytes_to_long(padded_flag), e, n))

検討

　「e=37だから37個集めてCRTすれば終わりっしょ」…なわけありませんでした。ちゃんと padding されていますのでダメです。

　そこで私はこう考えました。「Zmod(n) における 1 の e 乗根で 1 以外のもの（ここでは w と書くことにする）が判明して、たとえば w mod p ==1、w mod q !=1で1以外、なんていうことであれば、 GCD(w, n) == p となり幸せになれる！」*2

　最近クジ運はそう悪くない*3ので、実装してみることにしました。

　p, q が求められたら、mod.p、mod.q で e 乗根を計算して CRT すれば解候補を列挙できるので、そこから long_to_bytesして b"Alpaca{" を含むものを選べば OK です。

解法（ソルバ）

「solve.sage」

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
from pwn import *
import random
import itertools

HOST = <redacted>
PORT = <redacted>

while(True):
  r = remote(HOST, int(PORT))
  try:
    n = int(r.readline().decode().replace("n: ",""))
    m0 = random.randint(2**1023,2**1024) % n
    c = pow(m0,e,n)
    r.readline()
    kw = b"ciphertext: "
    data = str(c).encode()
    r.sendlineafter(kw, data)
    m = int(r.readline().decode().replace("plaintext:",""))
    enc = int(r.readline().decode().replace("encrypted flag: ",""))
    r.close()
    if m != m0:
      print("hit")
      root = m * pow(m0,-1,n) % n
      if 1 < gcd(root - 1, n) < n:
        break
  except:
    try:
      r.close()
    except:
      pass

p = gcd(root - 1, n)
q = n // p
d = pow(e,-1,(p-1)*(q-1))

mps = GF(p)(enc).nth_root(e, all=True)
mqs = GF(q)(enc).nth_root(e, all=True)

for mp in mps:
  for mq in mqs:
    pt = long_to_bytes(crt([int(mp),int(mq)],[p,q]))
    if b"Alpaca" in pt:
      print(pt)
      exit()

3. おわりに

　久しぶりにまとまった時間を使って Crypto に取り組んで楽しめました。

　解けなかった問題*4については「Upsolve queue」に投入し、腰を据えて取り込もうと思います。

*1:ここ最近は主に Dream Hack を埋めていました。

*2:ちょっとまどろっこしい考え方でしたが、間違いではなかったようです。

*3:宝くじは全く当たりませんが。

*4:maple3142さんゴメンサナイ！

Learning cyber security by playing and enjoying CTFs

Cyber Security関係の雑記帳です。表明されているお気持ちなどは全て個人的なものであり、筆者が所属もしくは関係する組織・団体の意向とは一切関係ありません。

AlpacaHack Round 9 (Crypto) Writeup

1. はじめに

2. Writeup

2.1. RSAMPC (16 solves)

設問

検討

解法（ソルバ）

2.2. addprimes (16solves)

設問

検討

解法（ソルバ）

3. おわりに