Attack All Around

今やCTFと競プロばかりだが、トビタテ生のアメリカ留学やTOEFL奮闘記

m1z0r3CTF 2021 writeup

m1z0r3CTF 2021で作った問題の解説をしていきます。

その前に問題を見ていない方はこちらから：m1z0r3CTF 2021 作問しました - Attack All Around



解説


github URL : GitHub - ksbowler/m1z0r3CTF_2021: m1z0r3CTF 2021 problem files


15Prime (warmup)

flagを整数型に変換し、最下位ビットが立っていたら512ビットの素数を、立っていないなら256ビットの素数2つの積をoutput.txtに出力します。その後、その整数を1ビット右シフト、つまり2で割ります(余りは無視)。flagが0になるまで繰り返していきます。


つまり、出力された整数が素数なのか合成数なのか判断できればflagを復元できそうです。素数判定の関数はたくさんありますが、solverではlong_to_bytesも使うのでCrypto.Util.numberのisPrimeを使っています。output.txtに出力されている値はflagの下位ビットから見ているのに注意です。

from Crypto.Util.number import *
f = open("output.txt")
a = f.readlines()
flag = ""
for c in a:
    c = int(c.strip())
    if isPrime(c): flag += "1"
    else: flag += "0"
print(long_to_bytes(int(flag[::-1],2)))


m1z0r3{There_are_many_module5_that_1mplement_the_isprime_funct1on}



Long Island (easy)

flagからformatを除いたものを2進数表現した文字列をFLAG、31ビットの乱数を2進数表現した文字列をkeyとしてます。

ASCIIの可視文字列は7ビットで表現できるのに対し、1バイト分のメモリ(?)を確保しています。つまり、下から数えて8kビット目は必ず0になります。暗号文の長さが470であったことから、要素0から数えて8k+6番目のFLAGは必ず"0"になるので、その部分は暗号文とkeyが一致します("0" ^ key[i] = ciphertext[i] )。iが31を超えた場合、keyはi%31番目の値を使っています。つまりrotateして使っています。8ビット毎"0"が現れ、31と互いに素であり全てのkey[i]が一回は必ず"0"になる部分とXORします。これを用いてkeyを復元して暗号文から平文を導出します。

from Crypto.Util.number import *

ct = eval(open("output.txt").read())

key = []
for _ in range(31): key.append(-1)
for j in range(6,len(ct),8):
    key[j%31] = ct[j]
    #print(key)
    if min(key) >= 0: 
        flag = ""
        for k in range(len(ct)):
            flag += str(key[k%31]^ct[k])
        print(long_to_bytes(int(flag,2)))


m1z0r3{009->59->31_This_is_Seiya_Matsubara's_backnumber_transition}



1024Prime (medium)

まずRSA暗号の公開鍵と暗号文が渡されます。任意の暗号文を復号してくれるようなのですが、その復号された値について怪しげな演算をしているようです。

素数のうち小さいものから順に1024個を、配列に降順で格納しています。復号された値のビットと素数配列の要素を対応させ、立っているものと対応している素数を掛け合わせて1024で割った余りがサーバから送られてきます。

サーバから送られる値は1024で割った余りなので1024通りしかありません。復号された値は1024ビットなので、異なる復号値でも同じ値がサーバから送られてきてしまいます。また、その値から元の復号された値を復元するのは難しそうです。


しかし、1024個の素数の中でも異彩を放つのが"2"です。一つだけ偶数ですね。1024個の素数をどう掛け合わせようと、その中に2が含まれていたら偶数になります。2が対応しているのは復号された値の最下位ビットですね。偶数を偶数で割った余りなら必ず偶数になりますし、奇数なら必ず奇数が余りとなります。つまり、サーバから送られた値の偶奇を調べれば復号された値の最下位ビットが分かります。


この時、LSB Decryption Oracle Attackが使えます。

mを知りたいとき、復号すると2mになるような暗号文c'をサーバに送ります。c' = (2m)e = 2e × me = 2e × c mod nとなります。

c'を復号した際に2mがNを超えるかどうかを判断します。m < Nであるので、2m < 2Nとなります。つまり、復号された値 = 2m or 2m - N となります。前者の場合返り値は偶数で2mがNより小さいことが分かり、後者なら奇数となり2mがNより大きいことが分かります。ここで、0 < m < Nであった平文mの取りうる範囲が、0 < 2m < N, もしくは N < 2m < 2N の半分の候補となります。


一般化してみると、aN < km < (a+1)N (kは2のべき乗)という範囲が分かっているとします。この時、m' = km mod N = km - aN とし、2m'がNを超えるかチェックします。その確認は上記のやり方で行えばOKです。

2m'がNを超えない、0 < 2m' < Nの場合

0 < 2m' < N
0 < 2(km-aN) < N  
0 < 2km - 2aN < N  (ここですべての辺に2aNを足す)
2aN < 2km < (2a+1)N

とさらに、範囲を半分にすることができました。

反対に、2m'がNを超える場合、

N < 2m' < 2N
N < 2(km-aN) < 2N 
N < 2km - 2aN < 2N  (ここですべての辺に2aNを足す)
(2a+1)N < 2km < (2a+2)N

とこちらの場合も範囲を半分にすることができました。


以上の操作を繰り返すと、aN < km < (a+1)N のkがかなり大きい値となります。a, k, m, Nは何れも整数なので、上の不等式を満たすmが一意に決まります。

細かい解説はgithubに載せた資料を参考にしてもらえればと思います。

from Crypto.Util.number import *
from functools import reduce
from operator import mul
from itertools import combinations
import sys
import socket, struct, telnetlib

# --- common funcs ---
def sock(remoteip, remoteport):
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect((remoteip, remoteport))
    return s, s.makefile('rw')

def read_until(f, delim='\n'):
    data = ''
    while not data.endswith(delim):
        data += f.read(1)
    return data

    
#HOSTはIPアドレスでも可
HOST, PORT = "127.0.0.1", 5000
s, f = sock(HOST, PORT)
e = int(read_until(f).split()[-1])
n = int(read_until(f).split()[-1])
c = int(read_until(f).split()[-1])
read_until(f)
bounds = [[0,1],[1,1]]
deno = 2
cnt = 0
while True:
    c2 = (pow(2,e,n)*c)%n
    read_until(f,"> ")
    s.send(str(c2).encode()+b"\n")
    ret = int(read_until(f).split()[-1])
    bounds[0][0] *= 2
    bounds[0][1] *= 2
    bounds[1][0] *= 2
    bounds[1][1] *= 2
    if ret%2 == 0:
        #LSB 0 : 上限小さく
        bounds[0][0] += 1
    else:
        #LSB 1 : 下限大きく
        bounds[1][0] -= 1
    read_until(f)
    if cnt%100 == 0: print(cnt,bounds)
    if bounds[0] == bounds[1] or cnt > 1024:
        m = (n*bounds[0][0])//bounds[0][1]
        print(m)
        print(long_to_bytes(int(m)))
        break
    cnt += 1
    deno *= 2
    c = c2


m1z0r3{Did_you_know_LSB_Decrytion_Oracle_Attack}



SqUArE (hard)


Challenge S

e = 8750とp-1, q-1と互いに素ではないが倍数でもないという微妙な値。hintもその値がたまたま二乗根を持っていてあれ？となった方もいるかもしれません。

まず、p, qを求めます。

(p+q)^2 = p^2 + 2pq + q^2 = p^2 + q^2 mod pq

となりますが、なぜかこの値が二乗根をたまたま持っていました。私の想定する解法としては、p2 ≒ q2 ≒ pq と近似すると(p+q)2 = 4n+hintとなりそうです。なので、hintにnを足していって二乗根があるか調べて、あとは解と係数の関係でp, qを算出します。


次に、e = 8750という厄介な公開鍵をどうするか考えていきます。実はこの問題の値を変えただけです。

Buckeye CTF Defective RSA writeup - Attack All Around

計算すると28通りのmの候補が出てきますが、それをすべて見ると一つ怪しい文字列が…


Challenge U

公開鍵(e,n)と秘密鍵dが渡され、今のものよりも小さい秘密鍵が欲しいというワガママをかなえてあげましょう。

現状、ed = 1 mod (p-1)(q-1) で秘密鍵を作っているとのことなので、ed' = 1 mod lcm(p-1,q-1) にしてd'が小さくなればいいな戦法を取ります。では、どうやってe, n, dからp, qを求めるのかというと、ed-1が(p-1)(q-1)の倍数であることを使います。

ed-1 をfactorDBなどで素因数分解してビット全探査などを使い(p-1)(q-1)の候補を出します。正しい(p-1)(q-1)であれば、n-(p-1)(q-1) = p+q-1となるので、ここからまた解と係数の関係を利用しp, qを出します。あとは、lcmを計算してd'が小さくなればOK、ダメならもう一度ncするを繰り返すとうまくいきます。

渡された文字列がまたしてもFLAGじゃなかったですね…


Challenge A

AESのCBCモードを利用したログインサービスとのことです。

渡された暗号文をそのまま投げてみると、"guest"でログインできて"admin"じゃないから秘密のメッセージを渡せないと言われます。

渡された暗号文の最下位バイトを少し変えてみると、"Padding Incorrect"と言われました。


padding oracle attackに気づいたら、あとは実装のお時間です。
超絶分かりやすいサイトはこちら↓

Padding Oracle Attack 分かりやすく解説したい - Attack All Around

Decryption Attackにより以下の平文が手に入ったと思います。

SqUArE secret system: username = guest

暗号文をそのまま投げたら"guest"でログインできたので、その部分を"admin"にした暗号文を作ることができたら秘密のメッセージとやらを貰えそうです。

Encryption Attackを頑張って実装し、"admin"としてログインできると、またしてもFLAGじゃないものです。


Challenge E

私のgithubのサイトが得られたはずです。アクセスすると、chalE.py, outputE.txtがありました。

chalE.pyを読むと、m_list.txtには2進数で何かが格納されており、eをm_list.txtの行数ではなくm_list.txt内の異なる値の個数分でnは256ビット素数2つの積がe個ある、RSA暗号が使われていることが分かります。


1つの平文に対してe個の暗号文があるので、Hastad's broadcast attackを使えば平文を復号できます。

Coppersmith's attack - Wikipedia

復号してlong_to_bytesしても可視文字列になりません。それどころか\xffしかない平文もありました。しかし平文の長さが短いことから復号は間違ってないと思えるはずです。


ここからエスパー要素ふんだんに入っているのですが、勘のいい方はこの問題が最後だと気付いたと思います。問題名のSqUArEと今までのChallengeがS, U, A, Eであることから想像したのかなと思います。

chalE.pyの23行目からmが2進数で保存されているので2進数に変換すると、m_listの個数と各要素の長さが同じであることに気付きましたでしょうか。問題名のSqUArEから正方形にしてみたらなにか見えるはずです…。

SqUArEのq, rだけなぜ小文字なのでしょう。正方形でqとr…。加えて問題文…。


はい、QRコードです。

1を"##"に、0を"(空白2つ)"にして文字サイズを小さくすると端末でもQRコードが見えやすいと思います。あとはスマホのカメラかアプリなどで読み取ってもいいですし、PILなどを使って画像を生成してもいいと思います。


m1z0r3{sQuaRe_ha5_many_mean1ngs_maybe}



所感

学生最後のm1z0r3CTFということもあり、気合いを入れて多くの問題を作りました。SqUArEのChallenge Aはサーバコードすら見せないPadding Oracle Attackというのはかなりエスパーだったそうで、そこは反省しております。Challenge AをクリアしていないのにChallenge Eの問題を見れるようにはしたくなかったので、githubにコードを置くのはChallenge Eだけにしようと思っていました。もっといい方法があったのかな、など考えております。


また、Challenge Aは1024Primeで使ったLSB Decryption Oracle Attackにする予定でしたが、これはどうやってもサーバコードを見せないと分からないなとか、相手チームの問題数もまあまああると聞いて分断しました。全部RSAとなるのもつまらないかなと思ってAESを入れたのですが、内輪ネタ&チームメイトが他のAES問題を作問したのでもう少し改善できたのかなと思っています。


SqUArEはボス問のような形にしたくて簡単には解かれたくなかったので(特に相手チームのsiro君には) Challenge 4つ構成にしましたが、1人が8時間かけてギリギリ解けないというかなり鬼畜設定にしすぎました。最後のQRコード変換はWebの問題をやったときに体験して自分も作ってみたいと思っていました。



もう一つ物議をかもした問題がLong Islandです。これが初心者用問題にはならんやろ！とお𠮟りを受けました。チーム内でもASCIIの8ビット毎に必ず0になるというのに気付く人はいなくて言われたら気付くという意見を貰いましたが、そのまま出題。見事(?)解かれませんでした。この問題は、布団に入ったはいいものの眠れなかった日に構想していたものです。

余談ですが、巨人松原選手が2022年シーズンにまた新しい背番号9になることが発表されました。プロ野球界では一桁背番号はかなり期待されている選手や主力が付ける傾向があり、巨人の背番号9は2021年引退した亀井選手が付けていました。今後の松原選手の活躍に期待ですね！