shiho-elliptic - Tumblr blog

[shiho-elliptic]

Crypto CTF 2023 Writeup (JA)

(English ver. https://shiho-elliptic.tumblr.com/post/722391959624433664/crypto-ctf-2023-writeup-en )

CryptoCTF 2023にieraeとして参加しました. 結果は13位(全完, 得点的には1位タイ)でした.

@ta1yak1_8926 視点: https://hackmd.io/@taiyaki/BJCWj0LKn

Solved by me

Bertrand (medium, 21 solves)

2nd solve.

暗号文は画像で提供される. 鍵の大きさに応じて回転するが, 回転は4種類しかない($$90\times n\lbrack\deg\rbrack$$)ので, 全パターンを列挙できる. また関数 sox は無視できる.

平文と暗号文はbyte-by-byteに対応するので, この暗号はtransposition cipherとして扱える. 鍵に依存したソート処理も存在するが, 鍵の長さは3に固定しているので, $$\lvert S _ 3\rvert = 3! = 6$$ パターンをすべて列挙すればよい.

後はフラグフォーマットを利用し, 鍵の各バイトを総当りすれば解ける. 最終的な計算量はちょうど$$4\times 6 + 256^3$$である.

Solver:

https://gist.github.com/elliptic-shiho/717b44cc1c5cc8b0707a81b7b345cdc9

Insights (medium, 88 solves)

d = next_prime(pow(n, 0.2919)) なので $$d$$ は $$n$$ から唯一定まる. Hardにしては簡単すぎると思っていたらmediumに落ちた. 作問ミス?

Solver:

https://gist.github.com/elliptic-shiho/6ec91e35e4a974572ecb1d576d446ba0

Shevid (hard, 17 solves)

SIDH. 構成からCastryck-Decru attackをそのまま適用できるように見えたため, https://github.com/GiacomoPope/Castryck-Decru-SageMath をもとにコードを少し書いて解いた.

Solver:

https://gist.github.com/elliptic-shiho/f5e694e2cf2233fccf3f199f60f45c6b

Barak (medium, 27 solves)

Hessian curveが与えられる. Hessian curveは楕円曲線と双有理同値なので, Marc Joye and Jean-Jacques Quisquater. 2001. Hessian Elliptic Curves and Side-Channel Attacks. 等を読みつつ楕円曲線上の点に変換.

楕円曲線の点として考えるとき, base point $$P$$とすると$$\lvert P\rvert = 3083219685676632130193959041477461850061047352503612$$である. この素因数はたかだか$$2^{35}$$程度でしかなく, ゆえにPohlig-Hellman attackを適用できる. 実際にはPari/GPの ellog 関数に任せた.

ただし, $$m\lt p$$ という制約しか存在しないにも関わらず$$\lvert P\rvert \lt p$$であるため, $$m$$を完全に復元することはできなかった. このため実際の解は$$x _ 0 + n\lvert P\rvert$$の形になる. ただし $$x _ 0$$ はECDLPの解, $$0\leq n\lt 25$$ ($$\because 24\lvert P\rvert \lt p \lt 25\lvert P\rvert$$).

Solver:

https://gist.github.com/elliptic-shiho/cf112ddf554ea9d447dff31cb40731bf

Byeween (hard, 22 solves)

楕円曲線$$E$$とその上の点$$Q$$が与えられる. $$2P = Q$$を満たす点をすべて計算すればフラグをもらえる.

楕円曲線における2分割点はdivision polynomialの解を計算すれば求められる. 実際SageMathの division_points もこれを利用したものである1. 完全にすべての解を求められない場合もあるようだが, ほとんどの場合うまく行く.

Solver:

https://gist.github.com/elliptic-shiho/deccae6523d5548086e237ee70f1ee42

Vinefruit (hard, 19 solves)

hash collisionを起こせばよい. 対象となるハッシュ関数$$\mathrm{vinefruit} _ {p, o, m}(m)$$はメッセージ$$(m _ i) _ {i = 1, \ldots, \ell}$$とパラメータ$$p, o, m$$に対し$$f(p)$$である. ただし

$$$ f(x) = ((o + m _ 1) x^\ell + m _ 2x^{\ell - 1} + \cdots + m _ \ell x) \bmod m. $$$

$$p, o, m$$を固定して考えるとき, 最も単純なのは $$\mathrm{vinefruit}(00^\ell)$$ への衝突である. これは$$\mathrm{vinefruit}(x) - \mathrm{vinefruit}(00^\ell)\equiv 0\pmod m$$の$$x$$を決定する問題を解くことで求められ, 特にModular knapsack problemに帰着できる. 次に示す格子はその解を与える:

$$$ \begin{pmatrix} 1 & 0 & \cdots & 0 & 0& p\cr 0 & 1 & \cdots& 0 & 0 & p^2\cr 0 & \vdots & \ddots & \cdots & \vdots & \vdots\cr 0 & 0 & \cdots & 1 & 0 & p^{\ell - k}\cr 0 & 0 & \cdots & 0 & 1 & c \cr 0 & 0 & \cdots & 0 & 0 & -m\cr \end{pmatrix} $$$

ただし $$$ c = ((o + m _ \ell)p^\ell + m _ {\ell - 1}p^{\ell - 1} + \cdots + m _ {\ell - k + 1}p^{\ell - k + 1} - \mathrm{vinefruit}(00^\ell)) \bmod m $$$

である. $$m _ \ell, m _ {\ell - 1}, \ldots, m _ {\ell - k + 1}$$は初期値としてランダムに選択する. 実際には重み付けをしているが割愛した. この格子のLLL簡約基底のうち, すべての値が0から255までに収まるようなものを取れば, hash collisionを引き起こせる.

ただし, この方針で進めた場合$$m$$が大きくなるほど衝突を構成しづらくなる. このため$$m = 2^{32}$$, $$m = 2^{64}$$ の場合のみを計算し, $$m = 2^{128}$$ の場合を無視することとした. 本問題は$$\ell\in\lbrace\,35, 34, \ldots, 17\,\rbrace$$に対してそれぞれ3通りの$$m$$が決まるため, $$(2/3)^{18} = 262144/387420489 = 1/(2^{10.52932\ldots}) \gt 1/1500$$より1500回に1回程度$$m \ne 2^{128}$$を仮定できる. これを利用して解いた.

Solver:

https://gist.github.com/elliptic-shiho/bc5cf7f519ad28f2369625ad49bd9089

After the comptetition:

本攻撃は第二原像攻撃を目指したものであったが, 実際には衝突攻撃を解けば十分である. 加えて vinefruit 関数はローリングハッシュとして扱えるため, よく知られたローリングハッシュの衝突実装を引用すれば簡単に解ける (この場合はSVPではなくCVPを解くことになる).

Solved with teammates

Risk (medium, 35 solves)

素因数分解は@ta1yak1_8926が終わらせていた(詳細: https://hackmd.io/@taiyaki/BJCWj0LKn#Risk-122-pts-35-solves-Medium )が, $$\gcd(\varphi(N), e) = 10728$$ な状況におけるRSAを解くところで詰まっていたのでそこだけ. $$\mathbb{F} _ q$$へと帰着して$$x^6 - A = 0$$の解として計算.

Solver:

https://gist.github.com/elliptic-shiho/cfd56e9dd47c7f2041157ffb6bb7477c

Big (hard, 23 solves)

パラメータ$$a, N = pq$$は既知. $$N$$の素因数分解は@ta1yak1_8926が終わらせていた(詳細: https://hackmd.io/@taiyaki/BJCWj0LKn#Big-169-pts-23-solves-Hard ). 最後の部分だけ.

各ビット$$b$$について$$\left(\frac{t}{N}\right) = 1\iff b = 1$$であるように$$t$$を選び, $$c := t - a/t \bmod N$$としている. $$c \equiv (t^2 - a)/t\pmod N$$より$$tc \equiv t^2 - a \pmod N \iff t^2 - tc - a \equiv 0\pmod N$$. 係数はすべて判明しているので, そのまま二次方程式として解けばよい.

Anca-Maria Nica. 2020. Quadratic Residues and Applications in Cryptography. - https://profs.info.uaic.ro/~webdata/doctorate/NicaAncaMaria/Rezumat-En.pdf §4.1.1 Cocks' IBE ciphertexts に同じものがある. フラグもそのことに触れていた.

Solver:

https://gist.github.com/elliptic-shiho/07b3440678135f0712d467925b9e81af

感想

本格的にCTFに取り組んだのは数年振りだったが, 良い結果になってよかった. 速度が落ちている感覚はあるので, リハビリがてら今年はいくらか参加していきたい.

https://github.com/sagemath/sage/blob/9.8/src/sage/schemes/elliptic_curves/ell_point.py#L886 ↩︎

[shiho-elliptic]

Crypto CTF 2023 Writeup (EN)

(日本語版: https://shiho-elliptic.tumblr.com/post/722392022714073088/crypto-ctf-2023-writeup-ja )

I participated to CryptoCTF 2023 as a team "ierae". we're placed at 13th (we completed all challenges, so the score is equal to 1st team's that).

My teammate's writeup: @ta1yak1_8926: https://hackmd.io/@taiyaki/BJbEomuF2

Solved by me

Bertrand (medium, 21 solves)

2nd solve.

We have an image file which is encoded the ciphertext. The encrypt function has been applied rotation to that, but rotation degree is only four patterns ($$90\times n\lbrack\deg\rbrack$$, $$n\in \mathbb{Z}$$) so we can enumerate the all cases. More, we can ignore sox because it used at image generation phase only.

The plaintext (= flag) and ciphertext corresponded byte-by-byte, hence this cipher can interpret as a transposition cipher. Further, It has a key-based sort process, but the key-length is only three bytes so we can enumerate all cases of that easily (It's only $$\lvert S _ 3\rvert = 3! = 6$$ patterns!)

I used the flag prefix CCTF{ as "known plaintext" for brute-force the key of that. the allover complexity is just $$256^3$$.

Solver:

https://gist.github.com/elliptic-shiho/717b44cc1c5cc8b0707a81b7b345cdc9

Insights (medium, 88 solves)

$$d$$ is uniquely determined from $$n$$ since d = next_prime(pow(n, 0.2919)). that's all.

Note: the difficulty of this challenge is "hard" at first. I thought "too easy for hard" at solved, but it was changed to "medium" later. lol

Solver:

https://gist.github.com/elliptic-shiho/6ec91e35e4a974572ecb1d576d446ba0

Shevid (hard, 17 solves)

It's an instance of SIDH. We can apply Castryck-Decru attack. I wrote a script that used https://github.com/GiacomoPope/Castryck-Decru-SageMath and solved it.

Solver:

https://gist.github.com/elliptic-shiho/f5e694e2cf2233fccf3f199f60f45c6b

Barak (medium, 27 solves)

We have a Hessian curve. Hessian curve is birationally equivalent to Elliptic curve, so I transform given curve and points to corresponded Elliptic curve and the points on that. Marc Joye and Jean-Jacques Quisquater. 2001. Hessian Elliptic Curves and Side-Channel Attacks. was a good reference for me.

When transformed on the Elliptic curve, the base point $$P$$ holds $$\lvert P\rvert = 3083219685676632130193959041477461850061047352503612$$. Any its prime factor is smaller than $$2^{35}$$, therefore we can use Pohlig-Hellman attack to this ECDLP instance. In fact, I used ellog function of Pari/GP.

Nonetheless, We can't get the plaintext $$m$$ even solved ECDLP correctly. It caused by that holds $$m\lt \lvert P\rvert \lt p$$. so "actual solution" is formed "$$m = x _ 0 + n\lvert P\rvert$$" where $$x _ 0$$ is the solution of ECDLP and $$0\leq n\lt 25$$ ($$\because 24\lvert P\rvert \lt p \lt 25\lvert P\rvert$$).

Solver:

https://gist.github.com/elliptic-shiho/cf112ddf554ea9d447dff31cb40731bf

Byeween (hard, 22 solves)

We have an ellitic curve $$E$$ and a point $$Q$$ on $$E$$. We need to compute ALL $$P\in E$$ that satisfies $$2P = Q$$ to get the flag.

In general, the two-division points of a point can compute by compute the roots of division polynomial for that. SageMath's division_points method1 uses that too. It can solve this challenge with fail a few times, because that can't compute the all solutions sometimes.

Solver:

https://gist.github.com/elliptic-shiho/deccae6523d5548086e237ee70f1ee42

Vinefruit (hard, 19 solves)

We need to collide the given hash function. the target hash function is defined by $$\mathrm{vinefruit} _ {p, o, m}(m) := f(p)$$, where $$(m _ i) _ {i = 1, \ldots, \ell}$$ is target message, $$(p, o, m)$$ is parameter, and $$f(x)$$ is

$$$ f(x) = ((o + m _ 1) x^\ell + m _ 2x^{\ell - 1} + \cdots + m _ \ell x) \bmod m. $$$

For simple, we fixed $$(p, o, m)$$ and omit that in below discussion.

Set $$\mathrm{vinefruit}(00^\ell)$$ as a target to collide. In this situation, the challenge can transform to "Compute a $$x$$ that satisfies $$\mathrm{vinefruit}(x) - \mathrm{vinefruit}(00^\ell)\equiv 0\pmod m$$" . In fact, we can reduce this challenge to an instance of Modular knapsack problem, so we can solve this challenge by LLL-reducing following lattice:

$$$ \begin{pmatrix} 1 & 0 & \cdots & 0 & 0& p\cr 0 & 1 & \cdots& 0 & 0 & p^2\cr 0 & \vdots & \ddots & \cdots & \vdots & \vdots\cr 0 & 0 & \cdots & 1 & 0 & p^{\ell - k}\cr 0 & 0 & \cdots & 0 & 1 & c \cr 0 & 0 & \cdots & 0 & 0 & -m\cr \end{pmatrix} $$$

where

$$$ c = ((o + m _ \ell)p^\ell + m _ {\ell - 1}p^{\ell - 1} + \cdots + m _ {\ell - k + 1}p^{\ell - k + 1} - \mathrm{vinefruit}(00^\ell)) \bmod m $$$

and choose $$m _ \ell, m _ {\ell - 1}, \ldots, m _ {\ell - k + 1}$$ randomly as an initial state. In actual code, I decorated(i.e. weighted) to the lattice but omitted. We can collide the hash function by a message constructed by a vector, that is LLL-reduced basis of the lattice and all element of that is an unsigned 8-bit integer (i.e. it is the 0 to 255).

However, this strategy is not effetive when large $$m$$ because the constraint "unsigned 8-bit integer" becomes too hard. I decide to ignore the case of $$m = 2^{128}$$ and precompute the cases of $$m = 2^{32}$$ and $$m = 2^{64}$$ (Note: $$m$$ is only these three cases).

In this challenge, $$m$$ is determined for every $$\ell\in\lbrace\,35, 34, \ldots, 17\,\rbrace$$ so the probability of "All $$m$$ does not equals to $$2^{128}$$" is $$(2/3)^{18} = 262144/387420489 = 1/(2^{10.52932\ldots}) \gt 1/1500$$. Hence we can solve that with about 1500-times reconnect.

Solver:

https://gist.github.com/elliptic-shiho/bc5cf7f519ad28f2369625ad49bd9089

After the comptetition:

This attack is a second-preimage attack. However collision attack is enough to solve this actually. In addition, vinefruit function can interpret as rolling hash, so we can attack that using any famous implementation. In this strategy, It use the Closest Vector Problem to solve that whereas I used the Shortest Vector Problem.

Solved with teammates

Risk (medium, 35 solves)

Prime factorization is done by @ta1yak1_89262. but he stucked to solve the RSA with $$\gcd(\varphi(N), e) = 10728$$. I solved that using the cannonical map $$\mathbb{Z} / pq\mathbb{Z}\hookrightarrow \mathbb{F} _ q$$ and solve $$x^6 - A \equiv 0\pmod q$$ by SageMath's roots() method.

Solver:

https://gist.github.com/elliptic-shiho/cfd56e9dd47c7f2041157ffb6bb7477c

Big (hard, 23 solves)

We know parameters $$a$$ and $$N = pq$$. Prime factorization is done by @ta1yak1_89263, I solved only after that.

For every bit $$b\in\lbrace\,0, 1\,\rbrace$$, Select $$\left(\frac{t}{N}\right) = 2b - 1$$ as randomly, and put $$c := t - a/t \bmod N$$. Since $$c \equiv (t^2 - a)/t\pmod N$$ so we have $$tc \equiv t^2 - a \pmod N \iff t^2 - tc - a \equiv 0\pmod N$$. all coefficients are known so we can solve that as an ordinary quadratic equation (over $$\mathbb{F} _ p$$ and $$\mathbb{F} _ q$$). CRT is useful.

If you interested in the theoretical details, see §4.1.1 Cocks' IBE ciphertexts in Anca-Maria Nica. 2020. Quadratic Residues and Applications in Cryptography. - https://profs.info.uaic.ro/~webdata/doctorate/NicaAncaMaria/Rezumat-En.pdf

Solver:

https://gist.github.com/elliptic-shiho/07b3440678135f0712d467925b9e81af

Afterwords

It's been a while since I played CTF seriously, and I could get a good result. Feel Good Inc.

However It's taking longer than it did before to solve challenge. I wanna participate to CTF as much as possible in this year.

https://github.com/sagemath/sage/blob/9.8/src/sage/schemes/elliptic_curves/ell_point.py#L886 ↩︎

Details: https://hackmd.io/@taiyaki/BJbEomuF2#Risk-122-pts-35-solves-Medium (in Japanese). ↩︎

Details: https://hackmd.io/@taiyaki/BJbEomuF2#Big-169-pts-23-solves-Hard (in Japanese). ↩︎

[shiho-elliptic]

Segment Tree

Edited (2019/09/21 02:45): $$build(\alpha)$$, Monoidの定義 (Thanks @a3VtYQo) Edited (2019/09/22 08:06): 出典等追記.

一定の理解度を得ることができた気がしたので, 一通りまとめた. なお, この記事は問題を解くために書かれたものではなく, 純粋にSegment Treeというデータ構造に関して書かれていてほしい内容をすべて説明した記事というのがどこにもなかったために書かれたものである.

概要

なぜか誰も擬似コードの形ではこれを書いていなかったのでそれで書く. C++コードが競技プログラミングの世界では主流のようだが, アルゴリズムだけ知りたいときにはやはり擬似コードぐらいの抽象度まで上げてよいと思う (主観).

現状Lazy-Propagationな場合については触れていないが, 今後追記する予定である.

本記事に載っているアルゴリズムは主に[1]を読んだ結果と[2], [9]のものを参考としている. また, 理論的背景に関しては[1], [3], [4], [5], [6], [7], [8], [9]の内容をもとに考察した結果である. [11]も読むには読んだが, 問題を解くだけならいいけども理論的背景はほぼ知れなかった. [12]は解説資料としては良いが理論的背景に関しては物足りない感じがある. 他には[13], [14]を参考資料として読んでいた.

仮定

要素数は必ず$$N := 2^k$$で表されると仮定する1. [3]で触れられている通りこれは圏として考えられる(totalityが実際には不要)わけだが, 自分の圏に対する理解が進んでいないことから, 本記事ではMonoidを使用したものを考える.

Monoidの定義: 集合$$T$$, 二項演算 $$f: T\times T\rightarrow T$$, ある$$e\in T$$について, 以下条件が成立しているとき, $$(T, f, e)$$をMonoidという:

$$\forall x\in T$$, $$f(x, e) = f(e, x) = x$$ (Identity Element)

$$x, y, z\in T$$, $$f(f(x, y), z) = f(x, f(y, z))$$ (Associativity)

例えば, 自然数全体の集合に0を付け加えた集合$$\mathbb{N} _ 0 = \mathbb{N}\cup\lbrace 0\rbrace$$は$$(\mathbb{N} _ 0, +, 0)$$とすればMonoidになる. また, $$(\mathbb{N}, \cdot, 1)$$もMonoidである. 本記事ではそれぞれ名前を付けているが, 一般的には, コンテクストが明瞭な場合にしばしば集合の記号を指してMonoidということがある. e.g. 「Monoid $$\mathbb{N} _ 0$$について〜」.

構造

木構造, 特に完全二分木. ただし, 根に区間$$\lbrack 1, N\rbrack$$, 深さ1の2頂点にはそれぞれ$$\left\lbrack 1, \frac{N}{2}\right\rbrack$$, $$\left\lbrack \frac{N}{2} + 1, N\right\rbrack$$の区間を割り当てる. 同様に深さ$$\ell$$の頂点には長さ$$\frac{N}{2^{\ell}}$$の区間を割り当てていく2.

深さ$$\ell$$の頂点に割り当てられる区間の和集合をとると$$\lbrack 1, N\rbrack$$に等しい. このことから深さ$$\ell$$にある頂点は深さ$$\ell-1$$にある頂点の半分の区間を持つという, いわば「カバー範囲」を半分ずつとる構造をしていることがわかる. この点から, Segment Treeは二分探索木のように見ることができる.

蛇足

Segment Treeはデータ構造であり, 構造以上のものではない. このため, 「Segment Treeを利用するアルゴリズム」はSegment Treeとは別個に語られるべきものである. いわば次節に示されている「Segment Treeにより区間演算が$$O(\log N)$$で可能である」という事実は単なるおまけである. 本質的なデータ構造としては区間の割当であり, 区切られた(Segment)木である.

アルゴリズム

本節においては, Segment Treeを応用した点代入・区間クエリアルゴリズムを示す. 前述の通り[1], [2], [9]を参考にしているが, 擬似コードとして書き直す段階でかなり書き直しをしている. また, これまでは閉区間を扱っていたが, 条件式が簡単になる都合から半開区間で考える.

Notation

$$\mathcal{M} = (T, f, e)$$: Monoid

二分木の葉: $$\mathrm{leaf}\lbrack 1\rbrack, \ldots, \mathrm{leaf}\lbrack N\rbrack$$

二分木の頂点$$v$$の子頂点, 親頂点, 値: $$(v.left, v.right)$$, $$v.parent$$, $$v.value$$

二分木の根: $$\mathrm{root}$$

構築($$build(\alpha)$$)

入力: 初期値 $$\alpha\in T$$

Let $$Q$$ be a FIFO queue

For $$i = 1, \ldots, N$$

$$\mathrm{leaf}[i].value \leftarrow \alpha$$

If $$(i\bmod 2) = 1$$:

$$\mathrm{Enqueue\ } \mathrm{leaf}[i].parent \mathrm{\ to\ } Q$$

End If

End For

While $$Q\ne\emptyset$$:

$$v\leftarrow \mathrm{Dequeue\ from\ } Q$$

$$v.value = f(v.left.value, v.right.value)$$

If $$v \ne \mathrm{root}$$:

If $$v.parent.left = v$$:

$$\mathrm{Enqueue\ } v.parent \mathrm{\ to\ } Q$$

End If

End If

End While

計算量: $$O(N)$$

すべての葉の値を$$\alpha$$で初期化する. 実装上はMonoidのIdentity Element $$e$$で初期化することが多いだろう.

このアルゴリズムはすべての頂点を葉から根へ幅優先で回る. 葉が$$N = 2^k$$個ある完全二分木なので, 全体の頂点数は$$1 + 2 + 2^2 + \cdots + 2^{k-1} + 2^k = 2^{k+1} - 1 = 2N - 1$$. ゆえに$$O(N)$$ (キューの処理時間は無視).

4.2行目の計算は$$\mathcal{M}$$のAssociativityにより正しく計算することができることが保証される.

更新($$update(i, v)$$)

入力: 葉の位置 $$i\in\lbrack 1, N+1)$$, 代入値$$v\in T$$

$$\mathrm{leaf}.value\lbrack i\rbrack \leftarrow v$$

$$c\leftarrow i$$

While $$c \ne \mathrm{root}$$:

$$c\leftarrow c.parent$$

$$c.value \leftarrow f(c.left.value, c.right.value)$$

End While

計算量: $$O(\log N)$$

$$\mathrm{leaf}\lbrack i\rbrack.value$$に$$v$$を代入する.

3.2行目の計算は$$\mathcal{M}$$のAssociativityにより正しく計算することができることが保証される.

クエリ($$query(\lbrack l, r))$$)

入力: 葉の区間 $$\lbrack l, r)$$

Return $$vertex\_query(\lbrack l, r), \mathrm{root}, \lbrack 1, N + 1))$$

計算量: $$O(\log N)$$

区間$$\lbrack l, r)$$について, $$f(\mathrm{leaf}\lbrack l\rbrack.value, f(\mathrm{leaf}\lbrack l+1\rbrack.value, f(\cdots, f(\mathrm{leaf}\lbrack r-2\rbrack.value, \mathrm{leaf}\lbrack r-1\rbrack.value)\cdots)))$$を計算する.

頂点指定クエリ ($$vertex\_query(\lbrack l, r), v, \lbrack a, b))$$)

入力: 葉の区間$$\lbrack l, r)$$, 現在見ている頂点$$v$$, 現在見ている頂点に割り当てられている区間 $$\lbrack a, b)$$

If $$r\leq a\lor b\leq l$$:

Return $$e$$

Else If $$a\leq l\land r\leq b$$:

Return $$v.value$$

End If

$$t_a\leftarrow vertex\_query\left(\lbrack l, r), v.left, \left\lbrack l, \frac{l + r}{2}\right)\right)$$

$$t_b\leftarrow vertex\_query\left(\lbrack l, r), v.right, \left\lbrack \frac{l + r}{2}, r\right)\right)$$

Return $$f(t_a.value, t_b.value)$$

計算量: $$O(\log N)$$

ある頂点$$v$$よりも下にある頂点から, $$\lbrack l, r)$$とオーバーラップしている部分の演算値を計算する.

6行目の計算は$$\mathcal{M}$$のAssociativityにより正しく計算することができることが保証される.

Conclusion

Segment Treeとは各頂点に区間を割り当てられた完全二分木である. その上にはMonoidによる演算を乗せることができ, その構造をうまく使うことで点代入・区間クエリを$$O(\log N)$$で処理することができる.

References

Jon Louis Ventley and Derick Wood. 1980. An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles.

秋葉 拓哉. 2010. プログラミングコンテストでのデータ構造.

セグメント木の上に乗る構造はモノイドではなく圏である - うさぎ小屋

遅延伝搬segment木についてもっと詳しく - うさぎ小屋

Segment木の種類とその要件 - うさぎ小屋

双対セグメント木という概念について - うさぎ小屋

完全二分木への添字付けであってセグメント木ではないものを考える - うさぎ小屋

/segment tree - wiki.kimiyuki.net

セグメント木について - beet's soil

遅延伝播セグメント木について (旧: 遅延評価セグメント木について) - beet's soil

秋葉 拓哉, 岩田 陽一, and 北川 宜稔. 2010. プログラミングコンテストチャレンジブック

Bowen Yu. 2016. The Art of Divide-And-Conquer

Nabil Ibtehaz, M. Kaykobad, and M. Sohel Rahman. 2018. Multidimensional segment trees can do range queriesand updates in logarithmic time

Pushkar Mishra. 2016. A New Algorithm for Updating and QueryingSub-arrays of Multidimensional Arrays

一般の$$N$$についても$$N\leq 2^k$$なる$$k$$を探し, 余った領域はIdentity Elementで埋めることでこの場合に帰着できる. ↩︎

[7]では添字が本質的という仮定を置いているが, それと自分の主張である「各頂点に割り当てられる区間が本質的」という主張は同値. これは, 添字割当の結果と区間割当の結果がそれぞれ一対一に対応するためである. ↩︎

[shiho-elliptic]

Facebook CTF 2019 Writeup

binjaとして参加した. 結果は9位 13687ptsで, うち974pts 1問を解いた.

↓↓↓ Writeup ↓↓↓

netscream (crypto)

バイナリファイルと暗号文, そして「a mysterious constant associated with this encryption scheme」と題された謎の定数$$d$$が渡される. バイナリファイルはELF形式で, アーキテクチャもx86_64だったのでIDA Pro Freeで解析することにした. Reversingはあんまりやらないので, メモ代わりに解析した流れを以下に記す.

このバイナリファイルは大体以下の様な流れで動いている:

引数チェック (0x400ec9)

楕円曲線の初期化 (0x4010d6)

引数から暗号化対象ファイルを読み込み (0x400f0c)

IV = EC_PRNG() (0x400fa4)

key = EC_PRNG() (0x400fb0)

keyをファイルkeyへと書き出し (0x400fbc)

ファイルencを開き, 最初にIVを書き出し (0x400ff8)

3で読み込んだ暗号文に対してAES-256-IGE1による暗号化処理を行い, 結果をファイルencに追記する (0x401040)

楕円曲線の初期化は以下の通り. デコンパイルは勉強も兼ねて手でやっているので, 意訳的になっている箇所がある可能性がある.

https://gist.github.com/elliptic-shiho/9be5a5949393edbe53cf38feb1c1980d

PRNG部分については自力でデコンパイルするには悩みどころが多かったため, チームの人にデコンパイルをお願いした. Ghidraでできるよとの教示と共にやってもらったGhidraのデコンパイル結果をもとに構築した乱数生成器が以下である:

https://gist.github.com/elliptic-shiho/6551b2b4c3f5f1847aa42f89a768f2a5

これを用いれば, IV, keyの生成は

https://gist.github.com/elliptic-shiho/aa5e5cba95ca51ef82740b08dec0a130

と書ける.

これを定式化しよう. 楕円曲線を$$E$$とし, その生成元を$$G$$とする. すると, 以下の漸化式により各$$X _ i$$が与えられる. ただし, $$M _ 0$$はシード値である.

$$$ \begin{aligned} M _ i &= x(M _ {i - 1} G)\cr X _ i &= x(M _ i Q) \end{aligned} $$$

そして, この$$X _ i$$を整形したものがPRNGの1回分の出力となる. これは「0xf0ビット以上であれば, 上位2バイトを削る」「残り必要なバイト数$$n$$が$$n\lt\text{0x1e}$$を満たすときは適当に右シフトを行い, 上位$$n$$バイトを取り出して用いる」という2点に要約され, 上記スクリプトはこの通りの処理を行っていることが理解できると思う.

さて, 与えられた$$d$$についていくらかの実験を行った結果, $$G = dQ$$であることがわかった. これを用いると, ある時点の乱数値からそれ以降の乱数値をすべて予測することができる. $$E$$の上の点で$$X _ i$$を$$x$$座標に持つような点の$$y$$座標はPari/GPのellordinate関数を用いたり, 適当な平方剰余をとることで簡単に計算できる. この$$y$$座標を$$Y _ i$$, これにより決まる点を$$P _ i = (X _ i, Y _ i)$$とすると,

$$$ \begin{aligned} d P_i &= d(M _ i Q)\cr &= M _ i (dQ)\cr &= M _ i G \end{aligned} $$$

なので, $$M _ {i+1} = x(d P _ i$$により$$M _ {i+1}$$が得られる. 一旦$$M _ i$$が得られれば, $$G$$, $$Q$$共にわかっているためこの先の$$M _ {i+1}$$, $$M _ {i+2}$$, ...はすべて計算可能である. 特に, この問題ではIVがこの方法で生成された後にkeyが生成されているから, ファイルencに含まれているIVをもとに内部状態を復元し, keyを生成して復号すればよいということがわかる.

しかし, IVは上で見たとおり$$X _ i$$そのままを含んでいるわけではなく, 32バイトのうち上位2バイトは削られている. このため, この部分は不明として総当りする. 正しい値を選べたかどうかは, 実際に$$M _ {i+1}$$から$$X _ {i+1}$$を生成し, IVの残り2バイトと一致するかどうかを見ればよい.

以上を実装したスクリプトが以下である:

https://gist.github.com/elliptic-shiho/b1f7dc33efbf7d0366ea770bde2a31f6

PythonでAES-256-IGEを復号するためのスクリプトを探すのが面倒だったので, OpenSSLを用いて復号するコードを別途書いた.

https://gist.github.com/elliptic-shiho/2fa2f2d68dc06ff78e5e524f2706b0aa

Flag: fb{dual_ec_is_not_a_good_prng_}

感想

Reversing問題だった. Cryptoとしては簡単目. PPPが一瞬で解いていたのはそういうことだと思う. それにしても早すぎませんか?

https://mgp25.com/AESIGE/ ↩︎

[shiho-elliptic]

PlaidCTF 2019 Writeup

I played as binja. I solved two challenges and one was solved after the competition.

R u SAd? (crypto)

In this challenge, we have a public key of RSA $$(e, n = pq)$$, encrypted flag $$c$$, $$i_q = q^{-1}\mod p$$, and $$i_p = p^{-1}\mod q$$.

$$i_p$$(resp. $$i_q$$) is an inverse element of $$q$$(resp. $$p$$) in $$\mathrm{mod}\ q$$(resp. $$\mathrm{mod}\ p$$). i.e.

$$$ \begin{aligned} pi_p &\equiv 1\pmod q\cr qi_q &\equiv 1\pmod p \end{aligned} $$$

There exists $$k_1, k_2\in\mathbb{Z}$$ such that satisfy following equations:

$$$ \begin{aligned} pi_p &= 1 + k_1q\cr qi_q &= 1 + k_2p\cr \end{aligned} $$$

Multiply these equations:

$$$ \begin{aligned} (pi_p)(qi_q) &= (1 + k_1q)(1 + k_2p)\cr &= k_1k_2n + k_1q + k_2p + 1 \end{aligned} $$$

Divide by n (in integer):

$$$ i_pi_q = k_1k_2 + \left\lfloor\frac{k_1}{p}\right\rfloor + \left\lfloor\frac{k_2}{q}\right\rfloor + \left\lfloor\frac{1}{n}\right\rfloor $$$

Since $$0\lt\left\lfloor\frac{1}{n}\right\rfloor\lt 1$$, we negligible it. $$k_1$$ and $$k_2$$ is smaller than $$n$$ trivially, so we know $$\left\lfloor\frac{k_1}{p}\right\rfloor$$ and $$\left\lfloor\frac{k_2}{q}\right\rfloor$$ is very small integers.

From these facts, we know there exists sufficiently small positive integer $$\varepsilon$$, such that $$i_pi_q - \varepsilon = k_1k_2$$. Actually, $$\varepsilon = 1$$ in this challenge (I checked by experiment).

Now, we have $$k_1k_2$$. since $$i_pi_qn = k_1k_2n + k_1q + k_2p + 1$$ and $$k_1q + k_2p = i_pi_qn - k_1k_2n - 1$$. Thus, we get $$k_1q$$ and $$k_2p$$ by solve quadratic equation $$x^2 - (k_1q + k_2p)x + (k_1q)(k_2p) = 0$$ using $$k_1k_2n = (k_1q)(k_2p)$$ and $$k_1q + k_2p$$.

We got $$k_1q$$ and $$k_2p$$. so we can compute $$p$$, $$q$$ by $$p = \gcd(n, k_2p)$$, $$q = n / p$$, and decrypt the ciphertext.

https://gist.github.com/elliptic-shiho/d78f4a3c7e4fe452f05dc2971dc19eab

horst (crypto, solved after the competition)

In this challenge, we have a permutation-based cryptosystem, two randomly generated plaintexts, and two ciphertexts corresponding to that.

At first, we formulate this cryptosystem. we denote the Symmetric Group $$S _ {64}$$ by $$\mathcal{S}$$, and let $$\mathcal{M} := \mathcal{S}\times\mathcal{S}$$.

Next, we denote the key of this cryptosystem by $$k\in\mathcal{S}$$, plaintext $$p_i\in\mathcal{M}$$, and ciphertext $$c_i\in\mathcal{M}$$ where $$i = 1, 2$$.

The round function $$R$$ and inverse that is defined by below:

$$$ \begin{aligned} R: \mathcal{M}\ni (x, y) \mapsto (y, kyk^{-1}x)\in\mathcal{M}\cr R^{-1}: \mathcal{M}\ni (x, y)\mapsto (kxk^{-1}y, x)\in\mathcal{M} \end{aligned} $$$

(Note: This writeup used right-to-left composition but the challenge's Permutation class used left-to-right that. e.g. $$kyk^{-1}x$$ is equivalent to x * k.inv() * y * k.)

We denote $$n$$-th iterated map of $$f$$: $$f\circ f\circ \cdots(n\mathrm{\ times\ repeat})\cdots \circ f$$ by $$f^{n}$$ and define the encrypt function as follows:

$$$ \mathrm{Enc}: \mathcal{M}\ni m \mapsto R^3(m)\in\mathcal{M}, $$$

and the decrypt function as follows:

$$$ \mathrm{Dec}: \mathcal{M}\ni c \mapsto (R^{-1})^3({c})\in\mathcal{M}. $$$

Our target is $$k$$, but we have only $$p_i$$ and $$c_i$$.

For convenience, let $$p_i = (x_i, y_i)$$ and $$c_i = (r_i, s_i)$$. By definition of $$\mathrm{Enc}$$, we got following equations:

$$$ \begin{aligned} r_i &= k^2y_ik^{-1}x_ik^{-1}y_i,\cr s_i &= k^3y_ik^{-1}x_ik^{-1}y_i^2k^{-1}x_i. \end{aligned} $$$

Now, we define $$X_i := r_iy_i^{-1}$$ and $$Y_i := s_ix_i^{-1}$$. Then, $$kX_ik^{-1} = Y_i$$ from definition. so let us solve the challenge by this fact.

To solve that, we need following three propositions:

Proposition 1 (decompose to relatively prime cyclic permutation). Let $$\alpha$$ be a permutation with $$n$$ elements. Then there exists an positive integer $$\ell$$ and relatively prime cyclic permutations $$\sigma_1, \sigma_2, \ldots, \sigma_{\ell}\in S_n$$ such that $$\alpha = \sigma_\ell\cdots\sigma_2\sigma_1$$.

Proposition 2. Let $$\alpha, \beta, \gamma$$ be a permutation with $$n$$ elements. Suppose that

$$\beta$$ can represented by cyclic notation: $$\beta = (i_1\ i_2\ \cdots\ i_k)$$

$$\alpha = \gamma\beta\gamma^{-1}$$

Then $$\alpha = (\gamma(i_1)\ \gamma(i_2)\ \cdots \gamma(i_k))$$ holds.

Proposition 3. Let $$\alpha, \beta, \gamma$$ be a permutation with $$n$$ elements. If $$\alpha = \gamma\beta\gamma^{-1}$$ then $$T(\alpha) = T(\beta)$$ where $$T(\alpha)$$ is cyclic type of $$\alpha$$.

From these propositions, we can solve conjugate equation $$Y_i = kX_ik^{-1}$$ by following procedure:

By Prop. 1, Decompose to relatively prime cyclic permuation: $$X_i = \sigma_\ell\cdots\sigma_1$$ and $$Y_i = \tau_m\cdots\tau_1$$.

By Prop. 3, $$m = \ell$$. Since following formula, there exists 1-to-1 map between $$\sigma_t$$ and $$\tau_t$$: $$$ \begin{aligned} Y_i &= kX_ik^{-1} = k(\sigma_\ell\cdots\sigma_1)k^{-1} = (k\sigma_\ell k^{-1})\cdots(k\sigma_1 k^{-1})\cr &= \tau_\ell\cdots\tau_1 \end{aligned} $$$ For simple, we assume the straight mapping: $$k\sigma_tk^{-1} = \tau_t$$ for $$t = 1, \ldots, \ell$$.

By Prop. 2, the 1-to-1 map between $$\sigma_t$$ and $$\tau_t$$ is $$k$$. i.e. if $$\sigma_t = (j_1\ j_2\ \cdots\ j_s)$$ then $$\tau_t = (k(j_1)\ k(j_2)\ \cdots\ k(j_s))$$. so $$k$$ can reconstruct by collect pairs $$(j_t, k(j_t))$$.

After this procedure, we have the key $$k$$. That's all.

It is a note of the implementation:

In the above procedure, we assume the straight mapping but actual mapping is not straight. so we need to brute-force a mapping of decomposed cycle permutations of $$X$$ that and $$Y$$ that.

Even if we selected correct mapping, we don't have information about how corresponding $$Y_i$$ to $$k(j_t)$$. so we have to brute-force all possibility.

~ ↑ in the competition period ~

~ ↓ after the period ~

I bugged code. that's all...

https://gist.github.com/elliptic-shiho/a089e540f8cbc6100b88342e54a414c5

[shiho-elliptic]

CyberRebeat CTF Writeup

scryptosで参加しました. 全完して同率1位, AC時のポイント積算で5126pt分を取りました. 解いた全問題のWriteupです.

↓↓↓ Writeup ↓↓↓

Rotation (Crypto)

Caeser暗号. テーブルエスパーと鍵エスパー.

https://gist.github.com/elliptic-shiho/e305016bcb95b2e5136c718a2878d7d5

Flag: CRCTF{WEAREHACKERS}

FLAG.encrypted (Crypto)

公開鍵見たらわかった.

https://gist.github.com/elliptic-shiho/d513a368e3041e0808f70f0ac0569401

Flag: CRCTF{On that day, there was definitely something behind Warlock's disappearance.}

Secret.pdf (Stegano)

Ctrl+A Ctrl+Cで FLAG is CRCTF{I don't know of a time without the internet} が得られる. Flag: CRCTF{I don't know of a time without the internet}

Alpha (Stegano)

内製ツールでヒストグラムを見てるとAlphaの値が252, 253のいずれかなことに気づいたのでそれで場合分けをした.

https://gist.github.com/elliptic-shiho/661341cab0acc020dc338895f110ae9a

Readme (Misc)

Square Word Calligraphy的な感じ. 遠目に見ると読める.

CAN YOU READ JAPANESE? IF SO, THIS QUESTION MAY BE DIFFICULT. CRCTF{YOUCANPLAYCYBERREBEATINBOTHLANGUAGES}

Flag: CRCTF{YOUCANPLAYCYBERREBEATINBOTHLANGUAGES}

Opening Movie (Misc)

FirefoxでNetworkタブを眺めるとDLL取ってきてるのがわかる. monoのwasmとかは無視してもいい. DLLをデコンパイルするとMoviePlayer.Pages.Indexにreturn this.encrypt ("FLAG_IS_HERE") + ".txt";とある. encryptメソッドの中身はmd5だったのでmd5("FLAG_IS_HERE") + ".txt"なのでそれにアクセスしておわり

Flag: CRCTF{to the twilight of the internet}

Monero (Trivia)

知らない人はセキュリティ関連のニュースを継続的に読むといいです.

Flag: CRCTF{coinhive}

Prime factor (Programming)

謎問. 与えられた$$n = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$$に対して$$\max(p_1, p_2, \ldots, p_k)$$を答える問題.

https://gist.github.com/elliptic-shiho/5095fb8b7fe40e9896b3d28ad0ad4246

Flag: CRCTF{I'm a calculating type by nature.}

Uploader (Web)

URLからしてSQLi. File name欄に適当に'||'とか入れるとわかる.

どうせsqliteだろうとsqlite_masterのsqlカラムを読むようなのを投げるとビンゴ. 後は ' and 1=2 union select id,file_name,1,1 from Files union select 1,userid,password,1 from Users;--で全データ取ってくるとsecret.zipがあることがわかる. ただしこのzipの中にあるフラグファイルにはパスワードが設定されていてそのままでは開けない. 同時に判明するcredential harada:seishin0129 を使ってログインするとsecret.zipのパスワードもわかる.

Flag: CRCTF{Today's_internet_is_full_of_concerning_vulnerabilities}

ChangeHistory (Recon)

@_N4NU_がIssueを見つけてくれていた. githubにpushされたオブジェクトはローカルで歴史改変をしてpush -fをしたところで消されるわけではないので無理矢理該当コミットを見ればOK.

https://github.com/ennach/ChangeHistory/commit/c476614bc439fe1910e494422b3aa207b776d486

Flag: CRCTF{the timer is set to 120 seconds}

Last 5 boxes (Stegano)

mp4のコンテナの構造を010 editorで読むと最後の方にPNGが入っていることがわかるのでこれを抽出するだけ. box構造については http://matsu623a.blogspot.com/2013/12/mpeg4boxatom.html を参考.

https://gist.github.com/elliptic-shiho/55a304ac903d4f77150e1c6b1d25ef26

Flag: CRCTF{Ever since we were born, we've had the net}

Signature (Crypto)

Hash length extension典型. 少しweb要素があって, parse_str関数を通すとnull文字が消えるのでそのまま流しこむだけだとnull terminationが効いてどうしようもなくなる. parse_strはパーセントエンコーディングを解釈するので, もう一段階エンコードすればよい.

https://gist.github.com/elliptic-shiho/c5da6bbe1ca7fc54e009c2f5be373e77

Flag: CRCTF{Two years ago, August 31st.}

感想

確かHarekazeの次に全完した. 大体Signatureでparse_strに翻弄されていたのが問題. どれもFirst Solveは取れなかったが解けたのでよかった. 速度は今後の課題. 初級者・中級者向けで国内開催のCTFとしては面白い問題が多かった.

[shiho-elliptic]

ASIS CTF Quals 2018 Writeup

scryptosで参加しました. 結果は1600pt, 20位でした.

↓↓↓ Writeup ↓↓↓

Uncle Sam (Crypto, 123pts)

First Solve. 画像ファイルは適当に https://www.onlineocr.net/ でOCR. Schmidt-Samoa暗号の$$n = p^2q$$, $$d = n^{-1}\mod (p-1)(q-1)$$と暗号文$$c$$が与えられる.

Schmidt-Samoa暗号では秘密鍵として$$pq$$が必要だが, ここでは与えられていない. Schmidt-Samoa暗号の代数的構造について考察すると$$2\ne 2^{nd}\mod n$$かつ$$0\le k\lt p$$が存在して$$2^{nd}\mod n = 2 + kpq$$という形になることがわかる. 後は$$n$$とgcdを取ってやればよい.

https://gist.github.com/elliptic-shiho/db47d80d78de8fb068eb76dd6ed233d2

Flag: ASIS{Y0u_c4N_m4n493_Schmidt_5am0A_CryP7o_SysT3M!!}

OPEC (Crypto, 202pts)

Second Solve. Okamoto-Uchiyama暗号.

$$n = p^2q$$で定義されているところが$$q = p$$になっていたため容易に素因数分解できてしまう. 後は適当に復号すればよい.

https://gist.github.com/elliptic-shiho/d31f87d374e0bd3758d1f32a840557d8

https://gist.github.com/elliptic-shiho/b5e5fb6f461532c669dd2fff19340acf

Flag: ASIS{OPEC_IZ_EP0C_L1k3_Effic1ent_Probabilis7ic_Public-K3y_3ncryption_with_S4me_Prim3s!!!}

[solved after the competition] Iran (Crypto, 237pts)

解けていないが終わった後解けた. 2パートに分かれているRSA暗号.

Iran.pyでは事前に計算された$$p, q, r, s$$からRSA鍵を2つ生成し, フラグを前半後半で分けて暗号化している. $$p, q, r, s$$はそれぞれ素数で$$e = 65537$$に固定されており, 追加で以下の4つの制約が存在する.

$$$ \begin{aligned} p-1&\equiv 0\pmod r\cr q-1&\equiv 0\pmod s\cr r^3-1&\equiv 0\pmod p\cr s^3-1&\equiv 0\pmod q \end{aligned} $$$

RSA鍵の一つ目は$$p_1 = r+s+t_0$$, $$q_1 = 4(r+s) + t_1$$の形で素数を計算していて, その積が$$n_1$$になっている. これは展開すると$$n_1 = 4(r+s)^2 + (4t_0 + t_1)(r+s) + t_0t_1$$になり, $$t_0, t_1$$を総当りしてこの二次方程式を解けば$$r+s$$の候補, そして$$n_1$$の素因数分解がわかる. ここまででフラグの前半が出る.

もうひとつのRSA鍵は$$p, q$$をそのまま用いている. なので前述の関係式からそれらを導出する必要がある. 現在手に入っているのは$$r+s$$, しかも正確な値ではなく候補というだけのもの.

まず$$r+s$$の候補について考える. 生成にはnext_prime関数が用いられているので, 少なくとも$$p_0 = r+s+t_0$$の$$t_0$$は$$p_0$$の前の素数から$$p_0$$までの間しか動かない. 同様に$$q_0$$についても$$t_1$$は素数と素数の間でしか動くことはない. なのでその間の数全てをとりあえず候補とすればよい. ここでどのようにして$$r+s$$(の候補)から$$r, s$$を導出するかだが, ここで関係式を用いる.

ここまでは大会中に考えた. 以下は大会後にIRCで出ていたヒントを元に解いたログである.

上記関係式のうち$$p-1\equiv 0\pmod r$$と$$r^3 - 1\equiv 0\pmod p$$に注目する. 適当な非零変数$$a, b$$を用意して$$p-1 = ar$$, $$r^3 - 1 = bp$$と書きなおし, これを$$p$$について解くと$$p = ar + 1$$, $$\displaystyle p = \frac{r^3-1}{b}$$となり, ここから恒等式$$b(ar+1) = r^3-1$$が得られる. 右辺を因数分解すると$$(r-1)(r^2+r+1)$$となり, 係数比較から$$b = r-1$$, $$a = r+1$$がわかる. このことから$$p = r^2 + r + 1$$と表すことができ, $$q = s^2 + s + 1$$も同様に示すことができる.

さて, 公開鍵$$pq = (r^2+r+1)(s^2+s+1)$$と$$r+s$$(の候補)が手元にある. これを用いて$$rs$$を導出しよう. まず, $$pq - ((r+s)^2 + (r+s) + 1) = rs(rs+(r+s)+1)$$より二次方程式$$x^2 + (r+s+1)x - k = 0$$が立てられる. ただし$$k = pq - ((r+s)^2 + (r+s) + 1)$$. この方程式の解のうち正のものは$$rs$$に等しい. これを用いて$$x^2 - (r+s)x + rs = 0$$, すなわち$$(x-r)(x-s) = 0$$を再度解くことにより$$r, s$$が手に入る. 後は関係式より$$\gcd(r^3 - 1, pq)$$を計算するなり, $$r^2+r+1$$を計算するなりで$$p$$, $$q$$を手に入れればよい.

https://gist.github.com/elliptic-shiho/e553e08eb4654d4de1b8d39c569a70c3

Flag: ASIS{0240093faf9ce4d7be86d87d49a95cf7}

感想

Iranは普通に脳死していた. これぐらいは解けておきたい. Okamoto-Uchiyama暗号好きだなあ. 日本勢の中では2位だったということで喜んでおく. Ebolaはcommon primeではないのだろうか? 1600個ほど集めたがうまくいかなかった.

[shiho-elliptic]

My authored challenges at CODE BLUE CTF 2017

Introduction

This post is for CTF Advent Calendar 2017. The previous post is DEF CON CTF Qualifier 2017 Pepperidge Farm Write-up by @ntddk.

I authored five challenges for CODE BLUE CTF 2017. In this article, I explain these challenges.

Common Modulus series

In these challenges, I focused on the Common Modulus Attack. The first challenge is a simple common modulus attack, but the second and third challenge has additional constraints.

Common Modulus 1

In this challenge, we have below python code and transcript:

https://gist.github.com/elliptic-shiho/a90ceb18f2adb4cbaae673acb755957f

This can be solved with the simple common modulus attack (more details: see [2, p.4]), because e1 and e2 are relatively prime.

https://gist.github.com/elliptic-shiho/d61618de0bd5077585b7e6422184bcad

Common Modulus 2

In this challenge, we have a script and transcript similar to Common Modulus 1 but with a slight difference: e1 and e2 share a common factor 3. Thus this is not solvable using Common Modulus Attack Solver.

https://gist.github.com/elliptic-shiho/8ef1a8f528c466a569e58eb3ca71c48e

We know the flag format from the flag of Common Modulus 1 (Concretely, FLAG = "CBCTF{" + some md5 + "}"). So we have $$FLAG \approx 2^{311}$$ and $$FLAG^{3}\approx 2^{933}$$. From this fact, we have $$FLAG^{3} \lt N$$ where $$N$$ is modulus.

In the (simple) Common Modulus Attack, It uses the following fact: $$e_{1}$$ and $$e_{2}$$ are relatively prime $$\iff$$ There exists $$a$$, $$b$$ such that $$ae_{1} + be_{2} = 1$$. If $$e_{1}$$ and $$e_{2}$$ are not relatively prime (i.e. $$e_{1}$$ and $$e_{2}$$ share a common factor which is not 1) then this fact extended as follows: $$e_{1}$$ and $$e_{2}$$ share a common factor $$g$$ $$\iff$$ There exists $$a$$, $$b$$ such that $$ae_{1} + be_{2} = g$$.

Using this fact, we can obtain the $$FLAG^{3}$$ from given public keys and ciphertexts. Moreover, we know $$FLAG^{3}\lt N$$ therefore we can obtain the $$FLAG$$ by computing integer cubic root.

https://gist.github.com/elliptic-shiho/2747f45c8ae13c496fe683256f0056a1

Common Modulus 3

In this challenge, we have a script and transcript similar to Common Modulus 1 and 2 but with more differences: e1 and e2 share a common factor 17 and the message is padded.

https://gist.github.com/elliptic-shiho/0f1cb48544a9136ad2fa578fda67702e

Following similar discussion as Common Modulus 2, We have $$FLAG^{17}$$. However due to padding property, we have $$FLAG^{17} \gt N$$ so we can't use 17-th root method for solve it.

Intended Solution

By the way, we have a useful tool: Coppersmith's Method. It can solve modular equations which have small roots. Formally, Coppersmith's Method (for the univariate case) can be represented below:

Theorem 1 (Coppersmith, [1]): Let $$N$$ be an integer of unknown factorization, which has a divisor $$b\geq N^{\beta}$$, $$0\lt\beta\leq 1$$. Let $$f(x)$$ be a univariate monic polynomial of degree $$\delta$$. Then we can find all solutions $$x_{0}$$ for the equation $$$ f(x) = 0\mod {b}\quad with\quad |x_{0}|\leq cN^{\frac{\beta^{2}}{\delta}} $$$ in time $$\mathcal{O}(c\delta^{5}\log^{9} N)$$.

Let us consider applying Coppersmith's Method. In this case, $$f(x) = (pad\cdot x)^{17} - FLAG^{17}$$, $$\beta = 1$$, $$\delta = 17$$, and $$c = 1$$ then we have $$|x_{0}| \leq N^{\frac{1}{17}}$$ (Remark: $$pad$$ is computable).

Let $$FLAG'$$ be an unpadded $$FLAG$$. Then we're able to write root of polynomial $$f(x)$$ as $$x_{0} = FLAG'$$. From $$FLAG'\approx 2^{311}$$, we need to check $$2^{311} \leq N^{\frac{1}{17}}$$.

By reading problem code carefully, we know $$N\approx 2^{8192}$$ and we can calculate $$\lfloor 8192/17\rfloor = 481$$. Therefore, we can use Coppersmith's Method in this challenge!

In my solver, I considered to make polynomial which has more small solution using the flag format. So that uses different polynomial.

https://gist.github.com/elliptic-shiho/356013b73834304752a53ce6034645a9

Unintended Solution

After the competition, I noticed an unintended solution by reply from some players...

In Intended Solution, we use fact: $$pad$$ is computable. However, In this challenge, the form of padding is like $$pad\cdot x$$. Due to the homomorphic property of RSA, We can compute $$\left(FLAG\cdot pad^{-1}\right)^{17}\mod N$$. Moreover, (From I was enlarged $$N$$) $$FLAG'^{17} \lt N$$. So this challenge can be solved with the 17-th root method. (If you need more details, see ymgve's writeup: https://github.com/ymgve/ctf-writeups/tree/master/codeblue2017/crypto-common_modulus )

Paillier Oracle

In this challenge, we have a decryption oracle of Paillier Cryptosystem [3], but it only returns the Least Significant Bit (LSB).

https://gist.github.com/elliptic-shiho/29dbb542786d6db76adf8b053e756d49

Recall that, Paillier Cryptosystem is homomorphic for addition. We use the following lemma:

Lemma 1: Let $$c$$ be a ciphertext of $$ m $$, encrypted by Paillier Cryptosystem $$(N, g)$$, and $$k$$ be an integer. Then, we can compute $$c' = Enc(m')$$ where $$m' \equiv k\cdot m\pmod{N}$$.

Proof: Due to the homomorphic property, $$Enc(\underbrace{m + m + \cdots + m}_{k\mathrm{\ times\ repeat}})\equiv \underbrace{Enc(m)Enc(m)\cdots Enc(m)}_{k\mathrm{\ times\ repeat}} \equiv c^{k}\pmod{N^{2}}$$. That's all.

Let us construct an algorithm that decrypts any message $$ m $$ using decryption oracle which only returns LSB.

First, Check LSB of $$ m $$.

Second, Set $$c'$$ If LSB of $$ m $$ is 1 then $$ c' \leftarrow c\cdot Enc(-1)$$ ($$\iff Enc(m - 1)$$) else $$c' \leftarrow c$$.

Next, $$c' \leftarrow c'^{2^{-1}\pmod{N^{2}}}$$. From Lemma 1, This is equivalent to divide corresponding plaintext by two.

Then, we obtain LSB of $$c'$$ using decryption oracle. Actually, obtained LSB is second-bit of message, because Second/Third operation is effectively equivalent to bit shifting!

So repeat Second and Third operation, we can get an any bit of plaintext. These operations construct an algorithm to decrypt any message $$ m $$ using decryption oracle which returns only LSB!

https://gist.github.com/elliptic-shiho/914acc71cd2bdd3c769cd1a3f518fa5a

Note

In TokyoWesterns CTF 2017, there was a challenge named BabyPinhole. This challenge summary is "We have decryption oracle of Paillier Cryptosystem, which returns only middle-bit. Decrypt encrypted flag!". Yes, This is a watered down version of the Paillier Oracle. I created this challenge at 2016, but they got ahead of me...

In addition, this discussion only used additive homomorphic property. Therefore we can apply the same attack to arbitrary additive homomorphic cryptosystem. In other words, In additive homomorphic cryptosystem, The Hardcore-bits is any bit of plaintext.

By the way, I construct this algorithm myself, but This method was already exists as paper [4]...

Smoke on the water

In this challenge, We have a script and transcript as follows:

https://gist.github.com/elliptic-shiho/bf9d4660b1dbb84dfad01d8775fdd95a

Most RSA challenges are solved with the Small Private Exponent Attack (e.g. Wiener's Attack, Boneh-Durfee's Attack, etc..). However, in this challenge, we know $$d$$ is very large. From given script, the private exponent was generated by $$d = \phi(N) - d'$$ where $$d'$$ be small integer (i.e. $$d'\leq N^{0.2}$$). In Wiener's Attack, that solve $$ed - 1\equiv 0\pmod {\phi(N)}$$ for private exponent, when $$d$$ is sufficiently small. In other words, we have a tool to solve an equation similar to the RSA equation.

We consider the "Large" private exponent attack, using small exponent attack (In my consideration, I used Wiener's Attack).

Using $$d = \phi(N) - d'$$, we transform $$ed \equiv 1\pmod {\phi(N)}$$ to $$e(\phi(N) - d') \equiv 1\pmod {\phi(N)}$$ $$\iff$$ $$ed' \equiv -1\pmod {\phi(N)}$$. If $$d'$$ is sufficiently small, This equation can solve by small private exponent attack for $$ed + 1 \equiv 0\pmod {\phi(N)}$$.

Suppose we can obtain $$d'$$. $$d'$$ satisfy $$ed'\equiv -1 \pmod {\phi(N)}$$, and we can confirm $$(m^{e})^{-d'}\equiv m\pmod {\phi(N)}$$ easily.

https://gist.github.com/elliptic-shiho/6bae1509af163012e8c497ad6db243dd

Final Words

Except Smoke on the water, all challenges were created at 2015 ~ 2016 but I think these challenges review were insufficiently and too easy...

In Paillier Oracle, we apologize for too slow server response... I didn't think of Network speed problem.

Anyway, I appreciate to crypto players, and thanks for all participants!

Acknowledgements

@mt_caret pointed out some English mistakes. Thanks!

References

[1] Alexander May. 2009. Using LLL-Reduction for Solving RSA and Factorization Problems: A Survey

[2] Dan Boneh. 1998. Twenty years of attacks on the RSA cryptosystem

[3] Pascal Paillier. 1999. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes

[4] Dario Catalano, Rosario Gennaro, and Nick Howgrave-Graham. 2001. The Bit Security of Paillier’s Encryption Scheme and Its Applications

[shiho-elliptic]

ASIS CTF Finals 2017 Writeup

scryptosで参加しました. 結果は8位, 3099pt (うち825ptを入れた)でした.

↓↓↓ Writeup ↓↓↓

Gracias (Crypto 287pts)

Multi-Prime RSAの問題. $$p$$, $$q$$, $$r$$を素数とし, $$n = pqr$$, $$\phi(n) = (p-1)(q-1)(r-1)$$とする. $$d\approx 2^{256}$$を選び, $$e \equiv d^{-1}\pmod{\phi(n)}$$を計算する.

明らかに$$d$$は$$n$$に比べて小さい. $$\log_2 n\approx 1536$$, $$\log_2 d\approx 256$$より$$d \approx n^{0.167}$$. これはRSAにおいて知られているBoneh-Durfee's Attack [2] ($$d\lt n^{0.292}$$)やWiener's Attack [1] ($$d\lt n^{0.25}$$)に比べても小さい.

次に, $$\phi(n)$$ と $$e$$ , $$d$$ について考える. このとき, ある $$k\in\mathbb{Z}$$ が存在して, 以下の式が成立する:

$$$ \begin{aligned} ed &\equiv 1\pmod{\phi(n)}\newline ed &= 1 + k\phi(n)\newline &= 1 + k(n - 1 - (pq+pr+qr)+p+q+r).\newline \end{aligned} $$$

ここで $$A = n-1$$, $$s = -(pq+pr+qr)+p+q+r$$とおくと,

$$$ 1 + k(A + s) \equiv0\pmod e $$$

がわかる. この式はBoneh-Durfee's Attackにおいて用いられる式と同じであり, 異なる点は$$s$$の上界といくつかの符号程度である. よって, この方程式を解くためにBoneh-Durfee's Attackのソルバを利用できると考えられる. $$(x, y) = (k, s)$$とおくと$$|x|\leq n^{0.167}$$, $$|y|\leq n^{2/3}$$であるため, 条件的にもBoneh-Durfeeの手法は十分適用可能である.

今回はDavid Wong氏による実装 (https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage)を参考に少し改変を加えた.

https://gist.github.com/elliptic-shiho/4fb0739bfc7ba4b711c5d3afebca9346

Flag: ASIS{Wiener_at7ack_iN_mUlt1_Prim3_RSA_iZ_f34sible_t0O!}

Hash Collision (Crypto 171pts)

ハッシュ関数が渡され, これを衝突させればフラグが貰える. メッセージは必ず / でパディングされ, 数回文字列自体を繰り返し利用するために一見衝突は不可能に見える.

しかし, パディングが予測可能なので a と a/ で衝突させられる. 原理的にはBoston Key Party CTF 2016 ltseorg ( https://github.com/smokeleeteveryday/CTF_WRITEUPS/tree/master/2016/BKPCTF/crypto/ltseorg )と同じ原理.

Flag: ASIS{ce8a30c725bdc9fea1da21102fdb480f}

Interested Message (Crypto 367pts)

HIME(R)暗号という暗号で暗号化されたメッセージと公開鍵, SECRETが渡される (当初SECRETは総当りかと考えていたが, いつの間にか公開されていた). $$n = p^2q$$は合成数だが, ASIS CTFで出る合成数で説明がないときにはまず $$|p - q|$$ が小さいことを疑ってかかるべきなのでこれを疑うと素因数分解ができた. 後は論文[3]に沿って解読処理をコーディングするだけ.

https://gist.github.com/elliptic-shiho/e44f1eb7065e8331fd61d80d66d133ce

Flag: ASIS{Highly_Interested_Message_Encryption_System_IS_HIME!!!}

感想

Sofies Verden, marijuanaを解きたかった.

References

[1] M.Wiener. 1990. Cryptanalysis of short RSA secret exponents. [2] D.Boneh and G.Durfee. 1999. Cryptanalysis of RSA with Private Key $$d$$ Less Than $$N^{0.292}$$. [3] Hitachi, Ltd. 2001. Specification of HIME(R) CryptoSystem

[shiho-elliptic]

ASIS CTF Quals 2017 Writeup

scryptosで参加していました. 結果は6位, 3650pt(うち681ptを入れ, 176pt分手伝った)でした.

F-4 Phantom (Crypto 176pts)

@_193sの手伝いをした. 大体探索とか計算は彼が進めてくれたので, 全体としてのWriteupを書く.

問題としてはある$$l$$-bitの素数$$p$$に対して$$p$$の$$k$$-bit目($$k\lt l/2$$)としてよい)と$$l-k$$-bit目を反転させ, next_primeを取る. 式にするとある$$x$$が存在して

$$$ \begin{aligned} p &= \mathrm{prime}\newline q &= p \pm 2^k \pm 2^{l-k} + x \end{aligned} $$$

となる. この$$p$$, $$q$$を使ってRSA暗号を利用するわけで, 今回はこれを素因数分解するのが目的. まずは$$n = pq$$を書き下すと,

$$$ \begin{aligned} n &= pq\newline &= p (p + \pm 2^k \pm 2^{l-k} + x)\newline &= p^2 + p(\pm 2^k \pm 2^{l-k} + x) \end{aligned} $$$

となる. これは$$p$$についての2次方程式と見ることができる. というのも, $$k$$, 符号, $$x$$についての総当りはそれぞれ$$l/2$$回, $$4$$回, $$0\leq x\leq 1000$$回等で抑えられ, これを総当りするのは難しくないため.

これを使って$$p$$が分かったとする. 今回の問題では必ず$$e | p-1$$になるようにされており, 普通にModular Inverseを取るだけでは解けないようになっている. そこで, $$q$$は特にそのような嫌がらせがされていないことに着目して複数の$$q$$について$$c^{1/e}\ \mathrm{mod}\ q$$を計算し, これらを中国人剰余定理で例えば$$\mathbb{Z}/q_1q_2\mathbb{Z}$$に引っ張り上げる事によって平文$$m$$を計算すればよい.

実際の計算やコーディングは@_193sがやってくれていた. 感謝

Flag: ASIS{Still____We_Can_Solve_Bad_F4!}

A fine OTP Server (Crypto 279pts)

一人で解いた. ある固定の平文$$M$$があり, これについて$$m _ 0 = M\times 2^k + x _ 0$$, $$m _ 1 = M\times 2^k + x _ 1$$とし, これをRSA暗号により暗号化したものとその公開鍵が渡される. ここから$$x _ 0$$, $$x _ 1$$を導出し, サーバーへ送信することでフラグが得られるという形.

通常Coppersmith's Short Pad AttackやFranklin-Reiter's Attackを用いるが, 今回は$$e = 3$$と小さいのもあってStereotyped-Message Attackを用いることにした. これは$$(M + x _ 0)^e$$についてCoppersmith's methodを適用することで$$x_0$$を計算するというシンプルな方法で, これを使うとすぐに解が出た.

Flag: ASIS{Great____As_you_have_found_This_is_Franklin-Reiter's_attack_CongratZ_ZZzZ!_!}

Secured OTP Server (Crypto 268pts)

First Solve. $$M$$が大きくなっているが, A Fine OTP Serverと全く同じソルバで解ける.

Flag: ASIS{gj____Finally_y0u_have_found_This_is_Franklin-Reiter's_attack_CongratZ_ZZzZ!_!!!}

unsecure ASIS sub-d (Forensics/Crypto 132pts)

First Solve. SSL/TLS通信がたくさん含まれているpcapが渡される. scapyで証明書を全て集めてgcdを取ると出てくる. 後は秘密鍵をWiresharkに投げれば解ける.

Flag: ASIS{easy_Common_Factor_iS_re4l1y_Forensic_N0t_Crypto!!!!}

Alice, Bob, and Rob (Crypto 202pts)

McEliece暗号. 最初はStern's Attackを実装するべきかと考えていくつか論文を読んでいたが, Goppa符号の生成行列$$G$$が$$G\cdot {}^t G = O$$を満たしている事に気づいたので, $$PK\cdot {}^t PK = O$$を用いて以下のようにして解いた.

暗号文$$C = M\cdot PK + e$$について, $$C\cdot {}^t PK = e\cdot {}^t PK$$を計算する. この時, $$e$$はハミング重みが1と小さいのでテーブルを作って$$e$$を計算できる.

$$C + e$$が計算できるので, $$M = (x_1, x_2, x_3, x_4)$$と$$M\cdot PK$$の対応テーブルから$$M$$を計算する.

Flag: ASIS{new_ASIS_CTF_So_new_McEliece_Cryptosystem!!}

感想

Old but interestingを解きたかった. Almost leetシリーズとCrows Know!も気になる.

参考文献

David Wong. 2015. Survey: Lattice Reduction Attacks on RSA - https://doc.lagout.org/security/Crypto/2015_rsa_lattice_attacks.pdf

Christopher Roering. 2013. Coding Theory-Based Cryptography: McEliece Cryptosystems in Sage - http://digitalcommons.csbsju.edu/cgi/viewcontent.cgi?article=1019&context=honors_theses

[shiho-elliptic]

ラボユースを卒業した

サイボウズ・ラボユース 5th, 6th生として活動してきましたが, 2017/3/30にこれを卒業しました. これから応募してみたいという方のために簡単に終わってみた感想を書きます.

私の成果物はこちらになります https://github.com/elliptic-shiho/ecpy/

5th

サイボウズ・ラボユース制度の細かい話については募集要項 ( http://labs.cybozu.co.jp/youth/requirements.html )を確認して頂ければと思います. 私は当時書いていたソフトウェアのソースコードを送ってみたり当時やっていたことをいくつか並べてみたりとしたらいつの間にか選考に通っていました. さほどすごいことはしていないのですが, ちゃんとある程度コードを書いていて公開している, かつ意欲がある人なら応募してみるのもありかな?と思います.

実は私はC++で開発をしたことが無く, 暗号に関するアプリケーションか音声処理でもやってみたいなという割とふわふわした理由で応募していました. そこで, 最初はC++に慣れることを目標に複素数クラスの実装や楕円曲線Diffie-Hellmanの実装をやってみたりと簡単なものを書く程度となっており, 夏休み分はそれで終了. 最終的に3月一杯を使ってPythonだけで楕円曲線・ペアリング計算ライブラリecpy を書くことになりました. 5th終了当時のコミットは https://github.com/elliptic-shiho/ecpy/tree/bb69867c9e89c1ab7703a510f09477ede470c792 です. あまり関係はないですが, この期間中に「暗号理論と楕円曲線」という本の誤植を2カ所ほど発見して報告しました. 現在は正誤表に載っています.

5th スライド: http://elliptic-shiho.github.io/slide/lab_youth_5th.pdf

通常ラボユース制度は年度末までですが, 私は3月に入ってからecpyを書き始めたということと@slankdevが2月から参加したということで2人で6thへ食い込むことになります. 私は2015/8/3に始めたので2016/8/3までつづくことになりました.

6th

5thで書いたecpyを高速化してみたい, というものがメインでした. 実際ライブラリとしての使い勝手もまだまだ微妙なのでこれもなんとかしてみたいとも思っており, 何より最初にやったC++関連のコード書きを一切やっていないということも大きく, とりあえず書いてみようということになりました. 案の定というか, 私はCやアセンブラは慣れ親しんでいましたがC++の経験は5thのそれがほぼ最初であり他と組み合わせるようなものの経験は皆無です. 設計についてもあまり知識は無く, 全体的に迷走しながら開発していました. 具体的には最初はBoost.Pythonを使い, これを使って2度書き直し, Python C Extension APIを用いて更に書き直しています. どう考えても時間の無駄でどうしようもなかったので, 光成さんに設計, インターフェース構築について教わることになります. 基本的にシンプル(疎結合の意)な構成で, 最初に全てまず確定させたほうが良いという教えのもとでC++の仕様について学びながら書くことになります. 設計がしっかりしていればちゃんと書けるもので, あたりまえですがちゃんと書き進めることができました. このような当たり前のことでも独学で学ぶにはかなりの時間が必要なので, この辺りを教授頂けるのもこの手の制度の良い点かと思います. 8/3で終了した後はオンラインで済む作業については可能だったのでコードレビューをお願いしたりバグの原因についてお聞きしたりとしていました. 実際に書き上がって大体のコード書きが完了したのは2017年の始めでしたが.

6thスライド: http://elliptic-shiho.github.io/slide/lab_youth_6th.pdf

課外活動

5th/6thを通して扱っている内容がペアリングや楕円曲線のような高度な数学を扱っているだけに数学的議論が出来る必要性を強く感じており, 更にちゃんとした理解をしたほうが良いということを6th終了前に言われ, 光成さんの昔大学で読んだ「代数概論」という本をラボユースの延長, 課外活動的にゼミの形で読んでみないかという話を頂きました. 私としてもありがたい話だったので進めていただき, 私は週に1度か2週間に1度, 1時間半ほどゼミの発表者をすることになりました. 最初は数学科で実際に行われている読み方を覚える所から始まり, 証明の不備を指摘されたり取り組み方自体の話を何度かされたりもしましたが半年ほど経つ頃には準同型定理の証明を読めるようになり, ヒントをもらいながらも群に関する5-lemmaの証明を示したりSylowの定理の証明を読むといった基本的なことについては独力でできるようになりました. これからも続けていきたいと思います.

支援内容について

実際の支援内容としては

出社して開発した時間によって支給されるお金

私が京都住みだったことから一ヶ月間東京へ来るためのマンスリーマンション代

会社までの交通費

etc, etc, ...

といった金銭的支援がかなり助かりました. 検討されている方は地方住まいでも問題なく参加することができるのでご安心下さい.

また, 専門家の直接指導が頂けるのは金銭的支援と同等かそれ以上にためになります. 発表会の前に中間発表会があって, ここでは他の専門家の方からの言葉もいただけたり, ラボユース生同士のつながりの中での知見の交換により得られるものも非常に大きいです. もしもちゃんと開発をやりたいという意欲があり, やりたい分野の専門家がメンターに居るのであれば文句の類は全く無いかと思います.

感想

一言で表すなら「最高」です. 未踏に応募するのもありですが, 個人的にはそれよりもメンターの距離が近く, 本社へ出社しながらの開発は非常に捗りました. 出来ることなら7thでも参加したいぐらいですが私は卒業してしまいました. 今後も何かしらラボユースという制度は広めていきたいです.

今回, 卒業記念品(?)として岩波書店の「岩波 数学辞典 第4版」を頂きました. ただの辞書ではなく, ちゃんと読めばこれだけでも理解できる箇所はある(勿論ちゃんとした本を読んだほうがわかりやすいですが)ので非常に良い辞書です. 今後数学について学ぶ際には役に立ってくれるだろうと期待しています.

最後になりましたが光成さんを始めサイボウズ・ラボ, サイボウズの方々には大変お世話になりました. 御礼申し上げます.

[shiho-elliptic]

0ctf quals 2017 Writeup

0ctf quals 2017にbinjaで参加しました. 結果は5443pt (うち189pt分を一人で, 687pt分を協力しながら解いてフラグを送信した), 2位でした.

oneTimePad (Crypto 114pts)

一人で解いた. 暗号化スクリプトと暗号文が渡される. processというCRCっぽい関数があり, 実際の暗号化処理はこの関数を中で使用するPRNGにより生成した乱数と平文のXORで, 3つの暗号文と2つの平文が与えられている. フラグは残る1つの暗号文を復号すると手に入るようだ.

扱いが単純になるため, 以下演算は全て$$GF(2^{256})$$上で行われるものと仮定する.

まずは暗号化処理について見てみる. process関数の内容はよく見れば$$process(r, s) := (r + s)^2$$であることが分かる. これを踏まえて, $$i$$番目の乱数を漸化式として書き下すと以下のようになる. ただし, $$r$$は起動毎に固定な乱数の初期ステートで, $$s$$は起動毎に固定なシード値と呼ばれる値である.

$$$ \begin{aligned} rand _ 1 &= r \newline rand _ {i+1} &= (rand _ i + s) ^ 2 \end{aligned} $$$

これを用いると, 平文$$m_i$$に対する暗号文$$c _ i$$は $$c _ i = m _ i + rand _ i$$と書ける.

さて, 現在わかっているのはスクリプトから$$m_2, m_3, c_1, c_2, c_3$$であり, 明らかに$$rand_2, rand_3$$も分かる. このとき, $$rand_1$$が手に入れば$$m_1$$を導出できると考えられる. そこで, $$rand_2, rand_3$$を実際に書き下すと,

$$$ \begin{aligned} rand_2 &= (r + s) ^ 2\newline rand_3 &= ((r+s) ^ 2 + s) ^ 2 \end{aligned} $$$

ところで, 拡大体に対する平方根演算は既にアルゴリズムが多数知られており, 例えば[1]を読めばこの場合でも計算が可能であることが分かる. よって, 平方根演算を利用できると仮定して式を変形すると,

$$$ \begin{aligned} \sqrt{rand_2} &= r + s\newline \sqrt{rand_3} &= (r+s)^2 + s\newline \end{aligned} $$$

従って,

$$$ \sqrt{rand_3} + rand_2 = s, \sqrt{rand_2} + s = r $$$

より$$rand_1 = r$$が計算できる.

Flag: flag{t0_B3_r4ndoM_en0Ugh_1s_nec3s5arY}

integrity (Crypto 75pts)

一人で解いた. 暗号化・復号のオラクルが与えられ, 文字列adminを暗号化せよというもの. しかし, 暗号文はパディング処理がなされ, パディング後の文字列とパディング後の文字列adminが一致する場合は暗号化できない. よって, パディング文字を後に追加する攻撃は不可能であることが分かる. また, 暗号化スキームから, 改竄も一見不可能である.

以下, 暗号化・復号スキームについて簡単に見る. $$m$$を平文, $$c$$を暗号文とする.

暗号化

$$m$$にパディングを付加する. これがadminのパディング後文字列と一致するならばエラー.

$$m$$のMD5ハッシュを計算する. このハッシュ値を文字列として$$hash$$変数で参照する.

IVを生成し, AES-128-CBCで$$hash || m$$を暗号化する. ただし $$||$$は文字列の結合を表す.

IVと暗号化結果を結合して返す.

復号

暗号文からIV, $$c$$を取り出す.

取り出したIVを用いてAES-128-CBCで$$c$$を復号する. 復号後の文字列を$$hash$$, $$m'$$と分割して保持する.

$$m'$$のMD5ハッシュを計算する. これを$$hash'$$とする.

$$hash = hash'$$ならば$$m'$$をパディングを外して返す. 異なるならエラー.

このスキームでは, MD5を利用して文字列のチェックを行う. ここで, パディングを付与することによるチェックは行っているが, 例えばpadding("admin") || "A"についてはチェックをパスすることに注目すると, padding("admin")は一つのブロックを作ることから, 暗号文は以下のような構造を持つと言える.

| IV | MD5(padding("admin") || "A") | Enc(padding("admin")) | Enc(padding("A"))

これは勿論暗号化可能である. よって, この暗号文は取得できる. では, 暗号文の最後のブロックをカットして, 以下のようにしてみてはどうだろう.

| IV | MD5(padding("admin") || "A") | Enc(padding("admin")) |

このままでは復号処理を通らない. これはMD5のチェックのためなので, これをIVを利用したBit-Flipping-Attackを用いて正しいMD5に直せばどうだろう?

| IV ^ MD5(padding("admin") || "A") ^ MD5(padding("admin")) | MD5(padding("admin") || "A") | Enc(padding("admin")) |

CBCモードの性質から, これは結果的に MD5(padding("admin")) || padding("admin")へ復号される. これは明らかに復号チェックを通るので, 無事adminという文字列を暗号化できたことになる.

Flag: flag{Easy_br0ken_scheme_cann0t_keep_y0ur_integrity}

py (Reverse 137pts)

@akiymさんがかなりやってくれていた. 自分は最後のバイトコードダンプからPythonコードへ戻す所だけをやった. バイトコードダンプは少し間違いがあり, これを適当に補正しながらハンドパワーと頭の回転で補って戻した. Pythonのバイトコードは比較的高級なので, 適当にdis.disassembleを使ってデバッグしながらコードを書けば同じバイトコードを生成する関数は容易に書ける.

Flag: flag{Gue55_opcode_G@@@me}

complicated xss (Web 177pts)

おそらくWeb担当の誰かが進めてくれていたと思う. 私が進めていた, という方はリプライ頂ければここに名前を載せます.

2段階でXSSする必要があり, 自分が見た時は最後のXHRで詰まっている状態だった. 問題では, delete window.XMLHttpRequestのように一部のオブジェクトがdeleteされており, 直接叩くことは不可能に思えた.

しかし, 同じドメインの404ページをiframeで表示し, そのcontentWindowを見ることによってXMLHttpRequestオブジェクトは取得できる. これを用いてファイルをアップロードすることでフラグが得られた.

Flag: flag{xss_is_fun_2333333}

oneTimePad2 (Crypto 366pts)

@_193sと一緒に解いた.

oneTimePadと似ているようで異なる問題. 以下, 計算は全て$$GF(2^{128})$$のものと仮定する.

まず, process1, process2と2つの関数がある. まず, process1は掛け算をしているだけなので, $$process1(x, y) := x\cdot y$$. process2は少し複雑で, 以下のように定義されている. ただし$$M_2(GF(2^{128}))$$は$$GF(2^{128})$$を値に持つ2次正方行列の全体を表す.

$$$ process2: M_2(GF(2^{128}))\times M_2(GF(2^{128}))\ni(A, B) \longmapsto A\cdot B \in M_2(GF(2^{128})) $$$

そして, これを用いて乱数を漸化式で定義すると以下のようになる. ただし, $$r$$は起動毎に異なる初期値で, $$n$$はあるランダムな数である.

$$$ \begin{aligned} rand _ 1 &= r\newline rand _ {i + 1} &= T^{n^{2^{i-1}}}[1, 1]\cdot rand_i + T^{n^{2^{i-1}}}[1, 2] \end{aligned} $$$ ただし, $$$ T := \begin{pmatrix}A & B \newline 0 & 1\end{pmatrix} $$$ であり, ここで$$A$$, $$B$$はそれぞれある定数である. さらに, $$T^n$$は実際には $$$ \begin{aligned} T^n &= \begin{pmatrix}A^n & B(A^{n-1} + A^{n-2}+\cdots+A+1) \newline 0 & 1\end{pmatrix}\newline &= \begin{pmatrix}A^n & B\cdot\sum _ {j = 1} ^ n A^{n-j} \newline 0 & 1\end{pmatrix} \end{aligned} $$$ であり, 加えて$$B\cdot\sum _ {j = 1} ^ n A^{n-j}$$は等比級数の性質から $$$ B\cdot\sum _ {j = 1} ^ n A^{n-j} = B\frac{1-A^n}{1-A} = B\frac{A^n+1}{A+1} $$$ と書ける. 最終的に, $$$ \begin{aligned} rand _ 1 &= r\newline rand _ {i + 1} &= A^{n^{2^{i-1}}}\cdot rand_i + B\frac{A^{n^{2^{i-1}}} + 1}{A + 1} \end{aligned} $$$ と書くことができる. これを$$i = 1$$の時に$$A^n$$について解くと, $$$ \begin{aligned} rand_2 &= A^n\cdot rand_1 + B\frac{A^n + 1}{A + 1}\newline rand_2\cdot(A + 1) &= A^n\cdot rand_1\cdot (A + 1) + B\cdot A^n - B\newline rand_2\cdot(A + 1) + B &= A^n\cdot (rand_1\cdot (A + 1) + B)\newline\newline \therefore A^n &= \frac{rand_2\cdot(A + 1) + B}{rand_1\cdot (A + 1) + B}\newline \end{aligned} $$$ これにより, $$A$$と$$A^n$$についてのDLPが構成できた. もし, このDLPが解けた(= $$n$$が判明した)ならば, $$A^{n^2}$$が計算でき, 乱数全体が計算できてしまう. しかし, $$A$$の位数は $$$ 2^{128}-1 = 3 * 5 * 17 * 257 * 641 * 65537 * 274177 * 6700417 * 67280421310721 $$$ である. これは最大の素数67280421310721でさえそれほどの大きさではなく, Pohlig-Hellmanを適用すれば十分に解ける範囲のDLPになると考えられる. これにより実際にDLPを解くことを試みると, 8秒ほどで計算が完了した. $$n$$を得ることができたので, 後は乱数を生成してフラグを出力するだけ.

Flag: flag{LCG1sN3ver5aFe!!}

感想

2位は嬉しい. zer0llvmが解けなかったのが残念.

参考文献

Gora Adj and Francisco Rodríguez-Henríquez. 2012. Square root computation over even extension fields. Cryptology ePrint Archive, Report 2012/685. https://eprint.iacr.org/2012/685.pdf

[shiho-elliptic]

Boston Key Party CTF 2017 Writeup

binja(前半少しだけ個人チーム)で参加しました. 結果は35位, 1501ptでした. 今回はかなりチームの方に助けられた面があります.

Prudentialv2 (cloud 50pts)

文字列が異なるがSHA1が同じ文字列を探せというもの. つい最近公開されたsha1 collision( https://shattered.io/ )の問題と言える. 公開された論文 ( https://shattered.io/static/shattered.pdf )から, 今回のsha1 collisionは「特定のヘッダ + collision pairの片方 + 特定のフッタ」の形で, ヘッダ/フッタは固定, collision pairはそれぞれの入力時の内部状態と出力時の内部状況が同じになるようなブロック (論文のp.3 Table 1). ここから「ヘッダ+collision pairの片方」だけを抜き出せば, 同じ内部状態を持つ文字列が得られるので, sha1が衝突する. 後はmageさんがフラグを取ってくれた.

Flag: FLAG{AfterThursdayWeHadToReduceThePointValue}

RSA Buffet (crypto 150pts)

個人チームでやっていた時に解いた. binjaでは参加時点で既にbonoさんに解かれていたので個人的に解いたというだけ.

key0, key6の間でgcd, key2がfactordbで素因数分解, key1がfermat法で分解可能だった. key3がwiener's attack可能だったのには後から気づいた.

Flag: FLAG{ndQzjRpnSP60NgWET6jX}

Sponge (crypto 200pts)

名前からしてSHA-3?と思っているとどうやら正解. Sponge構造についてはあまり資料が存在しないため, 一旦ここで解説する.

Sponge構造では, 写像\(f\)とパラメータ\(r, c\), パディングされたメッセージの列\(m _ i\) (それぞれのメッセージ長は\(r\))がある時に\(i\)番目の内部ステート\(state _ i\)は次のように定義される. ただし, \(00 ^ i\)は長さ\(i\)の\(00\)の並びを表し, \(||, \oplus\)はそれぞれ列としての結合, XOR演算を表す.

\[ state _ i = \begin{cases} 00 ^ {r+c} & (i = 0)\newline f((m _ i || 00 ^ {c})\oplus state _ {i-1}) & (i \geq 1) \end{cases} \]

これはスポンジにメッセージを「吸わせている」と言える. 使用する際には\(r\)で指定した範囲しか変更されることはなく, 後半の長さ\(c\)の範囲は\(f\)によって変更される以外確実に変更されない. イメージとしては, 吸わせているうちに毛細管現象により水が行き渡るような感じだろうか.

ハッシュ値として取り出すには, メッセージを指定せずに次のステートを取れば良い. 例えば, \(state _ k\)が最後の内部ステートだとすると

\[ HASH = state _ k[0, \ldots, r] || f(state _ k)[0, \ldots, r] \]

のようにすればよい. ただし, \(X[a, \ldots, b]\)は\(X\)の\(a\)から\(b\)までの範囲を切り出したものという意味. Python風に言えばX[a:b].

これは画像にするとこのようになる(出典: 「Cryptographic sponge functions」p.13 Figure 2.1)

こうすると, Length Extension Attackや原像攻撃が行いにくくなる. 詳しい話は参考文献にある論文へ.

今回は\(f\)は鍵が\(00^{16}\)な128-bit AES (ECB mode)で, \(r = 10\), \(c = 6\)である.

次に, Sponge構造におけるハッシュ衝突について考察する. 明らかに「ハッシュ値が同じ\(\iff\)異なるメッセージ列\(m _ i, m' _ i\)に対して最終的なステート\(state _ k, state' _ k\)が等しい」が成り立つ. 今回はcollisionを意図的に発生させたいので, \(f\)が逆写像を持つことからこれを攻撃する. 手法としてはmeet-in-the-middle attackの類似と言える.

\(f(m _ 1 || 00 ^ c) = P _ 1 || \alpha\), \(f ^ {-1}(m _ 2 || 00 ^ c) = P _ 2 || \alpha\)なるような\(m _ 1, m _ 2\)が存在するとする. この時, 新たにメッセージ列\(m' = \left\{m _ 1, P _ 1\oplus P _ 2, m _ 2\right\}\)を作り, このメッセージ列についてstateを考えてみる.

\[ \begin{aligned} state _ 1 &= f(m _ 1 || 00^c)\newline state _ 2 &= f(state _ 1 \oplus (P _ 1 \oplus P _ 2 || 00 ^ c)) \newline &= f(f(m _ 1 || 00^c) \oplus (P _ 1 \oplus P _ 2 || 00 ^ c))\newline &= f((P _ 1 || \alpha) \oplus (P _ 1 \oplus P _ 2 || 00 ^ c))\newline &= f(P _ 2 || \alpha)\newline &= m _ 2 || 00^c\newline state _ 3 &= f(state _ 2 \oplus (m _ 2 || 00 ^ c)) \newline &= f(00 ^ {r+c})\newline \end{aligned} \]

列を\(m'' = \left\{m _ 1, P _ 1\oplus P _ 2, m _ 2\oplus \mathbb{X}\right\}\)と取り直すと, この列に対する\(state _ 3\)は\(f(\mathbb{X} || 00^c)\)である. つまり, 任意のメッセージの最初のstateへ持っていくことができる.

以上を利用して, 問題となっている文字列に対する先の条件を満たす平文を探索することでハッシュ値を衝突させる. ところが, os.urandom(10) を用いたbirthday attackを行ってもそのようなペアが出てこない (31〜2万個ほどは探索したかと思う). すると, bonoさんから0から順に探索すれば見つかったと教えてもらい, これを使うことにした.

フラグはこれを本番サーバーへ投げればもらえた.

Flag: FLAG{MITM 3: This Time It's Personal!}

参考文献:

http://sponge.noekeon.org/CSF-0.1.pdf

https://eprint.iacr.org/2011/261.pdf

http://www.wil.waw.pl/art_prac/2013/MCC/5.pdf

http://wiki.uni.lu/esc/docs/CryptographicSponges-ESC2008.pdf

http://www.infosec.sdu.edu.cn/cans2011/Joan%20SpongeCANS2011.pdf

https://eprint.iacr.org/2008/263.pdf

Multi-Party Computation (crypto 250pts)

Paillier暗号とその準同型性を用いた暗号化された状態の多項式評価+αでゴチャゴチャ操作をしてくれる.

フラグの1文字を\(flag _ i\)とすると, サーバーの持つ値\(a _ i, b _ i\)は\(b _ i = \mathrm{rand}()\), \(a _ i = b _ i \times 2^8 + flag _ i\). ただし, \(b _ i \lt b _ {i + 1}\)

暗号化されていることを考慮しないで書くと, サーバーはこちらが多項式\(x^2+x+1\)を指定したとすると, \(c_i=rand() \times (a _ i ^ 2+a _ i+1)+a _ i\)を計算し, \(c _ i\)を返すと言える.

さて, 多項式への制約は存在しないため, こちらが0を多項式として指定すればそのまま\(a _ i\)が手に入る. このうちフラグ文字列自体は最下位バイトに存在するため, \(mod 256\)でフラグの文字が手に入る. しかし, 実は出力前に\(c_i\)はシャッフルされており, そのままだとフラグの文字列を手動アナグラムする必要が生じる.

悩んでいた所, bonoさんに\(b_i\)がソートされているので, 手に入ったランダムな順番のaiを再度ソートし, 上から順にmod256すればよいのでは, という指摘を受ける. 実際そのとおりで, この手順でフラグが出た.

Flag: FLAG{Monic polynomials FTW}

感想

量子暗号を使うような暗号問題が出てきたが, 正直太刀打ちできなかった. 勉強が足りない. また, bonoさんのアドバイスがなければ解けていなかった問題もあるので感謝. RSA Buffet Bonus Round!という問題がもう1問あったが解くことができず, これもwriteupを読んで勉強していきたい.

[shiho-elliptic]

Sharif CTF 2016 Writeup

scryptosで参加していました. 結果は11位 4397ptで, うち1235ptを入れました.

↓↓ Writeup ↓↓

LSB Oracle (Crypto 150 + 30)

First Solve. ボーナス問題. Plaid CTF 2016の時のソルバを流用した.

https://gist.github.com/elliptic-shiho/ae7d60627ca61487f9ee9f7a5a3e8cb6

Flag: SharifCTF{65d7551577a6a613c99c2b4023039b0a}

TPQ (Crypto 150 + 8)

素数を10個生成し, それらを自由に選んで使えるRSA Encryption Oracle. ただし 同じ素数を2乗することはできない. 平文を \(m\), 素数を \(p _ 0, \ldots, p _ 9\)とし, \(c _ {i, j} := m^e \mod p _ i p _ j\)とする.

オラクルから得られるのは暗号文のみである. なので, 自由に選べる素数の組み合わせを利用し, 以下のようにして素数を2つ得た後に通常のRSAとして復号することで解いた.

\[ \begin{align} c _ {0, 1} &= m^e - k _ 1 p _ 0 p _ 1 \newline c _ {0, 2} &= m^e - k _ 2 p _ 0 p _ 2 \newline c _ {0, 3} &= m^e - k _ 3 p _ 0 p _ 3 \newline \newline c _ {0, 1} - c _ {0, 2} &= p _ 0 (k _ 2 p _ 2 - k _ 1 p _ 1)\newline c _ {0, 2} - c _ {0, 3} &= p _ 0 (k _ 3 p _ 3 - k _ 2 p _ 2)\newline \newline \end{align} \]

\[ \therefore \gcd(c _ {0, 1} - c _ {0, 2}, c _ {0, 2} - c _ {0, 3}) = p _ 0 \]

以上を実装したものが以下になる.

https://gist.github.com/elliptic-shiho/f1702bcc2c0831cbd134c69f7b00a733

Flag: SharifCTF{7c62f12e7e6f08f9f5365e45588d34d8}

Unterscheide (Crypto 200 + 40)

First Solve. 暗号化処理を読むと, 定数 \(q\) が最低限分からなければならないことが分かる. 暗号化はビットごとに行われ, ビットの0/1ごとに定数が微妙に変わる. 平文の \(i\)ビット目を \(m _ i \)とすると,

\[ c _ i = \begin{cases} h ^ {x _ i ^ 2 p _ 1} \pmod q \cdot q \cdot (rand + i) + rand + i + 1 & (m _ i = 0) \newline h ^ {y _ i ^ 2 p _ 2} \pmod q \cdot q \cdot (rand + i) + rand + i + 1 & (m _ i = 1) \newline \end{cases} \]

ただし, \(x _ i\)はそれぞれ乱数で, \(y _ i = x _ i ^ {-1} \mod q-1\)

この式は以下のように変形できる. ただし, 今回あまり関連の無い \(h ^ {x _ i ^ 2 p _ 1}\), \(h ^ {y _ i ^ 2 p _ 2}\)は\(H _ i\)にまとめた.

\[ c _ i - c _ {i+1} + 1 = (H _ i (rand + i) - H _ {i + 1} (rand + i + 1)) q \]

\[ \therefore \gcd(c _ i - c _ {i+1} + 1, c _ {i + 1} - c _ {i+2} + 1) = q \]

\(q\)から\(p_1\), \(p _ 2\)は導出できる. また, \(c_i \mod q - 1 = rand\)なので\(rand\)も計算可能である. 平文のビットの0/1は \(\left\{(c _ i - rand - i - 1) / (q\cdot rand)\right\}^ {p _ 1}\pmod q\) 又は \(\left\{(c _ i - rand - i - 1) / (q\cdot rand)\right\}^ {p _ 2}\pmod q\) のうちどちらが\(h\)と等しいかで判別出来るため, 多数の暗号文に対して両方を試し, その結果のうちどの暗号文でも出てくる値が \(h\)だと考えられる. これによって \(h\)も得られたため, 後はこれを利用して復号するだけ.

https://gist.github.com/elliptic-shiho/d5706642caed170e3820b427d8a7c59e

Flag: SharifCTF{10ED2D76BCC417D9C48BE67F6790AF70}

GCM Magic (Crypto 250 + 17)

GCMモードで暗号化・復号できるサービスが与えられる. ある特定の平文はBANされており, この平文の暗号文を作り出せれば良い. まずはGCMモードについての資料として The Galois/Counter Mode of Operation (GCM) を読んだ (余談だが, このpdfを印刷すると空白が消えてしまい非常に読みにくい資料になってしまった. ).

P.5のFigure 1を眺めれば分かる通り, GCMモードでは暗号文自体は単なるXORで生成されている. このため, 暗号文自体は適当に偽造することが比較的簡単. しかし, GCMモードには鍵, 初期化ベクタ(Figure 2におけるCounter 0)のほかに暗号化毎に異なる値としてnonce (上記資料では"Auth Data 1"と書かれている)が必要で, このnonceと各暗号文からハッシュ値を生成し, これをAuth Tagとして出力する. これにより, 暗号文は偽造できるが復号時にAuth Tagが一致しない場合は不正な暗号文とみなして破棄することができる. 肝心のTagの生成方法についてもFigure 2を読めば分かるが, 一旦数式に落としこむことにする.

これ以降, 全ての演算は \(\mathbb{F} _ p ^ {128}\)の上で行われると仮定する.

1ブロックの場合について考える. 平文を \(m \), 暗号文を \(c\), nonceを \(nonce\)とする. この時, Auth Tagは次のように計算される. ただし, \(IV\) は初期化ベクタ, \(Enc_k\)は暗号化関数, \(H = Enc_k(0 ^ {128})\)である.

\[ Auth\_Tag = Enc _ k(IV) + (((nonce \times H + c)\times H) + (\mathrm{len}(nonce) || \mathrm{len}( c )))\times H \]

長いので一部の固定パラメータをまとめると以下のようになる.

\[ \begin{align} Auth\_Tag &= Enc_k(IV) + (((X + c)\times H) + Y)\times H\newline &= Enc_k(IV) + (X\times H + c\times H + Y)\times H\newline &= Enc_k(IV) + X\times H ^ 2 + c\times H ^ 2 + Y\times H \newline \end{align} \]

ここで, 2つの異なる暗号文\(c\), \(c'\)とそのAuth Tag \(t\), \(t'\)について考える. 目的はタグを偽造することなので, 先の式における\(c\)を調整できれば良いことが分かる. そのため, 差分を取ることでいずれかのパラメータを導出できないかを考えた.

\[ \begin{align} t + t' &= (Enc_k(IV) + X\times H ^ 2 + c\times H ^ 2 + Y\times H) + (Enc_k(IV) + X'\times H ^ 2 + c'\times H ^ 2 + Y'\times H)\newline &= (X + X')\times H ^ 2 + (c + c')\times H ^ 2 \end{align} \]

この暗号化/復号サービスではnonceを自由に調整することが出来る. そのため, 2つの暗号文を同じnonceを持つように調整してやると\((X + X')\times H\)の項が消えて\(t + t' = (c + c') H ^ 2\)となる. こうなれば, \(H ^ 2\)は明らかに求めることができるため, タグを偽造することが可能になる. (GCM nonce-reuse attack)

以上を実装してAuth Tagを偽造するコードは以下のようになる.

https://gist.github.com/elliptic-shiho/ea179d69614e78a8eb591de4763ad649

こうして得られたAuth Tagを使って復号するとフラグが得られた.

Flag: SharifCTF{bf9be0962ea0c3e33d2c0067b5b780a4}

Synced (Forensics 100pts)

チームチャットでDRBD (分散ストレージシステムの基盤らしい)のパケットだということが言われていたので, scapyのPacketを簡単に書いてデータを取り出しやすくしながら見ていた. foremostして出てきていた画像以外に[0mのような文字列が目に付く箇所が存在することに気づいた. そこで, \x1bの含まれるデータパケットのみを抽出してみるとASCII エスケープシーケンスによってフラグが書かれたテキストファイル(少し壊れているが読めた)が得られた.

https://gist.github.com/elliptic-shiho/f98ec0cc77430905916001ee87e78c06

Flag: SharifCTF{ceed10d4fa1228198e04ab85f32a7ce3}

Strange PDF (Forensics 100pts)

特に何もないPDF. 中身が全てテキストで構成されているのが少し気になるので見てみると何故かどこからも利用されていそうにないストリームが大量に存在した. 試行錯誤の結果, これらのデータを座標とみなしてプロットすることで10進数で書かれたフラグ文字列が得られた. どうやら他のWriteupを読むとこれはPostScriptとしてPDFを保存することで読めたらしい.

Flag: SharifCTF{d1242d2d0969741dde7ed79c3c409c46}

Poor guy (Web 150)

一見脆弱性はなさそうなサイトだが, 購入した本を選ぶ時のリクエストに \'||sleep(10);--等を入れてやると見事にリクエストが10秒遅れる. エラーそのものの表示は無いが, 選んだ本が存在するか否かのエラーメッセージは表示されるのでこれを利用してunion selectのカラム数を特定した. また, この時information_schema.tablesテーブルが何故かうまく読み取れなかった. このため, information_schema.processlistテーブルの内容を読んで現在実行されているSQL文からテーブル名等を特定, secret flag本について調べているとシリアルキーにフラグが載っていた.

Flag: SharifCTF{931b20ec7700a61e5d280888662757af}

感想

Crypto 300/400が解けなかったのが悔しい. Crypto 300はいずれにせよ解いておきたいので, 解いたらWriteupを書きたいと思う.

[shiho-elliptic]

EKOPARTY CTF 2016 Writeup

scryptosで参加した. 結果は2922pt (うち1625ptを入れ, rev150+for125を手伝った), 12位(日本勢の中では1位)だった.

↓↓↓ Writeup ↓↓↓

Hidden inside EKO (misc 50pts)

CTFが始まる前に背景画像をチェックしていたら偶然発見した.

Flag: EKO{th3_fl4g}

X-Flag (misc 150pts)

謎のサイトが与えられる. 全ポートを自分のPCへ回すようにNATを変えてWiresharkで見ていると6000番に接続が来ていた. Wiresharkの表示と6000番という番号的に, X Window Systemのリモートクライアントのようだ. 適当にサーバーを構築し, 自分のPCへと繋げさせるとうまく見えてくれた.

Flag: EKO{old_hackers_such_fataku_still_use_remote_display}

Mr.Robot (web 25pts)

これも大会開始前にrobots.txtを見ていて発見した.

https://ctf.ekoparty.org/static/wIMti7Z27b.txt

Flag: EKO{robot_is_following_us}

RFC 7230 (web 50pts)

curl -v

Flag: EKO{this_is_my_great_server}

Url shortener (web 200pts)

コードを読むからに, parse_urlによるホスト名チェックを回避すれば良さそう. ということで, http://YOUR_IP?@ctf.ekoparty.org/とすることでwget時にはYOUR_IPへ, parse_url時にはctf.ekoparty.orgが帰ってくる文字列を作れた.

Flag: EKO{follow_the_rfc_rabbit}

Welcome to the dark side (fbi 25pts)

torsocks curl -v https://silkroadzpvwzxxv.onion/

Flag: EKO{buy_me_some_b0ts}

Metadata (fbi 50pts)

fbi 25ptsと同じ

Flag: EKO{is_this_just_real_life_is_this_just_fantasy}

JVM (rev 25pts)

jd-gui

Flag: EKO{893116}

F#ck (rev 50pts)

F#のバイナリ. とはいえ.NETのファミリなので同じようにデコンパイル出来る. Windows機を持っていないので, MonoDevelopへ投げてC#で同じ動作をするコードを書いて解いた.

Flag: EKO{f#ck_this_sh#t}

RrEeGgEeXx (rev 75pts)

同上. 動かす必要もない

Flag: EKO{ooOOoo_sup3r_r3g3x_challenge_OOooOO}

Old times (rev 100pts)

SAVFで調べるとメインフレームあたりのデータ保存フォーマットだと分かる. jSAVFというツールを利用して中を読めば終わり.

Flag: EKO{0ld_t1m3s_n3v3r_c0m3_b4ck}

Ultra baby (pwn 25pts)

PIEバイナリ. Saved-IPの最後のバイトだけ書き換えられるので, これを書き換えてFlag関数に飛ばす.

Flag: EKO{Welcome_to_pwning_challs_2k16}

My first service I (pwn 100pts)

FSBがある. 適当にスタックを読んでいくとフラグがある.

Flag: EKO{LaBigBef0rd}

Certified Excel Hacker (for 50pts)

マクロをつい見てしまうが, 実際には隠しシートが存在して, そこにExcel方眼紙でフラグが書かれていた.

Flag: EKO{HIDDEN_SHEET_123}

Damaged (for 75pts)

気合で戻すとフラグが見える

Flag: EKO{b1tm4p_r3c}

Hacker In Disguise (for 100pts)

First Solve.

キーボードのスキャンコードとして数値を読む. ただし, プレフィクスにrを持つ数値のみをデコードする.

Flag: EKO{holapianola}

去年のスキャンコード問もFirst Solveだった.

Alice secret message (for 175pts)

exFATなイメージを渡される. いくつかファイルをFTK Imager Lite等で復元していくとOFICIO.txtというテキストファイルがある. このファイルの最初数十行の行末にはスペースかタブが存在する. これをスペース→0, タブ→1で01変換し, 文字列に変換するとフラグ.

Flag: EKO{this_is_my_secret_message}

PORN (for 400pts)

SCSI over USBなパケットが見える. USBメモリの通信を見たものだと見当を付けて通信を見ていくと, 8.2.1がUSBメモリで, ファイルを転送しているようだと分かる. NTFSのデータ構造も相まって読みにくいがそこは気合で. 途中, not_the_answer.txtがあるがこれの中身(EKO{this_is_not_the_answer})はもちろんダミーフラグ.

同時に, rarファイルが大量にあることが分かる. これらを適当に抽出し, 解凍してみるといくつか画像ファイルが出てくる. Y U NO.jpgの先頭をstringsでみてみるとEKO{Y_U_NO_KEEP_SEARCHING}があるがこれはダミーフラグ.

istringsを用いてpcapngを見ていくと, :ZoneIdentifierを見つけることが出来る. 位置を照らし合わせると, ここがRARファイルの内部に位置することが分かる. RARはNTFSのAlternate Data Streamを持つことが出来るので当たり前といえば当たり前だが, 他にも探しまわると:NULLをキーに持つADSデータがあることが分かる. これらはRARのヘッダが通常ファイルと異なるため, 010 Editor等のバイナリエディタを用いてこれを書き換え, CRCを修正する. すると, ADSデータをファイルとして解凍できるようになるので, これを見ると画像, 中にはフラグが書かれていた.

Flag: EKO{oh_snap_alternate_streams_again}

Back again (rev 150pts)

ここからは自分は途中までやったものを書く.

rev100に似ているが微妙に違うデータが渡される. 調べているとAS/400辺りのデータのようだがだからといって元には戻せないし, 動かすにもAS/400を持っているはずものないので無理. バイナリエディタで眺めている時にEBCDICで見ると一部フラグが紛れていそうな箇所を発見した. しかし通らすslackに貼っていたらいつの間にか @Charo_IT プロが解いていた.

Flag: EKO{c0b0l_l33t_ekoparty_pgm_ftw}

Knock Knock (for 125pts)

何かの通信っぽいのでまずビットごとにプロット. 1bit目がデータ, 2bit目がクロックのようだ. データ部分を読んでみると微妙にEKO{のビット列が見えたので, 全体を印刷してシャーペンを走らせてビット列を特定しようとしていたら途中うまく行かない(クロックの位相がズレている, データとクロックの時間差, データにスパイク状のノイズがある時があり, これを1とするべきか迷った等々) @Charo_IT プロが一瞬で解決してくれた.

Flag: EKO{oh..icu2}

感想

去年と比べると成長したと感じる. Cryptoが無いのはいただけないがfor400は面白かった.

[shiho-elliptic]

Tokyo Westerns CTF 2016 Writeup

Tokyo Westerns CTF 2016にscryptosで参加していました. 結果は8位, 3990pt (うち430pt分を解いて, 200pt分手伝いました)で, 日本勢の中では1位でした.

↓↓ Writeup ↓↓

Misc 50 glance

アニメーションGIFをフレームごとに分割して, 横にくっつけると懐かしいWindowsXPの画面とflagが出る.

Flag: TWCTF{Bliss by Charles O'Rear}

Misc 100 ninth

PNGのIDATを解凍すると最後にflagがある.

Flag: TWCTF{WAMP_Are_You_Ready?}

Crypto 100 Super Express

Affine写像を入れ子にした暗号. 入れ子の回数を \(i\) とすると, 以下のように定義できる. ただし, \(i\gt 0\) かつ \(a_i , b_i\) は暗号化鍵とし, \(M\) は自然数とする.

$$ \begin{align} f_0(x) &:= a_0x + b_0\newline f_i(x) &:= a_if_{i-1}(x)+b_i \mod M \end{align} $$

ここで, \(x = x' + a\) (\(a\in\mathbb{Z}\))の場合を考える. 通常の式展開として暗号化処理を考えると, ある定数 \(\alpha\) が存在して, \(\alpha x' + \alpha a + \mathrm{some\ constant}\) となる. つまり, 暗号化する際には最高次の係数が分かればある暗号文へいくらか足したり引いたりするだけで別の暗号文を作ることが出来るし, 元の平文がわかっていれば解読することが出来る. そしてこの問題ではフラグフォーマットから最初が TWCTF{ で最後が } と推測できるので, 各平文・暗号文の差分を取ってその差分を計算, 差分から最高次の係数を導出し, そこからテーブルを作って解いた.

Flag: TWCTF{Faster_Than_Shinkansen!}

Crypto 100 ESPer

RSAの鍵を毎回生成する暗号化・復号オラクルで, 終了間際に暗号化されたフラグが降ってくる. そして自分はどうもエスパーらしく, 任意の行の任意の変数を乱数に置き換えられるらしい. 復号処理が中国人剰余定理を利用したものなのでどう考えてもBoneh-DeMillo-LiptonのRSA-CRT Fault Attack. 実装して解くだけ.

Flag: TWCTF{I_don't_Lik3_ESPer_problems!}

Crypto 200 Vigenere Cipher

前半は@ki6o4がやってくれていた. 一部の文字が解読できていたので, 最初を適当にエスパーしてKPAした.

Flag: TWCTF{C14ss1caL CiPhEr iS v3ry fun}

実質@ki6o4の実績

感想

高得点Cryptoに久々にぶちあたったのに解けず. 精進.

[shiho-elliptic]

PlaidCTF 2016 Writeup

binjaで参加していました。結果は2317pt、うち275ptを自分が入れました。

↓↓Writeup↓↓

Untitled-1.pdf (misc50)

Libreoffice Writerで開いて、画像を移動させていると下の方にちらっと見えるので周りを暗くする

Flag: PCTF{how_2_pdf_yo}

the stuff(misc50)

pcapngを開き、 tcp.stream eq 4 をfollow tcp streamするとメールの通信が出てくるので、ここからflag.zipを手に入れることが出来る。しかし、これにはパスワードがかかっている。

パスワードがわかったので解凍するとフラグがある。

Flag: PCTF{LOOK_MA_NO_SSL}

rabit (crypto 175)

Rabin+Bit、LSB Decryption Oracleがある。\(n = pq\)(\(p, q \equiv 3 \mod 4\))として、暗号化・復号関数をまとめると、

$$ \begin{align} Enc(m) &:= m^2 \mod n\newline Dec( c ) &:= \sqrt{c} \mod n \end{align} $$

となる。オラクルは存在するが、これはLSBを返す(つまりmod 2)ようなオラクルで、しかもBlum数の特性を用いて平方剰余の計算をしているため、場合によっては想定しない値になる可能性がある。

ここでRSAの時を考える。LSBがわかっている時、RSA least significant bit oracle attack - Cryptography Stack Exchange にあるように二分探索によって\(m\)を探すことができる。では、Rabin暗号ではどうだろうか。その前に少し性質について調べる。

ある\(a\)について、\(\left(\frac{a}{p}\right) = 1\)かつ\(\left(\frac{a}{q}\right) = 1\)ならば\(Dec(Enc(a)) = a \mod n\)

ある\(a\)について、\(\left(\frac{a}{p}\right) = -1\)かつ\(\left(\frac{a}{q}\right) = -1\)ならば\(Dec(Enc(a)) = -a \mod n\)

それ以外の場合(Jacobi記号\(\left(\frac{a}{n}\right)\)が-1と等しくなる場合)はこれ以外の2つの解がそれぞれ出る。

この問題ではどうだろうか。問題ファイル中で2が平方剰余であることが保証されているため、Jacobi記号の準同型性から\(2^k\)も平方剰余になる。このことから、暗号文を\(c\)とした時、\(Dec(Enc(2^k) c) = 2^k m\)となり、先のRSA LSB Attackを適用することが可能になる。

以上を実装し、フラグを得た。

Flag: PCTF{LSB_is_4ll_y0u_ne3d}

感想

Crypto275を解きたかった。