memo46

競プロの精進記録その他。

SECCON Beginners CTF 2021 WriteUp

チームM15.(W|X)として参加し、全体23位 / 943、3327ptでした。

チームメンバーは

  • siro53(僕)
  • SUAN
  • Soeki
  • eren53

の4人です。

初めてチームを組みましたが、かなり健闘できたと思います。とても嬉しいです!(本当は他の分野も解きたかったですが、時間が足らず...) f:id:bakamono1357:20210523152059p:plain

個人では、Imaginary以外のCrypto 5問を解きました。ImaginaryはAES暗号なんも分からんって言ってたらeren君が解いてくれました...

以下解いた問題のWrite upです。

Simple RSA[Crypto]

n = 17686671842400393574730512034200128521336919569735972791676605056286778473230718426958508878942631584704817342304959293060507614074800553670579033399679041334863156902030934895197677543142202110781629494451453351396962137377411477899492555830982701449692561594175162623580987453151328408850116454058162370273736356068319648567105512452893736866939200297071602994288258295231751117991408160569998347640357251625243671483903597718500241970108698224998200840245865354411520826506950733058870602392209113565367230443261205476636664049066621093558272244061778795051583920491406620090704660526753969180791952189324046618283
e = 3
c = 213791751530017111508691084168363024686878057337971319880256924185393737150704342725042841488547315925971960389230453332319371876092968032513149023976287158698990251640298360876589330810813199260879441426084508864252450551111064068694725939412142626401778628362399359107132506177231354040057205570428678822068599327926328920350319336256613
from Crypto.Util.number import *
from flag import flag

flag = bytes_to_long(flag.encode("utf-8"))

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 3

assert 2046 < n.bit_length()
assert 375 == flag.bit_length()

print("n =", n)
print("e =", e)
print("c =", pow(flag, e, n))

problem.pyとoutput.txtが与えられます。

eが3と小さく、assert文から m3 < nであることがわかるので、二分探索すればよいです。

Flagはctf4b{0,1,10,11...It's_so_annoying.___I'm_done}

from Crypto.Util.number import *

n = 17686671842400393574730512034200128521336919569735972791676605056286778473230718426958508878942631584704817342304959293060507614074800553670579033399679041334863156902030934895197677543142202110781629494451453351396962137377411477899492555830982701449692561594175162623580987453151328408850116454058162370273736356068319648567105512452893736866939200297071602994288258295231751117991408160569998347640357251625243671483903597718500241970108698224998200840245865354411520826506950733058870602392209113565367230443261205476636664049066621093558272244061778795051583920491406620090704660526753969180791952189324046618283
e = 3
c = 213791751530017111508691084168363024686878057337971319880256924185393737150704342725042841488547315925971960389230453332319371876092968032513149023976287158698990251640298360876589330810813199260879441426084508864252450551111064068694725939412142626401778628362399359107132506177231354040057205570428678822068599327926328920350319336256613

ok = 0
ng = 10 ** 375
while ng - ok > 1:
    mid = (ok + ng) // 2
    if mid * mid * mid <= c:
        ok = mid
    else:
        ng = mid
print(long_to_bytes(ok))

Logical_SEESAW[Crypto]

from Crypto.Util.number import *
from random import random, getrandbits
from flag import flag

flag = bytes_to_long(flag.encode("utf-8")) # flagをlong型に変える
length = flag.bit_length() # flagのbit長
key = getrandbits(length) # key = flagと同じbit長のランダムな数字
while not length == key.bit_length():
    key = getrandbits(length)

# 2進数に変換し、['1', '0', '1', ...]みたいなlistを作る
flag = list(bin(flag)[2:])
key = list(bin(key)[2:])

cipher_L = []

for _ in range(16):
    cipher = flag[:]
    m = 0.5
    
    for i in range(length):
        n = random()
        if n > m:
            cipher[i] = str(eval(cipher[i] + "&" + key[i]))
            
    cipher_L.append("".join(cipher))


print("cipher =", cipher_L)

やっていることとしては、flagと同じbit長の乱数keyを生成し、flagとkeyをそれぞれ2進数に変換する

各bitごとに1/2の確率で、flagとkeyのi番目のbit同士をANDを取るということを独立にやる

その要領で生成したbit列を16個生成し、出力(output.txt)、です。

flag[i]が'0' のところは何をやっても0のままですし、flag[i]が'1'のところを全て'0'とANDを取られる確率は非常に低いので、cipherに1つでも'1'が含まれていたらその位置のbitは1、それ以外は0という風に復元すればokです。

Flagはctf4b{Sh3_54w_4_SEESAW,_5h3_54id_50}

GFM[Crypto]

FLAG = b'<censored>'

SIZE = 8
p = random_prime(2^128)
MS = MatrixSpace(GF(p), SIZE)

key = MS.random_element()
while key.rank() != SIZE:
    key = MS.random_element()

M = copy(MS.zero())
for i in range(SIZE):
    for j in range(SIZE):
        n = i * SIZE + j
        if n < len(FLAG):
            M[i, j] = FLAG[n]
        else:
            M[i, j] = GF(p).random_element()

enc = key * M * key

print('p:', p)
print('key:', key)
print('enc:', enc)

8×8行列の$key$と、flagが一部入った$M$が入っています。

$enc=key×M×key$

となっているので、$mod \space p$上で

$M={key}^{-1}×enc×{key}^{-1}$

とすればMが復元できます。逆行列は掃き出し法で求めます。

Mの中身を見ると小さい数字が入ってて明らかに怪しいのでそれらをasciiコードを順番に復元すればokです。

Flagはctf4b{d1d_y0u_pl4y_w1th_m4tr1x_4nd_g4l0is_f1eld?}

Field_trip[Crypto]

from Crypto.Util.number import *
from random import getrandbits
from flag import flag


flag = bytes_to_long(flag.encode("utf-8"))
flag = bin(flag)[2:]
length = len(flag)

A = []
a, b = 0, 0
for _ in range(length):
    a += getrandbits(32) + b
    b += a
    A.append(a)

p = getStrongPrime(512)
q = getStrongPrime(512)

assert q > sum(A)

pub_key = [a * p % q for a in A]
cipher = sum([int(flag[i]) * pub_key[i] for i in range(length)])

f = open("output.txt", "w")
f.write("pub_key = " + str(pub_key) + "\n")
f.write("cipher = " + str(cipher) + "\n")
f.close()

cipherの箇所を見ると、flagを2進数にして、bitが立ってるところのみのpub_key[i]の和を暗号としています。

これを復元するにはDPもしくは半分全列挙などをする必要がありますが(部分和問題)、どう考えてもオーダー的に不可能です。

そこで何かあるだろうとひたすらググり倒すと、

Merkle-Hellmanナップサック暗号 - Wikipedia

が見つかります。これとやってることは同じです。

攻撃法にはシャミアの攻撃法、低密度攻撃などがあるそうですが、今回はググるとSageMathでの実装が見つかった低密度攻撃で解きました。

PlaidCTF CTF 2015: Lazy - うさぎ小屋

今回の問題は密度が0.6ぐらいだったのでこれで解けます。ちなみにSageMathは↓でオンライン実行できます。

Sage Cell Server

2進数 -> 10進数の変換がなぜかバグっていた(?)ので、自分でそこだけ書き直したらフラグが出てきました。

Flagはctf4b{Y35!_I_ju5t_n33d3d_th353_num63r5!}

p-8RSA[Crypto]

from Crypto.Util.number import *
from random import getrandbits
from os import urandom
from flag import flag


def gen_primes(bits, e):
    q = getStrongPrime(bits)
    p = q
    while True:
        p = p-8 # p-8
        phi = (p - 1) * (q - 1)
        if isPrime(p) and GCD(phi, e) != 1:
            break
    return p, q

flag = flag.encode("utf-8") + urandom(64)
flag = bytes_to_long(flag)

e = 17
p, q = gen_primes(512, e)
n = p * q

print("n =", n)
print("e =", e)
print("c =", pow(flag, e, n))

p, qの値がかなり近そうなのでフェルマー法でNを素因数分解でき、p, qが求まります。

しかし、phiとeが互いに素でないので逆元が存在せず、秘密鍵dが求まりません。

ここで、eの値が小さいことに着目します。まず

$c \space mod \space p = m^{e} \space mod \space p$

$c \space mod \space q = m^{e} \space mod \space q$

より、p, qは素数であることからwolfram alphaを使って$mod p, q$上のcのe乗根の候補がそれぞれ求まります。

e乗根の候補はかなり少ないため、これらの候補を全て試して中国剰余定理で復元すれば、答えの候補が求まります。

後は適当にgrepするとflagが見つかりました。

Flagはctf4b{4r3_y0u_up5id3_d0wn?_Fr0m_6310w?_0r_60th?}

(wolfram alphaの使い方を調べるのに苦労...)

感想

Crypto全完して喜んでたらreversingとmiscほぼ全て解かれていてビビった。

WebとPwnはダメダメだったので、なんとかしたい。

おまけ

深夜に16位まで上昇し、上位勢のグラフに自チームの名前が入って興奮する我々 f:id:bakamono1357:20210523160443p:plain f:id:bakamono1357:20210523161212p:plain

気づいたらreversing全部通されててビビる僕

f:id:bakamono1357:20210523160841p:plain