Before diving right into more advanced attacks, let’s take a minute to do a quick recap because it’s been a long time since the last part. Once your mind is warmed up you can safely move on.
On the program today you have :
- Small public exponent
- Hastad broadcast attack
- Fermat’s attack
- Wiener’s attack
Spoiler: There will be Maths 😉
Recap#
In the last part you hopefully learned how to encrypt and decrypt using RSA.
$c = m^e \mod n$ and $m = c^d \mod n$
You have in mind the particularities of $e$ (public exponent) and $d$ (private exponent) :
\begin{align} & 1 < e < \varphi(n) \\ & gcd(e, \varphi(n)) = 1 \\ & de \equiv 1 \mod \varphi(n) \end{align}
You know how to extract the useful information from a PEM key file using Python or something else.
If you see a relatively small $n$ you have the reflex to look it up in factorDB to see if it’s the product of known primes.
You remember that using a common modulus between multiple person is a bad practice, because an external attacker can intercept two identical messages and decrypt them. And because that’s not enough, an internal attacker can compute the private key of every other person in the network.
Finally, if you ever encounter a picky decipher oracle that doesn’t want to decipher a particular ciphertext, you’ll be able to impose your will like a boss by abusing the maleability of RSA.
That’s it for the recap. Time to move on to the real part !
Small public exponent#
Let’s say Alice wants to share a small message $m$ (a symmetric key) over an insecure channel. She encrypts it using RSA. $n$ is chosen from strong primes and is quite big but she chose $e=3$.
It wouldn’t be a problem if she had used padding but it’s obviously not the case. You intercept the message and know that it was computed like this :
$c = m^3 \mod n$
But because $m$ is so small, $m^3 < n$ so it wasn’t affected by the modulo. You just need to compute the third root of $c$ to get the original message.
Hastad’s Broadcast Attack#
This attack is based on small public exponent like the previous one, but this time the message is longer so you can’t apply the same technique. However, the victim has sent the same message to multiple people using the same $e$ !
For this attack to be successful, you’ll need to capture at least $e$ ciphertexts corresponding to the same plaintext $m$.
Suppose $e=3$ and let $M = m^3$. You’ll have to solve this system of equations :
\begin{equation} \begin{cases} M \equiv c_1 \mod n_1 \\ M \equiv c_2 \mod n_2 \\ M \equiv c_3 \mod n_3 \end{cases} \end{equation}
The chinese remainder theorem tells us that a solution for $(4)$ exists, modulo $N = \prod_{i=1}^e n_i = n_1*n_2*n_3$, if $GCD(n_i, n_j) = 1, (i \neq j)$. You can safely assume that this condition is satisfied because otherwise, it would be possible to compute a factor of one of the $n_i$ by computing $GCD(n_i, n_j)$.
To find a solution to $(4)$, you first need to define $N_i = \frac{N}{n_i}$.
Because $GCD(N_i, n_i)=1$, you have $u_i*N_i + v_i*n_i = 1$ where $u_i$ is the invert of $N_i$ modulo $n_i$. In other words, $u_iN_i \equiv 1 \mod n_i$.
You also know that $u_iN_i \equiv 0 \mod n_j, (j \neq i)$ because $N_i$ is a multiple of $n_j$ by definition.
Now it’s pretty simple to construct a solution to $(4)$ :
$M \equiv \sum_{i=1}^e c_iu_iN_i \mod N$
And because $m < n_i$ logically $m^3 < N$ which means you can compute the third root of the solution you just found in order to get the original message. 😉
Example
The numbers for this example are taken from Qiwi CTF 2016.
import gmpy
e = 3
n1 = 95118357989037539883272168746004652872958890562445814301889866663072352421703264985997800660075311645555799745426868343365321502734736006248007902409628540578635925559742217480797487130202747020211452620743021097565113059392504472785227154824117231077844444672393221838192941390309312484066647007469668558141
n2 = 98364165919251246243846667323542318022804234833677924161175733253689581393607346667895298253718184273532268982060905629399628154981918712070241451494491161470827737146176316011843738943427121602324208773653180782732999422869439588198318422451697920640563880777385577064913983202033744281727004289781821019463
n3 = 68827940939353189613090392226898155021742772897822438483545021944215812146809318686510375724064888705296373853398955093076663323001380047857809774866390083434272781362447147441422207967577323769812896038816586757242130224524828935043187315579523412439309138816335569845470021720847405857361000537204746060031
c1 = 64830446708169012766414587327568812421130434817526089146190136796461298592071238930384707543318390292451118980302805512151790248989622269362958718228298427212630272525186478627299999847489018400624400671876697708952447638990802345587381905407236935494271436960764899006430941507608152322588169896193268212007
c2 = 96907490717344346588432491603722312694208660334282964234487687654593984714144825656198180777872327279250667961465169799267405734431675111035362089729249995027326863099262522421206459400405230377631141132882997336829218810171728925087535674907455584557956801831447125486753515868079342148815961792481779375529
c3 = 43683874913011746530056103145445250281307732634045437486524605104639785469050499171640521477036470750903341523336599602288176611160637522568868391237689241446392699321910723235061180826945464649780373301028139049288881578234840739545000338202917678008269794179100732341269448362920924719338148857398181962112
N = n1*n2*n3
N1 = N/n1
N2 = N/n2
N3 = N/n3
u1 = gmpy.invert(N1, n1)
u2 = gmpy.invert(N2, n2)
u3 = gmpy.invert(N3, n3)
M = (c1*u1*N1 + c2*u2*N2 + c3*u3*N3) % N
m = gmpy.root(M,e)[0]
print hex(m)[2:].rstrip("L").decode("hex")
The code follows the exact same steps as described above, with the same notations so I’m not commenting more about it. If you run it, it spits you the flag right away.
And no, I’m not writing the output. If you’re curious, run the script for yourself. 😜
Fermat’s attack#
In practice $p$ and $q$ must have the same bit length for a strong RSA key generation, but choosing too close primes can also completely ruin the security.
In fact if $p-q < n^{\frac{1}{4}}$, Fermat’s factoring algorithm can factor $n$ efficiently.
Fermat’s factoring algorithm uses the fact that :
$n = pq = {(\frac{q-p}{2})}^2-{(\frac{p+q}{2})}^2 = x^2 - y^2$
with :
$$ \begin{cases} x =\frac{q-p}{2} \\ y =\frac{p+q}{2} \end{cases} $$
You can now clearly see that $n$ can be factorized as such:
$n = (x+y)(x-y)$
Fermat’s algorithm to find one of the factors works as follows :
- $a = \sqrt{n}$
- $b = a*a-n$
- While $b$ is not a perfect square :
- increment $a$
- $b = a*a-n$
- return $a - \sqrt(b)$
Example
This value was taken from Pragyan CTF 2015: Weak RSA
n = 163325259729739139586456854939342071588766536976661696628405612100543978684304953042431845499808366612030757037530278155957389217094639917994417350499882225626580260012564702898468467277918937337494297292631474713546289580689715170963879872522418640251986734692138838546500522994170062961577034037699354013013
Compute the starting value for $a$ :
a = gmpy.sqrt(n)
a
# mpz(12779877140635552275193974526927174906313992988726945426212616053383820179306398832891367199026816638983953765799977121840616466620283861630627224899026986L)
Then for $b$ :
b = a*a-n
b
# mpz(-25559754281271104550387949053854349812627985977453890852425232106767640358612797665782734398053633277967907531599954243681232933240567723261254449797768817L)
Because $b < 0$ it doesn’t have a square root and thus can’t be a perfect square so you increment $a$ and recalculate $b$ :
a = a+1
b = a*a-n
b
# mpz(285156)
Check if $b$ is a perfect square :
gmpy.sqrt(b)
# mpz(534)
Yes it is ! That was quick ! Now you know a factor of $n$.
p = a-gmpy.sqrt(b)
p
# mpz(12779877140635552275193974526927174906313992988726945426212616053383820179306398832891367199026816638983953765799977121840616466620283861630627224899026453L)
Deduce $q$ and verify your results :
q = n/p
q
# mpz(12779877140635552275193974526927174906313992988726945426212616053383820179306398832891367199026816638983953765799977121840616466620283861630627224899027521L)
hex(p)
# '0xf402bcfd15d8effffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe15'
hex(q)
# '0xf402bcfd15d8f0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000241'
p*q == n
# True
That’s it ! 😁
Wiener’s attack#
Sometimes you’ll encounter public keys that have a relatively big public exponent compared to the modulus. You can see from $(3)$ that if $e$ is big, then $d$ will probably be quite small. It’s this flaw that Wiener’s attack exploits.
The simplified conditions for this attack are :
\begin{align} & d < \frac{1}{3}n^{\frac{1}{4}} \\ & q<p<2q \\ & e < n^{\frac{3}{2}} \end{align}
$(7)$ states that the public exponent should not be too large
Of course you don’t know the value of $d$ but you can get a feeling of it’s size just by looking at $e$. As for condition $(6)$, that’s almost always the case.
The proof#
Starting from $(3)$ you can show that :
$ed = k*\varphi(n)+1$ That’s the definition of the modulo
$|{ed-k*\varphi(n)}|=1$
$|{\frac{e}{\varphi(n)}-\frac{k}{d}}|=\frac{1}{d*\varphi(n)}$
Consider Legendre’s theorem related to Diophantine approximations. This theorem tells you that $\frac{k}{d}$ has to be a convergent $\frac{p_m}{q_m}$ of $\alpha$.
From the last equation, $\alpha$ would be $\frac{e}{\varphi(n)}$ which is problematic because you don’t know $\varphi(n)$. Instead you can make the approximation that $\varphi(n) = n$.
Now you have :
\begin{equation} |{\frac{e}{n}-\frac{k}{d}}| \end{equation}
Starting from the definition of $\varphi(n)$ you get this :
$\varphi(n) =(p-1)(q-1) =n - p -q +1$
$n - p - q < \varphi(n)$
\begin{equation} | n - \varphi(n)| < p + q \end{equation}
But from $(6)$ you get :
$n <p^2<2n$ $(6)$ multiplied by p
$p^2<2n$
$p<\sqrt{2}\sqrt{n}<2\sqrt{n}$
and :
$q^2<n$ $(6)$ multiplied by q
$q < \sqrt{n}$
Hence, $p+q < 3\sqrt{n}$. Replace this result in $(9)$ and you obtain :
\begin{equation} | n - \varphi(n)| <3\sqrt{n} \end{equation}
Now back to $(8)$, you want to do some magic so you can use $(10)$ :
$|{\frac{e}{n}-\frac{k}{d}}| =|\frac{ed-kn}{nd}|$ Put everything on the same denominator
$ = |\frac{ed-k*\varphi(n)-kn+k*\varphi(n)}{nd}| =|\frac{1-k(n-\varphi(n))}{nd}|$ From $(3)$ and the definition of the modulo
$|{\frac{e}{n}-\frac{k}{d}}| < |\frac{k(n-\varphi(n))}{nd}|$ Because |1-X| = |X-1| < |X|
From $(10)$ :
\begin{equation} |{\frac{e}{n}-\frac{k}{d}}| < |\frac{3k\sqrt{n}}{nd}| \end{equation}
From $(1)$ you know that :
$e < \varphi(n)$
$ke < k*\varphi(n)$
$ke < ed - 1 < ed$ From $(3)$ and the definition of the modulo
$k < d$
$k < \frac{1}{3}n^{\frac{1}{4}}$ From $(5)$
Replacing $k$ in $(11)$ gives you :
$|{\frac{e}{n}-\frac{k}{d}}| < |\frac{3*\frac{1}{3}n^{\frac{1}{4}}*\sqrt{n}}{nd}|$
$|{\frac{e}{n}-\frac{k}{d}}| < |\frac{n^{\frac{1}{4}}}{d\sqrt(n)}|$
$|{\frac{e}{n}-\frac{k}{d}}| < |\frac{1}{d*n^{\frac{1}{4}}\sqrt{n}}| < |\frac{1}{d*n^{\frac{1}{4}}}|$
For the last step you start again from $(5)$ :
$d<\frac{1}{3}n^{\frac{1}{4}}$
$2d<3d<n^{\frac{1}{4}}$
Finally you obtain :
$|{\frac{e}{n}-\frac{k}{d}}| < |\frac{1}{2d^2}|$
Which is exactly what is needed in order to use the theorem.
The attack#
The first thing you need to do is find the continued fractions expansion of $\frac{e}{n}$ and then the convergents $\frac{k}{d}$.
If you have in your possession a ciphertext that you want to decrypt, you could stop there and try every $d$ until you succeed. But if you don’t, you’ll have to work your way until $p$ and $q$ by doing the following :
For each convergents, you calculate $\varphi(n) = \frac{ed-1}{k}$. This comes from $(3)$.
Next, you solve the equation $x^2 - ((n-\varphi(n))+1)x + n = 0$.
The roots you find should be $p$ and $q$. You can verify that by multiplying them and comparing with $n$. If it doesn’t produce $n$ just do the same for the next convergent until you find $p$, $q$ and $d$.
Example
For this example I’ll be using the same values as the one on Wikipedia. Don’t blame me for that.🙂
You have $(n, e) = (90581, 17993)$
The continued fraction expansion of $\frac{e}{n}$ is :
[0, 5, 29, 4, 1, 3, 2, 4, 3]
You can get that from WolframAlpha or do your own script.
From that you calculate the convergents or you directly ask WolframAlpha again :
$\{0, \frac{1}{5},\frac{29}{146},\frac{117}{589},\frac{146}{735},\frac{555}{2794},\frac{1256}{6323},\frac{5579}{28086},\frac{17993}{90581}\}$
Starting from the first one ($\frac{1}{5}$) you assume $k=1$ and $d=5$.
Hence, $\varphi(n) = \frac{ed-1}{k} =\frac{17993*5-1}{1} = 89964$.
Now you can solve the equation :
$x^2 - ((n-\varphi(n))+1)x + n = 0$
$x^2 - ((90581-89964)+1)x + 90581 = 0$
$x^2 - 618x + 90581 = 0$
Which gives you the two roots : $x_1 = 239$ and $x_2 = 379$.
Check if it’s indeed the factorization of $n$ :
239*379
# 90581
Yes it is ! You found $q = 239$, $p = 379$ and $d = 5$. 🙂
For such small values it’s easy to do it by hand with the help of online tools but for real CTF tasks it’s better to make a script. Or use one already made, now that you understand how the attack works. 😉
Conclusion#
As you can tell, today’s topic was mainly oriented towards the choice of $e$.
Choosing $e$ really small is not bad if you use padding and only send your message to one person. But if it’s not the case, you saw that recovering the original message is not too difficult. On the opposite, using a big $e$ is also a bad practice because then $d$ will be small and easily found using Wiener’s attack.
The choice of $e$ is not the only thing you need to care about. $p$ and $q$ should also satisfy some conditions in order to avoid security issues. Fermat’s factorization method is really useful when you intuitively think that the factors of $n$ are too close.
There are other conditions to respect when choosing the factors of the modulus, but I reserve them for an other article. 😉