Posts

Attacking RSA for fun and CTF points – part 3

Posted on by ENOENT in Posts

Today the focus is on oracles ! You already encountered the decipher oracle in part 1 but now you’ll meet :

  1. The LSB oracle
  2. The padding oracle

Parity Oracle

Also called LSB Oracle, this oracle returns the last bit of the decrypted result.

Someday you might encounter an RSA decryption service (you know, round the street…) that doesn’t give you a decrypted plaintext but rather an information on its last bit (1,0, even, odd).
At this point you might be wondering: “WTF ? Encountering a decryption service is already not common but encountering one that gives you only the last bit is completely bullshit !”
And you’re right ! 🙂 LSB oracles don’t exist in real life, but they do in CTFs.
Here is how you can abuse such a device to decrypt a ciphertext.

You have in your possession a ciphertext c wich is, as you already know, computed from the plaintext p as such :

    \[c = p^e[n]\]

Sending c to the oracle, you’ll get a 1 or a 0.

n is the product of 2 primes. Primes are all odd numbers (except “2” but it would be the dumbest choice of factor for n) and thus n is also odd.
Even if you don’t know p, you know that 2p is even. For 2p[n] there are 2 cases :

(C1)    If 2p < n the modulo doesn’t come into play and the result is even.
(C2)    If 2p > n the remainder will be odd because n is odd.

If an attacker has a way of sending the ciphertext of 2p to the server, he can deduce from the parity of the result, an interval in which p is located.
Sending the ciphertext of 2p without knowing p is easy, you already saw that in part 1 with the decipher oracle.
Let’s say you made the server decrypt 2p and the result is odd. You know from (C2) that p must be contained in the interval \frac{n}{2} < p < n
Now you can call the oracle again on 4p and get maybe a result that is even. So 2(2p-n) < n. Remember, the step before was (C2) so the modulo came into play. You need to subtract n from the result otherwise it would be too big. From this, you deduce :

    \[2(2p-n) < n\]

    \[(2p-n) < \frac{n}{2}\]

    \[2p < \frac{3n}{2}\]

    \[p < \frac{3n}{4}\]

The previous interval can be further restricted :

    \[\frac{n}{2} < p < \frac{3n}{4}\]

Multiply again the plaintext by 2 and repeat until the interval gives only one possibility for p.

As you may have noticed, it’s a dichotomic search which has a complexity of O(log2(n)). This means you can fully recover p in log2(n) steps.

Example

This is the code for the LSB oracle I used in this example. The code is restricted to the bare minimum for better readability but keep in mind that it’s just a POC.
If you want to implement this attack for yourself, you’ll find the keys I used here.
I give you the private key because the oracle needs it obviously, but you as the attacker only know the public key.

# -*- coding: utf-8 -*-
# openssl genrsa -des3 -out private.pem 2048
# openssl rsa -in private.pem -outform PEM -pubout -out public.pem
# openssl rsa -in private.pem -out privateKey.pem -outform PEM

import socket
from Crypto.Cipher import PKCS1_v1_5
from Crypto.PublicKey import RSA

HOST = 'localhost'   # Symbolic name, meaning all available interfaces
PORT = 8001 # Arbitrary non-privileged port

# Encrypt the secret
# message = open("flagLSB.txt","r").read()
# key = RSA.importKey(open('public.pem').read())
# cipher = PKCS1_v1_5.new(key)
# ciphertext = cipher.encrypt(message)
# print ciphertext.encode("hex")
ciphertext = "6db9c3f7ddd92dc62cb46816379b482997be56f94a2d1e8d9b798df39dfd44209dfe99c1146d08d967f1ae5a36e77581b114dde298cb6d09c277156f566e055605027a8cf4231886256b3ef38854101312110f563d7b9dd9e475531934f9414772bee51dad948b50d0c075226127e0973bc1aa77b3c064cb2ab06b7a08ea919370a399d65ee1a4d504b48d7a9f23e3ba609a2d8f86ca351059cf4e552962ba2830c66b9d2bacd05e035e1c6f9855ed3e29184ee371f445553dc464d08d295212ee8c4907901a0a03186f917298d571e7dde54928b5c4870b50db7a6ee743291eb76c057d5c19ca0fa06bdbe13751d85d08557fa433971c93dac9cfb9b87c0114"

def decrypt(m):
    key = RSA.importKey(open('privateKey.pem').read())
    cleartext = key.decrypt(m)
    return bin(int(cleartext.encode("hex"),16))[-1]


s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
#Bind socket to local host and port
s.bind((HOST, PORT))
#Start listening on socket
s.listen(1)
#wait to accept a connection - blocking call
conn, addr = s.accept()
#now keep talking with the client
while 1:
    data = conn.recv(1024).strip()
    conn.send(decrypt(data.decode("hex"))+"\n")

s.close()

You start by computing 2p :

>>> twop = hex(c*pow(2,e,n) % n)
0x9b875979bffba75444c3755dbfc9f8d6f98799d785b9eccd6c1965da283a346b3d08b715e102f277eca059edce4b69074401545dd6972b936f010138545897844e0388c8a6df778111201b0d202e9d9a627eca4bc4d44978406f794e9e857349cca3029663898e5579e75db1c15774da513c0e6e2742e685301b231ccd4636a6a9b3f3ed187a3b74eda06d9c418e810e905516be73afe6a89341af5edda229f88db0048d0379d9d4f95106c65370ccd97927283a7cb964c53f7c256c4af7e0b8e059614a1fbfc8615e9f599f007f04db40517e5477ae8ca2190b10e4f150328cee6300ae1dd068041f5df356a5e0cded5efc1dd40072d5707c4d66df790d7a7d

When sending this ciphertext to the server, you get 0. This means that the plaintext is located somewhere between 0 and \frac{n}{2}.

Continue with 4p:

>>> fourp = hex(c*pow(4,e,n) % n)
0xb80d49ba6d281c9a5ac23d2018db0a9e16cb4160de000b3cd0515b00782f151425e5cb15ac1b6d1940bd51a62d2cf300238721385ce4308e7c3099c629415b41e343d7c8a2c0ca27e96df370e421072a81c8774ae2817daed0905726a38f341fa012112fb410fe9ec8e6a31ca4db3ec785b25a372b88c92a34bccc541b93cc166e0d583f4fa3187b943d754e474eb5de3ac1276c783c7cd4922c7bb78397ab989b8dd2f2e54a71705e8da03da296494769f537256e305b56b2eed475ce2e5196c14146cd6192a921815d601c571422fe14e8063a43a1093714e91cb1d5ad82db7df78460372a014e69b15eaf38d4406d4b4a1d2aba5b3dd8a01bfd004ece6e10

Again, the oracle returns 0. The interval is [0, \frac{n}{4}].

Continue with 8p, 16p, … The oracle always returns 0 until 32768p.

At this point the interval is [\frac{n}{32768},\frac{n}{16384}].

32768p
cipher: 
0x439344eec5acebf452626e1bd38fe7dd46f1ce0fd2afb93dc71b41579d43b6de660630e2d0fc1e6a4aac56bb82fdf0876d458453fba3c9858b8c83a7e9b1a47d8681aa132c5720ed21509d039ea4c356c92d47e6d16c0e947ab303a893e100b40cbef054acf4aa211fd502a727d2eb08a5c598c6ed6b8d9e0019914ca10411e4d377a50e8966ed056702ea4b3afc6c711d003ba18ab0c778916ef25f442bf25bcecd1852733c819a8836b8dc34f2764835a52c5bf5fa910b00df30a8e45098e410f4b14c36d3b26ba0863b6abb151c25a50b2e7c78604cddaee4de9cfe9621e912dbd1d7d594794f6325cb6da29652c3cff15d02c84480a503975afac58902ec
oracle result: 
1
interval :
[744939576338639552605319416655330584727470339881178649724651522471672111464997534946230107837438547060367401525060505230486326415780327322508514896907718632038792675721508064933089632411534513885140447467666995030078137901097026350787078481419184700675442911060630420213934944458892878435599125730278671851573244816919776929639054346362468613463953137316574221820712808324981836567197984527608617005823855307162087776803591631721271593529749261368597159337218617904347255597726466226807461168576047838958369061329350762374664576896924958622586861919704403110793798876719883764959221007395104587086922105397849271,1489879152677279105210638833310661169454940679762357299449303044943344222929995069892460215674877094120734803050121010460972652831560654645017029793815437264077585351443016129866179264823069027770280894935333990060156275802194052701574156962838369401350885822121260840427869888917785756871198251460557343703146489633839553859278108692724937226927906274633148443641425616649963673134395969055217234011647710614324175553607183263442543187059498522737194318674437235808694511195452932453614922337152095677916738122658701524749329153793849917245173723839408806221587597753439767529918442014790209174173844210795698542]

Continue like this until the end to get the flag hidden in this example 😉

Bleichenbacher’s Attack on Padding Oracle

The LSB oracle is not something you’ll encounter in real life. But the padding oracle is based on real world cryptographic issues !
In fact it was discovered in 1998 by Daniel Bleichenbacher. It affected SSL which used PKCS#1 v1.5 padding and returned error messages when the padding was wrong.
This knowledge allowed an attacker to decrypt previously encrypted packets by sending forged packets to the server.
More recently, in 2017, this attack was rediscovered and named ROBOT (Return Of Bleichenbacher’s Oracle Threat).
It exploits the same issue but in TLS (SSL’s successor) after bypassing the security measures that were taken to mitigate this attack.
You’ll see how knowing that the padding is wrong can help you decrypt a given ciphertext.

A plaintext has to respect those conditions to be PKCS conforming :

(C3)    Be as long as the key size (256 bytes in case of RSA 2048)
(C4)    The first 2 bytes should be 00 and 02 (Not true for signatures, but we are interested in encryption)
(C5)    Padding should not contain any null bytes because it’s what delimits the data from the padding
(C6)    The padding should end with a null byte

If a ciphertext produces a PKCS conforming plaintext, we say that the ciphertext is PKCS conforming.

I’ll use the same notations/titles as in the original document to avoid confusing the reader who wants more detailed explanations.

k is the length of n in bytes.

Let’s first define a constant B = 2^{8(k-2)} which will be equal to 0x000100…
The first 2 bytes here are important : 00 and 01.

The attacker will produce ciphertexts by choosing numbers s and computing c' = c*s^e.
When the oracle decrypts it, it gets m*s.
Where m is the original plaintext. The one you want to recover.

If m*s is PKCS conforming (and hence c') then you know from (C4) that :

    \[2B \leq m*s < 3B\]

The idea is to reduce the interval by collecting enough information. It’s similar to the LSB oracle but instead of focusing on the LSB, it focuses on the 16 MSBs.

The attack can be split into 4 parts :

  1. Blinding
  2. Searching for PKCS conforming messages
  3. Reducing the set of solutions
  4. Compute the solution

Step 1 – Blinding

This step is quite simple. It consist in finding a s_0 such that c_0 = c*{s_0}^e is PKCS conforming.

When you already have a valid ciphertext, it’s easy to see that s_0 = 1 will work.

You now have :

    \[c_0 = c\]

    \[i = 1\]

    \[M_0 = \{[2B, 3B-1]\}\]

i is a counter to track down the process of finding the solution.
M is the list of intervals in which the solution can be.

Step 2 – Searching for PKCS conforming messages

This step is dived into 3 cases.

Starting the search

The first one is when i=1, this means that you are just starting the search. In this case, you need to find the smallest s_1 \geq \frac{n}{3B} such that c_1 = {c_0}*{s_1}^e is PKCS conforming. No need to search for smaller values because {c_0}*{s_1} would never be PKCS conforming. This step can take a lot of time so be patient. When you’ve found it, go to step 3.

When you have more than 1 interval

In this case, i > 1 and |M_{i-1}| \geq 2. You just search for the smallest s_i > s_{i-1} such that {c_0}*{s_i}^e is PKCS conforming. When you’ve found it, go to step 3.

When you have a single interval

In this case, i > 1 and |M_{i-1}| = 1. Let’s give the two boundaries names :

    \[M_{i-1} = \{[a, b]\}\]

Now search for a value of s_i such that {c_0}*{s_i}^e is PKCS conforming, respecting the condition :

    \[\frac{2B+r_i*n}{b} \leq s_i < \frac{3B+r_i*n}{a}\]

with r_i \geq 2\frac{bs_{i-1}-2B}{n}

This condition ensures that the remaining interval is divided in half each iteration. More information can be found here. When you’ve found s_i, go to step 3.

Step 3 – Reducing the set of solutions

This step is the reconstruction of the intervals with the new information gathered. The new set M_i is computed as such :

    \[M_i = \bigcup_{a,b,r}\{[max(a,[\frac{2B+r*n}{s_i}]), min(b,[\frac{3B-1+r*n}{s_i}])]\}\]

Where the symbol \bigcup means the union of the intervals.

For each interval [a,b] \in M_{i-1} and for each possible value of r in :

    \[\frac{a*s_i-3B+1}{n} \leq r \leq \frac{b*s_i-2B}{n}\]

If the resulting M_i has only one element that is an interval of length 1, go to step 4. Otherwise increment i and go to step 2.

Step 4 – Compute the solution

You are left with a single interval of length 1 :

    \[M_i = \{[a,a]\}\]

You can now compute the value of m, the original message you want to decrypt :

    \[m = a*s_0^{-1}\]

But because s_0 = 1 :

    \[m = a\]

Example

This is the code for the padding oracle I used in this example. It’s basically the same as for the LSB oracle and the keys are also the same.

# -*- coding: utf-8 -*-
# openssl genrsa -des3 -out private.pem 2048
# openssl rsa -in private.pem -outform PEM -pubout -out public.pem
# openssl rsa -in private.pem -out privateKey.pem -outform PEM

import socket
import sys
from Crypto.Cipher import PKCS1_v1_5
from Crypto.PublicKey import RSA

HOST = 'localhost'   # Symbolic name, meaning all available interfaces
PORT = 8001 # Arbitrary non-privileged port

# Encrypt the secret
# message = open("flag.txt","r").read()
# key = RSA.importKey(open('public.pem').read())
# cipher = PKCS1_v1_5.new(key)
# ciphertext = cipher.encrypt(message)
# print ciphertext.encode("hex")
ciphertext = "15f8ae5f119e46eb8b02c3d4ef1bb91f1e4ab5c7fa2edc8bc6687cc33d7d59fadb75037e481122c43a3b7d7c8841026faba1d5e7d78afc95ebf8354c15237a24d372c70217bac486a5e446428a6113510344c48145d4e63800e1fbf417e292618bdfd33f947f30bf5f2810b357aa538b4478a320bc0b0639ef18d6cb47e45823719f16d33c1a2977bf06432403f585c042a089e1e697cdf4223b75753c8f4dd8226080ec0a2b2d02e13a893d0960f0216b9b30ad26c6b412f505824b8ae02898cd155f374bff6911a1dd75cc16210dfc258b60ff8c85cfc603f4b23be93bfe4fff9b027402ac7b788473dee8abf499c228f716ae04930ef6049a3cfe8c083979"

def tryDecrypt(m):

    if m.encode('hex') == ciphertext:
        return "You can't fool me like that !"

    key = RSA.importKey(open('privateKey.pem').read())
    cipher = PKCS1_v1_5.new(key)
    cleartext = cipher.decrypt(m, "padding error")
    return cleartext


s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
#Bind socket to local host and port
s.bind((HOST, PORT))
#Start listening on socket
s.listen(1)
#wait to accept a connection - blocking call
conn, addr = s.accept()
#now keep talking with the client
while 1:
    data = conn.recv(1024).strip()
    conn.send(tryDecrypt(data.decode("hex"))+"\n")
s.close()

You can skip step 1 because s_0 = 1.
Now you search for s_1 like in step 2, after 45 minutes of computing, you finally get s_1 = 163318

Now you re-calculate the intervals like in step 3, you should get |M_1| = 3. Because of that, you go back to the proper case of step 2. Be patient, this step also takes several minutes to complete but you should get s_2 = 199611

After re-calculating the intervals, you should have only one interval left. But its length is not equal to 1 so go back to step 2. From now on, each iteration should be completed in less than a second.

Even so every iteration is very fast, the whole process will still take around 5 more minutes to completely recover the plaintext.

You’ll see that as the value of s_i grows, the length of the interval in M_i shrinks.

Here are some more values for the next iterations :

    \[s_3 = 399221\]

    \[|M_3| = 1\]

    \[s_4 = 852880\]

    \[|M_4| = 1\]

    \[s_5 = 1705759\]

    \[|M_5| = 1\]

    \[s_6 = 3484102\]

    \[|M_6| = 1\]

    \[s_7 = 7004496\]

    \[|M_7| = 1\]

If your algorithm is correct, you should be able to find the flag for this example 😉

Conclusion

As you saw with the LSB oracle, the least significant bit of an RSA encrypted message is as secure as the entire message. This has been extended to prove that all RSA bits are secure. Bleichenbacher’s attack against padding oracles uses this property in an optimised way in order to minimise the number of chosen ciphertext needed to recover the plaintext.

I highly recommend you try implementing these attacks for yourself if you’re interested.
Feel free to send me a message on Twitter if you did, I’ll be happy to hear from you 🙂

5 thoughts on “Attacking RSA for fun and CTF points – part 3”

  1. Salut, sur la partie de l’attaque de Bleichenbacher avec un padding oracle, il me semble qu’il manque la clé publique pour qu’on puisse retrouver les valeurs intermédiaires et le flag ^^

    Reply

  2. There is an error in formula for r_i in Step2 “when you have single interval” (r_i \geq 2\frac{b_{s_{i-1}}-2B}{n}).
    b is multiplied with previous s (s_{i-1}), but in the formula is written “b index s_{i-1}”.
    Correct formula should be like r_i \geq 2\frac{b {s_{i-1}}-2B}{n}

    Reply
  3. Pingback: RSA in CTF – Quân

Leave a Reply

Your email address will not be published. Required fields are marked *