サークル合宿で主催したCTF(のようなもの)の解説
この記事は サークル合宿で主催したCTFの解説|nekomaru|noteの転載です。
幹事長(@progfay)、広報(@mayoneko)、自分(@nekomaru)の3人でCTF(という名目のオリエンテーション)を企画した。めちゃくちゃエモい概要記事は 合宿でCTFの主催をした記録|真夜猫|note。CTFの後にゴニョゴニョついているのはまさかりが怖いからです
この記事では自分が作成した問題を解説する。
A multipurpose toolkit (Misc:100)
問題
Get flag! 《callmenames.v4p》
解き方
環境がWindowsでかつ、vvvvがインストール済みの場合
callmenames.v4pをvvvvで実行する
- flagcolorの変数を変更する
- その他の環境
v4pはXMLファイルであるため、文字列抽出を試みる。
$ strings callmenames.v4p | grep octf{ <PIN pinname="Input String" visible="1" slicecount="1" values="octf{vvvv_is_not_virus}">
flag
octf{vvvv_is_not_virus}
感想
合宿1日目に後輩がvvvvを始めてみたいと言っていたのを小耳に挟んだので追加した。
How Tweet (Recon:50)
問題
Onsen-CTF has an official Twitter account. Find!
解き方
flag
感想
クライアントに気が付かず苦労する人がいる一方で、Crypto大魔王みたいな人とReconの神っぽい人がCTF開始前からアカウントを特定していたと聞いて戦慄した。
リプとかDM送りつけられたりパスワード変更申請出されたりして面白かった。
official Instagram (Recon:50)
問題
Onsen-CTF has an official Instagram account. Find!
解き方
How Tweetのクライアント名をクリックして紐付けられているURLにアクセスする。
flag
octf{y0u_are_greate_stalker}
感想
もはやエスパー(ごめんなさい)だけど全チーム解けていたのでちょっと引いた。"How Tweet" と合わせてTwitterAPIに興味を持ってくれるといいなという気持ちで制作した。結果としてはおまけ問題的な立ち位置になってしまった。泊まった旅館の名前でInstagramを検索している後輩を見かけて申し訳ない気持ちになった。
easy packet (network:100)
問題
Let's restore the site!《easy_packet.pcapng》
解き方
- pcapngファイルをWireSharkで開く。
- ファイル>オブジェクトをエクスポート>HTTPオブジェクトからファイルを保存する。
flag
octf{HTML_EXP0RT}
感想
先にI_input_the_flagを作ってからnetworkに易しい問題がなかったので作った。画像をbase64エンコードしてHTMLに埋め込んでみたらそこで苦戦している人がいて申し訳ない気持ちになった。これを期に勉強してください。
I_input_the_flag_1 (network:200)
問題
The answer is octf{*} . * = I_input_the_flag_1.pcapng's answer.
解き方
- pcapngファイルをWireSharkで開く。
protocol:USBからUSB通信のキャプチャだと推測。各パケットの差異からIRP_IDとLeftover Capture Dataに注目する。
IRP_IDは2種類、交互に入れ替わることから送信先と受信先を表している、Leftover Capture Dataは送受信しているデータであると推測。
I"input"the_flagとUSB通信からUSBキーボードの通信と推測。usb keyboard codeなどでググる。参考サイト
4のサイトと照らし合わせる(コードを書いたり、目で追ったりする)
flag
octf{mimorisuzuko}
感想
ctf4gの演習で習った問題。picoCTFの過去問にもある。何をしているのか理解すればググるだけでWriteUpを読める。最初は150点くらいにしようとしていた。
I_input_the_flag_2 (network:250)
問題
The answer is octf{*} . * = I_input_the_flag_2.pcapng's answer.
解き方
- 途中まではI_input_the_flag_1と同様。Leftover Capture Dataに注目し、解読する。
usbkeyboard
2.Leftover Capture Dataの画像赤枠部分が変化していることに注目。
usbkeyboardの太字部分にのみ入力されていることからShiftキーと推測。
flag
octf{USBKeyBoard}
感想
最初はI_input_the_flag_2だけだったが、Shiftキーなしで1問になると指摘されてI_input_the_flag_1ができた。実質450点問題。
nekomaru's Adventure (Extreme:800)
解き方
1-1.instabae.jpgのexif情報から撮影場所を抽出
1-2. lyric.jpgにstringsする
$ strings lyric.jpg JFIF 4ICC_PROFILE $appl mntrRGB XYZ ・・・ "fly high in the sky" this song by POSSIBILITY.
1-3. 1-2の内容をググるとsanagiという曲が出てくる。1-1の新宿周辺という情報と合わせて調べる。
1-4. サナギ 新宿に行っているときのツイートを探して答えると画像が与えられる
2-1. 配られた動画ファイルに埋め込まれているQRコードを重ねたりつなぎ合わせたりする
それぞれのQRコードからロッカーを特定する。
感想
広報がTwitterAdventureつくってて楽しそうだなーと思ったのでReconっぽい問題を作りたかった。
ゴリ押しでも解けるようにしようと解き方をいろいろ考えていたらものすごく簡単になった。(自分の問題が一番早く解かれた)
picoCTF2018 writeup
picoCTF2018に@progfayと@mayonekoとチーム「NCC」で参加しました。15510pt獲得して320位でした。
自分が解いた問題は
- General Warmup 1
- General Warmup 2
- General Warmup 3
- Resources
- grep1
- net cat
- strings
- pipe
- environ
- what base is this?
- Inspect Me
- Client Side is Still Bad
- Logon
- No Login
- Safe RSA
- rsa-madlibs
- Super Safe RSA
- Super Safe RSA2
- Super Safe RSA3
- Reversing WarmUp 2
- Forensics Warmup 1
- Recovering From the Snap
- admin Panel
- hex editor
- Truly an Artist
- now you don't
- Desrouleaux
でした。 この記事では上記の問題について書きます。
General Skills
General Warmup 1
If I told you your grade was 0x41 in hexadecimal, what would it be in ASCII? と言われる。0x41はASCIIでA。おわり。
General Warmup 2
Can you convert the number 27 (base 10) to binary (base 2)? と言われる。おとなしく10進数表記の27を2進数表記する。おわり。
General Warmup 3
What is 0x3D (base 16) in decimal (base 10).と言われる。0x3Dを10進数表記するだけ。おわり。
Resources
We put together a bunch of resources to help you out on our website! If you go over there, you might even find a flag! と言われる。リンク先としてhttps://picoctf.com/resourcesが渡されるのでpicoCTF{でページ内検索する。おわり。
grep1
fileが渡される。grepっていわれたので$strings file |grep picoCTF{
する。おわり。
net cat
netcatしろっていわれたので$ nc 2018shell2.picoctf.com 49387
する。おわり。
strings
fileが渡される。$ strings file | grep pico
する。おわり。
pipe
Connect with 2018shell2.picoctf.com 37542.っていわれるのでnetcatする。たくさん流れてくるので $ nc 2018shell2.picoctf.com 37542 | grep pico
する。おわり。
environ
environは環境的な意味をもってる英語(雑)。なので環境変数なのかな~と思って問題サーバーの中で$printenv
する。おわり。
what base is this?
指示された通りnetcatすると、底を変換する問題がたくさん出てくる。pythonでhex()とか入力して貼り付けする。Webツール使っても良さそう。おわり。
Web Exploitation
Inspect Me
htmlとcssとjsのファイルにそれぞれflagが分割されているので集める。おわり。
Client Side is Still Bad
jsのコードを読む。おわり。
Logon
Cookieにadmin:Falseがある。拡張機能なりなんなりつかってCookieを書き換える。Cookie Manager – Get this Extension for 🦊 Firefox (ja) をつかった。おわり。
No Login
link先に飛んでFlagボタンを押すとadminじゃないからFlagあげないよって言われる。あちこちさがすとadmin=FalseというCookieが見つかる。拡張機能なりなんなりつかってCookieを書き換える。Cookie Manager – Get this Extension for 🦊 Firefox (ja) をつかった。おわり。
Cryptography
Safe RSA
Nとeとciphertextが与えられてるRSA問題。e=3で小さいのでLow Public Exponent Attackってやつだ~ってする。
import gmpy2 m,_=gmpy2.iroot(2205316413931134031046440767620541984801091216351222789180593875373829950860542792110364325728088504479780803714561464250589795961097670884274813261496112882580892020487261058118157619586156815531561455215290361274334977137261636930849125,3) print(m) #mpz(13016382529449106065839070830454998857466392684017754632233929110204433151964285) hex(13016382529449106065839070830454998857466392684017754632233929110204433151964285) # '0x7069636f4354467b655f7734795f7430305f736d3431315f39663564323436347d'
asciiに変換してやれば終わり。
rsa-madlibs
netcatするとRSA暗号に関する問題が順番に渡され、答えられるかどうか聞かれる(yes/no)。yesと答えた場合はそのまま回答にうつる。
- 1問目
- p,qが与えられてnを求める。n=p*q
- 2問目
- n,pが与えられてqを求める。q=n/p
- 3問目
- e,nが与えられてp,qを求める
- 素因数分解できない桁数なのであきらて答えられませんってする
- 4問目
- p,qが与えられてtotient(n)を求める
- totient(n)=(p-1)*(q-1)
- 5問目
- plaintext,e,nが与えられてciphertextを求める
- ciphertext=plaintext^e mod n
- pow(plaintext,e,n)
- 6問目
- ciphertext,e,nが与えられてplaintextを求める
- 素因数分解が現実的でないので答えられませんってする
- 7問目
- q,p,eが与えられてdを求める
- totient(n)=(p-1)(q-1)
- d=e^(-1)mod totient(n)
- xgcd(e,totient(n))
def xgcd(b, a): x0, x1, y0, y1 = 1, 0, 0, 1 while a != 0: q, b, a = b // a, a, b % a x0, x1 = x1, x0 - q * x1 y0, y1 = y1, y0 - q * y1 return b, x0, y0
- 8問目
- p,ciphertext,e,nが与えられてplaintextを求める
- q=n//p
- n/pだと桁が大きいので丸められてしまう
- totient(n)=(p-1)*(q-1)
- d=e^(-1)mod totient(n)
- xgcd(e,totient(n))
- 上記コードを実行するとdが負の数となるため、totient(n)を加算する
- plaintext=pow(ciphertext,d,n)
- 9問目
- ascii変換しろっていわれる。おわり。
Super Safe RSA
ciphertextとNとeが与えられる問題。Nについて[https://factordb.com/:title]で検索すると素因数分解できるので、それをもとにdを求めて復号する。
_n=(p-1)*(q-1) def xgcd(b, a): x0, x1, y0, y1 = 1, 0, 0, 1 while a != 0: q, b, a = b // a, a, b % a x0, x1 = x1, x0 - q * x1 y0, y1 = y1, y0 - q * y1 return b, x0, y0 xgcd(e,_n) # (1, -3791887882690606072381444883453477933509422520181053061460720538328000246236303, 28386) d=-3791887882690606072381444883453477933509422520181053061460720538328000246236303+_n pt=pow(c,d,n) hex(pt) # '0x7069636f4354467b7573335f6c40726733725f7072316d33245f363739317d'
ascii変換したらおわり。
Super Safe RSA2
ciphertextとNとeが与えられる問題。eの値が大きいのでwieners attackを疑う。 GitHub - orisano/owiener: A Python3 implementation of the Wiener attack on RSAに実装があるのでお借りする。
import owiener e = 41612567195059539237042339144213248885498194048946559716002349006807748846714117750820396613149784044717908233637646356892484239003595253242761997955443952981295737644406362196847280712216803724529054751915978485375745590671877539386118316322595071621055245914992460194263596241613969669897021758528439566785 n = 94571655035635365085759398706325335236290014335257158654077953561714444504182235844072418519124645314654005337167889492376555798854895520053087805943958487865125705889152148392163149399684674863104849135010521387886940153492514295194610869892600350410689535971326333736353929224242288002733394049392037067061 d = owiener.attack(e, n) if d is None: print("Failed") else: print("Hacked d={}".format(d)) #Hacked d=65537
dが求まったのでpow(ciphertext,d,n)でplaintextも求まる。ascii変換する。おわり。
Super Safe RSA3
multi prime RSAの問題。 素因数がpとq以外にも増えるだけでeとdの算出方法は変わらない。 ciphertextとNとeが与えられるのでNを素因数分解する。 https://factordb.com/と Integer factorization calculatorを利用した。
n=3352798877*2369387227*2431171217*2584404167*2659774739*2699291249*3128975077*3592874927*2484437773*2615438143*2618494273*2624594587*2638968127*2670090937*3407996899*3542100181*4156481587*2217677383*2294163019*2360089261*2481642209*2750663507*2781222713*2869402951*3183321367*3510049541*3534801841*3678931409*3714860263*3816169081*4125046879*4267109251
import binascii c = 967423659976144422320526684513948978222873052874997628444834116664169862453024328079660763441932673618170544580223040334526399906457678605707715045865891898922525849277148177306814671533382959747679111362955790287148837808594332142213808332127835059659414298383140785818506776105499752340995329355686034 n = 1508547885745784901956544915558535724293536275843330479254283622986213460935121752835216459933606594073514738804678585260256102038249637956751407525024381745275550945663173358228639798583183241097702558167884351104283827556017494624405275607563140412199383210793765286714481226961015337761433908370379431 e = 65537 _n = (3352798877-1)*(2369387227-1)*(2431171217-1)*(2584404167-1)*(2659774739-1)*(2699291249-1)*(3128975077-1)*(3592874927-1)*(2484437773-1)*(2615438143-1)*(2618494273-1)*(2624594587-1)*(2638968127-1)*(2670090937-1)*(3407996899-1)*(3542100181-1) * \ (4156481587-1)*(2217677383-1)*(2294163019-1)*(2360089261-1)*(2481642209-1)*(2750663507-1)*(2781222713-1)*(2869402951-1) * \ (3183321367-1)*(3510049541-1)*(3534801841-1)*(3678931409-1) * \ (3714860263-1)*(3816169081-1)*(4125046879-1)*(4267109251-1) def xgcd(b, a): x0, x1, y0, y1 = 1, 0, 0, 1 while a != 0: q, b, a = b // a, a, b % a x0, x1 = x1, x0 - q * x1 y0, y1 = y1, y0 - q * y1 return x0 d = xgcd(e, _n) if d < 0: d += _n plaintext = pow(c, d, n) print(hex(plaintext))
ascii変換するだけ。おわり。
Reversing
Reversing WarmUp 2
Can you decode the following string dGg0dF93NHNfczFtcEwz from base64 format to ASCII?と言われる。base64でdecodeする。
Base64のデコード - オンラインBase64のデコーダ
などを使う。おわり。
Forensics
Forensics Warmup 1
Can you unzip this file for me and retreive the flag?と言われるのでunzipすると画像が出てくる。おわり。
Recovering From the Snap
There used to be a bunch of animals here, what did Dr. Xernon do to them?と言われる。とりあえずもらったanimal.ddにfileコマンドする。disImageか~となるので$ foremost animals.dd
で画像を引きずり出す。おわり。
admin Panel
WireSharkで開くと73パケット目でadmin認証完了のHTMLファイルが送られていることがわかる。passwordはその上の68パケット目で送信されている。
おわり。
hex editor
This cat has a secret to teach you.と言われるのでそっか~って言いながら$ cat hex_editor.jpg
する。おわり。
Truly an Artist
Can you help us find the flag in this Meta-Material?と言われる。CTFでもらったファイルはstringするものです。おわり。
now you don't
We heard that there is something hidden in this picture. Can you find it?と言われる。CTFでもらった画像ファイルは青空白猫(青い空を見上げればいつもそこに白い猫)にかけるものです。おわり。
Desrouleaux
netcatすると配られたファイルについて問題が出される。json処理して一番たくさん出現するsourceipやら同じハッシュ値のファイルの数を数える。あまりにも面倒で辛かったのでコードを残していない()。
感想
picoCTF 開催中、ctf4bに参加しました。Crypto講義でRSAの話を基礎から教わったおかげでRSA関連の問題をすべて解くことができてたのしかったです。 Reversing系ももう少し頑張りたいです。
ゼミの冬期課題の話
はじめに
今日も寒いですね。 1日で追い込んだゼミ課題の話をします。 秋学期は指定された教科書を使ってPythonに触れていました。
Practical Programming: An Introduction to Computer Science Using Python 3 (Pragmatic Programmers)
- 作者: Paul Gries,Jennifer Campbell,Jason Montojo,Lynn Beighley
- 出版社/メーカー: Pragmatic Bookshelf
- 発売日: 2013/10/04
- メディア: ペーパーバック
- この商品を含むブログを見る
ゼミ課題は「Pythonを使ってオリジナルなプログラムを作る」でした。 授業の共同課題で自分の担当だった経路探索アルゴリズムの説明をしました。
動機
授業課題で作成した作品は、電車の乗り換え経路と駅周辺の飲食店を提示するWebサービスでした。経路探索アルゴリズムの選定基準では、運賃及び距離の条件を無視しました。処理の高速化とユーザーに「時間を気にさせない」ことを目的にしていたためです。結果的に「幅優先探索」を採用しました。
班員にアルゴリズムを説明したものの理解してもらえず、ゼミ課題でも発表することにしました。 ついでに深さ優先探索も実装して比較しました。
アルゴリズムの説明
まずは道を作ります。道がないことには経路探索は始まりません。適当に作ります。
次に探索を行います。先ほど作ったネットワークでAからZに移動する場合について考えます。 幅優先探索も深さ優先探索も開始ノードから終了ノードが見つかるまで隣接するノードをすべて取得し、照合を行うアルゴリズムです。
幅優先探索では開始ノードに隣接するノードを全て調べ切ってから隣接するノードに対して照合を行います。
深さ優先探索では開始ノードに隣接するノードを一つ見つけるとさらに隣接するノードに対して照合を行います。
入力したデータをどの順番で取り出すかが異なっているため、幅優先探索ではキュー構造、深さ優先探索ではスタック構造が用いられます。
最後に経路の作成を行います。 終了ノードから直前のノードを再帰的に調べて開始ノードに行きつくまでのルートを作成します。
コード
まとめ
スタック、キュー構造や再帰等の考え方が入ってくるので弊学科のB2の勉強に向いていると感じました。 結局班員には理解してもらえませんでした。
ゼミの夏期課題の話
はじめに
今日も暑いですね。夏休みに頑張っていたゼミ課題の話をします。
春学期は指定された教科書を使ってR言語に触れていました。
課題は「Rでオリジナルのデータを扱う。」ということで、Twitterのデータを取得して遊びました。
- 作者: 金明哲
- 出版社/メーカー: 森北出版
- 発売日: 2017/03/25
- メディア: 単行本(ソフトカバー)
- この商品を含むブログを見る
動機
Twitterを使おうということは早い段階から決めていました。 自分はTwitterのリスト機能をよく利用するのですが、極度の面倒くさがりなので、
リストにユーザー追加を自動化したい
ツイートを見ずに概要を把握したい
という動機に基づいて「フォローユーザーのクラスタ分析」及び「ツイートの形態素解析」を行いました。
手法
フォローユーザーを分類するための手法として2パターン考えました。
順番に手順と結果を述べていきます。
ツイートの傾向で判別する
手順
1. データを収集する
タイムラインのツイートを1週間分遡って取得しました。
TwitterRを使う手もあったのですが、慣れていたのもあってpython3+Tweepyでタイムラインのツイート収集を行いました。
2. Rで形態素解析
取得したツイートから名詞に絞って形態素解析を行います。
RMeCabに含まれる関数、docMatrix()を用いました。
library(RMeCab)
data<-docMatrix("data/",pos=c("名詞"))
data.d<-dist(t(data))
clust<-hclust(d=data.d)
plot(clust)
3. 返り値をplotする
- デンドログラムに表しました(結果を黒塗りにしています)。
結論
上の図のようにうまくいきませんでした。原因として、
フォローしている人同士の話題が近く、違うカテゴリに入れたい人が似たような話をしている
あまりツイートが少ない人は分析が行いづらい
等が挙げられると思います。
ユーザー同士につながり(フォロー関係)があるかどうかで判別
手順
1. データを収集する
自分のフォローしたユーザーそれぞれについてフォローしているユーザーの情報を収集しました。
データの収集はpython3+Tweepyで行いました。
2. Rでネットワーク分析
自分がフォローしているユーザーについて、フォロー関係の有無を調べました。
パッケージのigraphを用いて、コミュニティ分析を行いました。分割には辺媒介性分割を用いました。
library(igraph)
d <- read.table("clustdata.txt")
g <- graph.data.frame(d,directed = FALSE)
plot(g, vertex.label="",vertex.size=10)
eb <- edge.betweenness.community(g)
V(g)$color <- eb$membership
plot(g,vertex.label="",vertex.size=10)
結果
先ほどよりも良い感じに分かれているような気がします。
それぞれに名前を付けると多少誤差はあるものの、以下のようになりました
A(緑) 先輩、教授などFMS関連の人
B(黄橙) 他のクラスタに含まれなかった人(デザイナーさんやbot)
C(赤橙) 学外の友人(オタク)
D(濃青) 高校の友人とbot
E(薄青) 後輩(5期生)
F(黄) 同期(4期生)
クラスタ内のトレンドを取得
フォロー関係でのクラスタ分析がうまくいった(主観)ので、当初の目標だったトレンド取得をします。
手順
1.クラスタ内のユーザーをリストに登録
eb1<-RMeCabFreq("eb1.txt")
eb1<-eb1[eb1$Info1=="名詞",]
eb1<-eb1[eb1$Info2=="一般"|eb1$Info2=="固有名詞",]
eb1<-eb1[order(eb1$Freq,decreasing = T),]
2.成形したデータを用いてリストを作成
https://github.com/aukkeyikon/list_share/addListUser_fromText.py
3.リスト内のタイムラインを取得
4.取得したデータから頻度分析
eb1<-RMeCabFreq("eb1.txt")
eb1<-eb1[eb1$Info1=="名詞",]
eb1<-eb1[eb1$Info2=="一般"|eb1$Info2=="固有名詞",]
eb1<-eb1[order(eb1$Freq,decreasing = T),]
結果
A | B | C | D | E | F |
---|---|---|---|---|---|
オタク | 自分 | 人 | 口座 | S | 成績 |
自分 | 人 | たより | 残高 | バイト | GPA |
人 | メッキ | イケ | 気 | 先生 | バイト |
感じ | 大人 | 自分 | 笑 | GPA | 基礎 |
あと | グラブル | 余裕 | 中野 | 自分 |
結果がわかりやすいように大学の成績発表の日程にトレンド取得しました。
以上の内容をゼミ合宿で発表したところ、教授からTF-IDF法について調べてはどうかという話がありました。
TF-IDF法を利用したトレンド抽出
当初提案された使い道は、グループ内の共通要素の削除でしたが、最終的に全トレンド要素が失われてしまいました。
原因としてはデータが少なかったためにトレンドも共通要素に含まれてしまったことが挙げられます。
そこで、データ数を補うためにも、全グループに共通する要素を削除します。
data<- as.data.frame( docMatrix( "作業用ディレクトリ", pos=("名詞"), weight = "tf*idf" ) )
ここで抽出されたデータ上位20件をクラスタ別の頻度分析用のデータから除外しました。
結果
A | B | C | D | E | F |
---|---|---|---|---|---|
シナリオ | メッキ | イケ | 入金 | 統計 | 基礎 |
ポスター | 自分 | たより | 君 | GPA | 成績 |
オタク | 信頼 | ショット | 口座 | S | 去年 |
人 | 映像 | セカンド | 残高 | 概論 | GPA |
スタフィー | 人 | 日 | 油田 | 中野 | 自分 |
先ほどよりも話している内容が想像できそうなトレンドになりました。
B,Cのグループについては個々人のツイートの頻度が少ないこともあって、特定のbot*1*2の影響が強くなっています。
まとめのようなポエム
ツイートの取得限界(APIでは1週間分)もあって、なかなか思うようにデータを取ることができませんでした。
時報のように「今何が話題だよ」と通知させる機構なども考えていたのですが、思ったよりも皆がツイートをしていないことを知りました。
夏休みの宿題、遅くなってしまいましたがこれにて完了です。