Plaid CTF 2022 pressure writeup

この土日はPlaid CTF 2022に出ていました。久しぶりにかなり頑張って張り付いた結果一問解くことができたのでwriteupです。

Plaid CTFは歴史ある高難易度CTFとして知られていて問題を解けて嬉しい。

overview

ed25519を用いた一種のDiffie Hellman鍵共有のようなプロトコルが実装されています。pynaclを使った実装になっていて丁寧だけど読みづらい。

from nacl.bindings.crypto_scalarmult import (
  crypto_scalarmult_ed25519_noclamp,
  crypto_scalarmult_ed25519_base_noclamp,
)
from nacl.bindings.crypto_core import (
  crypto_core_ed25519_scalar_mul,
  crypto_core_ed25519_scalar_reduce,
  crypto_core_ed25519_is_valid_point,
  crypto_core_ed25519_NONREDUCEDSCALARBYTES,
  crypto_core_ed25519_BYTES
)
import struct
import os
import ast
import hashlib
import random

def sha512(b):
  return hashlib.sha512(b).digest()

CONST = 4096

SECRET_LEN = int(random.randint(128, 256))
SECRET = [random.randint(1, 255) for i in range(SECRET_LEN)]

with open('flag', 'r') as f:
  FLAG = f.read()

def hsh(s):
  h = sha512(s)
  assert len(h) == crypto_core_ed25519_NONREDUCEDSCALARBYTES
  return crypto_scalarmult_ed25519_base_noclamp(crypto_core_ed25519_scalar_reduce(h))


def generate_secret_set(r):
  s = set()
  for (i, c) in enumerate(SECRET):
    s.add(hsh(bytes(str(i + 25037 * r * c).strip('L').encode('utf-8'))))
  return s


def genr():
  i = 0
  while i == 0:
    i, = struct.unpack('<I', os.urandom(4))
  return i


def handle_client1():
  print("Let's see if we share anything! You be the initiator this time.")
  r = genr()
  s = generate_secret_set(r)
  for k in range(1, CONST):
    s.add(hsh(bytes(str(k + CONST * (r % k)).strip('L').encode('utf-8'))))
  b = crypto_core_ed25519_scalar_reduce(os.urandom(crypto_core_ed25519_NONREDUCEDSCALARBYTES))
  server_s = set(crypto_scalarmult_ed25519_noclamp(b, e) for e in s)

  client_s = set()
  print("Send your data!")
  got = ast.literal_eval(input())
  for e in got:
    if not crypto_core_ed25519_is_valid_point(e):
      print("Bad client!")
      exit()

    client_s.add(e)

  server_combined_client = set(
    crypto_scalarmult_ed25519_noclamp(b, e) for e in client_s
  )

  client_resp1 = [e for e in server_combined_client]
  client_resp2 = [e for e in server_s]
  random.shuffle(client_resp1)
  random.shuffle(client_resp2)
  print(repr(client_resp1))
  print(repr(client_resp2))

  return r, s

def handle_client2(r, s):
  print("Let's see if we share anything! I'll be the initiator this time.")
  b = crypto_core_ed25519_scalar_reduce(os.urandom(crypto_core_ed25519_NONREDUCEDSCALARBYTES))
  server_s = set(crypto_scalarmult_ed25519_noclamp(b, e) for e in s)
  to_client = [e for e in server_s]
  random.shuffle(to_client)
  print(repr(to_client))

  client_s = set()
  print("Send client points: ")
  got = ast.literal_eval(input())
  for e in got:
    if not crypto_core_ed25519_is_valid_point(e):
      print("Bad client!")
      exit()

    client_s.add(e)

  masked_s = set()
  print("Send masked server points: ")
  got = ast.literal_eval(input())
  for e in got:
    if not crypto_core_ed25519_is_valid_point(e):
      print("Bad client!")
      exit()

    masked_s.add(e)

  if len(masked_s) != len(server_s):
    print("Bad client!")
    exit()

  if masked_s & server_s:
    print("Bad client!")
    exit()

  masked_c = set(crypto_scalarmult_ed25519_noclamp(b, e) for e in client_s)
  if masked_c == masked_s:
    print(FLAG)
  else:
    print("Aw, we don't share anything.")

def main():
  r, s = handle_client1()
  handle_client2(r, s)

if __name__ == "__main__":
  main()

は32bit（！）の乱数で、は

という集合です。最初にed25519上の点の集合を送り、その後256bit程度の乱数を用いた と 、 がもらえます。 となるような点の集合を求めることができればフラグを取得できます。ただしかつである必要があります。

方針

最終的な目的を達成するためにはの具体的な値を知ることが不可欠なので、まずはを求めたいというのが自然な発送に見えます。そしてが4バイトと小さいことから、まずはを求め、その後をを用いて算出することになりそうです。

rを求める

を求めるためにはとをうまく使う必要がありそうです。

のうちの部分はが用いられていて未知の値はだけで、未知と言っても候補の列挙が十分できる程度なのでこれが使えそうです。具体的にはから複数のについての剰余を求めて中国剰余定理でを復元できます。

たとえばこちら側でを用意しておけば、がに含まれていればであり、がに含まれていればであるということがわかるといった具合です。

ただし、たとえばとしても返ってきたでは未知数が掛けられていてどちらがでどちらがに相当するのかはわからなくなっています。2通り程度なら両方のパターンを試すこともできますが、全ての剰余についてそれをやっていては32bitの全探索をやっているのと同じです。

そこでと送った点の集合との対応を探す必要があります。ここで、仮にの場合の点に対応するがわかっているとすると、 であることからに一致する点があればそれがであると判断することができます。

の全ての点についてその点がであると仮定して上記のようにとを求め、もしどちらかが内に存在すれば、仮定が正しいと判断することができ、を見つけ出すことができます。がわかれば、同じ要領で対応付けを行うことでの点との点の対応を求めることができます。

あとはの点のうちに含まれるものからがわかるので、を計算することができます。の計算には比較的大きい剰余が３つもあれば十分です。

points = [
    hsh(str(1 + CONST*0).encode()),
    hsh(str(2 + CONST*0).encode()),
    hsh(str(2 + CONST*1).encode()),
]

for k in [4091, 4093, 4905]:
    for rem in range(k):
        points.append(hsh(str(k + CONST*rem).encode()))

sock.sendlineafter("data!\n", repr(points))  # Aを送っている

xs = ast.literal_eval(sock.recvline().decode())  # {b*P | P in A}
ys = set(ast.literal_eval(sock.recvline().decode())) # {b*P | P in s}

inv = crypto_core_ed25519_scalar_invert(h_int(str(1 + 4096*0).encode()))
k_0 = crypto_core_ed25519_scalar_mul(inv, h_int(str(2 + 4096*0).encode()))
k_1 = crypto_core_ed25519_scalar_mul(inv, h_int(str(2 + 4096*1).encode()))

pairs = []
P1_idx = None
for i, P1 in enumerate(xs):
    bX = crypto_scalarmult_ed25519_noclamp(k_0, P1)
    bY = crypto_scalarmult_ed25519_noclamp(k_1, P1)

    if not (bX in ys or bY in ys):
        continue

    # bXあるいはbYが見つかったということは仮定が正しく、P1を見つけることができた
    P1_idx = i

    # get r mod k
    for k in [4091, 4093, 4095]:
        for rem in range(k):
            krem = crypto_core_ed25519_scalar_mul(
                inv,
                h_int(str(k + CONST*rem).encode()),
            )
            bkremG = crypto_scalarmult_ed25519_noclamp(krem, P1)
            if bkremG in ys:
                pairs.append((rem, k))
                break
assert len(pairs) == 3
r, _ = crt(pairs)
print("[+] found r: {}".format(r))

sを求める

で、もさほど大きくないので、同じ要領で候補を全てから計算してそれがに含まれるかどうかを見れば候補が正しいかどうかを判定できます。

# calculate s
s = []
for i in range(256):
    for c in range(1, 256):
        k = crypto_core_ed25519_scalar_mul(
            inv,
            h_int(str(i + 25037*r*c).encode()),
        )
        bkG = crypto_scalarmult_ed25519_noclamp(k, P1)
        if bkG in ys:
            s.append(hsh(str(i + 25037*r*c).encode()))

for k in range(1, CONST):
    key = crypto_core_ed25519_scalar_mul(
        inv,
        h_int(str(k + CONST * (r % k)).encode()),
    )
    kG = crypto_scalarmult_ed25519_noclamp(key, P1)
    if kG in ys:
        s.append(hsh(str(k + CONST * (r % k)).encode()))

assert len(s) == len(ys)
print("[+] found s")

送るべきB, Cを求める

かつ, であるようなを求めます。とできれば一番楽ですが、これは禁じられているので、かわりにとすればいいです。

exploit

完成したexploitがこちらになります。libsodiumの演算で点を定数倍するときのint -> bytesの変換に自身がなかったのでcrypto_core_ed25519_addを使っているのがおちゃめポイントです

from nacl.bindings.crypto_scalarmult import (
  crypto_scalarmult_ed25519_noclamp,
  crypto_scalarmult_ed25519_base_noclamp,
)
from nacl.bindings.crypto_core import (
  crypto_core_ed25519_add,
  crypto_core_ed25519_scalar_mul,
  crypto_core_ed25519_scalar_reduce,
  crypto_core_ed25519_scalar_invert,
  crypto_core_ed25519_is_valid_point,
  crypto_core_ed25519_NONREDUCEDSCALARBYTES,
  crypto_core_ed25519_BYTES
)
import hashlib
import struct
import os
from ptrlib import Socket, Process, crt
import ast

CONST = 4096

def sha512(b):
  return hashlib.sha512(b).digest()

def hsh(s):
  h = sha512(s)
  assert len(h) == crypto_core_ed25519_NONREDUCEDSCALARBYTES
  return crypto_scalarmult_ed25519_base_noclamp(crypto_core_ed25519_scalar_reduce(h))

def h_int(s):
  h = sha512(s)
  assert len(h) == crypto_core_ed25519_NONREDUCEDSCALARBYTES
  return crypto_core_ed25519_scalar_reduce(h)


# -- main
sock = Socket("nc pressure.chal.pwni.ng 1337")
p = Process(["bash", "-c", sock.recvline().decode()])
sock.sendline(p.recvlineafter("hashcash token: "))
p.close()
# sock = Socket("nc localhost 9999")

points = [
    hsh(str(1 + CONST*0).encode()),
    hsh(str(2 + CONST*0).encode()),
    hsh(str(2 + CONST*1).encode()),
]
for k in [4091, 4093, 4905]:
    for rem in range(k):
        points.append(hsh(str(k + CONST*rem).encode()))

sock.sendlineafter("data!\n", repr(points))

xs = ast.literal_eval(sock.recvline().decode())
ys = set(ast.literal_eval(sock.recvline().decode()))

inv = crypto_core_ed25519_scalar_invert(h_int(str(1 + 4096*0).encode()))
k_0 = crypto_core_ed25519_scalar_mul(inv, h_int(str(2 + 4096*0).encode()))
k_1 = crypto_core_ed25519_scalar_mul(inv, h_int(str(2 + 4096*1).encode()))

pairs = []
hG_idx = None
for i, hG in enumerate(xs):
    # assume hG as b*h(1)*G
    bk0G = crypto_scalarmult_ed25519_noclamp(k_0, hG)
    bk1G = crypto_scalarmult_ed25519_noclamp(k_1, hG)

    if not (bk0G in ys or bk1G in ys):
        continue
    # base is found
    hG_idx = i

    # get r mod k
    for k in [4091, 4093, 4095]:
        for rem in range(k):
            krem = crypto_core_ed25519_scalar_mul(
                inv,
                h_int(str(k + CONST*rem).encode()),
            )
            bkremG = crypto_scalarmult_ed25519_noclamp(krem, hG)
            if bkremG in ys:
                pairs.append((rem, k))
                break
assert len(pairs) == 3
r, _ = crt(pairs)
print("[+] found r: {}".format(r))

hG = xs[hG_idx]

# calculate s
s = []
for k in range(1, CONST):
    key = crypto_core_ed25519_scalar_mul(
        inv,
        h_int(str(k + CONST * (r % k)).encode()),
    )
    kG = crypto_scalarmult_ed25519_noclamp(key, hG)
    if kG in ys:
        s.append(hsh(str(k + CONST * (r % k)).encode()))


for i in range(256):
    for c in range(1, 256):
        k = crypto_core_ed25519_scalar_mul(
            inv,
            h_int(str(i + 25037*r*c).encode()),
        )
        bkG = crypto_scalarmult_ed25519_noclamp(k, hG)
        if bkG in ys:
            s.append(hsh(str(i + 25037*r*c).encode()))
assert len(s) == len(ys)
print("[+] found s")


# handle_client2
sock.recvlineafter("this time.")
b_server_s = ast.literal_eval(sock.recvline().decode())

sock.sendlineafter("client points: \n", repr([crypto_core_ed25519_add(e, e) for e in s]))  # 2*s
# masked_c = b*2*s
sock.sendlineafter("masked server points: \n", repr([crypto_core_ed25519_add(e, e) for e in b_server_s]))  # b*s + b*s = 2b*s

sock.interactive()

感想

主にpynaclとlibsodiumのAPIについての情報が少なかったこと、変数の命名に失敗して*1で時間を取られて結局4時間〜5時間くらい掛けました。もっと整ってたら半分の時間で解けたはず……。序盤はlibsodiumがわかりづらすぎてブチ切れてたけど終わってみたら面白かったです

*1:渡されたスクリプトの命名が悪いんですけど

LINE CTF 2022 crypto challenges writeup

昨年に引き続きLINE CTF 2022が開催されました。企業がこういうCTFを開いてくれるのは嬉しいことですね。昔はFacebookとかKasperskyもCTFを開いていた気がしたけど、いつからなくなってしまったのか……。

私はzer0ptsとして出場して、チームでは6位でした。結構調子が良いように思われたけど上はまだ遠いですね。

個人としてはCryptoの問題に取り組んで全部解いたのでwriteupを書きます

ss-puzzle

この問題の本質は下の2行の式だけです。S・Rはそれぞれフラグの前半と後半を8バイトごとに分割したブロックで、フラグがLINECTF{...} のフォーマットに従っていることから、S[0] = b"LINECTF{" であることだけがわかっています。

Share[1] = xor(R[0], S[0]) + b"xxxxxxxx\0\0\0\0\0\0\0\0"  + xor(R[2], S[3]) + xor(R[3],S[2])
Share[4] = xor(R[0], S[3]) + xor(R[1], S[2]) + xor(R[2], S[1]) + xor(R[3],S[0])

この問題は単純なxorパズルなので、既知の値から未知の値を一つずつ導き出せば全部解けます。

from ptrlib import chunks, xor

with open("./Share1", "rb") as f:
    Share1 = chunks(f.read(), 8)

with open("./Share4", "rb") as f:
    Share4 = chunks(f.read(), 8)

S0 = b"LINECTF{"
R0 = xor(Share1[0], S0)
S3 = xor(Share4[0], R0)
R3 = xor(Share4[3], S0)
S2 = xor(Share1[3], R3)
R1 = xor(Share4[1], S2)
R2 = xor(Share1[2], S3)
S1 = xor(Share4[2], R2)

print(S0 + S1 + S2 + S3 + R0 + R1 + R2 + R3)

X Factor

I have generated a RSA-1024 key pair:
* public key exponent: 0x10001
* public key modulus: 0xa9e7...9c5b3

Here are some known plain -> signature pairs I generated using my private key:
* 0x945d86b04b2e7c7 -> 0x17b...d4
* 0x5de2 -> 0x3ea...de50
* 0xa16b201cdd42ad70da249 -> 0x9...3a
* 0x6d993121ed46b -> 0x2...7c
* 0x726fa7a7 -> 0xa...eb
* 0x31e828d97a0874cff -> 0x67...ffd
* 0x904a515 -> 0x9...e4a

**What is the signature of 0x686178656c696f6e?**

Take the least significant 16 bytes of the signature, encode them in lowercase hexadecimal and format it as `LINECTF{sig_lowest_16_bytes_hex}` to obtain the flag.
E.g. the last signature from the list above would become `LINECTF{174c96f2c629afe74949d97918cbee4a}`.

長い値は適当に省略していますが、上記のようなテキストが与えられます。これは個人の意見だけど、こういうパースしづらい形で値を渡すのなんの意味もないんでやめてほしいですね。何をするべきかも今回は自然言語で与えられているけど、どうしても書かれていない何かがあるのではと疑うことになるのでソースコードとかで曖昧性をなくしてほしい。実際に運営もたくさんclarを受け取るはめになっていたようだし。

さて今回の問題ですが、適当な のペアが数組与えられていて、特定のに対してを求めよ、という問題です。当然の値はわからないので愚直に求めることはできません。適当な組が事前に与えられていることからRSAの乗法準同型性を使うのだろうと推測できます。

乗法準同型性は要するにという特性で、事前に与えられているどうしを掛けたり割ったりしてを作ることができれば、同じ操作をに対して行えばが求められます。

はい

ms = [QQ(m) for m in [0x945d86b04b2e7c7, 0x5de2, 0xa16b201cdd42ad70da249, 0x6d993121ed46b, 0x726fa7a7, 0x31e828d97a0874cff, 0x904a515]]
n = 0xa9e7da28ebecf1f88efe012b8502122d70b167bdcfa11fd24429c23f27f55ee2cc3dcd7f337d0e630985152e114830423bfaf83f4f15d2d05826bf511c343c1b13bef744ff2232fb91416484be4e130a007a9b432225c5ead5a1faf02fa1b1b53d1adc6e62236c798f76695bb59f737d2701fe42f1fbf57385c29de12e79c5b3

cs = [0x17..., 0x3e..., 0x94..., 0x2b... 0xa7..., 0x67..., 0x92...]

t = 0x686178656c696f6e

from itertools import product

for pat in product([-2, -1, 0, 1, 2], repeat=len(ms)):
    s = 1
    for i, e in enumerate(pat):
        s *= ms[i] ** e
    if s == t:
        print(pat)

        s = 1
        for i, e in enumerate(pat):
            s = s * pow(cs[i], e, n) % n
        print("LINECTF{{{:016x}}}".format(int(s) % 2**(8*16)))

        quit()

Baby crypto revisited

この問題きらいです。LINE CTF 2021で出題されたbabycrypto4のリベンジ問題なのですが、nonceのうち不明な値が16bitから32bit64bit*1になっただけです。16bitで出題したときはnonceの不明な値を全探索するという解法が横行したから、ということなのでしょうが、32bitも十分全探索の圏内だし、去年の問題から何も変えてないんだから去年の問題を知ってる人は全探索以外の方法で解いているスクリプトを見つけ出して貼り付けるだけで解けます。実際私も去年解いた時のスクリプトを拾ってきて貼り付けたら解けました。あきらかにCTFアンチパターンです。運営は https://bit.ly/ctf-design の"Challenge Reuse and Multi-flag Tasks"の項を読んでないんか？？

ということでこの問題はECDSAの（いわゆるnonce）の未知部分が非常に小さいことから、LLLでCVPを解けば未知部分を求められ、解けます。

from hashlib import sha1

# 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())


r = []
s = []
k = []
h = []
with open("Babycrypto_revisited_b1f108dea290b83253b80443260b12c3cadc0ed7.txt") as f:
    for line in f:
        a, b, c, d = [int(x, 16) for x in line.strip().split(" ")]
        r.append(a)
        s.append(b)
        k.append(c)
        h.append(d)

R = E.lift_x(Integer(r[0]))
P = inverse_mod(r[0], n) * (s[0]*R - h[0]*G)

nonce_max = 2**64

def sign(msg):
    h = int(sha1(msg).hexdigest(), 16)
    while True:
        k = randint(2, nonce_max-1)
        if gcd(k, n) == 1:
            break

    r = int((h * G).xy()[0])
    s = (h + r*d) * inverse_mod(k, n) % n
    return (r, s)

N = len(r)
t = [r[i] * inverse_mod(s[i], n) % n for i in range(N)]
u = [h[i] * inverse_mod(-s[i], n) % n for i in range(N)]

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 = abs(row[0])
    x = (k1*s[0] - h[0]) * inverse_mod(r[0], n) % n
    if x*G == P:
        # print(x, k1) # find private key
        print(hex(x))

Forward or

問題名で解法を示唆するスタンスは私は嫌いです。

さて問題を見ていくと、一部省略して次のような感じです。

from present import Present
from Crypto.Util.strxor import strxor
import os, re

class CTRMode():
    def __init__(self, key, nonce=None):
        ...
    
    def XorStream(self, data):
       ...

    def encrypt(self, plaintext):
        return self.XorStream(plaintext)

    def decrypt(self, ciphertext):
        return self.XorStream(ciphertext)

class DoubleRoundReducedPresent():

    def __init__(self, key):
        ...
        self.cipher0 = Present(key[0:10], self.round)
        self.cipher1 = Present(key[10:20], self.round)

    
    def encrypt(self, plaintext):
        ...
        return self.cipher1.encrypt(self.cipher0.encrypt(plaintext))
    
    def decrypt(self, ciphertext):
        ...


if __name__ == "__main__":
    import sys, os
    sys.path.append(os.path.join(os.path.dirname(__file__), './secret/'))
    from keyfile import key
    from flag import flag

    # load key
    if not re.fullmatch(r'[0-3]+', key):
        exit(1)
    key = key.encode('ascii')

    # load flag
    flag = flag.encode('ascii') # LINECTF{...}

    plain = flag
    cipher = CTRMode(key)
    ciphertext = cipher.encrypt(plain)
    nonce = cipher.nonce

    print(ciphertext.hex())
    print(nonce.hex())

Presentというブロック暗号を使って、独自にDoubleRoundReducedPresent というブロック暗号のクラスを生成し、これをつかってCTRモードでフラグを暗号化しています。

注目するべきはkeyの候補が通りしかなく、それらは通りづつに分けられてcipher1とcipher2に使われているということと、DoubleRoundReducedPresent では暗号化にself.cipher1.encrypt(self.cipher0.encrypt(plaintext)) というロジックを採用しているということです。

こういう場合、平文と暗号文の組を一つ知っているときにMeet in the Middle攻撃*2によって鍵を探索することができます。

Meet in the Middle攻撃のアイデアは簡単で、一方では鍵を全探索しながら平文を暗号化し、もう一方でも鍵を全探索しながらこちらは暗号文を復号していきます。探索の途中でとある鍵による復号の結果が、とある鍵による暗号の結果と一致すればその鍵のペアが探していたものです。今回の場合はこれで鍵の探索を通りから通りを2回に減らすことができます。詳しくは CTF crypto 逆引き - ふるつき に書いた……と思ったら何も書いていなかったので今度埋めておきます。

とにかくこういう感じで解けます。

from present import Present
from ptrlib import xor
from itertools import product
from main import CTRMode
from tqdm import tqdm

ciphertext_hex="3201339d0fcffbd152f169ddcb8349647d8bc36a73abc4d981d3206f4b1d98468995b9b1c15dc0f0"
nonce_hex="32e10325"

ciphertext = bytes.fromhex(ciphertext_hex)
nonce = bytes.fromhex(nonce_hex)

key1 = xor(b"LINECTF{", ciphertext)
plain = nonce + (0).to_bytes(4, "big")

table = {}
print("forward...")
for pat in tqdm(product("0123", repeat=10)):
    k = "".join(pat).encode()
    cipher = Present(k, 16)
    table[cipher.encrypt(plain)] = k

print("backward...")
key = None
for pat in tqdm(product("0123", repeat=10)):
    k = "".join(pat).encode()
    cipher = Present(k, 16)
    x = cipher.decrypt(key1)
    if x in table:
        print("found")

        key = table[x] + k
        break

if key is None:
    quit()


ctr = CTRMode(key, nonce)
print(ctr.decrypt(ciphertext))

lazy-STEK

go言語のソースコードとpcapngが渡されます。ややこしいので省略しつつ、この場合は3条項BSDライセンスに従ってライセンス部分は削らない必要があるのかな……。

実装されているのは簡単なTLSのサーバプログラムです。まずはmain部分でセッションチケットの暗号化に使われるSessionTicketKeysが何やら不自然な作られ方になっています

...
func main() {
    var key0 [32]byte
    var key1 [32]byte
    var zero_value = [16]byte{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}

    // Generate key0
    _, err := rand.Read(key0[:])
    ...

    // I'm lazy, so I generate key1 from key0. key1 = SHA256( AES_ECB_ENC(0, SHA512(key0)[16:32]) )
    tmp_value := sha512.Sum512(key0[:])
    key0_ticket_encryption_aes_key := tmp_value[16:32]

    block, err := aes.NewCipher(key0_ticket_encryption_aes_key)
    ...
    ecb_mode := ecb.NewECBEncrypter(block)
    ecb_mode.CryptBlocks(key1[:16], zero_value[:])

    key1 = sha256.Sum256(key1[:16])

    ...
    cfg := &tls.Config{
        Certificates: []tls.Certificate{cert},
    }
    cfg.SetSessionTicketKeys([][32]byte{
        key0,
        key1,
    })
    ...
}
...

TLSのロジックに手を加えたと思しき部分も渡されています。

//This patch is provided under the 3-Clause BSD License, the original license of Golang.

/*
Copyright (c) 2009 The Go Authors. All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

   * Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.
   * Redistributions in binary form must reproduce the above
copyright notice, this list of conditions and the following disclaimer
in the documentation and/or other materials provided with the
distribution.
   * Neither the name of Google Inc. nor the names of its
contributors may be used to endorse or promote products derived from
this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

// This code was created based on src/crypto/tls/ticket.go (L131-L200) in Go1.7.1.
// original: https://github.com/golang/go/blob/go1.7.1/src/crypto/tls/ticket.go#L132-L200
// If you want to experiment with this patch, please use a virtual environment that you can throw away, such as Docker.
// e.g. https://hub.docker.com/layers/golang/library/golang/1.17.1/images/sha256-8f4773d3be4e83da2198ae437191f8d9dffb30507714f0b727d0daf222377886

const FLAG string = "LINECTF{...}"

func (c *Conn) encryptTicket(state []byte) ([]byte, error) {
    ...
    // write FLAG in certicicate
    new_state := make([]byte, len(state)+len([]byte(FLAG)))
    sessionState := new(sessionStateTLS13)
    if ok := sessionState.unmarshal(state); !ok {
        return nil, errors.New("tls: failed to unmarshal ticket data")
    }
    sessionState.certificate.Certificate = append(sessionState.certificate.Certificate, []byte(FLAG))
    new_state = sessionState.marshal()

    ...
    // Select Session Ticket Encryption Key (STEK).
    // aesKey is generated with following formula
    // aesKey = SHA512(STEK)[16:32]
    // ref: https://github.com/golang/go/blob/go1.17.1/src/crypto/tls/common.go#L758-L764
    rand.Seed(time.Now().UnixNano())
    index := rand.Intn(2)
    key := c.ticketKeys[index]

    copy(keyName, key.keyName[:])
    block, err := aes.NewCipher(key.aesKey[:])
    ...

    // I'm lazy, so I generate IV from aesKey.
    h := sha256.New()
    h.Write(key.aesKey[:])
    iv = h.Sum(nil)[:16]
    if 0 == index {
        copy(iv[12:], []byte{0xaa, 0xaa, 0xaa, 0xaa})
    } else {
        copy(iv[12:], []byte{0xbb, 0xbb, 0xbb, 0xbb})
    }
    copy(encrypted[ticketKeyNameLen:ticketKeyNameLen+aes.BlockSize], iv[:16])

    aesgcm, err := cipher.NewGCM(block)
    ...

    // AES-128-GCM_ENC(nonce=iv[:12](12-octet), plaintext=raw_ticket, aad=keyName(16-octet)+iv(16-octet))
    ciphertext := aesgcm.Seal(nil, iv[:12], new_state, encrypted[:ticketKeyNameLen+aes.BlockSize])
    copy(encrypted[ticketKeyNameLen+aes.BlockSize:], ciphertext)
    return encrypted, nil
}

func (c *Conn) decryptTicket(encrypted []byte) (plaintext []byte, usedOldKey bool) {
   ...
}

非常にややこしいですが、簡潔にまとめるとセッションチケットを暗号化する部分が次のようなロジックになっています。

• 鍵keyをkey0またはkey1からランダムに選択する
• AES-GCMを用いてnew_stateをkeyとiv=sha256(key)[:12]で暗号化する。nwe_stateにはフラグが含まれており、これを復号するのが目的

親切にivにaaaaaaaaまたはbbbbbbbbという特徴的なバイト列を挿入していますので、これをもとにpcapファイルを検索すると、key0を用いて暗号化されたものが2つ、key1を用いて暗号化されたものが1つあることがわかります。

さて、今回の問題でなにをすればよいかですが、new_stateを復号したいという目的がある以上、key0またはkey1の具体的な値を求めることになるはずです。そして、key0はランダムに生成されているため求めることは難しそうです。一方key1はsha512(key0)[16:32]という鍵を用いたAESでを暗号化したものに対してさらにsha256をとったものになっており、何らかの手法を用いてkey1の具体的な値を求められそうです。

どうやってそれを求めるかですが、先にいくつかの事実を把握しておく必要があります。

まずひとつ目は、encryptTicket関数中のコメントで触れられているようにaesKey（AES-GCMで用いられる鍵）はsha512(key0)[16:32]またはsha512(key1)[16:32]という形になっているということです。sha512(key0)[16:32]という形はkey1の導出にも出てきましたから、aesKeyの具体的な値か、この鍵を用いたAESでを暗号化した値が得られれば、key1の具体的な値を求めることができそうです。

ふたつ目はAES-GCMについてです。AES-GCMはAES-CTRと同じ暗号化を施したあとで、多項式の計算を用いて暗号文が改ざんされていないことを示すためのタグを付加します。タグの計算の詳細については省略しますが、ここで使われるという値はAESでを暗号化して計算されます。つまり、このを求めることができれば、key1 = sha256(H)としてkey1が計算できそうです。

そしてAES-GCMで同じ鍵、同じnonceを使っている場合にHを求めることができるというのは比較的よく知られた事実です。詳しくは 本当は怖いAES-GCMの話 - ぼちぼち日記 をご覧ください。

さてこれで方針が立ちました。key0とそれを用いて導出されたnonceを使って暗号化された２つの暗号文からHを求め、そのHからkey1を計算して、key1を用いて暗号文を復号してやれば良さそうです。

めちゃめちゃ説明した割にはソルバはこれだけ。

from ptrlib import chunks
from Crypto.Cipher import AES
from hashlib import sha256, sha512

c1 = bytes.fromhex("e875cec70f64aac0de67af2caaaaaaaa450abecfee723cdbe4393bbcf56add91e283615eaa6a5899906a138ce3dbe632ab778328029499c12eceefa0589945f7f3801748be3daa06ace2e682a77649da535f7235aa7ecb60bf0e3d6b7c1012e192411e29e6494c2fa05ce2c5d08d4698a05ffb5fa9ad2b2550737cea3b19ccacfdd93e7d3c3f6e641d5f8793b17261047b160c9acaf891577ef7")
c2 = bytes.fromhex("e875cec70f64aac0de67af2caaaaaaaa450abecfee723cdbe4393bbce26a50c35bd4b250c5395150b62c27d76e20535dea6a129d08c1c31e89475b79d36e45f7f3801748be3daa06ace2e682a77649da535f7235aa7ecb60bf0e3d6b7c1012e192411e29e6494c2fa05ce2c5d08d4698a05ffb5fa9ad2b2550737cea3b19ccacfdd93e7d3c3f6e641d5f1f668e1af6844a40e4cbdb6132cbd395")
c3 = bytes.fromhex("c336d16a10aac82969a59560bbbbbbbb6fe550ba6db4b6a2af74f6f0454d82d959daa387f694685dec4c1ff7c36e40d3b9fe6e4fd41596035a594f8b599b89c47c84aa66d6d63ef3999de5041f0c3b7598b1811012399575a0c442c1c364f669ecf7fd5dfbb06bc37fd830c03e3dde20c98bc747d74d0ac196936f364c2e81338fca4bdb193d52e19f23295fc9e7546288a7464baa258fcd5542")

iv1, c1, t1 = c1[:16], c1[16:-16], c1[-16:]
iv2, c2, t2 = c2[:16], c2[16:-16], c2[-16:]
iv3, c3, t3 = c3[:16], c3[16:-16], c3[-16:]

F.<a> = GF(2**128,  modulus=x**128 + x**7 + x**2 + x + 1)
PR.<x> = PolynomialRing(F)

def to_poly(x):
    bs = Integer(int.from_bytes(x, "big")).bits()[::-1]
    return F([0] * (128 - len(bs)) + bs)

def to_bytes(poly):
    return int(bin(poly.integer_representation())[2:].zfill(128)[::-1], 2).to_bytes(16, "big")

b1 = [to_poly(block) for block in chunks(c1, 16)][::-1]
b2 = [to_poly(block) for block in chunks(c2, 16)][::-1]

f = sum((a + b)*x**(i + 2) for i, (a, b) in enumerate(zip(b1, b2))) + to_poly(t1) + to_poly(t2)

for r, _ in f.roots():
    # r == AES.new(key=sha512(key0)[16:32]).encrypt(b"\0" * 16)
    key1 = sha256(to_bytes(r)).digest()
    aesKey = sha512(key1).digest()[16:32]

    if sha256(aesKey).digest()[:12] == iv3[:12]:
        print("!!", sha256(aesKey).hexdigest())

        aesgcm = AES.new(key=aesKey, mode=AES.MODE_GCM, nonce=iv3[:12])
        print(aesgcm.decrypt(c3))
        break

else:
    print(":thinking_face:")

全体的にもうちょっと簡潔にまとめらそうな雰囲気はあるけどできてない

*1:https://twitter.com/xrekkusu/status/1507932079635726336

*2:競技プログラミングでは半分全列挙と呼ばれるテクニックと同じものです

zer0pts CTF 2022 作問振り返り

zer0pts CTF 2022で出題した問題について軽く振り返ります。解き方を懇切丁寧に書いたりはしてないです。もし私が出題した問題の解法について詳しく知りたければ y011d4さんによるwriteup や BaaaaaaaarkingDogさんによるwriteup、今後リリース予定の公式writeup（英語）をご覧ください。また、zer0pts CTF 2022で出題した問題はすべて以下のリポジトリで公開しています。

github.com

ptr-yudaiは問題セットを作る上でこだわりを持ってうまく楽しめるように工夫しているということが zer0pts CTF 2022開催記 - CTFするぞ に書かれていましたが、私の場合はそんなことを考える余裕はなく、とにかくできるだけ面白くて学びのある問題を作ることで必死でした。

CurveCrypto

問題名が気に入らない問題その1です。楕円曲線上の点をと倍にしながら、そのxy座標にフラグをXORしたものを暗号として渡しています。

座標のサイズに対してフラグを分割したブロックがごく小さいので、もともとの座標の殆どの部分がわかっており、楕円曲線のの式にあてはめて適当にmultivariate Coppersmith's methodを使えばが復元できて簡単に解けます。multivariate Coppersmith's methodを知らない人は https://github.com/defund/coppersmith を眺めて見てください。2021年のCrypto問題を解く上では必携のスクリプトだったので今後も役に立つかもしれません。Crypto CTFプレイヤーにおすすめのVim Plugin 1選 - ふるつき で紹介しているVimプラグインを導入すればいつでも呼び出せて便利です。

もともと楕円曲線上の点に適当な誤差を足すとどうなるかというのを考えていて、xy座標両方あったら解けるじゃん*1ということを気がついて問題にならないかなということを言っていたらptr-yudaiがブロック暗号にするアイデアを出してくれました。

これはなかなか面白いぞと思っていたのに、完成したものを見返したらAeroCTF 2021で出題されたhorcruxの劣化版になっていたときはビビりましたが、horcurxは極めて複雑で難しい問題であること、他に類題がないことから出題してよかろうと判断しました。問題自体は面白いしね。現在まで特に怒られは発生していません。助かった。

というわけですのでCurveCryptoが解けた人はAeroCTF 2021のhorcruxにも挑戦してみると良いかもしれません。

EDDH

問題名が気に入らない問題その2です。だいたい問題名が気に入らないときはその問題もあんまり気に入ってないです。というよりはよくできた問題には頑張っていい名前をつけようとするから、これはそうでない問題だったということですね。

何をやっているかというといわゆる楕円曲線Diffie-Hellman鍵共有、いわゆるECDHなのですが、一般的な楕円曲線ではなくtwisted Edwards Curveという曲線を使っています。twisted Edwards CurveはEdDSAという電子署名アルゴリズムなどで使われています。例えば最近はSSH鍵を作るときに鍵のタイプにed25519と指定することがあるかと思いますが、ここで使われているのがEdDSA、ひいてはtwisted Edwards Curveです。

今回の問題ではtwisted Edwards Curve上の演算を自前で実装したうえで、与えられた点が曲線上にあるかどうかを確認しないことでdegenerate attackが行える、というのが脆弱性になっています。もはや群の演算を自前実装している問題は99%この種類の攻撃が想定解法であるといっても過言ではないと思います。degenerate attackというのはいわゆるinvalid curve attackのことですが、今回のケースにおいては「別の楕円曲線上での演算にしてしまう」ものではないため呼称が区別されています。

詳細はwriteupに譲りますが適当にを渡すとが計算され、今回の問題ではがsmoothな値であるため離散対数問題が解けます。

なんのひねりもない素直な問題になってしまったのは多少不満ですが*2、CurveCryptoとともにたくさん解かれていたので良かったです。あとフラグは多少Anti Fermatを意識して似た感じにしました。

OK

keymoon先生との合作です。Oblivious Transferはこれまでにも問題にしていますが、今回はRSA暗号を用いた実装について調べていて、これをどうにかできないかと思っていじりまわしていました。その結果となるような が多数与えられたときにが求まるか、という問題に帰着できそうということに気が付きました。

これが解けるかは頭をひねってもわからなかったのですが、もしかしたらと思いつつkeymoon先生にお見せしたところ「これはね、解けます」という力強いお言葉をいただき、無事問題に昇華されました。

私が形にした当初はの部分がASCII文字列だったため無理やりがちゃがちゃやって解ける感じだったのですが、これもkeymoon先生がすべていい感じにしてくれました。いやはや、頭が上がりません。

問題名や問題文、ダミーフラグやフラグはすべてアニメポケットモンスターのED曲「OK！」からとりました*3。おひさまとおつきさまがかわりばんこに顔を出してくれるところを、2つある平文のうちどちらか一方だけしか手に入らないOblivious Transferに重ねる着想はなかなか詩的で気に入っています。

Karen

eprintをなんとなく眺めていたところ、「これ解けるのまじか！」となって感動した問題を出題しています。要するに とすべての要素が0, 1からなるuniformly randomなn×m行列があるとき、のだけが与えられるのでとを求めて下さいという問題です。

この問題はHidden Subset Sumとして知られていて、Ngyuen-Sternのアルゴリズムの他にFastICAと呼ばれる独立主成分分析の手法でも解けるようです。

本当はこれらの手法を完全に理解した上でさらにひとひねりを加えたような問題を出題したいところではありましたが、理解が及ばなかったことやこれまであまり知られていない問題をさらに応用した問題をいきなり出しても苦痛の大きい問題になりそうなこと、最終的な問題のソースコードが非常にコンパクトにまとまってきれいだったことからそのまま出題しています。writeupを見ても問題の特性からうまくHidden Subset Sumという単語に辿り着いて解くというものがほとんどだったので*4、結果をみても狙い通りと言えます。

ところでかなりstraightforwardなまま出した理由は上記にあるように「これまであまり知られていない」からなのですが、maple3142さんのwriteup を拝見していたところ、AIS3 EOF Qualsという大会でこの１月に出題されていたようです。まじか……。これはハラキリ物の失態です。大変失礼しました。でもこのCTFは名前すら知らなかったので許してください……

問題名が意味しているのはきんいろモザイクの九条カレンさんです。Ngyuen-Sternのアルゴリズムの最初のステップであると直交するような格子の基底を求める部分がOrthogonal Lattice Attackという名前で、これから正規直交基底のポーズが連想されたのでKarenとしました。Surveyを見ている限りではこの問題名は好評な様子でよかったです。

*1:ちゃんと考えてないけどx座標だけの時どうなるんだろう。2倍の式から解けたりしますか？　解けそうな気もするな……

*2:"twisted" Edwards Curveなのでひとひねりされているという説もあります。ガハハ！

*3:なんとkeymoon先生はこの曲を知らないらしいです。まじか

*4:以前論文を読んでいたので思い出して見に行きました、という人もいてさすがでした