Harekaze mini CTF 2020 Writeup
zer0pts
で参加していました。
Crypto 2問だけ解いたので、Writeupを書いておきます。
Disaster Level Hackerのwriteupはこちら
[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=}")
はそれぞれ展開すると、 となる項はmod n で0になるので、
となります。 あとは、
となり、 を入手できますが、せっかくなのでもう少し丁寧に式を追うと、
となるので、 と でGCDを取れば を求めることができ、フラグを入手できます。
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を とすると、
と表せられます。ここで、 は下位ビットを切り落としている処理を表しています。また、大文字の変数( )は知っている値としています。
これは、CVPで解けそうな匂いがプンプンするので、解きます(雑)。 CVPに関する記事は、以下のwriteupが最初に読むものとしてはとても簡潔に、わかりやすく書かれていると思います。(詳しく書かれた難しいのは知らん)
もう少しわかりやすく書くと、
となり、以下のような格子を考えることでうまく行きます。
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回目の開催ですね。
軽く振り返ろうと思います。
運営メンバーの記録
準備
今年もやろうというのはかなり前から決まっていたと思います。 問題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位でした.
むずい...
[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つの処理になりそうです.
msg
を組み合わせ を使って2進数m
に変換- その
m
の下2桁を見ていき、条件に応じた3のn乗で構成されるc
を生成
これらの処理をざっと見る感じ、逆の処理をすることができそうです.
2.
の処理からやってみます.
この2.
の処理を関数 とすると、逆関数 を作ることが目標です.
具体的な値を入れて考えてみると、以下の表のようになります.
bin(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 |
この表から の3の余りに注目することで1ビットずつ特定していけそうです.
注意する点としては、余りが2のときはその後に続く0の数だけm
のビットは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
が 以下であれば配列m[i-1]
を1にして諸々引きます.
この処理を繰り返していった結果が先程手に入れたものです.
m
は手に入っているので、どのi
で が計算されているのかわかります.
さらに、m
の長さからn=493
であることがわかります.
後はk
さえわかればmsg
を手に入れることができそうです.
n=493
と大きくないので、総当りで十分計算できそうです.
あとは、該当する を足していけばおっけー
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
は を暗号化することで、特定できます.
a
は b
が求まったので、 を入力し
と計算できます.
最後にp
ですが、modを外し、
としたとき、 が1となるような を入力したとき求めることができます. そのような は小さい値なのですが、小さすぎると が0になってしまうので、適当に探します.
これでパラメータa, b, 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を残した方がいいなと思った節もあります.
チームメンバーの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上で発表者が画面共有をする方法を取りました。 参加者はtheoremoonとptr-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
弊チーム楕円曲線担当が実際にいろいろな攻撃手法を解説してくれました。 スライドの目次なんですが、
といった、どこかで見たことがあるような目次となっていました。
理論解説→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
が出るのですが動くので無視します.