場阿忍愚CTF(BurningCTF) Write Up
SITW#29で教えてもらっていたBurningCTFに参加した。ちびちびとしかできなくて一応100位以内には入ったけど、もう少しそれっぽい問題解きたかった。まだまだだなぁ。
初めて使ったライブラリ等あっていいきっかけになった。あと、典型的なものは解き方をストックしておくと別のCTFで役に立ちそうだ。次は何にしようかな。write up書いて残したいから何か締め切りがあるものがいい。
以下、解いた問題に関する記録(1つ解けてないのが混じってるけど)。練習と芸術は省略。
121-二進術-100
対話的に問題を解くことになるけど、問題文から1万回やらないといけないぽいのでプログラムで解いた(hdすると10 27な行があるからここ書き換えたらいいかもしれんけどなるべく機械的に解きたかったので試さなかった)。今回はexpectライブラリで解いてみた。
$ cat solve.rb
require "pty"
require "expect"
PTY.getpty("./121-calculation") do |i, o|
n = 10000
n.times do |j|
i.expect(/((?:\d+)?\s*[-+*\/%]\s*\d+)\s*=\s*/, 10) do |line, question|
o.puts(eval(question).to_s)
end
puts "#{j+1}/#{n}"
end
i.readline
puts "flag: #{i.readline}"
end
$ ruby solve.rb
...
flag: FLAG_5c33a1b8860e47da864714e042e13f1e
IO#expectは期待する出力があるまで待つ処理らしいので、1万回実行した。初めて使ったけど普通に使う分には便利っぽい。
132-解読術-100
忍者といえば以下らしいという事をぐぐったので、
- 忍者といえば「山」「川」の符丁
- 忍者なら当時は神代文字が読めた
見比べながら読むと「やまといえば」という事に見えたので「かわ」と入力。
flag: かわ
133-解読術-200(これは解けてないのでダラダラと残してある作業記録)
とりあえず中身を見てみる。本当に公開鍵のようだ。
$ openssl rsa -inform pem -in Decrypt_RSA/public-key.pem -text -pubin ...
秘密鍵で暗号化してある場合に備えて念のため以下を実行。
$ openssl rsautl -decrypt -inkey Decrypt_RSA/public-key.pem \ -in Decrypt_RSA/flag.txt unable to load Private Key 6629:error:0906D06C:PEM routines:PEM_read_bio:no start line:/SourceCache/OpenSSL098/OpenSSL098-52.8.4/src/crypto/pem/pem_lib.c:648:Expecting: ANY PRIVATE KEY
とりあえず思いつくのはどれかの素因数分解アルゴリズムで見つけやすいnになってるというところだろうか。
以下など見ながら何パターンか試してみる。
まずはnを確認。上を加工してもいいけど、以下で直接。
$ ruby -r openssl -e 'p OpenSSL::PKey::RSA.new(File.open("Decrypt_RSA/public-key.pem")).n.to_i' 3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609
一応既知のものでないかnでぐぐってみるも特になし。(検索語が長過ぎると言われるので適当に切って検索)
何パターンか試してみる。
フェルマー法
pとqが平方根に近いと速そう。
$ cat fermat.rb
def prime_division(n)
x = Math.sqrt(n).to_i + 1
y = Math.sqrt((x ** 2 - n).abs).to_i
loop do
w = x ** 2 - n - y ** 2
if w == 0
return x+y, x-y
elsif w > 0
y = y + 1
elsif w < 0
x = x + 1
end
end
end
p prime_division(ARGV[0].to_i)
$ ruby fermat.rb 3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609
(しばらく待ったけど解けないので違ってそう)
pari/gp
> factor(3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609)
残念ながら手元だとメモリ不足で死んでしまった。
msieve
$ msieve -n -e -v 3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609
残念ながらやってる範囲では終わらなかった。
もし素因数分解に成功していたら
以下で復号しようと思って準備はしていたがその夢はかなわなかった。残念。
試しに128bitの鍵を作ってpublic_encrypt→公開鍵の情報からmsieveで素因数分解→private_decryptで復号まではできたのだが、素因数分解アルゴリズムの事を調べきれないうちにおしまい。似たような事をする機会がまたありそうなので、その時にでも調べよう。
$ cat solve.rb
require 'openssl'
module RSAPrivateKeyAttrRecalculatable
def p=(val)
recalc_attributes do
super
end
end
def q=(val)
recalc_attributes do
super
end
end
private
def recalc_attributes
res = yield
if self.p && self.q
self.d = e.mod_inverse( (p-1)*(q-1) )
self.dmp1 = d % (p - 1)
self.dmq1 = d % (q - 1)
self.iqmp = q.mod_inverse(p)
end
res
end
end
class OpenSSL::PKey::RSA
prepend RSAPrivateKeyAttrRecalculatable
end
pubkey = OpenSSL::PKey::RSA.new(File.open("Decrypt_RSA/public-key.pem"))
pubkey.p = ARGV[0].to_i
pubkey.q = ARGV[1].to_i
puts "flag: #{pubkey.private_decrypt(File.read("Decrypt_RSA/flag.txt"))}"
opensslライブラリ便利だ。今回は以下の事を調べたので次回は調べなくていいのは楽。mod_inverseが用意されてるのがすごいうれしい。どこかで一度正面から突破してみたいな。
- pとqが入ってれば秘密鍵とみなされる
- p=やq=を呼んでもdなどは再計算されない
- というのも、なんの分岐もないから
- 一番嬉しいのはp=とq=をしたらよしなにしてくれる事だけどそこまではしてくれないようだ
- newの時にpとqが指定できるでもよかったんだけど、それも見当たらなかった
以上から自分で再計算するとto_dem後にopensslコマンド叩くなり、private_decryptなりで復号できそうだ(上記)。
Module#prepend使うとこういうのが書きやすくていいので最近多用してる気がするな...
でも残念ながら素因数分解が(手元では)終わらなかったのでアプローチが間違ってるのかもしれない。とここまでが独力。
ひとさまのwrite upを見た後
pとqは既知だったらしい(上でぐぐってるけど、やり方がわるかったかなぁ...)。
$ ruby solve.rb 1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511579 1900871281664822113126851573935413975471896789968515493666638539088027103802104498957191261465571 flag: FLAG_IS_WeAK_rSA
次はfactordbも使ってみよう。
161-電網術-50
- Wiresharkで161-problem.pcapを開く
- ftpでフィルタリングして99フレーム目にFLAG.tarを見ている事を確認
- 100フレーム目以降のパケットを生で見てFLAG.tarとして保存
- 保存したファイルを開くと RkxBR3tYVEluWDY5bnF2RmFvRXd3TmJ9Cg== という文字列が現れる
- $ ruby -r base64 -e 'print Base64.decode64("<4.の文字列>")'
flag: FLAG{XTInX69nqvFaoEwwNb}
162-電網術-75
- Wiresharkで162-basic.pcapを開く
- httpでフィルタリングして39フレーム目にBasic認証に成功したパケットを確認
- ヒントがbasicという事なのでベーシック認証に渡した文字列を確認(aHR0cDovL2J1cm5pbmcubnNjLmdyLmpw保存したファイルを開くと )
- $ ruby -r base64 -e 'print Base64.decode64("<3.の文字列>")'
- http://burning.nsc.gr.jp にアクセスして、ユーザ名に"http"、パスワードに"//burning.nsc.gr.jp"を入力(※Basic認証は:区切り)
5.ではまずパケットが接続してる先を見るべきだったかもしれない。
flag: flag={BasicIsNotSecure}
171-諜報術-100
web.archive.org。
flag: ソフトウェア開発エンジニア
181-記述術-100
大分非効率な感じのスクリプトで見つけた。もっと効率的な方法があるといいなぁ。
$ cat solve.rb
substr = nil
s = ARGF.read
s_len = s.length
(2..(s_len)).each do |n|
candidates = (0..(s_len - n)).to_a.collect { |i| s[i..(i+n)]}
candidates.each_with_index do |s, i|
if candidates[(i+1)..-1].index(s)
if substr.nil? || s.length > substr.length
substr = s
break
end
end
end
puts "#{n}: #{substr}"
end
$ ruby solve.rb
(8文字目くらいまで見て、条件を満たす範囲の続きの文字を回答)flag: f_sz!bp_$gufl=b?za>is#c|!?cxpr!i><
182-記述術-200
- 1. 'alert'がないので数値から組み立てると仮定して文字っぽいものを確認
$ irb > 0x52.chr # => "R" > 0x54.chr # => "T" > 0b1001100.chr # => "L" > 101.chr # => "e" > 0O000101.chr # => "A" > 1.chr # => "\x01"
- 2. 最初の3つくらいを1つずつブラウザで試す
window["map"] => undefined
window["eval"] => function eval() { [native code] }
window["eval"]["call"] ...
- 3. chrっぽい事をして「荒痕(1)」なだけに "alert(1)" を組み立てるようなものにする
window["eval"]["call"]`${
[ (0O000101), (0b1001100), (101), 0x52, 0x54 ]
["map"](x=>String["fromCodePoint"](x))["join"]("")["toLowerCase"]() +"(1)"
}`;
以下が出てくる。
flag: Flag={4c0bf259050d08b8982b6ae43ad0f12be030f191}
183-記述術-100
- 1. 1文字ずつ入力すると何文字ありそうかわかる。長い...(ので総当りを諦める)
$ cat find_chars.rb
require "http"
((?a..?z).to_a + [?_, ?{, ?}]).each do |c|
url = "http://210.146.64.36:30840/count_number_of_flag_substring/?str=#{c}"
puts "#{c}: #{HTTP.get(url).to_s.lines.grep(/member/).first}"
sleep 5
end
$ find_chars.rb
(この結果をsolve.rbに反映)
- 2. 1文字ずつ先頭から見ていけば無駄な試行回数を減らせそうだなと思ったのでそうする
$ cat solve.rb
require "http"
# find_chars.rb の結果を参照(flagは除外)。
chars = [
?_ * 6,
?a * (10 - 1),
?d * 9,
?e * 4,
?f * (9 - 1),
?g * (3 - 1),
?h * 3,
?i * 7,
?j * 2,
?k * 4,
?l * (1 - 1),
?n * 6,
?o * 1,
?r * 8,
?s * 8,
?u * 3,
?x * 5,
].join.chars
class RetryError < StandardError; end
res = "flag={"
begin
chars.uniq.each do |c|
s = res + c
# puts "try: #{s}"
url = "http://210.146.64.36:30840/count_number_of_flag_substring/?str=#{s}"
if md = /member of "[^&]+" are (\d+)/.match(HTTP.get(url).to_s)
if md[1].to_i > 0
res += c
chars.delete_at(chars.index(c))
puts "current: #{res}"
raise RetryError
end
end
sleep 5
end
if chars.empty?
res += "}"
puts "flag: #{res}"
end
rescue RetryError
retry
end
$ ruby solve.rb
...
flag: flag={afsfdsfdsfso_idardkxa_hgiahrei_nxnkasjdx_hfuidgire_anreiafn_dskafiudsurerfrandskjnxxr}
184-記述術-100
- 1. とりあえず正直に手で解凍してしばらく様子を見る
$ bunzip2 < 184-flag.txt| bunzip2 | funzip | tar xOf - | gunzip -c | funzip | tar xOf - | bunzip2 | tar xOf - | tar xOf - | funzip | funzip | funzip | bunzip2 | funzip | tar xOf - | bunzip2 | tar xOf - | tar xOf - | tar xOf - | gunzip -c | bunzip2 | tar xOf - | ...
- 2. 1.で特定の方式しか使われなかったのでサブコマンドでやろうとする(標準入力は複製されないんだったか)
$ bunzip2 < 184-flag.txt| (bunzip2; funzip; tar xOf -; gunzip -c) 2> /dev/null | (bunzip2; funzip; tar xOf -; gunzip -c) 2> /dev/null | ...
- 3. コードを書いて自動でファイル判別→解凍を繰り返す
$ cat solve.rb
require "tempfile"
def extract(path)
f = Tempfile.create("184")
f.close
case `file #{path}`
when /bzip2/
system("bunzip2 < #{path} > #{f.path}")
return f.path
when /gzip/
system("gunzip -c < #{path} > #{f.path}")
return f.path
when /tar/
system("tar xOf - < #{path} > #{f.path}")
return f.path
when /Zip archive data/
system("funzip < #{path} > #{f.path}")
return f.path
else
system("cat #{path}")
return true
end
end
f = Tempfile.create("184")
f.close
system("bunzip2 < 184-flag.txt > #{f.path}")
res = extract(f.path)
while res != true do
res = extract(res)
end
$ ruby solve.rb
もう少し短く書けばいいのにと思ったけど頑張らなかった。なお、1024回くらい圧縮してあった。追記されるヘッダ分からもう少し多めの回数で圧縮されてるのかと思ってたけど、案外少なかった。
flag: flag={6aKuZrEqxvBZUIqBOXgMclLwpQCo8OXi}
192-超文書転送術-100
- 問題文の最後に記載されたURL(省略)/about に隠されたヒントを見逃すなとある
- HTMLの中身を見ても.hintクラスを含めて特にないので大文字の部分だけ抜き出して読む
- 実際にしでかしてみる(flag.txtをfindで探してcatした)
flag: flag={Update bash to the latest version!}
