InterKosenCTF 2020 writeup

チームOJI(Little Twoos)として参戦,5276点で6位でした. ほとんどはチームメイトが解いてくれたので,多分まだ見てない問題を中心に解いた.

No pressure

問題

from Crypto.Cipher import ARC4
from hashlib import sha256
from base64 import b64encode
import zlib
import os

flag = open("./flag.txt", "rb").read()

nonce = os.urandom(32)
while True:
    m = input("message: ")
    arc4 = ARC4.new(sha256(nonce + m.encode()).digest())
    c = arc4.encrypt(zlib.compress(flag + m.encode()))
    print("encrypted! :", b64encode(c).decode())

解き方

zlibが使われたため,おそらく後ろの入力が前のflag文字列とかぶれば,文字列の長さはそれほど増やさないと判断し,KosenCTF{を一文字ずつ入れてみて長さを見てみると,長さはうまく81のままだったため,長さを81以下なる入力をbruteforceで当てに行ったらうまく解けた.

solver

from pwn import *
from base64 import b64decode
from string import printable

flag = 'KosenCTF{'

io = remote('misc.kosenctf.com',10002)
head = 'message: '
while True:
    for x in printable:
        tmp = flag + x
        io.readuntil(head)
        io.sendline(tmp)
        l = io.readline()
        c = l.split(':')[-1].strip()
        d = b64decode(c)
        if len(d) <= 81:
            flag += x
            print flag
            break
    if flag[-1] == '}':
        break

harmagedon

問題

4択でどんどん展開しにいく問題,最終的に自分が選択した文字列がフラグになる.
バイナリファイルをghidraに投げる
1. ロジックの部分はsyscallが多用
2. ケツにめっちゃ長い文字列がある

解き方

whileから抜ける条件は以下のようになる

while c != 0xb77c7c:
    c = (c + input_idx)<<2

ですのでまず文字数を絞る,足し算の部分を無視して純粋に4の何乗を見れば大体な長さが11でわかる
その後は全探索で当てに行けば何番を選べばいいのかが計算できて,最後はそのまま入力すればok

solver

# coding: utf-8
for i in itertools.product([1,2,3,4],repeat=11):
    c = 0
    for x in i:
        c += x
        c = c << 2
    if c == 0xb77c7c:
        print i
# output: (2, 3, 1, 3, 1, 3, 2, 4, 1, 3, 3)
'''
which is your choice? [fRD3]R
which is your choice? [Ymug]u
which is your choice? [kcJQ]k
which is your choice? [yhtP]t
which is your choice? [uDPJ]u
which is your choice? [05n7]n
which is your choice? [V0Np]0
which is your choice? [8GFr]r
which is your choice? [Dar3]D
which is your choice? [UDi8]i
which is your choice? [KS3c]3
congratz. your choices are the flag
'''

bitcrypto

問題

server.pyが配布され,サーバにbitごとの暗号化/復号化のアルゴリズムが実装されたことが判明
具体的に暗号化/復号化は↓な感じ

enc:
(n,z) -> pubkey
x -> random(2,n)
1: pubkey.z * x**2
0: x**2

dec:
for c in ciphertext:
    t = c ** ((privkey.p-1)//2)
    if t == 1:
           m = 1
    else :
           m = 0

queryは2つの入力条件があり
1. 8文字以下 2. keyword含まれない
tokenも2つの条件がある
1. 同じ0の位でも異なる値が求められる
2. 値は全部正数

解き方

暗号化された値を復号化の式に代入すると
${1: z^{(p-1)//2}x^{p-1}}$←①
${0: x^{p-1}}$←②

pは素数のため,フェルマーの小定理により,式①の結果は前半の部分で,式②の結果は常に1になるはず.
なのでここは以下の方法で解く
1. 0(0b110000)を送り,暗号化された結果をもらう
2. 0と1の結果を一個ずつ取る
3. 0は必ず式②の結果を1にしないと行けないため${getPrime(256)²}$で増殖し,1は基本なんでもokなんで${x_1・2ⁱ}$でバリエーションを増やす
4. 最終的に送れば高い確率?で通るはず

solver

from pwn import *
from Crypto.Util.number import *

keyword = 'yoshiking, give me ur flag'
k_bin = ''.join([b for b in "{:b}".format(bytes_to_long(keyword))])

query = '0' # 110000

io = remote('crypto.kosenctf.com',13003)
#io = remote('localhost',10001)
io.readuntil('your query: ')
io.sendline(query)
enc = io.readline()
enc = eval(enc.split(':')[-1].strip())
assert len(enc) == 6
print enc
x_1 = enc[0]
x_0 = enc[2]
print io.readuntil('your token: ')

token = []
for idx,x in enumerate(k_bin):
    if x == '1' :
        token.append(x_1 * pow(2,idx))
    else:
        t = getPrime(256)
        token.append(t**2)
token = repr(token).replace('L','')
assert len(token.split(',')) == len(k_bin)
io.sendline(token)
print io.readline()
print io.readline()

ochazuke

問題

ECDSAの問題で,サーバ側はochazuke以外の文字列の署名の発行がやってくれる,なんやかんやでochazukeの署名作ればokという予測

解き方

普段なECDSAとはkの求め方です
k = Zn(ZZ(sha1(message).hexdigest(), 16)) * private_keykはmessageのsha1値に依存することが判明し,sha1collisionで同じ結果にすることが可能
またkを一致すればprivate_keyを割り出すことも可能
よって流れは以下のうように
1. sha1collisionでハッシュ値が同じpdf生成
2. サーバに送りそれぞれの署名をもらえる
3. private_keyを割り出す
4. ochazukeの署名を自分で計算する
5. サーバに送る

solver

from pwn import *
from binascii import hexlify
from hashlib import sha1
from Crypto.Util.number import *

with open('shattered-1.pdf','rb') as f:
    pt1 = f.read()
with open('shattered-2.pdf','rb') as f:
    pt2 = f.read()

pt1 = hexlify(pt1)
pt2 = hexlify(pt2)

ip = 'crypto.kosenctf.com'
port = 13005

# io = remote(ip,port)
# io.readline()
# pubkey = [98664527284046924431103876265370791373438293020179316375883642857046660842422,51449822108608164116773906593599196539335313713052966364410874461652593273305]
# io.readuntil(':')
# io.sendline(pt1)

# # sig1
# sig1 = io.readline()
# sig1 = eval(sig1.split(':')[-1])
# print sig1
# io.close()


# io = remote(ip,port)
# io.readline()
# io.readuntil(':')
# io.sendline(pt2)

# # sig2
# sig2 = io.readline()
# sig2 = eval(sig2.split(':')[-1])
# print sig2

r1,s1 = (31150389226879548734307094288693105064656618066963344177653161349106620886514L, 12841807904550618931158792373525971859617703967016459921869962189487250843902L)
r2,s2 = (31150389226879548734307094288693105064656618066963344177653161349106620886514L, 96420393187933516068408660378146591249838645116318546612272298822307206485147L)

h = int('38762cf7f55934b34d179ae6a4c80cadccbb7f0a',16)

n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551 # EC.order()

privkey = ((int(pt1,16) - int(pt2,16)) * inverse(h*(s1-s2),n)) % n
print privkey

io = remote(ip,port)
sig = '(98165594340872803797719590291390519389514915039788511532783877037454671871717, 115665584943357876566217145953115265124053121527908701836053048195862894185539)'
io.readline()
io.readuntil(':')
io.sendline(pt2)
io.readline() # your signature
print io.readuntil(':')
io.sendline(sig)
print io.readline()

署名用スクリプトはサーバスクリプトそのまま

from Crypto.Util.number import bytes_to_long
from binascii import unhexlify
from hashlib import sha1
from sage.all import *
import re

def sign(private_key, message):
    z = Zn(bytes_to_long(message))
    k = Zn(ZZ(sha1(message).hexdigest(), 16)) * private_key
    assert k != 0
    K = ZZ(k) * G
    r = Zn(K[0])
    assert r != 0
    s = (z + r * private_key) / k
    assert s != 0
    return (r, s)
private_key = 313681195146870630150443675574660225833
EC = EllipticCurve(
    GF(0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff),
    [-3, 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b]
)
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551 # EC.order()
Zn = Zmod(n)
G = EC((0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,
        0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5))
print(sign(private_key,b'ochazuke'))