Suppose I have a message in the form of:
$m = \text{prefix} \mathbin\| \text{secret} \mathbin\| \text{padding}$
We have:
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:
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 :)
