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, <$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.

  • $\begingroup$ What is the source of this question? $\endgroup$ – kelalaka Apr 19 at 14:55
  • $\begingroup$ Hmmmm, if we assume that the modulus size is 2048 bit (and so $n_{\text{padding}}$ is no more than 512 bits, the secret is 128 bits and prefix is 40 bits, that's a total of 660 bits; cubed, that's only 1980 bits, which is less than the modulus size. Wouldn't a simple (nonmodular) cube root recover $m$? $\endgroup$ – poncho May 20 at 13:18

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

| improve this answer | |
  • $\begingroup$ There is considerably simpler when $n$ is wide; specifically, larger than about 3 times the width of $m$. Independently: if the attack scenario supposes that the attacker gets hold of several ciphertexts for the same secret but encrypted with different prefixes as assumed in this answer, that should be clarified in the question. $\endgroup$ – fgrieu Apr 20 at 12:04
  • $\begingroup$ Correct, feel free to edit the part about a large $n$ (not the case here but good point!) $\endgroup$ – S. L. Apr 20 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.