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

さて、問題ですが、適当な のペアが数組与えられていて、特定のに対してを求めよ、という問題です。当然の値はわからないので愚直に求めることはできません。適当な組が事前に与えられていることから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から32bitになっただけです。16bitで出題したときはnonceの不明な値を全探索するという解法が横行したから、ということなのでしょうが、32bitも十分全探索の圏内だし、去年の問題から何も変えてないんだから去年の問題を知ってる人はスクリプト見つけ出して貼り付けるだけです。実際私も去年解いた時のスクリプトを拾ってきて貼り付けたら解けました。あきらかにCTFアンチパターンです。運営は https://bit.ly/ctf-design の"Challenge Reuse and Multi-flag Tasks"の項を読んでないんか？？

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

from hashlib import sha1


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

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

    
    flag = flag.encode('ascii') 

    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攻撃*1によって鍵を探索することができます。

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}

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

    
    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のロジックに手を加えたと思しき部分も渡されています。

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

func (c *Conn) encryptTicket(state []byte) ([]byte, error) {
    ...
    
    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()

    ...
    
    
    
    
    rand.Seed(time.Now().UnixNano())
    index := rand.Intn(2)
    key := c.ticketKeys[index]

    copy(keyName, key.keyName[:])
    block, err := aes.NewCipher(key.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)
    ...

    
    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():
    
    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:")

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