明石高専が主催のCTFがあったので、参加しました．

チーム Ocamelot として参加して、総得点2201点で2位でした．

[Sample 1pts] Welcome
[Binary 100pts] signature
[Binary 100pts] wrong copy
[Crypto 100pts] base64
[Crypto 200pts] knapsack
[Crypto 200pts] modulo
[Crypto 300pts] Circular RSA

[Sample 1pts] Welcome

コピー&ペーストできますかの問題

NITAC{sup3r_dup3r_sc0re_serv3r} 無事できました．

[Binary 100pts] signature

binaryが与えられます．壊れているっぽいので、hexで見てみます．

00000000: 7f45 4c46 0d0a 1a0a 0000 000d 4948 4452  .ELF........IHDR
00000010: 0000 0423 0000 021d 0806 0000 0007 efb7  ...#............
00000020: 2f00 0000 0473 4249 5408 0808 087c 0864  /....sBIT....|.d
00000030: 8800 0000 1974 4558 7453 6f66 7477 6172  .....tEXtSoftwar
00000040: 6500 676e 6f6d 652d 7363 7265 656e 7368  e.gnome-screensh
00000050: 6f74 ef03 bf3e 0000 1c96 4944 4154 789c  ot...>....IDATx.

IHDRが見えるので画像が入ってそうです．suffixをみるとIENDもあったので、取り出せそうです．ただ、IHDRより前（厳密にはlength 0d より前）がelfのヘッダーになっているので修正します． solverはpythonで書きました．

from binascii import unhexlify

with open('./signature', 'rb') as f:
    data = f.read().strip()

h = "89504e470d0a1a0a000000"
h = unhexlify(h)
p = data[0x0b:-4]
with open('./flag.png', 'wb') as f:
    f.write(h+p)

f:id:y05h1k1ng:20200126182413p:plain

[Binary 100pts] wrong copy

binaryがもらえるので、初手stringsをします．すると、それっぽいものが見えるのでHだけ取り除くと終わりです．

u+UH
NITAC{c0H
py_15_d1H
ff1cul7}
[]A\A]A^A_

NITAC{c0py_15_d1fficul7} objdumpすらしてないけど、なんだったんだ

[Crypto 100pts] base64

自明 of 自明 echo "TklUQUN7RE9fWU9VX0tOT1dfQkFTRTY0P30K" | base64 -d

NITAC{DO_YOU_KNOW_BASE64?}

[Crypto 200pts] knapsack

暗号文と鍵しかもらえないです．問題名からひねりのないナップサック暗号と仮定して、solverに投げます．

from sage.all import *
from binascii import unhexlify

with open('./ciphertext.txt') as f:
    c = int(f.read().strip())
with open('./publickey.txt') as f:
    data = f.read().strip()
pk = list(map(int, data.split(', ')))

def create_matrix(c, pk):
    n = len(pk)
    i = matrix.identity(n) * 2
    last_col = [-1]*n
    first_row = []
    for p in pk:
        first_row.append(p)
    first_row.append(-c)
    
    m = matrix(ZZ, 1, n+1, first_row)
    m = 1000 * m
    bottom = i.augment(matrix(ZZ, n, 1, last_col))
    m = m.stack(bottom)
    return m

def find_short_vector(matrix):
    for col in matrix.columns():
        if col[0] != 0:
            continue
        if is_short_vector(col):
            return col

def is_short_vector(vector):
    for v in vector:
        if v != 1 and v != -1 and v != 0:
            return False
    return True

m = create_matrix(c, pk)
lllm = m.transpose().LLL().transpose()
short_vector = find_short_vector(lllm)
solution_vector = []
for v in short_vector:
    if v == 1:
        solution_vector.append(1)
    elif v == -1:
        solution_vector.append(0)
m = "".join(map(str, solution_vector))

print(unhexlify(hex(int(m, 2))[2:]))

$ sage solver.py 
b'NITAC{Ra1ph_Merk1e&Martin_Edward_He11man}'

ナップサック暗号の資料としては、これがわかりやすいです．

katagaitai workshop #7 crypto ナップサック暗号と低密度攻撃 from trmr

www.slideshare.net

lazyのsolverと同じでよくて、去年の年末にあった韓国のChiristmasCTFでも同じでも同じことをしました．

暗号化をするスクリプトを配布しないのは、いまいちかなと思いました．

[Crypto 200pts] modulo

こちらが入力した $n$ でflagのmodを取ったものが返ってきます．ただ、 $n$ の範囲が $$ 0 < n < 123456$$ なのでflagの下位ちょっとしか分からないです．

ポイントとしては、こちらが自由に法を取ることができることです．つまり、中国人剰余定理を用いることで、flagを見つけることができます．初めは、中国人剰余定理って2つ素数（厳密には互いに素なやつ）で成り立つやつやんけと思っていたのですが、ふるつきに一般化したやつあるぞと言われるまで、完全に忘却の彼方でした． Wikipediaにあるように一般的な定理を用いることで、どの2つも互いに素な任意の整数 $m_i$ の総乗を法とした $x$ をもとめることができます（変数名はwikipediaより）．

互いに素な任意の整数を取るわけですが、範囲内でとりうる大きな素数を持ってこればよいです．ただ、 $x$ は求めたいflagなので、 $\prod_{i=0}^n m_i$ がflagより大きくないといけないことに注意しなければなりません．

さっとスクリプトを書いてもいいですが、脳死マンはsageでさくっと作ります（適当に20個ぐらいあればflagより大きくなるかという気持ち）．

sage: p = 123456
sage: ps = []
sage: for i in range(20):
....:     p = previous_prime(p)
....:     ps.append(p)

これで psができたので、これを法とした任意の整数 $a_i$ をserverから取得します（素数だからpsと名付けましたが、wikipedia通りに行くなら $m_i$ のことです）．

from ptrlib import *
import re

ps = [123449, 123439, 123433, 123427, 123419, 123407, 123401, 123397, 123379, 123377, 123373, 123341, 123323, 123311, 123307, 123289, 123269, 123259, 123239, 123229, 123217, 123209, 123203, 123191, 123169, 123143, 123127, 123121, 123113, 123091]

cs = []
for p in ps:
    sock = Socket('modulo.ctf.jyoken.net', 80)
    sock.recvuntil('n = ')
    sock.sendline(str(p))
    data = sock.recvline().strip().decode()
    c = int(re.compile(r'(\d+)').findall(data)[0])
    cs.append(c)
    sock.close()

print(ps)
print(cs)

これで、後は中国人剰余定理を適応すれば解けます．なぜかここで、僕はsageを使って解きました．（良い子は、行ったり来たりしないようにしましょう！ミス防止のためにも）

sage: ps = [123449, 123439, 123433, 123427, 123419, 123407, 123401, 123397, 123379, 123377, 123373, 123341, 123323, 123311, 123307, 123289, 123269, 123259, 123239, 123229, 123217, 123209, 123203, 123191, 
....: 123169, 123143, 123127, 123121, 123113, 123091]
sage: cs = [36600, 44509, 46577, 34045, 22782, 110367, 13713, 6285, 25340, 26323, 114854, 15597, 14353, 69992, 27973, 62704, 87354, 88307, 115945, 96226, 99843, 16210, 47993, 27209, 30470, 69517, 22583, 7
....: 7273, 90434, 56007]
sage: m = CRT(cs, ps)
sage: from binascii import unhexlify
sage: unhexlify(hex(m)[2:])
b'NITAC{CRT_4lw4ys_h3lps_m3}'

sageのスクリプト上で外部パッケージ（ptrlibとかpycryptodomeとか）がインポートできない問題に悩まされているのですが、いつになったら解決できるんだろうか

[Crypto 300pts] Circular RSA

以下のスクリプトがもらえます．

from Crypto.Util.number import getPrime
from secret import flag

m = int.from_bytes(flag, byteorder='big')
assert m.bit_length() < 1024

p, q = getPrime(512), getPrime(512)
n = p * q
e = 0x10001
c = pow(m, e, n)
rr = (p**2 + q**2) % n

print("(p, q) is over R: x^2 + y^2 = {} mod {}".format(rr, n))
print("c = {}".format(c))

変わった点といえば、 $$x²+y²$$ がもらえます．ここからひたすら式をイジイジするのですが、手掛かりになりそうな式を立てることができませんでした．こうしていると、以下のヒントが公開されました．

Circular RSA：(p^2+q^2) / (pq)の取り得る値の範囲を考える

範囲といわれると、とりあえずwolfram alphaへ投げます．すると、wolfram alphaは賢いので、式を以下のように変形してくれました． (p² + q²) / (pq) = p/q + q/p ここで、(p² + q²) / (pq)が意味するのは、p² + q² = r % n を商と余りの関係から、p² + q² = kn + rと直したときのkに当たるものです．つまりk = p/q + q/pとなり、p, qは同じビット数であり近いので、kが非常に小さいことがわかります（厳密にはkは3以上になることはないのですが詳しくは作問者writeupを見てください）．

この辺りで、わちゃわちゃしていたら、ふるつきがk = 2っぽいぞということを教えてくれました．

以上より、合同式ではなく、等式としての p² + q²を求めることができました．あとは、p * q = nをもっているので、連立方程式として解くことができそうです．ここでもsageを使います．sageを使うと脳死で連立方程式が解けるので、頭が弱い僕はガンガン使っていきます．

from sage.all import *
from binascii import unhexlify
import re

with open('./chall.txt') as f:
    data = f.read().strip()

r, c = map(int, re.compile(r' = (\d+)').findall(data))
n = int(re.compile(r' mod (\d+)').findall(data)[0])

k = 2

p, q = var('p q')
eq1 = p*q == n
eq2 = p**2 + q**2 == r + k*n

sols = solve([eq1, eq2], p, q, solution_dict=True)

for s in sols:
    sol_p = s[p]
    sol_q = s[q]
    if 0 < sol_p and 0 < sol_q and sol_p * sol_q == n:
        d = inverse_mod(0x10001, n - sol_p - sol_q + 1)
        m = pow(c, d, n)
        flag = unhexlify(hex(m)[2:])
        if b'NITAC' in flag:
            print(flag)
            exit()

$ sage solver.py 
b'NITAC{r3str1ct10n_r3v34ls_1nf0rm4t10n}'

yoshikingのがんばる日記

あたまよくないけどがんばります

NITAC miniCTF 3rd Writeup