Skip to content

writeup.ja.md

Latest commit

 

History

History
100 lines (76 loc) · 5.9 KB

writeup.ja.md

File metadata and controls

100 lines (76 loc) · 5.9 KB

Sanity Check Writeup (ja)

Solution

Envoyというプロキシを立ち上げるcompose.ymlが与えられます。 プロキシには、数百個のリダイレクトルールが設定されており、パスに設定する文字列によりレスポンスが変わるようです。

大抵の場合、ngというレスポンスが返ってきますが、okというレスポンスが返ってくる入力が存在するようです。 空の文字列を入力するとokとなるようなので、どうにかしてTSGCTF{blah}形式の文字列を空文字列に変換できないか考えてみます。

文字列を消去するリダイレクトルールとして、以下の26種類が存在します。

  • A(a) を消去
  • B(b) を消去
  • ...
  • Z(z) を消去

これらは、Aを開き括弧、(a)を閉じ確固としてみれば26種類の括弧記号からなる括弧列として見ることができます。 これ以外に、アルファベットの大文字を消したり変換するルールは存在しません。 フラグの内容に関わらず、先頭のTSGCTFを削除することを考えると最終的に目指すべき形がTSGCTF(f)(t)(c)(g)(s)(t)になることがわかります。

(と)を生み出す方法については、関連するルールが以下の5つしか存在しません。

  1. }{ を + に変換
  2. } を　) に変換
  3. { を　(/ に変換
  4. _ を　)(/ に変換
  5. /) を　) に変換

波括弧を生成するルールが存在しないこと、+を消去するルールが存在しないことなどを踏まえると、フラグ形式は以下の通りです。

TSGCTF{aaaa_bbbb_cccc_dddd_eeee_ffff}

括弧の変換ルールを適用すると、以上のフラグは次のように変換されます。

TSGCTF(/aaaa)(/bbbb)(/cccc)(/dddd)(/eeee)(/ffff)

目指すべき形であるTSGCTF(f)(t)(c)(g)(s)(t)と見比べると、/aaaaの部分をfに書き換える問題が独立して6個ある形になりました。

使っていないルールを確認すると、以下の4種類に大別できます。

  1. /ab を kXYZ/ に変換
  2. /ab を (s)(t)(u)XYZ/ に変換
  3. /ab を (s)(t)(u)/ に変換

abの部分は1文字なこともありますが、それらのルールは優先順位が低いため、右端で1文字だけ余った時に適用されます。

いずれの場合でも、/の直後にある1-2文字を何か別の文字列に変換し、/を後ろにスライドさせています。 これらのルールの適用前は(の直後にある/記号ですが、適用を繰り返すことでこの記号が右にカーソルのように移動し、)に到達した段階で消滅します。

/変換後の記号列は、アルファベット大文字(XYZなど)と小文字((s)(t)(u)など)から構成されており、文字列を消去するルールが適用できます。 しかし、ルール1に含まれる kのみ括弧に含まれておらず、文字列を消去するルールが適用できません。 これは、目指すべき形TSGCTF(f)(t)(c)(g)(s)(t)に含まれるfなどに相当するものです。 よって、(f)に対応する括弧内にはfXYZ/の形の変換ルールを入れることが確定します (TSGCTF(f/XYZ???)(t/XYZ???)(c/XYZ???)(g/XYZ???)(s/XYZ???)(t/XYZ???))。 ただし、そのままではXYZ部分が邪魔なので、ルール3を用いて(z)(y)(x)を出現させ、対消滅させたいところです。 しかし、(z)(y)(x)を直接出現させるルールは存在しないため、ルール2を何回か繰り返すことでルール3がハマる形を作ることになります。 (オートマトン的な気持ち)

これは、「ルールの適用」を辺としたグラフを考えてあげるとBFSで探索可能です。

  1. 頂点 k (始点) から 頂点 XYZ への有向辺 (ラベル: ab)
  2. 頂点 UTS から 頂点 XYZ への有向辺 (ラベル: ab)
  3. 頂点 UTS から 頂点 (終点) への有向辺 (ラベル: ab)

例えば、(f)に相当する頂点では以下の経路が唯一の解です。同様に、(t)(c)(g)(s)(t)についても求められます。

  • (始点)
    • 変換　ht: fVDM
  • 頂点 VDM
    • 変換　tp: (V)(D)(M)EJW
  • 頂点 EJW
    • 変換　-r: (E)(J)(W)VJV
  • 頂点 VJV
    • 変換　d1: (V)(J)(V)YZA
  • 頂点 YZA
    • 変換　re: (Y)(Z)(A)ZAA
  • 頂点 ZAA
    • 変換　ct: (Z)(A)(A)EHH
  • 頂点 EHH
    • 変換　5-: (E)(H)(H)WSM
  • 頂点 WSM
    • 変換　ca: (W)(S)(M)HCB
  • 頂点 HCB
    • 変換　n: (H)(C)(B)
  • 終点

あとは、今までの考察から逆算してフラグを復元します。

  • TSGCTF{http-red1rect5-can_funct10n_as-tur1ng-c0mp1ete_m4rk0v-a1g0rithm_proce55ing_funct10n}
  • TSGCTF(/http-red1rect5-can)(/funct10n)(/as-tur1ng-c0mp1ete)(/m4rk0v-a1g0rithm)(/proce55ing)(/funct10n}
  • TSGCTF(fVDM(V)(D)(M)EJW(E)(J)(W)VJV(V)(J)(V)YZA(Y)(Z)(A)ZAA(Z)(A)(A)EHH(E)(H)(H)WSM(W)(S)(M)HCB(H)(C)(B/))(tQOB(Q)(O)(B)TQB(T)(Q)(B)DZS(D)(Z)(S/))(cQOH(Q)(O)(H)PVK(P)(V)(K)MHC(M)(H)(C)QLD(Q)(L)(D)QMA(Q)(M)(A)MDL(M)(D)(L)ULP(U)(L)(P)PQH(P)(Q)(H/))(gOAL(O)(A)(L)HYA(H)(Y)(A)DTI(D)(T)(I)PJD(P)(J)(D)EPV(E)(P)(V)PAV(P)(A)(V)JTO(J)(T)(O/))(sTOW(T)(O)(W)RXQ(R)(X)(Q)XTL(X)(T)(L)VMM(V)(M)(M/))(tQOB(Q)(O)(B)TQB(T)(Q)(B)DZS(D)(Z)(S/))
  • TSGCTF(fVDM(V)(D)(M)EJW(E)(J)(W)VJV(V)(J)(V)YZA(Y)(Z)(A)ZAA(Z)(A)(A)EHH(E)(H)(H)WSM(W)(S)(M)HCB(H)(C)(B))(tQOB(Q)(O)(B)TQB(T)(Q)(B)DZS(D)(Z)(S))(cQOH(Q)(O)(H)PVK(P)(V)(K)MHC(M)(H)(C)QLD(Q)(L)(D)QMA(Q)(M)(A)MDL(M)(D)(L)ULP(U)(L)(P)PQH(P)(Q)(H))(gOAL(O)(A)(L)HYA(H)(Y)(A)DTI(D)(T)(I)PJD(P)(J)(D)EPV(E)(P)(V)PAV(P)(A)(V)JTO(J)(T)(O))(sTOW(T)(O)(W)RXQ(R)(X)(Q)XTL(X)(T)(L)VMM(V)(M)(M))(tQOB(Q)(O)(B)TQB(T)(Q)(B)DZS(D)(Z)(S))
  • TSGCTF(f)(t)(c)(g)(s)(t)
  • (受理状態)

Flag

TSGCTF{http-red1rect5-can_funct10n_as-tur1ng-c0mp1ete_m4rk0v-a1g0rithm_proce55ing_funct10n}