Short padding + known prefix RSA attack Suppose I have a message in the form of:

$m = \text{prefix} \mathbin\| \text{secret} \mathbin\| \text{padding}$

We have:


$e=3$
$n$
$n_\text{padding}$ (length of the random padding, &lt;$1/4$ of $m$)
$\text{prefix}$, which is small, only 5 bytes


Is there a way to recover the message with these parameters? I thought about using a variant of Coppersmith but didn't come across anything satisfactory that seemed to work using what I have.
So after some more help and an extensive reboot of my math skills, I found the answer. The information that I overlooked but is crucial to have is the total length of the message. Moreover, we also need a second message with slightly changed parameters. This thus presupposes that an attacker has access to at least 2 known ciphertexts with known prefix and that both ciphertexts only differ by the prefix (known) and padding (unknown).

Following the above we end up with:


$c_1$ = $(prefix_1 + secret + padding_1)^e mod \ n$
$c_2$ = $(prefix_2 + secret + padding_2)^e mod \ n$


Now, without the prefix change this would be a simple case of Coppersmith's short pad attack. But the prefix requires some changes. This is where the length comes in handy: if we know the prefix change (e.g. a 0 byte becomes a 1 byte), and we know the total length, we can find the additional delta between the 2 ciphertexts (i.e. the delta besides from the padding), since we know which bits changed and can then add/substract $2^i$ for all changed $bit_i$

Example: if 

$prefix_1$ = 'hello\x00'

$prefix_2$ =   'hello\x01'

and the total message length (including secret and padding) is 100, we know that the 94th byte changed from 0 to 1. In bits, it means the 752nd bit changed from 0 to 1, hence adding $2^{752}$.

From here we can pick up the Coppersmith attack whereby the second polynomial needs to incorporate the difference:

$g_2(x,y) = (x+y+\Delta)^e - c_2$

The rest follows the classic attack. Now once we have $y$, we can use the Franklin-Reiter related message attack with the small exception that we need to also add the $\Delta$ we calculated from the prefix.

I realize this might have gone beyond the scope of my answer but I thought it was an interesting twist on existing exploits that could help someone out in the future :)