Attacking RSA for fun and CTF points - part 3

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 that doesn’t give you a decrypted plaintext but rather an information on its last bit (1,0, even, odd). 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 $m$ as such : \[c = m^e \mod 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 $m$, you know that $2m$ is even. For $2m \mod n$ there are 2 cases :

1. If $2m < n$, the modulo doesn’t come into play and the result is even.
2. If $2m > n$, the remainder will be odd because $n$ is odd.

If an attacker has a way of sending the ciphertext of $2m$ to the server, he can deduce from the parity of the result, an interval in which $m$ is located. Sending the ciphertext of $2m$ without knowing $m$ is easy, you already saw that in part 1 with the decipher oracle.

Let’s say you made the server decrypt $2m$ and the result is odd. You know from condition 2 that $m$ must be contained in the interval $\frac{n}{2} < m < n$. Now you can call the oracle again on $4m$ and get maybe a result that is even. So $2(2m-n) < n$. Remember, the step before was $2m > n$ 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(2m-n) < n\] \[(2m-n) < \frac{n}{2}\] \[2m < \frac{3n}{2}\] \[m < \frac{3n}{4}\] The previous interval can be further restricted : \[\frac{n}{2} < m < \frac{3n}{4}\] Multiply again the plaintext by 2 and repeat until the interval gives only one possibility for $m$.

As you may have noticed, it’s a dichotomic search which has a complexity of $O(log2(n))$. This means you can fully recover $m$ 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 $2m$ :

twom = 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 $4m$:

fourm = hex(c*pow(4,e,n) % n)
# 0xb80d49ba6d281c9a5ac23d2018db0a9e16cb4160de000b3cd0515b00782f151425e5cb15ac1b6d1940bd51a62d2cf300238721385ce4308e7c3099c629415b41e343d7c8a2c0ca27e96df370e421072a81c8774ae2817daed0905726a38f341fa012112fb410fe9ec8e6a31ca4db3ec785b25a372b88c92a34bccc541b93cc166e0d583f4fa3187b943d754e474eb5de3ac1276c783c7cd4922c7bb78397ab989b8dd2f2e54a71705e8da03da296494769f537256e305b56b2eed475ce2e5196c14146cd6192a921815d601c571422fe14e8063a43a1093714e91cb1d5ad82db7df78460372a014e69b15eaf38d4406d4b4a1d2aba5b3dd8a01bfd004ece6e10

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

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

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

# 32768m
# 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 usually 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 :

1. Be as long as the key size (256 bytes in case of RSA 2048).
2. The first 2 bytes should be \x00\x02 (Not true for signatures, but we are interested in encryption).
3. Padding should not contain any null bytes, because it’s what delimits the data from the padding.
4. 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 paper 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 : \x00\x01.

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 condition 2 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. Computing 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 divided 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 - Computing 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 if 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 🙂