RSA padding oracle hands-on

I’ve published a hands-on guide to Padding Oracle Attacks on RSA that appears in Hakin9 – Defend Yourself! Hands-on Cryptography. It is a practical experience on how to break RSA using a side-channel and contains references to our recent results on real devices. Author: riccardo

I am Associate Professor in Computer Science at the University Ca' Foscari of Venice. My main research interest is computer and network security, from foundations to practical aspects. I coordinate the secgroup@cafoscari.

8 thoughts on “RSA padding oracle hands-on”

1. Cheng Chen says:

Hi,

I am reading your paper “Practical Padding Oracle Attacks on RSA” and “Efficient Padding Oracle Attacks on Cryptographic Hardware”.

I have reproduced the experiments of your paper on standard PKCS oralce (FFT oracle) and found that the most overhead (calls of padding oralces) is dertermined by the step2a phase, where the algorithm tries to find the first s making a conforming ciphertext. However, in the trimming phase, some coprime integer pair (u,t) can be easily found. And a conforming ciphertext can be generated from it. My question is why s can be directly generated by (u/t). Because it is so fast to find (u,t) to make a conforming ciphertext.

2. riccardo says:

thanks a lot for your comment. Unfortunately you cannot do so since you want s1 to be as much small as possible because a small s1 will give fewer intervals (values of r) at next step. If you try with trimmers you will get a very big value and a huge amount of intervals to deal with (requiring too much memory and iterations).

I’ve tried on a real implementation and I get this number of intervals:

1313027833876878913828657212759882127145441754844455461740132661417687359213790300735017998474183646
8888544215742760443912883993512429420159530888605366817301081250879891341615993695108868297422362033
4296751537966920003570433704860723494650268784139840387231261682301450687043675217203146880618305178

that it’s clearly not possible to deal with. This is why you need to start from the smallest possible s1 and proceed sequentially.

3. saroj says:

Hi,
I have read your paper ”Practical Padding Oracle Attacks on RSA”, I found it interesting and hence decided to implement it.

I am finding some issues while implementing the portion
“3. A simple parity side-channel”,

In the python code parity.py inside the function:

def partial(y,n):
k = int(math.ceil(math.log(n,2)))  # n. of iterations
getcontext().prec = k    # allows for 'precise enough' floats
l=Decimal(0)
u=Decimal(n)
for _ in range(k):
h = (l+u)/2
if parity(y,n):
u = h            # we get the left interval
else:
l = h            # we get the right interval
y=(y*enctwo) % n     # multiply y by the encryption of 2
return int(u)

I feel that y=(y*enctwo) % n statement should follow immediately after the for loop because we should multiply the cipher text(y) with the “enctwo = (2 ** e) % n” and after that we should run the if statement.

And more significantly I am not being able to find the ./EEGGs ” program code.

So can u kindly send me the program / link so that I can continue with my work.

I would be grateful if you could kindly explain me the reason why you did that way and whether the logic that I am pondering over is correct or not.

4. riccardo says:

Hi,

it is indeed necessary to multiply by enctwo before the branch but notice that in the script I invoke partial on value y*enctwo. This does the trick:

You can implement EEGGs in different ways. Here is a simple python code that invokes openssl:

#!/usr/bin/python

from subprocess import *
from binascii import *
import sys

p = Popen(['/usr/bin/openssl','rsautl','-decrypt','-inkey','key','-raw'], stdout=PIPE)

r = p.communicate()

rr = int(hexlify(r),16)

if (rr % 2) == 0:
print 'OK'
else:
print 'Sorry, only an even number of eggs can be ordered'

5. raviz says:

Hi,

I was trying to understand the paper and found these lines of code in narrowing the interval code snippet.

print fk % newa
print fk % newb

I couldn’t understand what fk means here? Can you please clarify?

6. riccardo says:

Thanks for your comment. fk is just a format string to print in hexadecimal. I forgot to paste it in the code. Just add the following:

k = 128 # number of bytes of modulus 128 = 1024 bits
fk = '%0'+str(k*2)+'x' # format string to print hex 0 padded

7. Jay says:

Hi,

I’m trying to understand Chapter 5 ‘The Bleichenbacher attack’, but something confuse me for several days.

‘Let m0 note this correctly padded plaintext.’
‘We now compute m1 = m0s1 mod n, with different values of s1 until we get that m1 is correctly padded’

If m0 is the plaintext what we want to get, it means we do not know the m0.
By the condition we only know n and s1 as a middle man, how can we compute ‘m1 = m0s1 mod n’?

8. riccardo says:

Hi Jay,

sorry for this late answer.

The answer to your question is in the box right before, named “Simulating the attack”. The actual multiplication is done as y1 = y0*E(s1) mod n, where y0 is the encryption of m0 and E(s1) is the encryption of s1. Since you know the public key you can compute E(s1) from s1. Then, by the multiplicative property of RSA you get that y1 = E(m0*s1 mod n). Your padding oracle will tell you whether or not mo*s1 mod n is correctly padded according to PKCS#1 v1.5.

Since you can encrypt any value and multiply it to the ciphertext in the tutorial we simulate the attack by working directly with plaintext values and by using an oracle that directly tells you compliance of those values to PKCS#1 v1.5 (you actually don’t need an oracle as you can check yourself if the format corresponds to PKCS#1). The actual implementation of course will work on ciphertexts as explained above.

I hope this clarifies.

This site uses Akismet to reduce spam. Learn how your comment data is processed.