ふるつき

v(*'='*)v かに

ACTF 2022 writeup

zer0pts で ACTF に出たのでwriteupです。真面目に取り組んで8位でした。簡単な前2問はよくできていて面白かったです。後ろ2問は特にcrypto的に面白いことがない割に取り組むのが大変でした

Impossible RSA

from Crypto.Util.number import *
from Crypto.PublicKey import RSA

e = 65537
flag = b'ACTF{...}'

while True:
    p = getPrime(1024)
    q = inverse(e, p)
    if not isPrime(q):
        continue
    n = p * q;
    public = RSA.construct((n, e))
    with open("public.pem", "wb") as file:
        file.write(public.exportKey('PEM'))
    with open("flag", "wb") as file:
        file.write(long_to_bytes(pow(bytes_to_long(flag), e, n)))
    break

あまりにきれいな問題設定に、これ既出じゃないのかという驚きが。

RSA q = e^{-1} \mod pです。つまり適当な正整数 k \lt eをもってきて eq = 1 + kpがなりたつので、 en = peq = p(1 + kp) = p + kp^2です。 kを全探索すれば未知数は pだけなので、二次方程式を解けばよいです。

from Crypto.Util.number import getPrime, inverse, isPrime, long_to_bytes, bytes_to_long
from Crypto.PublicKey import RSA
from tqdm import tqdm
from gmpy2 import iroot

key = RSA.import_key(open("public.pem").read())

n = key.n
e = key.e


for k in tqdm(range(1, e)):
    a = k
    b = 1
    c = -n*e

    x, ok = iroot(b**2 - 4*a*c, 2)
    if not ok:
        continue

    if (b + x) % (2*a) == 0:
        p = int(abs((b + x) // (2*a)))
        break

    if (b - x) % (2*a) == 0:
        p = int(abs((b - x) // (2*a)))
        break

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

c = bytes_to_long(open("flag", "rb").read())
m = pow(c, d, n)

print(long_to_bytes(m))

RSA Leak

from sage.all import *
from secret import flag
from Crypto.Util.number import bytes_to_long


def leak(a, b):
    p = random_prime(pow(2, 64))
    q = random_prime(pow(2, 64))
    n = p*q
    e = 65537
    print(n)
    print((pow(a, e) + pow(b, e) + 0xdeadbeef) % n)


def gen_key():
    a = randrange(0, pow(2,256))
    b = randrange(0, pow(2,256))
    p = pow(a, 4)
    q = pow(b, 4)
    rp = randrange(0, pow(2,24))
    rq = randrange(0, pow(2,24))
    pp = next_prime(p+rp)
    qq = next_prime(q+rq)
    if pp % pow(2, 4) == (pp-p) % pow(2, 4) and qq % pow(2, 4) == (qq-q) % pow(2, 4):
        n = pp*qq
        rp = pp-p
        rq = qq-q
        return n, rp, rq
    
n, rp, rq = gen_key()
e = 65537
c = pow(bytes_to_long(flag), e, n)
print("n =", n)
print("e =", e)
print("c =", c)
print("=======leak=======")
leak(rp, rq)

'''
n = ...
e = 65537
c = ...
=======leak=======
122146249659110799196678177080657779971
90846368443479079691227824315092288065
'''

 p = a^4 + r_p, q = b^4 + r_q という[RSA] で、[$ n, e, c]の他に n_2, leak = r_p^e + r_q^e + 0xdeadbeef \mod n_2がもらえる。 n_2は十分小さいので素因数分解でき、 r_p, r_qは24bit程度なので全探索できます。 r_pが決まれば自動的に r_qが決まりますが、 n_2が64bitくらいなので、適当にやると r_qも64bitくらいになるところ、正しい r_pを選べていると r_qが24bit程度になるはずなのでわかります。

また、 n \approx a^4b^4 なので n^{1/4} = abがなりたちます。これで n = (a^4 + r_p)(b^4 + r_q), ab = a*bという2式があって、未知数が a, bの2つなので連立方程式を立てれば解けます

from tqdm import tqdm
from sympy.solvers import solve
from sympy import symbols
from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes


n = 3183573836769699313763043722513486503160533089470716348487649113450828830224151824106050562868640291712433283679799855890306945562430572137128269318944453041825476154913676849658599642113896525291798525533722805116041675462675732995881671359593602584751304602244415149859346875340361740775463623467503186824385780851920136368593725535779854726168687179051303851797111239451264183276544616736820298054063232641359775128753071340474714720534858295660426278356630743758247422916519687362426114443660989774519751234591819547129288719863041972824405872212208118093577184659446552017086531002340663509215501866212294702743
e = 65537
c = 48433948078708266558408900822131846839473472350405274958254566291017137879542806238459456400958349315245447486509633749276746053786868315163583443030289607980449076267295483248068122553237802668045588106193692102901936355277693449867608379899254200590252441986645643511838233803828204450622023993363140246583650322952060860867801081687288233255776380790653361695125971596448862744165007007840033270102756536056501059098523990991260352123691349393725158028931174218091973919457078350257978338294099849690514328273829474324145569140386584429042884336459789499705672633475010234403132893629856284982320249119974872840

ab, _ = iroot(n, 4)
a, b = symbols("a, b", integer=True)

n2 = 122146249659110799196678177080657779971
leak = 90846368443479079691227824315092288065

p2 = 8949458376079230661
q2 = 13648451618657980711

d2 = pow(e, -1, (p2-1)*(q2-1))
x = leak - 0xdeadbeef

for rp in tqdm(range(0, 2**24)):
    rq = pow(x - pow(rp, e, n2), d2, n2)
    if rq < 2**24:
        print((rp, rq))

        y = n - (ab**4 + rp*rq)
        solutions = solve([a**4*rq + b**4*rp - y, ab - a*b])
        for sol in solutions:
            print(sol)
            a_ = int(sol[a])

            p = a_**4 + rp
            q = n // p

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

secure connection

力尽きてきた。bluetoothかなにかの通信が実装されていて、パケットのダンプもあるけど一部データがXXに置き換わったりしてます。 CRCがついてるのでこれに合うようにXXの部分を全探索して、shared numeric keyが24bit 程度しかないので全探索!

retros

Revするとこういう感じのVMであることがわかります

"""
VM:
    regs:
        0: pc
        1: memptr
        2: memptr
        3: value
        4: value
        5: global
        6: flag
    mem[32]: shuffled 32 values
    global: number
"""

pc = 0
ptr1 = 1
ptr2 = 2
val1 = 3
val2 = 4
glob = 5
flag = 6


def check_and_halt():
    """
    print flag if mem is sorted
    """
    return [0]


def add_g(idx):
    assert idx in [0, 1, 2, 5, 6]
    return [1, idx]


def sub_g(idx):
    assert idx in [0, 1, 2, 5, 6]
    return [2, idx]


def mv_from_mem(reg, ptr):
    """
    reg = mem[ptr]
    """
    assert reg in [3, 4]  # general register
    assert ptr in [1, 2]  # mem ptr register
    return [3, reg, ptr]


def mv_to_mem(ptr, reg):
    """
    mem[ptr] = reg
    """
    assert ptr in [1, 2]
    assert reg in [3, 4]
    return [4, ptr, reg]


def set_g(val):
    """
    global = val
    """
    assert 0 <= val < 256
    return [5, val >> 4, val & 0x0f]


def set_g_if(val):
    """
    if flag == 1:
        global = val
    """
    assert 0 <= val < 256
    return [6, val >> 4, val & 0x0f]


def memcmp():
    """
    if mem[ptr1] >= mem[ptr2]:
        flag = 1
    """
    return [7]


def cmp_ge(reg):
    """
    if reg >= global
     flag = 1
    """
    assert reg in [0, 1, 2, 3, 4, 5, 6]
    return [8, reg]


def mv_to_g(reg):
    """
    global = reg
    """
    return [9, reg]

31バイト以内でバイトコードを組み立てて送りつけて、32要素のメモリをソートしてcheck_and_haltを呼べばフラグが手に入ります。crypto要素はバイトコードはAES CBCで暗号化したものを送りつけないと行けないけど、鍵は知らないのでpadding oracle encryption attackを使ってオラクルを頼りに暗号文を構築するところで、あとはrev + miscです。

謎の31バイト制限&10000ステップ制限、貧弱なバイトコード、readlineの実装のせいで暗号化したバイトコードに0x0aは含められないなど様々な制約を突破するとフラグが手に入ります。このあたりのバイトコード組み立てとかの詳しいことは id:keymoon が書いてくれるはず。私はRevとpadding oracleしたのと、0x0aが含められなくて困るけどpadding oracle encryptionの最後のブロックは自由度があるのでそこをガチャすればいいって言うかかりをやりました

↓こういう感じで解ける

import random
from ptrlib import Process
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

"""
VM:
    regs:
        0: pc
        1: memptr
        2: memptr
        3: value
        4: value
        5: global
        6: flag
    mem[32]: shuffled 32 values
    global: number
"""

pc = 0
ptr1 = 1
ptr2 = 2
val1 = 3
val2 = 4
glob = 5
flag = 6


def check_and_halt():
    """
    print flag if mem is sorted
    """
    return [0]


def add_g(idx):
    assert idx in [0, 1, 2, 5, 6]
    return [1, idx]


def sub_g(idx):
    assert idx in [0, 1, 2, 5, 6]
    return [2, idx]


def mv_from_mem(reg, ptr):
    """
    reg = mem[ptr]
    """
    assert reg in [3, 4]  # general register
    assert ptr in [1, 2]  # mem ptr register
    return [3, reg, ptr]


def mv_to_mem(ptr, reg):
    """
    mem[ptr] = reg
    """
    assert ptr in [1, 2]
    assert reg in [3, 4]
    return [4, ptr, reg]


def set_g(val):
    """
    global = val
    """
    assert 0 <= val < 256
    return [5, val >> 4, val & 0x0f]


def set_g_if(val):
    """
    if flag == 1:
        global = val
    """
    assert 0 <= val < 256
    return [6, val >> 4, val & 0x0f]


def memcmp():
    """
    if mem[ptr1] >= mem[ptr2]:
        flag = 1
    """
    return [7]


def cmp_ge(reg):
    """
    if reg >= global
     flag = 1
    """
    assert reg in [0, 1, 2, 3, 4, 5, 6]
    return [8, reg]


def mv_to_g(reg):
    """
    global = reg
    """
    return [9, reg]

instructions = []
jump_marker = {}


def jump1(name1):
    # 3: set_g
    # 2: add_g
    return [name1, None, None, None, None]  # placeholder


def jump(name1, name2):
    # 3: set_g
    # 3: set_g_if
    # 2: add_g/sub_g
    return [name2, None, None, name1, None, None, None, None]  # placeholder


def mark(name):
    jump_marker[name] = (len(instructions)) * 4



mark("outer_loop_begin")
# ptr1 += 1
instructions += set_g(1)
instructions += add_g(ptr1)

# ptr2 = 0
instructions += mv_to_g(ptr2)
instructions += sub_g(ptr2)

# flag = ptr1 >= 32
instructions += set_g(32)
instructions += cmp_ge(ptr1)
instructions += jump("check", "inner_loop_begin")

mark("inner_loop_begin")
# flag = mem[ptr1] >= mem[ptr2]
instructions += memcmp()
instructions += jump("inner_loop_end", "swap")

mark("swap")
instructions += mv_from_mem(val1, ptr1)
instructions += mv_from_mem(val2, ptr2)
instructions += mv_to_mem(ptr1, val2)
instructions += mv_to_mem(ptr2, val1)

mark("inner_loop_end")
# flag = ptr2 >= 31
# ptr2 += 1
# if (flag) break;
# else      continue;
instructions += set_g(1)
instructions += add_g(ptr2)

instructions += mv_to_g(ptr1)
instructions += cmp_ge(ptr2)
instructions += jump("outer_loop_begin", "inner_loop_begin")

mark("check")
instructions += check_and_halt()

g_if_ind = set()
# encode instructions
is_jump_forward = False
for i in range(len(instructions)):
    if isinstance(instructions[i], str):
        name = instructions[i]
        jump_to = jump_marker[name]
        if i+3 < jump_to:
            is_jump_forward = True
        else:
            is_jump_forward = False

        if isinstance(instructions[i+3], str):
            g_if_ind.add(i + 3)

        if i in g_if_ind:
            a, b, c = set_g_if(abs(jump_to - (i+5) * 4))
            instructions[i+0] = a
            instructions[i+1] = b
            instructions[i+2] = c
        else:
            a, b, c = set_g(abs(jump_to - (i+8) * 4))
            instructions[i+0] = a
            instructions[i+1] = b
            instructions[i+2] = c

    elif instructions[i] is None:
        if is_jump_forward:
            a, b = add_g(pc)
            instructions[i+0] = a
            instructions[i+1] = b
        else:
            a, b = sub_g(pc)
            instructions[i+0] = a
            instructions[i+1] = b

print(len(instructions), instructions)

i = 0
remain_insns = list(instructions)
res = ""
insts = [(1, "check"), (2, "add_g"), (2, "sub_g"), (3, "mv_from_mem"), (3, "mv_to_mem"), (3, "set_g"), (3, "set_g_if"), (1, "memcmp"), (2, "cmp_ge"), (2, "mv_to_g")]
while len(remain_insns) != 0:
    l, name = insts[remain_insns[0]]
    ops = remain_insns[:l]
    args = ops[1:]
    remain_insns = remain_insns[l:]
    
    op =   (str(ops[0])).rjust(3)
    arg0 = (str(ops[1]) if 2 <= l else "").rjust(3)
    arg1 = (str(ops[2]) if 3 <= l else "").rjust(3)

    if name in ["set_g", "set_g_if"]:
        disasm = f'{name}({ops[1] * 0x10 + ops[2]})'.ljust(18) + f'# {ops[1]}, {ops[2]}'
    else:
        disasm = f'{name}({", ".join(map(str, args))})'
    res += f'{str(i).rjust(3)}: {op} {arg0} {arg1} | {disasm}\n'
    i += l * 4

print(res)

if len(instructions) % 2 == 1:
    instructions.append(0)
payload = []
for i in range(0, len(instructions), 2):
    payload.append((instructions[i] << 4) | instructions[i+1])

if payload[-1] != 0:
    payload.append(0)
print(len(payload), payload)
assert 16 < len(payload) < 32
payload = pad(bytes(payload), 16)

# on remote, encode payload by using padding oracle encryption attack
iv = b"\0"*16
key = b"A" * 16
with open("./key", "wb") as f:
    f.write(key)

"""
aes = AES.new(mode=AES.MODE_CBC, key=key, iv=iv)
ticket = aes.encrypt(payload)

sock = Process("./retros")

input("WAIT> ")
sock.sendline(ticket)
sock.sendlineafter("fortune: ", b"\0"*0x10)
sock.interactive()
"""

import pwn, subprocess

LOCAL = False

# if LOCAL: io = pwn.process('./retros')
if LOCAL: io = pwn.remote("localhost", 8003)
else: io = pwn.remote('123.60.146.157', 9999)

if not LOCAL:
    print(io.recvline())
    dat = io.recvline().split(b'`')[1].decode().split()[2]
    print(dat)
    dat = subprocess.check_output(['hashcash','-mb26',dat])
    print(dat)
    dat = dat.decode().split(' ')[-1].strip()
    print(dat)
    io.sendline(dat)
    print(io.recvline())
    print(io.recvline())

def _do_oracle(ct2, token, j):
    if j < 0:
        return token, False
    
    candidate = []
    last_byte = None
    xval = ([0] * 16 + [16 - j] * (16 - j))[-16:]
    for i in range(256):
        token[j] = i
        send_token = pwn.xor(token, xval)
        if b'\n' in send_token:
            candidate.append(i)
            continue
        io.sendline(send_token + ct2)
        io.sendline(b'\x00' * 16)
    for i in range(256):
        if i in candidate: continue
        r = io.recvline()
        if b'not complete' in r:
            print(j, i, token)
            last_byte = i
    if last_byte is not None:
        token[j] = last_byte
        res, _ = _do_oracle(ct2, bytearray(token), j - 1)
        return res, True

    assert 1 <= len(candidate)
    print(f'[+] {j=} {token[j + 1]=} {len(candidate)=}')
    for i in candidate:
        token[j] = i
        res, confidence = _do_oracle(ct2, bytearray(token), j - 1)
        print(res)
        if confidence:
            print(f'[+] discoverd! {res=}, {confidence=}')
            return res, True
    return res, confidence

def do_oracle(ct2):
    token = bytearray(b'\x00' * 16)
    j = 15
    res, _ = _do_oracle(ct2, token, j)
    return res

init_ct2 = b'superneko'.ljust(16, b'\x00')

ct2 = do_oracle(init_ct2)
print(f'{ct2=}')
ct2 = pwn.xor(ct2, payload[16:])
ct3 = do_oracle(ct2)
print(f'{ct3=}')
ct3 = pwn.xor(ct3, payload[:16])

io.send(ct2 + init_ct2 + b'\n' + ct3 + b'\n')

io.interactive()

ある種のEdDSAの実装に対するDouble-PubKey Oracle Attack

話題はこれ↓

www.reddit.com

詳しい話はこれ↓

blog.safeheron.com

興味があるところだけ書くと、EdDSAの署名は秘密鍵 x、公開鍵 A = xGとして、平文 mを受け取って次のように計算した (R, S)の組*1。詳しくはwikipediaとかを見てください。

  •  r = h(h_{\{b \dots 2b-1\}}(k) || m), R = rG
  •  e = h(R || A || m)
  •  S \equiv r + ex \mod q

ここで署名のロジックが入力として (k, m, A)を受け取っているとき、 (R, S) = sign(k, m, A), (R, S') = sign(k, m, A') のように不正な公開鍵 A'を渡して、これが計算されてしまうとECDSAにおけるnonce reuse attackのような感じで xが計算できる。

具体的には S \equiv r + ex \mod q, S' \equiv r + e'x \mod qで、 r, xが未知なので2式で引き算をして rを消すと S - S' \equiv (e - e')x \mod qになって、 x = \frac{S - S'}{e - e'} \mod qとやって xが得られる。

上述のポストなどでは署名するロジックは Aは受け取らずに自前で計算するか、受け取ってもそれが kに対応したものであることを確かめましょうといってる(まあこれは計算して一致するか見ることになる)。

個人的には引数に誤った値を渡したらロジックが思わぬ挙動になって結果的に困るみたいなのはそうですねと思うんだけど、特にredditの記事では割と深刻っぽい雰囲気で書いてある。誤用しうる状態すらも許せないってことなんだろうか。実際これが攻撃やバグにつながるかと言われると、それこそCTFでくらいしかそういうシチュエーションにならないような気がするし、これで問題を作れって言われても自然な形にするのにはだいぶ苦心することになるだろうな、と思う。暗号界隈的にはどういう受け止め方をされているんだろう。気になる。

redditのスレちゃんと読んでなかったけどCTFでは既出らしいです ctf/2018-12-08-hxp/crypto_uff at master · p4-team/ctf · GitHub

*1:ここで Rは曲線状の点だけど Sは整数なので注意。あと k x = h_{0 \dots b-1}(k)であるシード

SECCON Beginners 2022 - Omni RSA writeup

writeup くらい書いておかないとなにもしていないような悲しい気持ちになるのでwriteupです

問題はこう

from Crypto.Util.number import *
from flag import flag

p, q, r = getPrime(512), getPrime(256), getPrime(256)
n = p * q * r
phi = (p - 1) * (q - 1) * (r - 1)
e = 2003
d = inverse(e, phi)

flag = bytes_to_long(flag.encode())
cipher = pow(flag, e, n)

s = d % ((q - 1)*(r - 1)) & (2**470 - 1)

assert q < r
print("rq =", r % q)

print("e =", e)
print("n =", n)
print("s =", s)
print("cipher =", cipher)

こういう問題をみたら、 ed \equiv 1 \mod \phiをたてて、 \phiを開いて N, p, q, rで表したうえで ed = 1 + k(N + \dots + 1)という形に剰余を開きたくなりますね。そのあと N eで剰余を取り直す。

しかし今回の場合与えられている s u \equiv d \mod (q-1)(r-1)の下位470bitなので愚直にそういうアプローチは取れずちょっと工夫が必要になりそうです。とにかく書いてみると、 u = s + x*2^{470}として

 e(s + x*2^{470}) \equiv 1 \mod (q-1)(r-1)

です。適当な整数 kを持ち出してきて剰余を開き、ついでに t = r \% q = r - qも与えられているので、 r = q + tとおきなおすとこうです。

  e(s + x*2^{470}) = 1 + k(q-1)(q+t-1)

一見これで \mod qを取り直して \beta = 0.25くらいでcoppersmith methodをすると xが十分小さいので解けるように見えます。実際解けるっぽくて作問者writeupではそうなっていたんですが、私はパラメータの調整を雑にやった結果これでは解けないという誤った確信に至ったので別の方法をとりました。

ここで \mod 2^{470}をとると下式のようになり、未知数は k, qですが、 e \lt k e = 2003なので全探索すれば良さそうなので未知数は実質 qだけです。

 es \equiv 1 + k(q-1)(q+t-1)  \mod 2^{470}

これをいきなり解くのは難しいので*1、更に簡単にして \mod 2^mを考えます。

 es \equiv 1 + k(q-1)(q+t-1) \mod 2^m

すると十分小さい mの元では qの下位bitの候補が全探索できます。まず m=1 qの最下位bitの候補を2通り探索し、続いて m=2として下から2bit目の候補を探索します。候補数が 2^m個に増えそうですが、 qの下位bitと一致している場合は必ず等式が成り立つことを考えると、どこかのタイミングで上位bitの候補がなくなった場合は下位bitの選択がまちがっていたということなので捨ててよく、候補数はそんなに増えないことが期待できます*2

というように m 1から 470枝刈り全探索をやって残っていた候補はわずかなはずなので、そのなかで nを割り切れるやつが qです。というわけで qが求められたので、 r = q + tから rを、 n = pqrから pを求めて素因数分解が完了したのでRSAは解けました。

エクスプロイトはこう! 2冪で小さい方から枝刈り全探索というとTSG CTF 2019のOPQRXを思い出しますねとおもったけどこれは大きい方からだったか……

from Crypto.Util.number import inverse

t = 7062868051777431792068714233088346458853439302461253671126410604645566438638
e = 2003
n = 140735937315721299582012271948983606040515856203095488910447576031270423278798287969947290908107499639255710908946669335985101959587493331281108201956459032271521083896344745259700651329459617119839995200673938478129274453144336015573208490094867570399501781784015670585043084941769317893797657324242253119873
s = 1227151974351032983332456714998776453509045403806082930374928568863822330849014696701894272422348965090027592677317646472514367175350102138331
cipher = 82412668756220041769979914934789463246015810009718254908303314153112258034728623481105815482207815918342082933427247924956647810307951148199551543392938344763435508464036683592604350121356524208096280681304955556292679275244357522750630140768411103240567076573094418811001539712472534616918635076601402584666

qs = []

def dfs(sz, qbits, k):
    if sz == 470:
        qs.append(qbits)
        return

    if sz > 256 and qbits.bit_length() > 256:
        return

    q1 = qbits
    q2 = qbits | (1 << sz)

    a = e*s % 2**(sz+1) == (1 + k*(q1-1)*(q1+t-1)) % 2**(sz+1)
    b = e*s % 2**(sz+1) == (1 + k*(q2-1)*(q2+t-1)) % 2**(sz+1)
    if a:
        dfs(sz + 1, q1, k)
    if b:
        dfs(sz + 1, q2, k)

for k in range(1, e):
    dfs(0, 0, k)

for q in qs:
    if n % q != 0:
        continue
    r = q + t
    p = n // (q*r)
    phi = (p - 1) * (q - 1) * (r - 1)
    e = 2003
    d = inverse(e, phi)

    m = pow(cipher, d, n)
    print(bytes.fromhex(hex(m)[2:]))

*1:SageはHensel's liftを使ってこういうのを解く方法も提供しているらしくそれでも解けそうでした https://twitter.com/nuo_chocorusk/status/1533324083135324160

*2:具体的にどのくらいに抑えられるのかは知りません。なんかやったらうまくいったので……