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 😉
In the last part you hopefully learned how to encrypt and decrypt using RSA.
You have in mind the particularities of (public exponent) and (private exponent) :
You know how to extract the useful information from a PEM key file using Python or something else.
If you see a relatively small 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 persons 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.
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 (a symmetric key) over an insecure channel. She encrypts it using RSA. is chosen from strong primes and is quite big but she chose .
It wouldn’t be a problem if she had used padding but it’s obviously not the case. You intercept the message and deduce from the public key that it was computed like so :
But because is small, so it wasn’t affected by the modulo. You just need to compute the third root of 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 !
For this attack to be successful, you’ll need to capture at least ciphertexts corresponding to the same plaintext .
Suppose and thus . You’ll have to solve this system of equations :
The chinese remainder theorem tells us that a solution for (S1) exists, modulo, if . You can safely assume that this condition is satisfied because otherwise, it would be possible to compute a factor of one of the by computing .
To find a solution to (S1), you first need to define .
Because , you have where is the invert of modulo . In other words, .
You also know that because is a multiple of by definition.
Now it’s pretty simple to construct a solution to (S1) :
And because logically which means you can compute the third root of the solution you just found in order to get the original message. 😉
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) 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 😛
In practice and 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 , Fermat’s factoring algorithm can factor efficiently.
Fermat’s factoring algorithm uses the fact that :
You can now clearly see that can be factorized as such:
Fermat’s algorithm to find one of the factors works as follows :
- While is not a perfect square :
This value was taken from Pragyan CTF 2015: Weak RSA
n = 163325259729739139586456854939342071588766536976661696628405612100543978684304953042431845499808366612030757037530278155957389217094639917994417350499882225626580260012564702898468467277918937337494297292631474713546289580689715170963879872522418640251986734692138838546500522994170062961577034037699354013013
Compute the starting value for :
>>> a = gmpy.sqrt(n) >>> a mpz(12779877140635552275193974526927174906313992988726945426212616053383820179306398832891367199026816638983953765799977121840616466620283861630627224899026986L)
Then for :
>>> b = a*a-n >>> b mpz(-25559754281271104550387949053854349812627985977453890852425232106767640358612797665782734398053633277967907531599954243681232933240567723261254449797768817L)
Because it doesn’t have a square root and thus can’t be a perfect square so you increment and recalculate :
>>> a = a+1 >>> b = a*a-n >>> b mpz(285156)
Check if is a perfect square :
>>> gmpy.sqrt(b) mpz(534)
Yes it is ! That was quick ! Now you know a factor of .
>>> p = a-gmpy.sqrt(b) >>> p mpz(12779877140635552275193974526927174906313992988726945426212616053383820179306398832891367199026816638983953765799977121840616466620283861630627224899026453L)
Deduce and verify your results :
>>> q = n/p >>> q mpz(12779877140635552275193974526927174906313992988726945426212616053383820179306398832891367199026816638983953765799977121840616466620283861630627224899027521L) >>> hex(p) '0xf402bcfd15d8effffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe15' >>> hex(q) '0xf402bcfd15d8f0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000241' >>> p*q == n True
That’s it ! 😀
Sometimes you’ll encounter public keys that have a relatively big public exponent compared to the modulus. You can see from (P3) that if is big, then will probably be quite small. It’s this flaw that Wiener’s attack exploits.
The simplified conditions for this attack are :
(C3) with Public key not too large
Of course you don’t know the value of but you can get a feeling of it’s size just by looking at . As for the second condition, that’s almost always the case.
Starting from (P3) you can show that :
That’s the definition of the modulo
Consider Legendre’s theorem related to Diophantine approximations. This theorem tells you that has to be a convergent of .
From the last equation, would be which is problematic because you don’t know . Instead you can make the approximation that .
Now you have :
Starting from the definition of you get this :
But from (C2) you get :
(C2) multiplied by p
(C2) multiplied by q
Hence, . Replace this result in (E2) and you obtain :
Now back to (E1), you want to do some magic so you can use (E3) :
Put everything on the same denominator
From (P3) and the definition of the modulo
Because |1-X| = |X-1| < |X|
(E4) From (E3)
From (P1) you know that :
From (P3) and the definition of the modulo
Replacing in (E4) gives you :
For the last step you start again from (C1) :
Finally you obtain :
Which is exactly what is needed in order to use the theorem.
The first thing you need to do is find the continued fractions expansion of and then the convergents .
If you have in your possession a ciphertext that you want to decrypt, you could stop there and try every until you succeed. But if you don’t, you’ll have to work your way until and by doing the following :
For each convergents, you calculate . This comes from (P3).
Next, you solve the equation .
The roots you find should be and . You can verify that by multiplying them and comparing with . If it doesn’t produce just do the same for the next convergent until you find , and .
For this example I’ll be using the same values as the one on Wikipedia. Don’t blame me for that 🙂
The continued fraction expansion of 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 :
Starting from the first one () you assume and .
Now you can solve the equation :
Which gives you the two roots : and .
Check if it’s indeed the factorization of :
>>> 239*379 90581
Yes it is ! You found , and 🙂
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 understood how the attack works 😉
As you can tell, today’s topic was mainly oriented towards the choice of .
Choosing 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 is also a bad practice because then will be small and easily found using Wiener’s attack.
The choice of is not the only thing you need to care about. and 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 are too close.
There are other conditions to respect when choosing the factors of the modulus, but I reserve them for an other article 😉