Overview

In 1998 Daniel Bleichenbacher showed an efficient way to recover RSA encrypted messages via an adaptive chosen ciphertext attack. Specifically, these messages must be padded according to the PKCS#1 v1.5 standard for this attack to work. If this is the case then all that is needed to decrypt a message is an oracle (or a black box program if you like) that indicates whether or not a ciphertext decrypts to a message with PKCS#1 v1.5 compliant padding. You are free to submit as many ciphertexts as you like to the oracle in this attack. We have set up an oracle that you can submit ciphertexts to at the following location:

https://id0-rsa.pub/problem/pkcs15-oracle/[ciphertext]/

Your solution should be in the form of an ASCII encoded string. (Note depending on server response time the network may be a bottleneck in this case, it might take a couple of minutes, ~10 on my machine, to solve this one).

Attack Details

The original paper documenting the attack can be found here, and a good overview of the attack is given here. Hint: This attack uses a small RSA modulus (384 bit) therefore there will likely be no need to handle the multi-interval case (step 2b from the paper).

Parameters

The parameters in this case are the 384 bit RSA public key and the target ciphertext. There will be no need to recover the private key in this attack, in fact the whole point of this attack is to use the padding oracle to recover the original message.

N = 0x4c81390477e071a7a9afd85eeb93f3596cf69fb8e7fadf422f22c68891586611af5e74aa8b4df9a585486898f632ae63
e = 0x3
ciphertext = 0x1cb75d15d80c8bd7572281de5da592a428db429870b4a654b8722f98acc220b6701f6c0b7313fb9ef4ca15a87d9273bb

Oracle Usage

The oracle endpoint should be accessed via a GET request and the [ciphertext] value should contain only digits in the range 0-9. The HTTP response to the request above will be a 1 if the ciphertexts decryption has valid padding, or a 0 if the padding is invalid. An example (in python2) is below:

from urllib2 import urlopen

baseurl = 'https://id0-rsa.pub/problem/pkcs15-oracle/'
ctxt = 11223344556677889900
response = int(urlopen(baseurl + str(ctxt)).read())

Solution