[Crypto][Python] D.Bleichenbacher attack on RSA PKCS#1, part I

Introduction

Prerequisite: see my previous blog post about RSA blinding.

What is PKCS#1 1.5 padding? It's when your message is padded by random stuff, actually, prepended at start:

      2.  EME-PKCS1-v1_5 encoding:

          a.  Generate an octet string PS of length k - mLen - 3
              consisting of pseudo-randomly generated nonzero octets.
              The length of PS will be at least eight octets.

          b.  Concatenate PS, the message M, and other padding to form
              an encoded message EM of length k octets as

                 EM = 0x00 || 0x02 || PS || 0x00 || M.

( RFC8017 )

In plain English: zero byte, 0x02 byte, random stuff, zero byte, your message. Now we know that this padding scheme employs a 16-bit header: 0x0002.

In other words, we can say that the resulting RSA message is in between the following range: 0x00020000...0000 and 0x0002FFFF...FFFF. Can we exploit that fact? Let's see.

Test message: "Hello, world! Hola, mundo! Guten Tag!" Here I encrypt this message and decrypt it in two modes: in PKCS and 'raw'.

openssl rsautl -encrypt -pubin -inkey rsa512.pub -in test.txt -out cipher512.txt -pkcs
openssl rsautl -decrypt -inkey rsa512.pem -in cipher512.txt -out decipher512.txt -pkcs
openssl rsautl -decrypt -inkey rsa512.pem -in cipher512.txt -out decipher512_raw.txt -raw

When '-pkcs' applied, openssl removes padding and resulting file contains only ASCII string I used as plaintext. When '-raw' applied, the resulting file is:

 % xxd -g 1 decipher512_raw.txt
00000000: 00 02 01 72 f1 4a 75 d1 41 e6 0d ed 35 33 e7 3e  ...r.Ju.A...53.>
00000010: 68 14 b4 db be 64 07 6c c5 00 48 65 6c 6c 6f 2c  h....d.l..Hello,
00000020: 20 77 6f 72 6c 64 21 20 48 6f 6c 61 2c 20 6d 75   world! Hola, mu
00000030: 6e 64 6f 21 20 47 75 74 65 6e 20 54 61 67 21 0a  ndo! Guten Tag!.

You see here 00 02 header, random stuff, zero byte and the text string. That padding, including random stuff, was generated by openssl during encryption.

Let's garble random byte in cipher512.txt and try to decrypt it. This would work, openssl is silent:

openssl rsautl -decrypt -inkey rsa512.pem -in cipher512_garbled.txt -out decipher512_garbled_raw.txt -raw

But the resulting decipher512_garbled_raw.txt contains noise. Can't be decrypted. Now what if...

 % openssl rsautl -decrypt -inkey rsa512.pem -in cipher512_garbled.txt -out decipher512_garbled_raw.txt -pkcs
The command rsautl was deprecated in version 3.0. Use 'pkeyutl' instead.
RSA operation error
40C77EE8627F0000:error:0200009F:rsa routines:RSA_padding_check_PKCS1_type_2:pkcs decoding error:../crypto/rsa/rsa_pk1.c:269:
40C77EE8627F0000:error:02000072:rsa routines:rsa_ossl_private_decrypt:padding check failed:../crypto/rsa/rsa_ossl.c:500:

This is noise and openssl can't find valid 00 02 header at the start, so it returns the error.

Now think about this: openssl is silent if the decrypted plaintext message is in the 0x00020000...0000 and 0x0002FFFF...FFFF range. And it returns the 'padding check failed' error if the message is not in that range. We will use openssl as an 'oracle' or a device that will say if the decrypted message is in the range or not.

Toy Wolfram Mathematica example

This.

Here we have n=93. Small and artificial. We pretend that valid range is within 20 and 30. We have an encrypted message that is in that range, which is 24. (But we don't know the message, we only know that is is accepted by openssl, in encrypted form.)

First I multiply (unknown) message by s=2. The resulting ms message is not in range. What if s=3? Not in range. s=4? Overlapped (due to modulo division). Not in range. s=5? In range! At this moment we know that m*5 is in 20-30 range, but we still don't know m.

(Wolfram Mathematica notebook.)

See another explanation in this paper by Juraj Somorovsky (pp 17-20).

Less toyish example

Now here is a real parameters for 64-bit RSA. See how the oracle() function works. So far, it only checks for header. Before attacking, we know that the message has size of 64 bits. But the header is 16 bits. So a message must have maybe ~48 bits.

All the math (so far simple) was stolen from Somorovsky's paper.


import random, math, sys, os
import functools

HEADER_BITS=16

BITS=64
"""
p=3900617629
q=2378309513
m=0x0002112233445566
"""
e=17
n=9276876013626204677
good_c=7799333987906023269

def binlog(x):
    assert (x>0)
    return math.log(int(x), 2)

B=2**(BITS-HEADER_BITS)
_2B=2*B
_3B_1=(3*B)-1

m_min=_2B
m_max=_3B_1
s1_min=n//m_min
s1_max=n//m_max

calls_to_oracle=0

# Only header is checked
@functools.cache
def oracle(c):
    d=4911287298007382225
    plaintext=pow(c, d, n)
    return (plaintext>>(BITS-HEADER_BITS))==2

def step_1():
    t=[]
    print ("step_1() begin")
    global calls_to_oracle
    s=n // _3B_1
    #s=2
    while True:
        print("step_1. trying s", hex(s),"  \r", end="")
        rt=oracle(good_c*pow(s, e, n) % n)
        calls_to_oracle=calls_to_oracle+1
        if rt:
            print ("rt=True")
            print ("s", hex(s))
            print ("overlaps in range (inclusive): ", s//s1_min, (s//s1_max))
            for overlaps in range(s//s1_min, (s//s1_max)+1):
                lower=(_2B+n*overlaps)//s
                upper=(_3B_1+n*overlaps)//s
                if lower>=_2B and upper<=_3B_1:
                    print ("m is between:", hex(lower), hex(upper))
                    print ("lower:", hex(lower))
                    print ("upper:", hex(lower))
                    print ("binlog(diff) %.1f" % binlog(upper-lower))
                    t.append((lower, upper, s))
            return t
        s=s+1
        if s-1 == n:
            assert False

step_1()
print ("calls_to_oracle", calls_to_oracle)

step_1() begin
rt=True trying s 0x7c94
s 0x7c94
overlaps in range (inclusive):  1 2
m is between: 0x2112194233721 0x21123a2337652
lower: 0x2112194233721
upper: 0x2112194233721
binlog(diff) 33.0
calls_to_oracle 20907

We narrowed range from ~48 bits to ~33 bits. You see that 3 valid 4-bit nibbles from plaintext are already surfaced: 112. And only ~21k calls to 'oracle'.

Maybe not that impressive, but cool, ha? This step corresponds to the step 2a from the original D.Bleichenbacher's paper.


Click for the next part.

(the post first published at 20230123.)


List of my other blog posts.

Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.