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