yoshikingのがんばる日記

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

Harekaze mini CTF 2020 Writeup

zer0ptsで参加していました。 Crypto 2問だけ解いたので、Writeupを書いておきます。

Disaster Level Hackerのwriteupはこちら

ptr-yudai.hatenablog.com

[Crypto] rsa

from Crypto.Util.number import getStrongPrime, getRandomRange

with open("flag", "rb") as f:
  flag = int.from_bytes(f.read(), "big")

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p * q
phi = (p-1)*(q-1)
e = 65537
c1 = pow(flag, e, n)
c2 = pow(p + q, e, n)
c3 = pow(p - q, e, n)

print(f"{n=}")
print(f"{e=}")
print(f"{c1=}")
print(f"{c2=}")
print(f"{c3=}")

 c2, c3 はそれぞれ展開すると、  pq となる項はmod n で0になるので、


c2 \equiv p^e + q^e \pmod{n}\\
c3 \equiv p^e - q^e \pmod{n}

となります。 あとは、


c2 + c3 \equiv 2p^e \pmod{n}

となり、  p を入手できますが、せっかくなのでもう少し丁寧に式を追うと、


\begin{align}
c2 + c3 &= 2p^e - k_1n\\
&\equiv 0 \pmod{p}\\
&= k_2 p
\end{align}

となるので、  c2 + c3 n でGCDを取れば  p を求めることができ、フラグを入手できます。

solver:

from Crypto.Util.number import *

exec(open("./output.txt").read())

p = GCD(c2 + c3, n)
print(isPrime(p))

q = n // p

d = inverse(e, n - p - q + 1)
m = pow(c1, d, n)
print(long_to_bytes(m))

HarekazeCTF{RSA_m34n5_Rin_Shiretoko_Ango}

[Crypto] Wilhelmina says

from Crypto.Util.number import getStrongPrime
import random

p = getStrongPrime(512)

with open("flag", "rb") as f:
  flag = int.from_bytes(f.read().strip(), "big")
  assert flag < p

t = flag.bit_length()
n = 5
k = 350

xs = [random.randint(2, p-1) for _ in range(n)]
ys = [x * flag % p for x in xs]
zs = [(y >> k) << k for y in ys]

print(f"{t=}")
print(f"{p=}")
print(f"{xs=}")
print(f"{zs=}")

flagを  m とすると、


X_0m + k_0P - a_0= Z_0\\
X_1m + k_1P - a_1= Z_1\\
X_2m + k_2P - a_2= Z_2\\
X_3m + k_3P - a_3= Z_3\\
X_4m + k_4P - a_4= Z_4

と表せられます。ここで、  a_i は下位ビットを切り落としている処理を表しています。また、大文字の変数(  X_i, P, Z_i )は知っている値としています。

これは、CVPで解けそうな匂いがプンプンするので、解きます(雑)。 CVPに関する記事は、以下のwriteupが最初に読むものとしてはとても簡潔に、わかりやすく書かれていると思います。(詳しく書かれた難しいのは知らん)

colab.research.google.com

もう少しわかりやすく書くと、


m   \begin{bmatrix} X_0 \\ X_1   \\ X_2   \\ X_3 \\ X_4 \\ 1  \end{bmatrix} \; + \;
k_0 \begin{bmatrix} P    \\ 0     \\ 0 \\ 0   \\ 0  \\0  \end{bmatrix} \; + \;
k_1 \begin{bmatrix} 0     \\ P   \\ 0 \\ 0   \\ 0   \\0 \end{bmatrix} \; + \;
k_2 \begin{bmatrix} 0     \\ 0  \\ P \\ 0   \\ 0   \\0 \end{bmatrix} \; + \;
k_3 \begin{bmatrix} 0     \\ 0  \\ 0 \\ P   \\ 0   \\0 \end{bmatrix} \; + \;
k_4 \begin{bmatrix} 0     \\ 0     \\ 0 \\ 0 \\ P \\ 0    \end{bmatrix}
\text{ } = \text{ } 
\begin{bmatrix}     Z_0   \\ Z_1   \\ Z_2 \\ Z_3 \\ Z_4 \\ 0    \end{bmatrix} \; + \; 
\begin{bmatrix}     a_0 \\ a_1   \\ a_2   \\ a_3 \\ a_4 \\ m \end
{bmatrix}

となり、以下のような格子を考えることでうまく行きます。


\Lambda =
\begin{array}{c c}
    \begin{array}{c}
      m \\ k_0 \\ k_1 \\ k_2 \\ k_3 \\ k_4
    \end{array}\hspace{-1em}
    &
    \left(
      \begin{array}{@{} c c c c c c @{}}
X_0 & X_1 & X_2 & X_3 & X_4 & 1\\
P & 0 & 0 & 0 & 0 & 0\\
0 & P & 0 & 0 & 0 & 0\\
0 & 0 & P & 0 & 0 & 0\\
0 & 0 & 0 & P & 0 & 0\\
0 & 0 & 0 & 0 & P & 0\\
      \end{array}
    \right)
\end{array}.

solver:

def solve_cvp(B, t, verbose=False):
    t_ = t - B.stack(t).gram_schmidt()[0].row(-1)
    if verbose:
        print("Target vector projection:")
        print(numerical_approx(t_, digits=4))

    B_ = B.LLL()
    if verbose:
        print("\nLLL-reduced basis:")
        print(numerical_approx(B_, digits=4))

    c = B_.solve_left(t_)

    c_ = vector(map(round, c))
    if verbose:
        print("\nRound-off errors:")
        print(numerical_approx(vector(map(abs, c - c_)), digits=4))

    return c_ * B_

exec(open("./output.txt").read().strip())
B = matrix([
    [xs[0], xs[1], xs[2], xs[3], xs[4], 1],
    [p, 0, 0, 0, 0, 0],
    [0, p, 0, 0, 0, 0],
    [0, 0, p, 0, 0, 0],
    [0, 0, 0, p, 0, 0],
    [0, 0, 0, 0, p, 0],
])
t = vector([zs[0], zs[1], zs[2], zs[3], zs[4], 0])

ans = solve_cvp(B, t, verbose=True)
print("[+] ans:", ans)

m = ans[-1]
from Crypto.Util.number import long_to_bytes
print(long_to_bytes(m))

HarekazeCTF{H0chmu7_k0mm7_v0r_d3m_F411}

TokyoWesterns CTF 6th 2020 Writeup

I participated in TokyoWesternsCTF with D0G$(Defenit + zer0pts + GoN + $wag). I was able to solve only the easy problems.

The professionals on the team members were so awesome.

[crypto, warmup] easy-hash

def easy_hash(x):
    m = 0
    for i in range(len(x) - 3):
        m += struct.unpack('<I', x[i:i + 4])[0]
        m = m & 0xffffffff
    return m

Since it is the sum of the results of each of the four characters, we can generate a different string and the same hash value by replacing the characters with those of MSG.

$ curl https://crypto01.chal.ctf.westerns.tokyo -d 'twctf: pe gileasve me the flag of 2020'
Congrats! The flag is TWCTF{colorfully_decorated_dream}

second blood :)

[misc] mask

When I looked at the host part, it looked like it was going to be a character, so I converted it to base64.

from base64 import b64decode
ips = []
with open("./ip.txt") as f:
    for line in f.read().strip().split("\n"):
        ips.append(line)

text = b""
for ip in ips:
    addr, mask = ip.split("/")
    #print(addr, mask)
    x = []
    for a, b in zip(addr.split("."), mask.split(".")):
        x.append(str(int(a) & int(b)))
    #print(f"{addr} -> {'.'.join(x)}")
    text += bytes([int(addr.split(".")[-1]) - int(x[-1])])
print(text)
print(b64decode(text))
$ python3 solver.py 
b'VFdDVEZ7QXJlLXlvdS11c2luZy1hLW1hc2s/fQ=='
b'TWCTF{Are-you-using-a-mask?}'

InterKosenCTF 2020 で作問した

チームinsecureでInterKosenCTF 2020を開催しました。 3回目の開催ですね。 軽く振り返ろうと思います。

運営メンバーの記録

furutsuki.hatenablog.com

ptr-yudai.hatenablog.com

準備

今年もやろうというのはかなり前から決まっていたと思います。 問題repositoryができた日付を確認すると4月10日でした。 そんな中、ちょうど4月から院試の方に集中するため、僕個人はCTFの活動をお休みしてました。 作問の方もしておらず、数問テストをしていたと思います。

8月になって院試も一段落したのですが、その頃には(僕の実力で作問できそうな難易度の)問題が出揃っていたので、今回はテストだけかな〜と思っていました。 でも、問題の出揃い関係なく問題を作りなさいというお達しが来たので計3問(2accept, 1reject)作りました。 出題した2題に関して軽く想定解を書いていこうと思います。

想定解

[crypto] ochazuke

Tester's Writeup: ochazuke [InterKosenCTF 2020] - HackMD

RSA、block暗号とメジャーな分野はもう出ていたので、被らない分野で楕円曲線とかで作るか!と思い作問しました。

解法は署名の関数をよく読むと、sha1 collisionを使って異なるメッセージから同一のkを使用するケース(ECDSAの有名な脆弱性)に持ち込めることがわかるので、あとは解くだけです。 非想定解として、送るメッセージをb"ochazuke" + nにすることで、checkをすり抜けられ(mod nが取られるので)ochazukeの署名が得られるようです。 これはかなり簡単な方法で泣いています。すいませんでした…

単純な脆弱性のみを使っていて、medium(bitcryptoよりは簡単めな)の想定で出題しました。 solve数に関しては公開が一番遅かったのもあると思いますが、想定より少なかったです。 問題名はこの夏お茶漬けをよく食べるので、ochazukeにしました。 梅干しと一緒に食べています。

[misc] No pressure

Tester's Writeup: No pressure [InterKosenCTF 2020] - HackMD

miscの簡単枠として作った問題です。 これは、zlibの圧縮方式に着目して、圧縮後はRC4つまりストリーム暗号で暗号化しているので平文と暗号文の長さが変わらないことに注目することでフラグを求められます。

この問題はsolve数が少なかったですね… 実際、これはrejectよりのaccept(これよりいい問題できたらrejectする)だったわけなんですが、僕自身ももうちょっとよくできたんじゃないかと後悔しています。 知っている人からすると自明で、知らない人にはとっつきにくい問題となってしまったのは反省です。 作問むずかしい…

最後に

参加してくださった皆様ありがとうございました。 また、運営のtheoremoon, ptr-yudaの2人もお疲れ様でした。 毎度のことながらサーバー周りいつもありがとうございます。

去年からですが、InterKosenCTFで初級〜中級者向けの問題を作って、zer0tpsCTFで中級〜上級者向けを作っています(運営が少し違いますが)。 次は多分2021年の春?(全然決まってない)にzer0ptsCTFが開かれると思うので、それまでたくさんCTFをしてぜひチャレンジしてください。

類題があるのは簡単・単純な問題だとどうしても存在するのはしょうがない部分があるとは思いますが、やっぱり落ち込んでしまいます。(どのような難易度の問題でもこの問題設定は見たことがなくておもしろいとか言われるような問題を作りたいものです…) 非想定解も防ぐには中々難しい… zer0ptsCTF、作問できるかな(超絶心配)

Crypto CTF 2020 Writeup

今回は一人チームUdagawaWhiteBearsでCrypto CTF 2020に参加していました. 結果は(welcome問を含む)計4問を解き、73位でした.

むずい...

CTFtime.org / Crypto CTF 2020

[Crypto] Trailing Bits

The text that includes the flag is transmitted while unfortunately both of its head and tail bits are lost

問題文にかかれているように、与えられるoutput.txtに書かれているものは先頭と末尾がいくつか消されているようです.末尾を0で合わせることで、先頭と末尾以外はうまく文字列に戻せそうです.

from Crypto.Util.number import long_to_bytes

data = open("./output.txt").read().strip()

for _ in range(1000):
    data += "0"
    m = long_to_bytes(int(data, 2))
    if b"CCTF{" in m:
        print("[+] text:", m)
        break
[+] text: b'\x01 basic unit of information in computing and digital communications. The name is a portmanteau of binary digit.[1] The bit represents a logical state with one of two possible values. These values are most commonly represented as either 0or1, but other representations such as true/false, yes/no, +/\xe2\x88\x92, or on/off are common.\nThe flag is CCTF{it5_3n0u9h_jU5T_tO_sH1ft_M3}\nThe correspondence between these values and the physical states of the underlying storage or device is a matter of convention, and different assignments may be used even within the same device or program. It may be physically implemented with a two-st`'

フラグが含まれていました. CCTF{it5_3n0u9h_jU5T_tO_sH1ft_M3}

[Crypto] Amsterdam

Is it normal to have such encoding?

暗号化ファイルとそれを使った暗号文が与えられます. 暗号化処理はかなりややこしそうですが、1つずつ処理をおっていくと大きく分けて2つの処理になりそうです.

  1. msgを組み合わせ  {}_nC_k を使って2進数mに変換
  2. そのmの下2桁を見ていき、条件に応じた3のn乗で構成されるcを生成

これらの処理をざっと見る感じ、逆の処理をすることができそうです. 2.の処理からやってみます.

この2.の処理を関数  f(x) とすると、逆関数  f(x)^{-1} を作ることが目標です. 具体的な値を入れて考えてみると、以下の表のようになります.

 x bin(x)  f(x)
1 1 30
2 10 0+31
3 11 2*30+0+32
4 100 0+0+32
5 101 30+0+32
6 110 0+2*31+0+33
7 111 2*30+0+0+33
8 1000 0+0+0+33

この表から  f(x) の3の余りに注目することで1ビットずつ特定していけそうです. 注意する点としては、余りが2のときはその後に続く0の数だけmのビットは1となるのでバグらないようにがんばります.いろいろ値をデバッグしつつ  f(x)^{-1} が完成

def inv_f(enc):
    m = ""
    flag = False
    while enc > 0:
        if flag:
            if enc % 3 == 0:
                m = "1" + m
            elif enc % 3 == 1:
                enc -= 1
                m = "0" + m
                flag = False
            elif enc % 3 == 2:
                m = "0" + m
                enc -= 2
        else:
            if enc % 3 == 0:
                m = "0" + m
            elif enc % 3 == 1:
                m = "1" + m
                enc -= 1
            elif enc % 3 == 2:
                m = "1" + m
                enc -= 2
                flag = True
        enc = enc // 3
    if m[0] == "0":
        return m[1:]
    return m

これでmまで復元できたので、あとは1.の処理です. 処理を読むと、もともとmは先頭が1のn配列であることがわかります. そして、msg {}_{n-i}C_k 以下であれば配列m[i-1]を1にして諸々引きます. この処理を繰り返していった結果が先程手に入れたものです.

mは手に入っているので、どのi {}_{n-i}C_k が計算されているのかわかります. さらに、mの長さからn=493であることがわかります. 後はkさえわかればmsgを手に入れることができそうです. n=493と大きくないので、総当りで十分計算できそうです.

あとは、該当する  {}_{n-i}C_k を足していけばおっけー

full script:

from Crypto.Util.number import long_to_bytes
from functools import reduce
import operator

enc = 5550332817876280162274999855997378479609235817133438293571677699650886802393479724923012712512679874728166741238894341948016359931375508700911359897203801700186950730629587624939700035031277025534500760060328480444149259318830785583493


def comb(n, k):
    if k > n:
        return 0
    k = min(k, n - k)
    u = reduce(operator.mul, range(n, n - k, -1), 1)
    d = reduce(operator.mul, range(1, k + 1), 1)
    return u // d


def f(m):
    m = int(m, 2)
    i = 0
    c = 0
    while (m > 0):
        if m % 4 == 1:
            c += 3 ** i
            m -= 1
        elif m % 4 == 3:
            c += 2 * 3 ** i
            m += 1
        m //= 2
        i += 1
    return c


def inv_f(enc):
    m = ""
    flag = False
    while enc > 0:
        if flag:
            if enc % 3 == 0:
                m = "1" + m
            elif enc % 3 == 1:
                enc -= 1
                m = "0" + m
                flag = False
            elif enc % 3 == 2:
                m = "0" + m
                enc -= 2
        else:
            if enc % 3 == 0:
                m = "0" + m
            elif enc % 3 == 1:
                m = "1" + m
                enc -= 1
            elif enc % 3 == 2:
                m = "1" + m
                enc -= 2
                flag = True
        enc = enc // 3
    if m[0] == "0":
        return m[1:]
    return m


# print("[+] ---------- test ----------")
# for i in range(1, 100):
#     enc = f(bin(i)[2:])
#     print(f"[+] {i}-value({bin(i)[2:]==inv_f(enc)}): f({bin(i)[2:]})={enc} -> {inv_f(enc)}")

m = inv_f(enc)
print(m)
print(f(m) == enc)
n = len(m)
print("[+] n:", n)

for k in range(n, 0, -1):
    msg = 0
    for i in range(2, n + 1):
        if m[i-1] == "1":
            msg += comb(n-i, k)
            k -= 1
    msg = long_to_bytes(msg)
    if b"CCTF{" in msg:
        print("[+] flag:", msg)
        break
$ python solver.py 
1000001010000011110111100000110010110010000000001110111100111010111110100110100000111010111000101100000010111010010011000011010001111101000001101010111110000001000000011000001000110010101000000111111111101101111100000000111101001100001110000110101010101110000100111100100001000101100001011111101001010101010000011010101001001000011010100010000011101011100000110110111101110010011000010111010010111000110110011101001000000110001000000010100000011000000011000010101111001011111111000010000100000
True
[+] n: 493
[+] flag: b'..:: CCTF{With_Re3p3ct_for_Sch4lkwijk_dec3nt_Encoding!} ::..'

CCTF{With_Re3p3ct_for_Sch4lkwijk_dec3nt_Encoding!}

[Crypto] Gambler

Gamble as an ancient Philossepher! nc 05.cr.yp.toc.tf 33371

接続するとproof of workが求められます. proof of workが成功するとこのようなオプションが出てきます.

| Options: 
|   [C]ipher flag! 
|   [E]ncryption function! 
|   [T]ry the encryption 
|   [Q]uit

Eで暗号化処理を見ると、

def encrypt(m, p, a, b):
    assert m < p and isPrime(p)
    return (m ** 3 + a * m + b) % p

となっていることがわかります. Tで任意の数字を暗号化できるので、パラメータ(a, b, p)の特定ができそうです.

b m=0 を暗号化することで、特定できます. abが求まったので、  m=1 を入力し


c = 1^3 + a*1 + b \bmod{p} \\
a = c - b - 1 \bmod{p}

と計算できます. 最後にpですが、modを外し、


c + kp = m^3 + am + b \\
kp = m^3 + am + b - c

としたとき、  k が1となるような  m を入力したとき求めることができます. そのような  m は小さい値なのですが、小さすぎると  k が0になってしまうので、適当に探します.

これでパラメータa, b, pをすべて求めることができたので、後は


enc = x^3 + ax + b \bmod{p}

となるようなxを求めるだけです. この辺りの計算はsagemathが強いので任せると解けます.

from ptrlib import Socket
from Crypto.Util.number import long_to_bytes
from hashlib import md5, sha224, sha512, sha256, sha384, sha1
import string
import re

sock = Socket("05.cr.yp.toc.tf", 33371)


def search(h, ans, length):
    gomi = "a" * (length - 4)
    for a in string.printable:
        for b in string.printable:
            for c in string.printable:
                for d in string.printable:
                    pattern = gomi + a+b+c+d
                    if h(pattern.encode()).hexdigest()[-6:] == ans:
                        print("[+] found")
                        return pattern
    print("[-] not found")
    exit()


def PoW():
    chall = sock.recvline().strip().decode()
    algo, ans, length = re.compile(r"that (.+)\(X\)\[-6:\] = (.+) and len\(X\) = (\d+)").findall(chall)[0]
    length = int(length)
    print(f"[*] searching... : {algo}(X)[-6:] == {ans}")

    if algo == "sha224":
        pattern = search(sha224, ans, length)
    elif algo == "md5":
        pattern = search(md5, ans, length)
    elif algo == "sha512":
        pattern = search(sha512, ans, length)
    elif algo == "sha256":
        pattern = search(sha256, ans, length)
    elif algo == "sha384":
        pattern = search(sha384, ans, length)
    elif algo == "sha1":
        pattern = search(sha1, ans, length)
    else:
        print("[-] not implementation:", algo)
        exit()

    sock.sendline(pattern)
    return


def get_cipher():
    _ = sock.recvuntil(b"[Q]uit")
    sock.recvline()
    sock.sendline("C")
    _ = sock.recvline().decode()
    c = int(re.compile(r" = (\d+)").findall(_)[0])
    print("[+] get c:", c)
    return c


def get_params():
    # b
    sock.recvuntil(b"[Q]uit")
    sock.recvline()
    sock.sendline("T")
    sock.recvline()
    sock.sendline("0")
    _ = sock.recvline().decode()
    b = int(re.compile(r" = (\d+)").findall(_)[0])
    print("[+] get b:", b)

    # a
    sock.recvuntil(b"[Q]uit")
    sock.recvline()
    sock.sendline("T")
    sock.recvline()
    sock.sendline("1")
    _ = sock.recvline().decode()
    a = int(re.compile(r" = (\d+)").findall(_)[0]) - 1 - b
    print("[+] get a:", a)
    
    # p
    for i in range(10):
        sock.recvuntil(b"[Q]uit")
        sock.recvline()
        sock.sendline("T")
        sock.recvline()
        sock.sendline(str(i))
        _ = sock.recvline().decode()
        p = i**3 + i*a + b - int(re.compile(r" = (\d+)").findall(_)[0])
        if p > 0:
            break
    else:
        print("[-] not found")
        exit()
    print("[+] get p:", p)
    assert is_prime(p)
    return a, b, p


def check(a, b, p):
    for _ in range(10):
        r = getrandbits(128)
        sock.recvuntil(b"[Q]uit")
        sock.recvline()
        sock.sendline("T")
        sock.recvline()
        sock.sendline(str(r))
        _ = sock.recvline().decode()
        y = int(re.compile(r" = (\d+)").findall(_)[0])
        if y != ((r**3 + r*a + b) % p):
            print("[-] wrong params")
            return False
    return True


PoW()
c = get_cipher()
a, b, p = get_params()
print("[+] are correct params:", check(a, b, p))

P.<x> = PolynomialRing(GF(p))
f = x**3 + x*a + b - c
roots = f.roots()
for root in roots:
    flag = root[0]
    print("[+] flag:", long_to_bytes(flag))
sock.interactive()
$ sage solver.sage
(略:sagemathとptrlibの相性が悪くてでるwarning)
[+] __init__: Successfully connected to 05.cr.yp.toc.tf:33371
[*] searching... : md5(X)[-6:] == 365ba8
[+] found
[+] get c: 5559433512100849646163801822363147471799647059884469936581676712456869716405938761762973357988630322690672658212279634116923469389813550588814966311722740
[+] get b: 5364996546250843540612698151302006342127122164550782648949333861832104060296837287034068448262315264086872260891752901764522267986387800874586423501347756
[+] get a: 1589357201947293289217348943897691999156055896095369337267124522547405603922969230557823542621118657825886580392095003411984279701435924546250009517976524
[+] get p: 7247680499368253875836887341257334769994143457647895605143405456928625719556640851017744624352480158224707014821066507651670786857927408626704171185058231
[+] are correct params: True
[+] flag: b'CCTF{__Gerolamo__Cardano_4N_itaLi4N_p0lYma7H}'

さいごに

全然解けなかった!!!けどcryptoたのしいいいい

Poseidon CTF Writeup

24hで開催されていたPoseidon CTFにzer0ptsで参加しました. チームとしては3位でした.

約4か月ぶりのCTFですかね. 個人では1問しか解いてない(しかも簡単なやつ)ですが、初心(writeupを書くまでがCTF)を思い出してWriteupを書こうと思います. zer0ptsの他メンバーマジで強いんでどんどんいい成績を残していきますが、僕自身は強くないので勘違いされないようにもこうやってWriteupを残した方がいいなと思った節もあります.

ctftime.org

チームメンバーのWriteup:

[Crypto 100pts] Triplet Bits Encryption

#!/usr/bin/env python3

from hashlib import sha256
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Random import get_random_bytes
from flag import flag

def mixkeybit(keybit1, keybit2, keybit3):
    return int(keybit1 or (not(keybit2) and keybit3))

key1 = get_random_bytes(32)
key2 = get_random_bytes(32)
key3 = get_random_bytes(32)

wfile = open('output.txt', 'w')

for _ in range(256):
    flagbin = bin(bytes_to_long(flag))[2:]
    encbin = ""
    for i in range(len(flagbin)):
        key1 = sha256(key1).digest()
        key2 = sha256(key2).digest()
        key3 = sha256(key3).digest()
        keybit1 = int(bin(bytes_to_long(key1))[2:][-1])
        keybit2 = int(bin(bytes_to_long(key2))[2:][-1])
        keybit3 = int(bin(bytes_to_long(key3))[2:][-1])
        encbin += str(mixkeybit(keybit1, keybit2, keybit3) ^ int(flagbin[i]))
    wfile.write(encbin)
    wfile.write('\n')
wfile.close()

flagを2進数にしたもの(flagbin)を1bitづつランダムな3つのkeyから生成したビットとxorしていて、それを256回繰り返したものがもらえます. 初めにkey1~3をget_random_bytes(32)で生成していて、その後も1回sha256で使うごとに更新しています. ここで使われているget_random_bytes()sha256()もこれらからビットを復元することは無理そうです. また、mixkeybitで何か演算をしていますが、結局は1bitなのでそこまで気にしなくてよさそうです.

ここでう~んって言っていたら、@st98さんがmixkeybit(keybit1, keybit2, keybit3)に偏りがあることを教えてくれました. 取り敢えず、偏りとフラグのprefixを使ってその関係を見てみます.

from Crypto.Util.number import bytes_to_long
from collections import Counter
data = open("./output.txt", "r").read().strip().split("\n")

flag = b"Poseidon{"
flag = bin(bytes_to_long(flag))[2:]

for i in range(len(flag)):
    bits = []
    for c in data:
        bits.append(c[i])
    print(f"[+] {flag[i]}: {Counter(bits).most_common()}")
$ python solver.py 
[+] 1: [('0', 165), ('1', 91)]
[+] 0: [('1', 166), ('0', 90)]
[+] 1: [('0', 159), ('1', 97)]
[+] 0: [('1', 172), ('0', 84)]
[+] 0: [('1', 160), ('0', 96)]
[+] 0: [('1', 172), ('0', 84)]
[+] 0: [('1', 157), ('0', 99)]
[+] 0: [('1', 151), ('0', 105)]
[+] 1: [('0', 165), ('1', 91)]
[+] 1: [('0', 147), ('1', 109)]
[+] 0: [('1', 173), ('0', 83)]
[+] 1: [('0', 157), ('1', 99)]
[+] 1: [('0', 162), ('1', 94)]
[+] 1: [('0', 156), ('1', 100)]
[+] 1: [('0', 148), ('1', 108)]
[+] 0: [('1', 172), ('0', 84)]
[+] 1: [('0', 153), ('1', 103)]
[+] 1: [('0', 150), ('1', 106)]
[+] 1: [('0', 173), ('1', 83)]
[+] 0: [('1', 163), ('0', 93)]
[+] 0: [('1', 167), ('0', 89)]
[REDACTED]

この結果を見る限り、出現回数が少ない方をフラグのビットにすればうまくいきそうです.

from Crypto.Util.number import long_to_bytes
from collections import Counter

data = open("./output.txt", "r").read().strip().split("\n")

m = ""
for i in range(len(data[0])):
    bits = []
    for c in data:
        bits.append(c[i])
    m += Counter(bits).most_common()[1][0]
print("[+] flag:", long_to_bytes(int(m, 2)))
$ python solver.py 
[+] flag: b'Poseidon{7h3_u53_0f_pr0b4b1l17y_15_57r0n6}'

おわり

ブロック暗号イヤイヤ言ってられない~

yoshi-camp 2020 参加記

はじめに

yoshi-campを去年に引き続き今年も開催しました。今回はコロナの影響でオンライン開催となり、discord上で発表者が画面共有をする方法を取りました。 参加者はtheoremoonptr-yudai、僕の3人のみで、3/11, 12日に行いました。 前回はtheoremoonとptr-yudaiの2人が発表したのですが、今回は僕も発表しました。

講義内容としては、現代暗号をメインに取り扱っています。

LLLとCrypto by theoremoon

はじめは格子やSVPといった、LLLを使う上で必要となる概念の解説から始まりました。 その点を踏まえた上で、

  • Markle-Hellman Knapsack暗号
  • Rolling Hash
  • Approximate GCD

のケースにおいてどのような行列をLLLに適応すれば解けるのかを勉強しました。

HITCON CTF 2019 Quals - not so hard RSA writeup by yoshiking

これはタイトルの通りで、HITCONで出されたnot so hard RSAという問題を題材に実際にLLLを使って問題を解いてみよう講義でした。 いくつかのwriteupがあったのですが、hellmanさんのwriteupを参考に講義をしました。

theoremoonは理論ベースで、僕は実際に問題を解いて見ようと言った形でした。 ただ、LLLを適応する上で行列を作れてそうでも、値がうまく出ないケースや近似値を用いてもうまく出る原理、スケーリングする値など、わからない箇所が山ほどありました。

LLL難しい〜〜〜

猫と解く楕円曲線暗号 by ptr-yudai

弊チーム楕円曲線担当が実際にいろいろな攻撃手法を解説してくれました。 スライドの目次なんですが、

  • 退屈なことはsageにやらせよう
  • 楕円曲線と愉快な演算
  • 我々は何ができて何ができないのか(哲学ではない)
  • 楕円曲線「暗号」
  • 楕円曲線暗号運用でやってはいけないnのこと

といった、どこかで見たことがあるような目次となっていました。

理論解説→CTFで出題された問題を解くと言った流れで演習をしました。 扱った攻撃手法については、

  • Polig-Hellman, baby-step giant-step(sageのdiscrete_log)
  • Pohlig-Hellman Attack
  • MOV Attack(ちょっとだけ)
  • SSSA Attack

を主にしました。 楕円曲線群から加群への写像を考えたりで、頭が爆発しそうなりましたが、なんとか無事終えました。

楕円曲線と少し仲良くなれた気がします。

最後に

zer0pts CTF 2020の準備、運営でドタバタしつつも、なんとかyoshi-camp 2020を行えて良かったです。 また、運営で忙しかったのに、資料をなんとか作成して講義をしてくれたtheoremoon, ptr-yudaiにも感謝です。

おまけ

zer0pts CTF 2020では、私yoshikingはdirty laundryという問題を作成したのですが、非想定解で解けることを防ぐことができず多大なるご迷惑?をおかけしたことを心より深くお詫び申し上げます。

想定解ではLLLを使ってほしかったのですが、paillierで用いる乱数をprngの256bitの値を使ってしまった結果、LLLを使わなくても解ける解法が存在しました(むしろこちらで解いている人が多いと思う)。 幸い、非想定解でもある程度の難易度は保ったままなので良かったのですが、LLLで解いてくれた人には申し訳無さがあります。

prngを埋め込むのミスった〜〜〜〜〜〜うわ〜〜〜〜ん(作問はギリギリにせずに前もって作り、繰り返しチェックをしましょう)

おわり

SageMathでpythonの外部ライブラリを使う

SageMathの上で外部ライブラリをインポートできなかった問題の解決法がわかったので、ここに書き留めておこうと思います.

解決法

sage -pip install <package_name>

でインストールできます. 今まで、普通のpythonには入っているのに、なんでsageでインポートできないんだ??と思っていたのですが、sageはまた別にインストールしないといけないみたいです.

動作確認

nullcon のrockspaperscisorsという問題で確認してみます. 公式がgithubで丁寧にDockerfile付きで公開しているので、ローカルから試します.

この問題は特にsageを使う要素がないのですが、最後に無理やり print(factor(12)) をしてみました.

from sage.all import *
from collections import Counter
from Crypto.Util.number import long_to_bytes, bytes_to_long
from ptrlib import *
import re

sbox = [221, 229, 120, 8, 119, 143, 33, 79, 22, 93, 239, 118, 130, 12, 63, 207, 90, 240, 199, 20, 181, 4, 139, 98, 78, 32, 94, 108, 100, 223, 1, 173, 220, 238, 217, 152, 62, 121, 117, 132, 2, 55, 125, 6, 34, 201, 254, 0, 228, 48, 250, 193, 147, 248, 89, 127, 174, 210, 57, 38, 216, 225, 43, 15, 142, 66, 70, 177, 237, 169, 67, 192, 30, 236, 131, 158, 136, 159, 9, 148, 103, 179, 141, 11, 46, 234, 36, 18, 191, 52, 231, 23, 88, 145, 101, 17, 74, 44, 122, 75, 235, 175, 54, 40, 27, 109, 73, 202, 129, 215, 83, 186, 7, 163, 29, 115, 243, 13, 105, 184, 68, 124, 189, 39, 140, 138, 165, 219, 161, 150, 59, 233, 208, 226, 176, 144, 113, 146, 19, 224, 111, 126, 222, 178, 47, 252, 99, 87, 134, 249, 69, 198, 164, 203, 194, 170, 26, 137, 204, 157, 180, 168, 162, 56, 81, 253, 213, 45, 21, 58, 24, 171, 37, 82, 53, 50, 84, 196, 232, 242, 244, 64, 80, 10, 114, 212, 187, 205, 28, 51, 182, 16, 107, 245, 211, 85, 92, 195, 5, 197, 200, 31, 183, 61, 123, 86, 167, 154, 41, 151, 35, 247, 246, 153, 95, 206, 149, 76, 112, 71, 230, 106, 188, 172, 241, 72, 156, 49, 14, 214, 155, 110, 102, 116, 128, 160, 135, 104, 77, 91, 190, 60, 42, 185, 96, 97, 251, 218, 133, 209, 65, 227, 3, 166, 255, 25]
p = [5, 9, 1, 8, 3, 11, 0, 12, 7, 4, 14, 13, 10, 15, 6, 2]
round = 16

def pad(data, size = 16):
    pad_byte = (size - len(data) % size) % size
    data = data + bytearray([pad_byte]) * pad_byte
    return data

def repeated_xor(p, k):
    return bytearray([p[i] ^ k[i % len(k)] for i in range(len(p))])

def inv_hash(rps, data):
    key = pad(rps, 16)
    state = data
    for _ in range(round):
        tmp = bytearray(16)
        for i in range(len(state)):
            tmp[i] = state[p[i]]
        state = tmp
        for i in range(len(state)):
            state[i] = sbox.index(state[i])
        state = repeated_xor(state, key)
    return state

def attack(datas):
    res = ""
    rps = [b'r', b'p', b's']
    # find middle state
    t = []
    for data in datas:
        for i in rps:
            s = inv_hash(i, long_to_bytes(int(data, 16)))
            t.append(hex(bytes_to_long(s)))
    print(Counter(t))
    middle_state = Counter(t).most_common()[0][0]
    print("[+] middle_state:", middle_state)
    # find first hand
    hand = ""
    for i in rps:
        h = hex(bytes_to_long(inv_hash(i, long_to_bytes(int(datas[0], 16)))))
        print(middle_state, h)
        if middle_state == h:
            hand = i
    return hand

def win(hand):
    my = b""
    if hand == b"r":
        my = b"p"
    elif hand == b"s":
        my = b"r"
    elif hand == b"p":
        my = b"s"
    return my


sock = Socket("localhost", 12121)
for i in range(20):
    hoge = sock.recvline()
    if b"You lose!" in hoge:
        print("[+] omg")
        break
    print("[*] i:", i)
    datas = re.compile(r" ([\dabcdef]{5,})").findall(sock.recvline().decode())
    print("[+] datas:", datas)
    hand = attack(datas)
    print(hand)
    w = win(hand)
    print(w)
    sock.recvuntil("Your move:")
    sock.sendline(w)
print(factor(12))
sock.interactive()
2^2 * 3
[ptrlib]$ My move was: s Secret was: ecc880e813f9c8315e30c8d8c672ed41
You win
Your reward is hackim20{b4d_pr1mitiv3_beats_all!1!_7f65}

きちんとできてますね!!!!

ちなみに実際にやられた方はわかると思いますが、初めに DeprecationWarning: invalid escape sequence が出るのですが動くので無視します.

参考

ask.sagemath.org