令和4年度 京都工芸繊維大学 情報工学課程 編入試験受験体験記

2021/7/3に実施された京都工芸繊維大学編入学試験を受験しました．
結果は不合格だったのですが，情報共有という形で体験記を書きたいと思います．
(9/10追記)
枠に空きが出たということで追加合格の連絡をいただきました．

※本体験記は 2021/9/10時点 の情報に基づいて書かれています．

目次

  1. スペック
  2. 勉強内容
    1. 情報基礎
  3. 受験前日
  4. 受験当日
  5. 結果発表
  6. 最後に

1. スペック

筑波大学の体験記にあるので，そちらを参照してください．

2. 勉強内容

数学・英語の勉強内容は 筑波大学の体験記 にあるので，そちらを参照してください．

2.1. 情報基礎

京都工芸繊維大学情報工学課程の編入試験では数学の他に情報基礎という分野での試験があります．
これがとても厄介で，C言語によるプログラミングをはじめとして論理回路や情報理論，制御工学，線形計画法といった広い範囲からの出題となります．
全部対策するとなるととても時間がかかるため，僕はヤマを張る形で勉強していました．
3，4年次の授業で論理回路，制御工学をやっていたので，勉強は主に授業ノートを読み進める形で行いました．
特別な参考書等は使用していません．
線形計画法も授業でやっていたのですが，正直興味がもてず苦手な分野だったので触りませんでした．

3. 受験前日

京都には前日入りしました．
気持ちとしてはできるだけ大学に近いところに宿泊地を確保したいところですが，京都工芸繊維大学の周りにはほとんどホテルはありません．
僕は四条にあるヴィアイン京都四条室町というホテルに宿泊しました．

ホテルにチェックインした後は大学へ下見に行きました．
特に掲示などは無いので本当に外から見るだけです．

その後は帰りにちょっとゲームセンターに寄るなどして，ホテルに戻りました．
ホテルでは過去問を1年分解いて，日付が変わる前には布団に入りました．

4. 受験当日

前日に通ったルートをそのままなぞって大学に行きました．
開場予定時刻の20分くらい前に着いたのですが，既に10人くらいいました．
そのためなのか，開場予定時刻より早めに試験場の扉を開けてもらえました．

試験場内での電子機器の使用は特に制限が無いようだったので，スマートフォンで数学関連のサイトを確認するなどしました．(もちろん試験が始まった後はNGですが)
他の人も音楽を聞いたり参考書を開いたり，かなり自由な雰囲気でした．

試験開始の30分くらい前からアナウンスが始まりました．
また，合わせて問題用紙と解答用紙が配られます．
この問題用紙ですが，表紙と問題の間に何も挟まれていないので問題が見えてしまっています．
不正を疑われたくないなら常に前をみるなどしたほうが良いと思います．
(ちなみに数学・情報基礎ともに進行は同じです)

数学

問題の構成は「連立方程式」「1変数関数の極限と極値」「2変数関数の重積分と極値」「微分方程式」でした．
2変数関数と微分方程式は全部解けましたが少しミスが含まれているとして9割程度，連立方程式の方は行基本変形のミス，1変数関数は arctan(1/√3)=π/3 とするミスがあって6〜7割といったところです．
総合点は160/200位だと思います．

情報基礎

問題の構成は「C言語によるプログラミング」「論理回路」「語句穴埋め(コンピュータの構成)」「情報理論」「制御工学」「フーリエ級数」でした．
まさかフーリエ級数が出るとは思わず詰みました．
授業でもやったことは無く，もちろん未対策です．
問題を読んだ瞬間に不合格を確信しました．
数学でミスがあったため情報基礎で逆転しようと考えていたのですが，小問1つが丸々空欄となってしまったためこれはもう無理だなという感情になりました．
とはいえ全く解かないというのはダメなので，他の問題をしっかり解きました．
総合点は140/200位だと思います．

試験が終わった後はかなり落ち込みましたが，本命は1週間後の筑波大学だったので，良い練習になったと思って気分を切り替えることでなんとか精神を正常に保ちました．

5. 結果発表

不合格でした．
合格者は2人のみでした．
出願が65人でほぼ全員が参加していたことを考えると単純に計算して倍率は30倍超です，受かった方凄すぎる．
(自分が出来なさすぎるだけという話だが…)

(9/10追記)
最終的な結果としては追加合格枠での合格でした．
この枠に期待はしていませんでしたが，合格者が少ない場合はこういうことも起こるみたいです．(かなり嬉しい)

6. 最後に

情報基礎の対策はしっかりやったほうが良いです．
出題傾向はほぼ無いに等しいので変にヤマを張らない方が良さそうです．

ここまで読んでいただきありがとうございました．

令和4年度 筑波大学 情報科学類/情報メディア創成学類(併願) 編入試験受験体験記

2021/7/10に実施された筑波大学編入学試験を受験し，情報メディア創成学類に合格することができました．
受験勉強中には数多くの体験談に助けられたところがあり，また体験記を書くことがちょっとした夢でもあったのでしっかり書きたいと思います．

※本体験記は 2021/7/24時点 の情報に基づいて書かれています．

目次

  1. スペック
  2. 勉強内容
    1. 数学
    2. 英語
    3. 専門科目
  3. 受験前日
  4. 受験当日
  5. 結果発表
  6. 最後に

1. スペック

所属学校・学科

  • 学習到達度試験の出来は下から数えたほうが早いレベルの高専
  • 情報系学科

卒業生の8割強が就職，進学する人も専攻科または技科大という感じです．
こういう高専だと過去問はもちろん，進路担当の先生も編入試験に関する情報をほとんど持っていません．(実際そうだった)

僕は4年の前半に編入試験に関する情報をかき集めて分類するなどしました．
また，学校から十分サポートを得られるようにクラス担任と進路担当の先生に集めた情報をプレゼンしたりしました．
学校内に編入試験に理解を示してくれる先生がいると心強いです．

席次

1年: 15位
2年: 3位
3年: 1位
4年: 1位
5年: 4位(前記中間時点)
※1クラスの人数は大体40人

高専全体で見ると中間くらいのレベルではないかと思います．(数字だけ見ると良さそうですがそもそものレベルが低めなので)
学力での受験では席次はほぼ考慮されないと思いますが，クラス内で上位1割を維持しておくと推薦での受験も視野に入るため万が一の場合に備えることが出来ます．
最初から学力一本の場合は別ですが，とりあえず定期試験では良い点数を取り続けておいて損はないと思います．

TOEIC

780(L: 410, R: 370) → 815(L: 420, R: 395) → 810(L: 430, R: 380)

全部でTOEICは3回受験しました．
編入試験で十分戦えるだけの点数は取れたと思います．

2. 勉強内容

2.1. 数学

2.1.1. 使用した参考書など

2.1.1.1. 編入数学徹底研究

難易度: ★★☆☆☆
おすすめ度: ★★★★★

どの体験記にも出てくる人気の参考書です．
この一冊に編入数学の基礎が詰まっているといっても過言ではないと思います．

自分は勉強始めにとりあえず1周し，その後は復習したくなったタイミングで適当に開いて問題を解いたりしました．

2.1.1.2. 極めるシリーズ 大学・高専生のための微分積分Ⅰ/Ⅱ

難易度: ★★★☆☆
おすすめ度: ★★★★★

高専の先生が書かれた微分積分に関する参考書です．
全体的な難易度は徹底研究よりは少し高めです．
この本は他の参考書に比べて解答が細かく書かれており「どうしてそうなった」的なことになることはほとんどありませんでした．
また，公式集が充実していること，問題数の多さから辞書として使うのにも適していると思います．

Ⅰ/Ⅱともに1周ずつ解いて，その後は公式集として使ったりしました．

2.1.1.3. ベクトル・行列・行列式 徹底演習

難易度: ★★☆☆☆
おすすめ度: ★★★☆☆

大学編入を目指す高専生向けに書かれた参考書です．
ベクトルとは何かという所から行列の対角化まで丁寧に書かれています．
最後に少しだけベクトル空間について触れています．
とにかく行列に関する問題の基礎をつけることが出来るといった感じなので，徹底研究で理解できればやる必要はないと思います．

1周だけ解いて，その後はほとんど開きませんでした．

2.1.1.4. 新装版 線形代数学

難易度: ★★★★☆
おすすめ度: ★★☆☆☆

線形代数について300ページぎっしりと書かれている参考書です．
理論から押さえたい場合はとても良い本だと思います．
編入試験では手を動かして解くタイプの問題が多いのであまり合わないと感じました．

証明問題でわからない問題があったときに辞書として使いました．

2.1.1.5. 大学編入試験問題 数学/徹底演習

難易度: ★★★★☆
おすすめ度: ★★★★★

編入試験の過去問が詰まった問題集です．
割と新しめの問題も入っていて，問題数も多めなのでおすすめです．
ただ，解説の誤りが多すぎて頻繁に正誤表を参照することになるのがちょっと辛いです．

この本は4周しました．
1，2週目は何も考えずに全部解いて2週目でも分からなかった問題に付箋を付け，残り2周は付箋がついた問題のみを解くということをしました．

2.1.1.6. 編入数学過去問特訓

難易度: ★★★★★
おすすめ度: ★★★★☆

徹底研究の著者の方が書かれた本で，これも他の体験記で人気の問題集です．
問題が3ランクに分類されており，受験する大学のレベルに合わせて問題を解くことが出来ます．

正直言うと自分はこの本を0.5周くらいしかしなかったのであまり書くことがありません．
ただ，問題の多さと解説の丁寧さからおすすめ度は高めにしています．

2.1.1.7. 予備校のノリで学ぶ「大学の数学・物理」(ヨビノリ)

難易度: -
おすすめ度: ★★★★★

Youtube上に投稿されている動画です．
重積分や偏微分，固有値など，編入勉強に必要な分野はほぼ全て網羅されていると言っても良いと思います．
加えて，解説の詳しさや編集の丁寧さが最高です．

最初にあったように僕が在籍している高専のレベルはかなり低めであるので4年の前期でようやく重積分に触れるといったシラバスになっており，十分に学んでいないまま編入勉強せざるを得ない状況でした．
このときにヨビノリにはとても助けられました．
当時はまだ完結していない連続講義もありましたが，今ではかなり充実しています．
同じ状況にある方がいれば，とにかくおすすめします．

2.1.2. 勉強方法

まずは徹底研究を解き，次に極める微分積分とベクトル徹底演習を，最後は数学/徹底演習をとにかく解きました．
また，間にヨビノリを挟んで基礎を固めていました．

とにかく問題を解くことが大切だと思います．
また，ネット上の情報に惑わされないことも大切です．
1周1週間で終わったとかそういうヤバい人の言うことは適当に流して，自分のペースを崩さず着実に勉強を進めるべきです…

2.2. 英語

2.2.1. 使用した参考書など

2.2.1.1. 大岩のいちばんはじめの英文法

難易度: ★☆☆☆☆
おすすめ度: -

名詞とは何か，SVCとは何かといったレベルから書かれている参考書です．
帯にも書かれているのですが，本当に中学レベルから始まります．
誰にでも分かるように相当噛み砕いて書かれています．
章末問題といったものはほぼ無いに等しいので，とにかく勉強用といった位置づけの本です．

僕は中学英語からすっかり飛んでたのでこの本から始めました．
変にカッコつけて高校の参考書をやるより，プライドなんて捨てて1からやり直すのが一番です．(本当に)
1周もすれば英語の基本的な部分は身につきます．
SVCについて知った時は感動しました．

…中学生からまともに英語を勉強してきた人にはいらないです．

2.2.1.2. TOEIC Part5 でる1000問

難易度: ★★☆☆☆
おすすめ度: ★★★★★

TOEIC向けの問題集です．
Part5の問題がタイトル通り1000問(実際には少し多い)，後は解くためのテクニックが書かれています．

TOEICは英語力だけでなく，テクニックも必要になります．
そのためこの本は必須です．
1周もすれば100点くらい上がります．(冗談抜きで)

2.2.1.3. abceed

難易度: -
おすすめ度: ★★★★★

これはスマートフォン向けのアプリケーションです．
月額1000円くらいでTOEICの練習問題を無限に解き続けることが出来ます．
また，練習問題の出来からスコア予測も行ってくれる機能があります．
英語の勉強は自身がどのレベルにいるのか分かりづらいことが多いのですが，スコアという指標によって英語力を客観的に判断することが出来ます．

僕は1日5時間くらいこのアプリを使って勉強をしていました．
リーディングは他の参考書を使用していますが，リスニングに関してはabceedしか使っていません．
とにかく練習問題を解き続ける事ができるのが良いです．
欠点を指摘するとすれば，練習問題を解き続けることしか出来ないといったところでしょうか．
他の勉強アプリにあるような講義動画などは一切ありません．
さらに課金することで参考書をアプリ上で買うことが出来ますが，正直紙で買ったほうが断然良いです．

ちなみに，僕のスコア推移はこんな感じです． (2020/10/29のスクリーンショット，これ以降abceedを起動していません)

f:id:guguru0014:20210724171642p:plain:w320:h600

2.2.1.4. TOEIC L&R TEST 出る単特急銀のフレーズ

難易度: ★★☆☆☆
おすすめ度: ★★★☆☆

有名な単語帳です．
過去にTOEICに出た単語のみが収録されているそうです．
淡々と単語が掲載されているだけなので特に書くことはありません．

同じシリーズで，少しレベルが上った金のフレーズがあります．
普通にやる場合には金から始めても十分だとは思います．
(自分は銀だけやりました)

2.2.2. 勉強方法

まず始めにいちばんはじめの英文法，次にでる1000問を1周し，残りはずっとabceedをやっていました．
また，夜寝る前の30分で銀のフレーズをやりました．

個人的な意見ではとにかくabceedをやっとけば問題無いなといった感じです． それととにかく毎日欠かさず続けることが大切だと思います．
英語は1ヶ月程度で伸びないと言われていますが，本当にそうだと感じます．
僕は勉強を始めて2，3ヶ月経ってようやく成長を感じることが出来ました．
受験生の方は諦めずに続けてください…!

2.3. 専門科目

専門科目の勉強はほとんどやっていません．
受験の1週間前に「定本 Cプログラマのためのアルゴリズムとデータ構造」を買って読んだくらいです．
とにかくこの定本さえ読んでおけば専門科目は戦えるといった感じです．

3. 受験前日

つくばには前日入りしました．
旅程としては，新幹線で東京駅，東京駅から山手線で秋葉原駅，秋葉原駅からつくばエクスプレスをつかってつくば到着といった感じです．

つくばエクスプレスに乗るためにJR秋葉原駅を一回出る必要があったので，ついでに秋葉原探索をしました．
一緒に受験する友人と行動し，電子工作関連のショップを周りました．
店に入ると同年代の人で溢れかえっていて，全員つくば受験者では？？などと言い合っていましたが，当日の受験者数をみるとあながち間違いでもないと思います．
正直自分は電子工作に詳しいわけではないので後ろに立ってはえーって感じになっていました，とても楽しかったです．
見てるだけで楽しい，秋葉原最高って感じです．

話を戻して，つくばでの宿泊地はダイワロイネットつくばというホテルに宿泊しました．
このホテルは情報学群の試験場である春日試験場まで徒歩10分，しかもつくば駅からも徒歩2分といった受験生のために存在しているようなホテルです．
また，部屋にはこれで勉強しろと言わんばかりの巨大な机が配備されています．

試験会場に当日の注意事項が掲示されていたので見に行きました．
受験番号別の部屋割が掲示されているのでここで受験者数を確認することが可能です．
多くても受験者数は100人くらいだろうと思っていましたが，今年の総受験者数は150人を超えていました，最悪です．
少なくとも120人くらい落ちると思うと急に緊張感が高まりました．
コロナウイルスの影響で受験者数が跳ね上がっているようです．

掲示を確認して春日エリアをちょっと散歩した後は夕ご飯を食べました．
つくば駅の近くには大きめの建物があり，この中にサイゼリヤなどがあります．
夕ご飯はここで食べました．
コンビニや雑貨店もあるので足りないものがあればここで全部補充できそうな感じでした．

夜は過去問を解いて寝るつもりだったのですが，ここで急に緊張してきてそれどころではありませんでした．
仕方がないのでシャワーを浴びて布団に入ったのですが，動悸が止まらず結局3時くらいまで練れませんでした．
普段良く緊張する人は，最悪の場合に備えて睡眠薬的なものを持っていくと良いかもしれません．

4. 受験当日

受験当日は7時くらいに起きました．
睡眠時間は4時間無いくらいです，最悪の状態です．
ついに今日試験を受けるんだと思うと何も口に入らず，ホテルの朝食もなんとか少し詰め込んだといった感じでした．
ホテルから受験会場までは一本道なので迷いようがありませんでしたが，気を抜いたら迷うんじゃないかってレベルで緊張していました．
友人と来ていたので雑談を挟んでなんとか正気を保ちつつ会場入りに成功しました．

会場内では携帯電話などの電子機器の使用は禁止のようです．
ネット上のページを参考にして直前に勉強しようと思っている場合は，コンビニで印刷などしておかないといけません．

受験開始時刻15分前から問題用紙と解答用紙が配られます．
筑波大学では受験開始前に受験番号や名前を書かせてもらえます．
ただ，この書く時間がとても短いので注意です．

受験開始のアナウンスの後はただひたすら解くのみです．
解答用紙は完全な白紙ではなく罫線が印刷されています．
罫線の幅がとても広く全体の行数が少ないので解答には十分注意しないといけません．

数学1

広義積分とn次導関数に関する証明問題でした．
広義積分は問題に従って解くだけなのですが，n次導関数の問題は始め全く手が出ませんでした．
結局最後までこれといった解答を出すことが出来なかったので，なんとかやってる風の解答を書き残して部分点狙いとしました．

厳しく採点されたとすると3〜4割，部分点がもらえたなら4〜5割といったところです．

数学2

ベクトルの線形結合とベクトル空間に関する問題でした．
ベクトルの線形結合はただやるだけ…のはずだったのですが，終了5分前に計算ミスをみつけて解答全消し．
急いで解答を書いたのでほとんど点数を取れていないと思います．
また，ベクトル空間の方も悲惨なことになっていて空欄のままです．
後から解き直すと単に式変形をすれば良かっただけでした．
やはり睡眠は大切です．
しかも緊張が加わっていたので多分頭はほとんど働いていなかったと思います．

おそらく0〜1割です．

プログラム1

ソートに関する問題でした．
問題がとても丁寧に書かれているので，ほぼ全員満点を取れたと思います．
多分10割取れてると思います．

プログラム2

バーコードの読み取りに関する問題でした．
これも問題がとても丁寧に書かれており，指示通りにプログラムを書いていくだけでした． 添字の指定が少し嫌らしい感じになっていたので，落とすならここだろうと思いながら解答を書きました．
しっかり確認したので10割取れてると思います．

数学が思うように解けず，これまであんなに勉強したのに…なんて思っていました．
また，プログラムが簡単になっていると感じたので数学でほぼ決まると思い，試験が終わった後は間違いなく不合格だと思いました．

帰りには気晴らしのために秋葉原でまたお店巡りをしました．
もうどうでもよくなっていたので帰る時間を予定より2時間くらい遅らせました．

5. 結果発表

合格していました．
第一志望の情報科学類ではなく，併願のメディア創成学類の合格ですがとにかく嬉しかったです．
自分の番号があることが信じられませんでした．
全身の力が抜けるという感覚を始めて味わいました．

数学の出来が悲惨なので，おそらく合格最低点を取っていると思います．
勝因はよく分かりません…(?)

6. 最後に

正直勉強量に対して出来が見合ってないので複雑な気持ちでありますが，とにかく合格できていて良かったです．

数学の難易度はここ数年で急に上がっている気がします…．
また，筑波大学は多めに合格者が出ている印象だったのですが今年は受験者数が増えたにも関わらず，去年より合格者が少なくなっていました．
傾向が変わってきている感じがするので，5年前くらいの受験体験記はあまり役に立たなくなってしまうかもしれません．
来年以降受験する方は気をつけてください．

ここまで読んでいただきありがとうございました．

Beginners CTF 2020 Writeup (ctf4b)

概要

タイトル通りです。
2020/5/23 ~ 2020/5/24にかけて開催されたCTFイベントに参加しました。

注意

  • Writeupを書くのは初めてです
  • CTF初心者です

Writeup 目次

Web

Reversing

  • mask

Misc

  • Welcome
  • emoemoencode

Writeup

Web

Spy

ある会社の従業員が使用しているサイトについて、アカウントが登録されている従業員を探し出す問題です。

サーバプログラム「app.py」と従業員のリスト「employee.txt」が配布されています。

始めはSQLインジェクション…?なんて思っていたのですが、app.pyやサイト表示を確認してみると、ログインボタンが押されてから処理が完了するまでの時間が表示/計算されていることに気づきました。

またapp.pyをよく読むと、「アカウントが存在しない」「パスワードが正しくない」といった分岐が成立しなかったときに処理時間の計測を終了するようになっていました。

加えてプログラム内にヒント

# auth.calc_password_hash(salt, password) adds salt and performs stretching so many times.
# You know, it's really secure... isn't it? :-)

が書かれていました。

これらの情報から

  • 処理時間を確認することで、どこで認証プロセスが打ち切られたのかが分かる
  • どうやら auth.calc_password_hash には何かしらの脆弱性があるらしい

ことが分かりました。

そして、従業員全てについてログインを試行してみると、ある従業員だけが異様に処理時間が遅いことに気づきました。

よって、auth.calc_password_hash を実行した場合相当の時間がかかるのだろうと判断し、その呼び出しに到達している時点でユーザの存在確認がされていたことから、処理時間が異様に長い従業員がアカウント登録されているのだと分かりました。

得られた情報をサイト上のChallengeページに入力するとフラグ ctf4b{4cc0un7_3num3r4710n_by_51d3_ch4nn3l_4774ck} を獲得できました!

Reversing

mask

配布されているバイナリファイル「mask」の挙動を検証する問題です。

mask を実行してみると文字列の入力を求められました。

入力した文字列はある一定の規則のもとで変換が行われ、その変換結果が検証されるようです。

そこで、mask を逆アセンブルしたものを読んでいくと以下の規則があることが判明しました。

  • 入力された文字列の i 番目の文字コードと 0x75 のandを取ったものが変換後の文字列Aになる
  • 入力された文字列の i 番目の文字コードと 0xffffffeb のandを取ったものが変換後の文字列Bになる
  • AとBが別に存在する文字列と一致したときの入力文字列がフラグ

文字列A, Bと比較する文字列は strings コマンドを使って取り出します。

よって、全探索で雑にフラグを見つけるコードを書いて実行するとフラグ ctf4b{dont_reverse_face_mask} を得ることができました!

(解いている途中にmaskのcへの人力逆コンパイルを行ったのでその結果も貼っておきます)

(間違いがあればご指摘ください)

mask_solve.c

#include <stdint.h>
#include <stdio.h>
#include <string.h>

#define TARGETA "atd4`qdedtUpetepqeUdaaeUeaqau"
#define TARGETB "c`b bk`kj`KbababcaKbacaKiacki"

char *target_a = TARGETA;
char *target_b = TARGETB;

char solve(int32_t idx) {
    for(char c = '!'; c <= '~'; ++ c) {
        if((c&0x75) == target_a[idx] && (c&0xffffffeb) == target_b[idx])
            return c;
    }
    return '@';
}

int main() {
    char *target_a = TARGETA;
    char *target_b = TARGETB;

    for(int32_t idx = 0; idx < strlen(target_a); ++ idx) {
        printf("%c", solve(idx));
    }
}

mask(人力逆コンパイル結果)

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>

#define USAGE   "Usage: ./mask [FLAG]\n"
#define PUTTING "Putting on masks...\n"
#define TARGETA "atd4`qdedtUpetepqeUdaaeUeaqau"
#define TARGETB "c`b bk`kj`KbababcaKbacaKiacki"
#define SUCCESS "Correct! Submit your FLAG.\n"
#define FAILED  "Wrong FLAG. Try again.\n"

int main(int32_t argc, char **args) {
    // 1. 引数チェック
    if(argc < 2) {
        printf(USAGE);
        return 0;
    }

    // 2. strcpy, strlen FLAG
    int32_t flag_len = strlen(args[1]);
    char *flag = malloc(flag_len*sizeof(char)+1);
    strcpy(flag, args[1]);

    // 3. "Putting~" 出力
    printf(PUTTING);

    // 4. 変数準備
    char *str_90 = malloc(flag_len*sizeof(char)+1);
    char *str_50 = malloc(flag_len*sizeof(char)+1);

    for(int32_t idx = 0; idx < flag_len; ++ idx) {
        // 4. str90のidx文字目 = (flagのidx文字目) & 0x75
        str_90[idx] = flag[idx] & 0x75;

        // 5. str50のidx文字目 = (flagのidx文字目) & 0xffffffeb
        str_50[idx] = flag[idx] & 0xffffffeb;
    }

    // 6. str90, str50の末端に0x00(null文字)を追加
    str_90[flag_len] = 0x00;
    str_50[flag_len] = 0x00;

    // 7. str90, str50出力
    printf("%s\n", str_90);
    printf("%s\n", str_50);

    // 8. str90と文字列A, str50と文字列Bを比較 -> 分岐
    if(strcmp(str_90, TARGETA) == 0 && strcmp(str_50, TARGETB) == 0) {
        printf(SUCCESS);
    } else {
        printf(FAILED);
    }

    // 9. 実行終了
    return 0;
}

Misc

Welcome

説明通りCTF4BのDiscordサーバにアクセスすると、フラグ ctf4b{sorry, we lost the ownership of our irc channel so we decided to use discord} を得ることができます。

emoemoencode

絵文字が書かれたテキストファイル「emoemoendode.txt」いろいろ弄ってフラグを獲得する問題です。

とりあえず、hexdump を用いて中を見てみます。

すると…

0000000 f0 9f 8d a3 f0 9f 8d b4 f0 9f 8d a6 f0 9f 8c b4
0000010 f0 9f 8d a2 f0 9f 8d bb f0 9f 8d b3 f0 9f 8d b4
0000020 f0 9f 8d a5 f0 9f 8d a7 f0 9f 8d a1 f0 9f 8d ae
0000030 f0 9f 8c b0 f0 9f 8d a7 f0 9f 8d b2 f0 9f 8d a1
0000040 f0 9f 8d b0 f0 9f 8d a8 f0 9f 8d b9 f0 9f 8d 9f
0000050 f0 9f 8d a2 f0 9f 8d b9 f0 9f 8d 9f f0 9f 8d a5
0000060 f0 9f 8d ad f0 9f 8c b0 f0 9f 8c b0 f0 9f 8c b0
0000070 f0 9f 8c b0 f0 9f 8c b0 f0 9f 8c b0 f0 9f 8d aa
0000080 f0 9f 8d a9 f0 9f 8d bd 0a
0000089

という結果を得ることができました。

パッと見ただけでも規則性があることが大体分かりました。

  • 4バイトで1区切り
  • f0 9f 全てで共通なので無視してよさそう
  • 残り2バイトを解読していくとフラグが得られそう
  • 8d, 8c は何らかの種類を示しているだけで文字自体の情報は持っていなさそう

ということで、まずは各文字4バイト目だけに着目して解読をしてみます。

先頭5文字は ctf4b であるはずなので、これをもとにASCII表と見比べつつ対応を探すと、

  • (英小文字) = (値) - 161 + 97
  • (数字) = (値) -176 + 48

という規則があることが分かりました。

合わせて、3バイト目の 8c 8d についてはそれぞれ 「数字」「英小文字」表していることが分かりました。

この規則をとりあえず全ての値に対して適応していくとフラグ ctf4b{stegan0graphy_by_em000000ji} を得ることができました!

解く際に使用したコードを以下に貼ります。(ファイル末尾の改行文字を無視しているので、フラグが出力された後 IndexError で落ちます)

with open("emoemoencode.txt", "rb") as f:
    content = f.read()
    for idx in range(0, len(content), 4):
        chars = content[idx:idx+4]
        bias = 0
        if chars[2]-0x8c == 0:
            bias = -176+48
        elif chars[2]-0x8c == 1:
            bias = -161+97
        # print(chars[2], end=",")
        # print(chars[3], end=",")
        print(chr(chars[3]+bias), end="")

まとめ

今回は Web/Reversing/Misc を解きました。

Crypt/Pwnに全く手を出すことができずに終わったのが悔しいです。 やはり自分の知識&技術不足を痛感したのでもっと精進していくべき…していきます。

また、点数を見て避けてしまっていたことがあったのでチャレンジしていくべきだと感じました。

今回は開始と同時に参加することができなかったので、次はスケジュールもしっかり立てておきます…

最後に、CTFを開催するにあたって様々な準備、サポートをしてくださった運営の方々ありがとうございました!(楽しかったです!)

読んでいただきありがとうございました!

一応貼っておく、みたいなもの

maskを読んでいるときに書いていたメモです、一応貼ります。

f:id:guguru0014:20200524021349j:plain

AVX+DGEMMのコードを読む

目次

  1. 概要
  2. コードを読む前に
  3. コードを読む
  4. つまづいたポイント
  5. まとめ
  6. 実際に使用したコード

概要

パタヘネの「3.8 高速化:半語並列性および行列の演算」で示されていたコードでつまづきました

備忘録として、この記事を書きます

コンピュータの構成と設計 第5版 上・下電子合本版

コンピュータの構成と設計 第5版 上・下電子合本版

コード

実際に本に示されていた、行列の乗算を行うプログラム DGEMM (Double precision GEneral Matrix Multiply:倍精度汎用行列乗算) は以下の通りです

// AVXを利用して高速化したver
void dgemm_use_avx(int n, double *A, double *B, double *C) {
    for(int i = 0; i < n; i += 4) {
        for(int j = 0; j < n; ++ j) {
            __m256d c0 = _mm256_load_pd(C+i+j*n);
            for(int k = 0; k < n; ++ k) {
                __m256d a0 = _mm256_load_pd(A+i+k*n);
                __m256d b0 = _mm256_broadcast_sd(B+k+j*n);
                c0 = _mm256_add_pd(c0, _mm256_mul_pd(a0, b0));
            }
            _mm256_store_pd(C+i+j*n, c0);
        }
    }
}

コードを読む前に

コードを読む部分で重要になってくる 半語並列性、AVX について書きます

半語並列性

1つの命令で複数のデータを演算できる特性のこと

SIMD(Single Instruction Multi Data)

128bitなど、広いレジスタ内をいくつかのパーティションに分けることで (16bit * 8, 32bit * 4 ...)、複数の演算を同時に行うことができたりする

AVX

2011年に登場したintelの拡張命令セット

レジスタ幅がそれまでの128bitから倍増され256bitとなり、単一の操作で32bitの浮動小数点演算を8つ、64bitの浮動小数点演算を4つ行うことができるようになった

コードを読む

1. 関数定義

void dgemm_use_avx(int n, double *A, double *B, double *C) {

dgemm_use_avx 関数を定義しています

4つの引数をもち、それぞれ以下の意味を持ちます

  • n : 行列の次元
  • A, B, C : 行列を展開して1次元配列に変換したもの

2. ループ

    for(int i = 0; i < n; i += 4) {
        for(int j = 0; j < n; ++ j) {

行列の全ての要素を対象にして演算を行うために2重ループを使用しています

ただし、AVXを利用することで double(64bit) を対象とした演算は 同時に 4 つ 行うことができるため、変数iの増加量は 4 になっています

これは、同時に4列分の演算を行うため、一次元配列内において通常の4倍の増加させてあげる必要があります (行列を1次元配列で表現しているところがミソです)

3. 演算結果格納用行列Cへのアクセス

__m256d c0 = _mm256_load_pd(C+i+j*n);

演算結果を格納するための行列Cへのアクセスを行います

指定アドレスから256bit分読み込みを行うため、double 配列 4 要素を変数c0で 1 度に扱うことができます(下に説明があります)

4. 演算

for(int k = 0; k < n; ++ k) {
     __m256d a0 = _mm256_load_pd(A+i+k*n);
     __m256d b0 = _mm256_broadcast_sd(B+k+j*n)
    c0 = _mm256_add_pd(c0, _mm256_mul_pd(a0, b0));
}

行列乗算は対応する成分同士で掛け算を行い、その和を足し合わせることで行います

演算中に成分を足し合わせるために、変数kを用いたループを行っています

コードで使用している関数は以下のような処理を行います

_mm256_load_pd(double *p)

AVX命令を使用して4つの倍精度小数点(64bit * 4)を、指定したアドレスから連続した256bitの領域から読み込む

f:id:guguru0014:20200323001002p:plain

_mm256_broadcast_sd(double *p)

指定したアドレスからスカラ型の倍精度小数点を読み込んで、同一のコピーを4つ生成する

_mm256_add_pd(m256d a, m256d b)

足し算、要素ごとに演算が行われる

_mm256_mul_pd(m256d a, m256d b)

掛け算、要素ごとに演算が行われる

大きく分けて3演算を行っているのですが、それぞれ次のようなことをやっています

  1. _mm256_load_pd を用いて Aの行列の4成分を読み込む
  2. _mm256_broadcast_sd を用いてBの行列の1成分を読み込む
  3. それらを掛け合わせた後に足す

実際に行われている演算の様子を図示します

256bitという広い幅のレジスタを用いて、同時に4データを保持しつつ演算していることに注目します

また、この時行われている行列乗算は B*A であることに注意します (A*Bではない!!!!)(ここで時間かけた)

f:id:guguru0014:20200322235654g:plain

5. ストア

c0変数に格納していた演算結果を行列Cに書き出します

自分がつまづいたポイント

B*A

単純に自分が気づけなかっただけですが、演算は A*B ではなく B*A が行われます

degmmが元からこのような仕様なのか、それとも本のコードが間違っているかは謎ですが、戸惑いました

(一部コードを変更するだけでA*B を行うことができます)

単純に半語並列性の理解不足

複数データを同時に処理する場合のアドレス指定について、単純に理解不足でした

コードでは行列を1次元配列で表現しているのですが、その場合のアドレス指定の仕方で混乱していました

まとめ

AVXを用いた行列乗算について、コードを読んでいきました

並列処理への理解が少し(少し...)だけ深まりました

自分の思い込みによる寄り道が多すぎたので、もっと慎重になるべきだな…といった気持ちです

稚拙な文章ですが、最後まで読んでくださりありがとうございました

もし書いてある内容に誤り、不備があればご指摘をよろしくお願いします

実際に使用したコード

デバッグ用であったり、main関数を加えたコードの完全版を示します

// 実行
gcc -O0 -mavx -o degmm degmm.c
#include <stdio.h>
#include <stdlib.h>
#include <x86intrin.h>

void print(int n, double *A);
void print_m256d(__m256d m);

void dgemm(int n, double *A, double *B, double *C) {
    for(int i = 0; i < n; ++ i) {
        for(int j = 0; j < n; ++ j) {
            double c0 = C[i+j*n];
            for(int k = 0; k < n; ++ k) {
                c0 += A[i+k*n] * B[k+j*n];
            }
            C[i+j*n] = c0;
            /* printf("%d %d\n", i, j); */
            /* print(4, C); */
            /* printf("\n"); */
        }
    }
}

void dgemm_use_avx(int n, double *A, double *B, double *C) {
    for(int i = 0; i < n; i += 4) {
        for(int j = 0; j < n; ++ j) {
            __m256d c0 = _mm256_load_pd(C+i+j*n);
            for(int k = 0; k < n; ++ k) {
                __m256d a0 = _mm256_load_pd(A+i+k*n);
                __m256d b0 = _mm256_broadcast_sd(B+k+j*n);
                c0 = _mm256_add_pd(c0, _mm256_mul_pd(a0, b0));
                /* print_m256d(a0); */
                /* print_m256d(b0); */
                /* print_m256d(c0); */
                /* printf("\n"); */
            }
            _mm256_store_pd(C+i+j*n, c0);
            /* printf("%d %d\n", i, j); */
            /* print(4, C); */
            /* printf("\n"); */
        }
    }
}

void print(int n, double *A) {
    for(int i = 0; i < n; ++ i) {
        for(int j = 0; j < n; ++ j) {
            printf("%f ", A[i*n+j]);
        }
        printf("\n");
    }
}

void print_m256d(__m256d m) {
    double M[4] = {0};
    _mm256_store_pd(M, m);
    for(int i = 0; i < 4; ++ i)
        printf("%f ", m[i]);
    printf("\n");
}

int main() {
    double A[16] = {
        14, 12,  2,  6,
         1, 10,  9, 16,
         7,  8,  4, 11,
        13,  5,  3, 15
    };
    double B[16] = {
        11,  6,  4, 10,
        13,  8,  3,  5,
        12,  7, 14, 16,
         9,  1,  2, 15
    };
    double C1[16] = {0}, C2[16] = {0};
    dgemm(4, A, B, C1);
    dgemm_use_avx(4, A, B, C2);
    print(4, C1);
    print(4, C2);
    return 0;
}

TCPでDNSリクエスト

概要

TCPでDNSリクエストを送ることに成功したので、備忘録として書きます。

目次

  1. DNSリクエストパケット
  2. TCPを使用する際の変更点
  3. 実装
  4. まとめ

1. DNSリクエストパケット

基本的な構成はTCP/UDP共に同じです。

以下ページが大変参考になったのでリンクを貼らせていただきます。

DNSリクエストパケットの構成が分からない方はとりあえず読んでみてください!

pcap.it-mem.info

2. TCPを使用する際の変更点

パケットサイズを先頭につけるだけです。

パケットサイズは16bitで指定します。

TCPでDNSリクエストを送る際のパケットの構成は、以下のようになります。

**

f:id:guguru0014:20191223232715p:plain:w300
パケットの構成

3. 実装

DNSリクエストの生成と、レスポンスを解析するプログラムです。

リクエスト

#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <string>

uint8_t *makeDNSReqMsg(std::string hostURL)
{
    std::vector<std::string> labels = yn0014::mystring::split(hostURL, ".");
    size_t hd_len = 7 * sizeof(int16_t), qb_len = 0;
    uint16_t header[7] = {0};
    uint8_t *qsecBody = (uint8_t*)calloc(labels.size()*15+5, sizeof(uint8_t));

    // DNS Query Header(TCP)
    header[2] |= RD;   // RDビット
    header[3] = 1;        // QuestionSectionの数

   // DNS Quesition Section
    for(auto part : labels) {
        qsecBody[qb_len++] = part.size();   // ラベルサイズ
        for(char c : part) {
            qsecBody[qb_len++] = c; // ラベル
        }
    }
    qsecBody[qb_len++] = 0;   // ラベル終端
    qsecBody[qb_len++] = 0;  // Aレコード要求
    qsecBody[qb_len++] = 1;   // Aレコード要求
    qsecBody[qb_len++] = 0;
    qsecBody[qb_len++] = 1;
    header[0] = hd_len+qb_len-2;  // パケットサイズ(QuestionSectionの長さが確定してから)

    // 組み立て
    uint8_t *msg = (uint8_t*)malloc(hd_len+qb_len);
    for(int32_t idx = 0; idx < (int32_t)hd_len; idx += 2) { // エンディアンの影響で素直にmemcpyが使えない
        msg[idx] = (header[idx/2] & 0xff00) >> 8;
        msg[idx+1] = header[idx/2] & 0x00ff;
    }
    memcpy(msg+hd_len, qsecBody, qb_len);
    free(qsecBody);
    return msg;
}

(yn0014::mystring::splitは与えられた文字列を区切り文字で区切り、std::vector<std::string>を返します。)

ヘッダでは RD ビットとQuestionSectionの数を指定しています。

ヘッダとQuestionSectionを連結する部分が少し面倒です。

uint16_t で扱っているヘッダをそのまま memcpy するとリトルエンディアン環境であった場合は、意図しない内容のリクエストパケットが生成されてしまいます。

(ネットワークバイトオーダ = ビッグエンディアン)

そのため、リトルエンディアンからビッグエンディアンに変換する処理を挟んでいます。

QuestionSectionについては特に問題なく memcpy できます。

レスポンス解析

#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <string>

#define memcpynum16(dst, src) ((dst |= ((src)[0] << 8) | (src)[1]))
#define memcpynum32(dst, src) ((dst |= ((src)[0] << 24) | ((src)[1] << 16) | ((src)[2] << 8) | (src)[3]))

std::vector<std::string> parseDNSResMsg(uint8_t *msg, size_t qb_len)
{
    uint16_t flag = 0, resp = 0, offset = 0;

    // Header
    memcpynum16(flag, msg+4);        // オプション
    memcpynum16(resp, msg+8);       // AnswerSectionの数           
    if((flag & RCODE) != 0 || (flag & RA) != RA) {          // RCODEが1 => 正常に完了しなかった, RAビットが0 => 名前解決不可能
        cerr << "Received error response" << endl;
        return std::vector<std::string>();
    }
    if(resp == 0) {
        cerr << "AnswerSection is empty" << endl;
        return std::vector<std::string>();
    }
    msg += 14;

    // Question Section
    msg += qb_len;     // 読み飛ばす

    // Answer Section
    std::vector<std::string> ipList;
    for(; resp > 0; -- resp) {
        memcpynum16(offset, msg);
        if((offset & 0xc000) == 0) {   // 先頭2ビットが立っていない => ラベル省略なし、そのままくっついている
            offset = 0;
            while(msg[offset] != 0) ++ offset;
        } else {     // 先頭2ビットが立っている => ラベル省略
            offset = 2;
        }
        msg += offset + 10;
        ipList.emplace_back(yn0014::mystring::format("%d.%d.%d.%d", msg[0], msg[1], msg[2], msg[3]));
        msg += 4;
    }

    return ipList;
}

(yn0014::mystring::formatは内部でsprintfを行い、std::stringを返します。)

QuestionSectionを読み飛ばすために、parseDNSResMsg でそのサイズを受け取るようにしています。

簡単に解析するなら、以上のプログラムで十分だと思います。(多分…)

リクエストの時と同じように、エンディアンの違いが邪魔をするので簡単なマクロを定義しています。

また、AnswerSectionについてくるラベルについては読む必要がないと判断したので、切り捨てられているorラベルがくっついている のを判定したのちに読み飛ばすようにしています。

送信

std::vector<std::string> resolve(std::string hostURL)
{
    uint8_t *reqMsg = makeDNSReqMsg(hostURL), *respMsg;
    size_t reqLen = ((uint16_t*)reqMsg)[0];
    reqLen = ((reqLen & 0xff00) >> 8) | ((reqLen & 0x00ff) << 8);
    reqLen += 2;

    yn0014::net::TCPConnector conn("8.8.8.8", 53);
    conn.sendMsg(reqMsg, reqLen);
    respMsg = conn.getRecv();

    std::vector<std::string> result = parseDNSResMsg(respMsg, reqLen-14);   // QuestionSectionの長さだけ欲しいのでヘッダーサイズを引く
    free(reqMsg);
    free(respMsg);
    return result;
}

(yn0014::net::TCPConnectorはTCP通信を行うための自作クラスです、実装は省略します)

4. まとめ

TCPでDNSリクエストを送っている記事が見当たらなかったので書きました。

正直UDPで送る場合とほとんど変わりがないので薄い記事になってしまった感じが…します。

記事中のプログラムについては、実装中のコードからコピーして良い感じに整えたものです。

自己満足のような記事になってしまいましたが、最後まで読んでいただきありがとうございました。

理解や実装に間違いがあれば、ご指摘のほどよろしくお願いします…。