RSA padding oracle hands-on

8 thoughts on “RSA padding oracle hands-on”

1. 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. 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. 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. 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:

   print '%0256x' % partial((y*enctwo)%n,n) # print the result in hexadecimal
   

   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[0]),16)
   
   if (rr % 2) == 0:
       print 'OK'
   else:
       print 'Sorry, only an even number of eggs can be ordered'
   

5. 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. 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. 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. 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.

Comments are closed.