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

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