kakujiroのblog

日々のアウトプットとしての雑記帳。カテゴリが貯まればそのうちHPに移行するかも。

LINE CTF 2022

CTF

zer0ptsCTFの復習が終わらぬまま１週間後に再びCTF。今回もcrypt限定で解いた。全５問で４問解けたのでまあまあではないでしょうか。最後の１問はgoで書かれてたので何も分からず。なお他分野と合わせても序盤でかなりcryptが解かれてたので今年は簡単だったのかも。。。

X Factor

I have generated a RSA-1024 key pair:
* public key exponent: 0x10001
* public key modulus: 0xa9e7da28ebecf1f88efe012b8502122d70b167bdcfa11fd24429c23f27f55ee2cc3dcd7f337d0e630985152e114830423bfaf83f4f15d2d05826bf511c343c1b13bef744ff2232fb91416484be4e130a007a9b432225c5ead5a1faf02fa1b1b53d1adc6e62236c798f76695bb59f737d2701fe42f1fbf57385c29de12e79c5b3

Here are some known plain -> signature pairs I generated using my private key:
* 0x945d86b04b2e7c7 -> 0x17bb21949d5a0f590c6126e26dc830b51d52b8d0eb4f2b69494a9f9a637edb1061bec153f0c1d9dd55b1ad0fd4d58c46e2df51d293cdaaf1f74d5eb2f230568304eebb327e30879163790f3f860ca2da53ee0c60c5e1b2c3964dbcf194c27697a830a88d53b6e0ae29c616e4f9826ec91f7d390fb42409593e1815dbe48f7ed4
* 0x5de2 -> 0x3ea73715787028b52796061fb887a7d36fb1ba1f9734e9fd6cb6188e087da5bfc26c4bfe1b4f0cbfa0d693d4ac0494efa58888e8415964c124f7ef293a8ee2bc403cad6e9a201cdd442c102b30009a3b63fa61cdd7b31ce9da03507901b49a654e4bb2b03979aea0fab3731d4e564c3c30c75aa1d079594723b60248d9bdde50
* 0xa16b201cdd42ad70da249 -> 0x9444e3fc71056d25489e5ce78c6c986c029f12b61f4f4b5cbd4a0ce6b999919d12c8872b8f2a8a7e91bd0f263a4ead8f2aa4f7e9fdb9096c2ea11f693f6aa73d6b9d5e351617d6f95849f9c73edabd6a6fde6cc2e4559e67b0e4a2ea8d6897b32675be6fc72a6172fd42a8a8e96adfc2b899015b73ff80d09c35909be0a6e13a
* 0x6d993121ed46b -> 0x2b7a1c4a1a9e9f9179ab7b05dd9e0089695f895864b52c73bfbc37af3008e5c187518b56b9e819cc2f9dfdffdfb86b7cc44222b66d3ea49db72c72eb50377c8e6eb6f6cbf62efab760e4a697cbfdcdc47d1adc183cc790d2e86490da0705717e5908ad1af85c58c9429e15ea7c83ccf7d86048571d50bd721e5b3a0912bed7c
* 0x726fa7a7 -> 0xa7d5548d5e4339176a54ae1b3832d328e7c512be5252dabd05afa28cd92c7932b7d1c582dc26a0ce4f06b1e96814ee362ed475ddaf30dd37af0022441b36f08ec8c7c4135d6174167a43fa34f587abf806a4820e4f74708624518044f272e3e1215404e65b0219d42a706e5c295b9bf0ee8b7b7f9b6a75d76be64cf7c27dfaeb
* 0x31e828d97a0874cff -> 0x67832c41a913bcc79631780088784e46402a0a0820826e648d84f9cc14ac99f7d8c10cf48a6774388daabcc0546d4e1e8e345ee7fc60b249d95d953ad4d923ca3ac96492ba71c9085d40753cab256948d61aeee96e0fe6c9a0134b807734a32f26430b325df7b6c9f8ba445e7152c2bf86b4dfd4293a53a8d6f003bf8cf5dffd
* 0x904a515 -> 0x927a6ecd74bb7c7829741d290bc4a1fd844fa384ae3503b487ed51dbf9f79308bb11238f2ac389f8290e5bcebb0a4b9e09eda084f27add7b1995eeda57eb043deee72bfef97c3f90171b7b91785c2629ac9c31cbdcb25d081b8a1abc4d98c4a1fd9f074b583b5298b2b6cc38ca0832c2174c96f2c629afe74949d97918cbee4a

**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}`.

要約

同じRSAの秘密鍵で複数の平文に署名がされている。この時与えられた平文に署名をすることができるか？

解法

マークダウンで問題が与えられるのは目新しい。最初はCRT使う系かと思ったがe,dはどれも同じなのでそれは無理。結論としてはRSAが積を保つことを利用する。具体的には平文と署名のペアを(pi, ci)として

p1 = 811 · 947^3 · 970111
p2 = 2 · 61 · 197
p3 = 970111 · 2098711^2 · 2854343
p4 = 947 · 970111 · 2098711
p5 = 61 · 197^2 · 811
p6 = 2098711 · 2854343 · 9605087
p7 = 197 · 811 · 947

であることから、署名したい平文pは

p = 2 · 197 · 947 · 2098711 · 9605087
   = p2 * p6 * pow(p5, -1, n) * pow(p3, -1, n) * pow(p4, 2, n) * pow(p1, -1, n) * pow(p7, 2, n)

と書ける。どうせpがp1~p7の積で書けるだろうということは素因数分解をしている時点で確信したので、実際の分解はエスパーで頑張った。ちゃんとやるには線型方程式作ればいいが、そこまでしなくても５分程度でなんとなくこの分解にたどり着く。

あとはこの分解が署名の方でも成り立つことから、求める答えは

s = s2 * s6 * pow(s5, -1, n) * pow(s3, -1, n) * pow(s4, 2, n) * pow(s1, -1, n) * pow(s7, 2, n) % n

下位16byteをバイト列に直したものがフラグということで、出てきた文字列は全然フラグっぽくないけどもえいやで提出。

コード

e = 0x10001
n = 0xa9e7da28ebecf1f88efe012b8502122d70b167bdcfa11fd24429c23f27f55ee2cc3dcd7f337d0e630985152e114830423bfaf83f4f15d2d05826bf511c343c1b13bef744ff2232fb91416484be4e130a007a9b432225c5ead5a1faf02fa1b1b53d1adc6e62236c798f76695bb59f737d2701fe42f1fbf57385c29de12e79c5b3

p1 = 0x945d86b04b2e7c7
p2 = 0x5de2
p3 = 0xa16b201cdd42ad70da249
p4 = 0x6d993121ed46b
p5 = 0x726fa7a7
p6 = 0x31e828d97a0874cff
p7 = 0x904a515

s1 = 0x17bb21949d5a0f590c6126e26dc830b51d52b8d0eb4f2b69494a9f9a637edb1061bec153f0c1d9dd55b1ad0fd4d58c46e2df51d293cdaaf1f74d5eb2f230568304eebb327e30879163790f3f860ca2da53ee0c60c5e1b2c3964dbcf194c27697a830a88d53b6e0ae29c616e4f9826ec91f7d390fb42409593e1815dbe48f7ed4
s2 = 0x3ea73715787028b52796061fb887a7d36fb1ba1f9734e9fd6cb6188e087da5bfc26c4bfe1b4f0cbfa0d693d4ac0494efa58888e8415964c124f7ef293a8ee2bc403cad6e9a201cdd442c102b30009a3b63fa61cdd7b31ce9da03507901b49a654e4bb2b03979aea0fab3731d4e564c3c30c75aa1d079594723b60248d9bdde50
s3 = 0x9444e3fc71056d25489e5ce78c6c986c029f12b61f4f4b5cbd4a0ce6b999919d12c8872b8f2a8a7e91bd0f263a4ead8f2aa4f7e9fdb9096c2ea11f693f6aa73d6b9d5e351617d6f95849f9c73edabd6a6fde6cc2e4559e67b0e4a2ea8d6897b32675be6fc72a6172fd42a8a8e96adfc2b899015b73ff80d09c35909be0a6e13a
s4 = 0x2b7a1c4a1a9e9f9179ab7b05dd9e0089695f895864b52c73bfbc37af3008e5c187518b56b9e819cc2f9dfdffdfb86b7cc44222b66d3ea49db72c72eb50377c8e6eb6f6cbf62efab760e4a697cbfdcdc47d1adc183cc790d2e86490da0705717e5908ad1af85c58c9429e15ea7c83ccf7d86048571d50bd721e5b3a0912bed7c
s5 = 0xa7d5548d5e4339176a54ae1b3832d328e7c512be5252dabd05afa28cd92c7932b7d1c582dc26a0ce4f06b1e96814ee362ed475ddaf30dd37af0022441b36f08ec8c7c4135d6174167a43fa34f587abf806a4820e4f74708624518044f272e3e1215404e65b0219d42a706e5c295b9bf0ee8b7b7f9b6a75d76be64cf7c27dfaeb
s6 = 0x67832c41a913bcc79631780088784e46402a0a0820826e648d84f9cc14ac99f7d8c10cf48a6774388daabcc0546d4e1e8e345ee7fc60b249d95d953ad4d923ca3ac96492ba71c9085d40753cab256948d61aeee96e0fe6c9a0134b807734a32f26430b325df7b6c9f8ba445e7152c2bf86b4dfd4293a53a8d6f003bf8cf5dffd
s7 = 0x927a6ecd74bb7c7829741d290bc4a1fd844fa384ae3503b487ed51dbf9f79308bb11238f2ac389f8290e5bcebb0a4b9e09eda084f27add7b1995eeda57eb043deee72bfef97c3f90171b7b91785c2629ac9c31cbdcb25d081b8a1abc4d98c4a1fd9f074b583b5298b2b6cc38ca0832c2174c96f2c629afe74949d97918cbee4a

p = 0x686178656c696f6e

print(p % n == p2 * p6 * pow(p5, -1, n) * pow(p3, -1, n) * pow(p4, 2, n) * pow(p1, -1, n) * pow(p7, 2, n) % n)

s = s2 * s6 * pow(s5, -1, n) * pow(s3, -1, n) * pow(s4, 2, n) * pow(s1, -1, n) * pow(s7, 2, n) % n

print(hex(s)[-32:])

出力

True
'a049347a7db8226d496eb55c15b1d840'

ss-puzzle

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# 64 bytes
FLAG = b'LINECTF{...}'

def xor(a:bytes, b:bytes) -> bytes:
    return bytes(i^j for i, j in zip(a, b))

S = [None]*4
R = [None]*4
Share = [None]*5

S[0] = FLAG[0:8]  # = b'LINECTF{'
S[1] = FLAG[8:16]
S[2] = FLAG[16:24]
S[3] = FLAG[24:32]

# Ideally, R should be random stream. (Not hint)
R[0] = FLAG[32:40]
R[1] = FLAG[40:48]
R[2] = FLAG[48:56]
R[3] = FLAG[56:64]

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

# This share is partially broken.
Share[1] = Share[1][0:8]   + b'\x00'*8       + Share[1][16:24] + Share[1][24:32]

for s in Share:
    print(s)

要約

フラグを8byteずつ分割してお互いにxorを何回か取った結果が与えられるので、元のフラグを復元せよ。

解法

あまりに簡単で拍子抜け。こっちの方がwarmupなのでは。フラグ最初の8文字はbLINECTF{で完璧に割れているので、あとはウニャウニャ復元していくだけ。

コード

with open("ss_puzzle_8d056282d224bc3eedcf3da887e4ab704f2a169d/Share1", "rb") as f:
    Share1 = f.read()
    
with open("ss_puzzle_8d056282d224bc3eedcf3da887e4ab704f2a169d/Share4", "rb") as f:
    Share4 = f.read()

# Share1
S0 = b"LINECTF{"
R0S0 = Share1[0:8]
R2S3 = Share1[16:24]
R3S2 = Share1[24:32]

# Share4
R0S3 = Share4[0:8]
R1S2 = Share4[8:16]
R2S1 = Share4[16:24]
R3S0 = Share4[24:32]

R0 = xor(S0, R0S0)
S3 = xor(R0, R0S3)
R2 = xor(S3, R2S3)
S1 = xor(R2, R2S1)
R3 = xor(S0, R3S0)
S2 = xor(R3, R3S2)
R1 = xor(S2, R1S2)
print(S0 + S1 + S2 + S3 + R0 + R1 + R2 + R3)

出力

b'LINECTF{Yeah_known_plaintext_is_important_in_xor_based_puzzle!!}'

Forward-or

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

class CTRMode():
    def __init__(self, key, nonce=None):
        self.key = key # 20bytes
        self.cipher = DoubleRoundReducedPresent(key)
        if None==nonce:
            nonce = os.urandom(self.cipher.block_size//2)
        self.nonce = nonce # 4bytes
    
    def XorStream(self, data):
        output = b""
        counter = 0
        for i in range(0, len(data), self.cipher.block_size):
            keystream = self.cipher.encrypt(self.nonce+counter.to_bytes(self.cipher.block_size//2, 'big'))
            if b""==keystream:
                exit(1)

            if len(data)<i+self.cipher.block_size:
                block = data[i:len(data)]
            block = data[i:i+self.cipher.block_size]
            block = strxor(keystream[:len(block)], block)
            
            output+=block
            counter+=1
        return output

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

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

class DoubleRoundReducedPresent():

    def __init__(self, key):
        self.block_size = 8
        self.key_length = 160 # bits
        self.round = 16
        self.cipher0 = Present(key[0:10], self.round)
        self.cipher1 = Present(key[10:20], self.round)
    
    def encrypt(self, plaintext):
        if len(plaintext)>self.block_size:
            print("Error: Plaintext must be less than %d bytes per block" % self.block_size)
            return b""
        return self.cipher1.encrypt(self.cipher0.encrypt(plaintext))
    
    def decrypt(self, ciphertext):
        if len(ciphertext)>self.block_size:
            print("Error: Ciphertext must be less than %d bytes per block" % self.block_size)
            return b""
        return self.cipher0.decrypt(self.cipher1.decrypt(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というストリーム暗号を二重に用いて暗号化した結果が与えられるので、そこからフラグを復号せよ。 （なおPresentのコードも与えられたが、内部構造は知らなくても解けるのでここでは割愛）

解法

この問題が今回の問題セットの中で一番解き甲斐があった。まず最初に気づく点として

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

とあることから鍵は0,1,2,3のみから成り鍵候補は非常に少ない。またPresentを二重にかけている所が明らかに怪しい。

ここでブロック暗号についてググっていると次のふるつき先生のコメントに行き当たる：

2段や3段の暗号化で、使われている鍵が短い (Meet in the Middle Attack)

Meet in the Middle Attackができる。

見事に本ケースに当てはまるので、おそらくこれで間違い無いだろう。Meet in the Middleは平文暗号文ペアから鍵を割り出す手法。一見すると平文暗号文ペアなんて与えられてないので困ってしまうが、これもss-puzzle同様平文の先頭がbLINECTF{なことから対応する暗号文も与えられた暗号文の先頭8文字として得られる。

あとはMeet in the Middle (MITM)するだけだがちょっと注意。暗号化の仕方を見ると

  1. nonce(既知)から２回暗号化してビットマスクを得る。
  2. 平文にビットマスクをかけて暗号文とする。

なので、MITMの仕方としては

nonce ---(encode)---> [collision!!!] <---(decode)--- plaintext xor ciphertext

となる。

鍵長は10で各文字は0,1,2,3の4パターンなので、鍵空間のサイズは410~0(106)オーダー。この全ての鍵に対してnonceをencodeした結果及びビットマスクをdecodeした結果を辞書に保存しておき、それぞれの結果で一致したものがあれば、それがcollision!!!に対応するものであって同時にencodeに使った鍵とdecodeに使った鍵もわかる。

鍵が割れればあとは素直に与えられた暗号文を二重decodeすれば完成。

コード

import itertools
from collections import defaultdict
from tqdm import tqdm

cipher=bytes.fromhex("3201339d0fcffbd152f169ddcb8349647d8bc36a73abc4d981d3206f4b1d98468995b9b1c15dc0f0")
nonce=bytes.fromhex("32e10325")
p = b'LINECTF{'
c = cipher[:8]
mask = strxor(p, c)
init = nonce + b'\x00\x00\x00\x00'

forward = defaultdict(set)
backward = defaultdict(set)

for key in tqdm(itertools.product('0123', repeat=10)):
    key = ''.join(key)
    key = key.encode('ascii')
    cipher = Present(key, 16)
    f = cipher.encrypt(init)
    b = cipher.decrypt(mask)
    forward[f].add(key)
    backward[b].add(key)

collision = (forward.keys() & backward.keys()).pop()
print(f"{collision=}")

key0 = forward[b'\x9f?An\x87\xac\xba\xe1'].pop()
key1 = backward[b'\x9f?An\x87\xac\xba\xe1'].pop()
print(f"{key0=}, {key1=}")
key = key0 + key1

ciphertext=bytes.fromhex("3201339d0fcffbd152f169ddcb8349647d8bc36a73abc4d981d3206f4b1d98468995b9b1c15dc0f0")
nonce=bytes.fromhex("32e10325")

cipher = CTRMode(key, nonce)
cipher.decrypt(ciphertext)

出力

collision=b'\x9f?An\x87\xac\xba\xe1'
key0=b'3201323020', key1=b'2123003302'
b'LINECTF{|->TH3Y_m3t_UP_1n_th3_m1ddl3<-|}'

Baby crypto revisited

0xe6b7c5a62d08e0216e1e7ed7948c96b74c0be9cd 0x49e1050393f885117de74e7a02d1091d67faa3d0 0xff07bbee67c3ab910000000000000000 0xe91f3200a87205d18a97bdf3bb3027c9f532c8a4
0x7e7b86c8624c9b597131bb883053b1856527a5ff 0x7787b9157fbbaf178ed091b23ce30b2e1ccf9abf 0x882f44f29c56aea60000000000000000 0x37c9f0d06570b0087430b9c66372e385839bb348
0x7951eb8b6ef6ebd080c0171252c53b40fd4ac3b5 0xe70efd784e8a5a35ebd875c4df23132324946e5f 0x842f1342234670730000000000000000 0x7635013447c4b0e7c637dde0b9f8f2eed2cda796
0xae1f8afabb6c971626e8616f30dc0781dee744ae 0xd836a959f2e963291c572a261081ada95ff8a3a 0x37261d496392b4140000000000000000 0x2e7684cae69cd153426acc333bace2c6a294ed4c
......(以下略)......

要約

なんとただの数字列しか与えられてない！このテキストファイルをダウンロードする際に書かれている問題文に

Last time, our side-channel attack was quite easy. But our victim found out about our sneaky attack and increased the size of nonce. Fortunately, we could still capture the first half of the nonce, which is 64-bit this time. Now please help us to find out the encryption key again. The victim is using the secp160r1 curve. The following is the captured data: r, s, k, and hash respectively. Flag is LINECTF{}, e.g. LINECTF{0x1234}

と添えられているので、去年の問題を知っていることが前提らしい。コレは辛すぎでは！？

解法

去年どんな問題が出たかググるとふるつき先生のwriteupが先にヒットしてしまう。どうやら楕円曲線のkeyが３変数目に対応していて、0000....の部分が欠損を表しているらしい。これをHidden Number Problemと見てLLLすれば解けるとある。なんと同じスクリプトで解けちゃった。手応えのなさ。。。。。。

ふるつき先生のwriteupにある埋め込み法とやら、何も分かってないのでどこかで勉強したいところ。いいリファレンス募集中。

コード

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

dataset = []
with open("Babycrypto_revisited_b1f108dea290b83253b80443260b12c3cadc0ed7.txt") as f:
    lines = f.read().strip().split("\n")
    for l in lines:
        # r_, s_, k_, h_ = [int(x, 16) for x in l.split(" ")]
        dataset.append( [int(x, 16) for x in l.split(" ")] )
        
r, s, k, h = zip(*dataset)
N = len(h)
t = [r[i] * inverse_mod(s[i], n) % n for i in range(N)]
u = [((h[i] * inverse_mod(-s[i], n) % n) + k[i]) % n for i in range(N)]

nonce_max = 2**64

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 = int(abs(row[0]))
    if k1 != 0 and k1 != nonce_max and k1 < nonce_max:
        d = ((k1+k[0])*s[0] - h[0]) * inverse_mod(r[0], n) % n
        print(k1, d)
        print(int(d)*G)
hex(d)

出力

1446378667213923537 1230222089369119785522693236372753381379974297636
(1022452337409376433083787356631666209330746972930 : 1193181433859553698543067687618966502051663733210 : 1)
'0xd77d10fec685cbe16f64cba090db24d23b92f824'