LINE CTF 2022 crypto challenges writeup

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

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

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

ss-puzzle
X Factor
Baby crypto revisited
Forward or
lazy-STEK

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を受け取るはめになっていたようだし。

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

乗法準同型性は要するに $m_1^d * m_2^d \equiv (m_1 * m_2)^d \mod n$ という特性で、事前に与えられている $m_i$ どうしを掛けたり割ったりして $x$ を作ることができれば、同じ操作を $m_i^d \mod n$ に対して行えば $x^d \mod n$ が求められます。

はい

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

ということでこの問題はECDSAの $k$ （いわゆる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の候補が $4^{20}$ 通りしかなく、それらは $4^10$ 通りづつに分けられてcipher1とcipher2に使われているということと、DoubleRoundReducedPresent では暗号化にself.cipher1.encrypt(self.cipher0.encrypt(plaintext)) というロジックを採用しているということです。

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

Meet in the Middle攻撃のアイデアは簡単で、一方では鍵を全探索しながら平文を暗号化し、もう一方でも鍵を全探索しながらこちらは暗号文を復号していきます。探索の途中でとある鍵による復号の結果が、とある鍵による暗号の結果と一致すればその鍵のペアが探していたものです。今回の場合はこれで鍵の探索を $4^{20}$ 通りから $4^{10}$ 通りを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で $0$ を暗号化したものに対してさらにsha256をとったものになっており、何らかの手法を用いてkey1の具体的な値を求められそうです。

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

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

ふたつ目はAES-GCMについてです。AES-GCMはAES-CTRと同じ暗号化を施したあとで、多項式の計算を用いて暗号文が改ざんされていないことを示すためのタグを付加します。タグの計算の詳細については省略しますが、ここで使われる $H$ という値はAESで $0$ を暗号化して計算されます。つまり、この $H$ を求めることができれば、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:競技プログラミングでは半分全列挙と呼ばれるテクニックと同じものです