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