2
$\begingroup$

I've read this and this but I'm not understanding why padding a message with a simple random is not secure.

For example, consider a 256 bytes modulus. We can agree that the first byte from the message is 0x00, the next $n$ bytes are the message itself and the next $m$ bytes are random bytes. We have that $1+n+m=256$. The message is then encrypted with RSA. When decrypted, one can remove the first byte and the last $m$ bytes.

The first bytes 0x00 ensures that the message is less than the modulus and the last $m$ bytes will guarantee a probabilistic encryption.

Why isn't this secure?

Improve this question
$\endgroup$
4
  • $\begingroup$ Your format is $\texttt{|0x00|message|random_bytes|}$ where LSB is on the right? $\endgroup$
    – kelalaka
    Commented Feb 1, 2019 at 19:42
  • $\begingroup$ You can say so. Is that really matters? $\endgroup$
    – mip
    Commented Feb 1, 2019 at 19:44
  • $\begingroup$ What if the message is short and If we multiply with the encryption of two, does your padding will give a warning? $\endgroup$
    – kelalaka
    Commented Feb 1, 2019 at 19:46
  • $\begingroup$ The "2" will be "absorbed" in the padding and you din't known that the message was tampered. Thank you!! $\endgroup$
    – mip
    Commented Feb 1, 2019 at 19:51

2 Answers 2

Reset to default
7
$\begingroup$

Your message format is;

$$\texttt{padded_message} =\texttt{|0x00|message|random_bytes|}$$

You did not specify what will happen if the message is short. If we assume that it is filled with zero then a short message is;

$$\texttt{|0x00|0x00...0x00|short message|random_bytes|}$$

Now there is an active attack. Since the attacker knows the public key $(n,e)$ then the attacker can modify your ciphertext $$c = E_{k_{pub}}(\texttt{padded_message})$$ by multiplying with the encryption of $2$ $$c_2 = E_{k_{pub}}(2)$$ and the result is;

$$D_{k_{prv}}(c \cdot c_2) = \texttt{|0x00|0x00...0x00|short message|r|random_bytes|0} $$

where your plaintext (short message) is shifted by one and a random bit value is assigned from MSB of the $\texttt{random_bytes}$.

The BT in The PKCS#1 v1.5 padding can prevent this attack. For a general answer, please see;

Improve this answer
$\endgroup$
4
  • $\begingroup$ RSA encryption only delivers confidentiality, correct? So this would become a problem because it could somehow leak the message afterwards? $\endgroup$
    – Maarten Bodewes ♦
    Commented Feb 2, 2019 at 1:54
  • $\begingroup$ Yes but using the attack that @kelalaka explained we could modify the hash of a document that was sign with the private key $\endgroup$
    – mip
    Commented Feb 2, 2019 at 8:05
  • $\begingroup$ Ah, yeah, for signature generation that could work (?). The E and D operations put me on the wrong track in that case. I think the attacks indicated by fgrieu are probably more general though - and they do consider confidentiality rather than malleability. $\endgroup$
    – Maarten Bodewes ♦
    Commented Feb 3, 2019 at 11:17
  • 1
    $\begingroup$ @MaartenBodewes Yes, I was out to complete, but Fgrieu gave the rest. $\endgroup$
    – kelalaka
    Commented Feb 3, 2019 at 13:30
5
$\begingroup$

There are at least two attacks that breach confidentiality under chosen plaintext attack, allowing to distinguish and perhaps decipher ciphertext for some messages (with low numerical value, e.g. the all-zero message).

  • If the public key $(N,e)$ is such that $m\,e<\log_2(N)/8$ (that is $m\le85$ for the common $e=3$ and $2048$-bit $N$), then for some messages (including the all-zero message) the padded message is less than $\sqrt[e]N$. This allows to decipher the ciphertext by taking its $e^\text{th}$ root then removing padding. This attack can be extended to sizably larger $m$.
  • Whatever the public exponent $e$, there is a meet-in-the-middle attack with cost only $O(2^{4m})$ modular multiplications and memory, which is at least worrying for $m<20$ and probably practicable for $m=13$ (which I suppose in the following illustration). The idea is to obtain ciphertext $C$ for the all-zero message, and hope that the padded message ($m=13$ random bytes) factors as the product of two integers $x$ and $y$, with $x<2^{48}$ and $y<2^{56}$, which is reasonably likely. We tabulate the $2^{48}$ values of $x^{-e}\,C\bmod N$, then search the $2^{56}$ values of $y^e\bmod N$ in this table. When we have a match, we know that $C$ is for the all-zero message.

Update: when the same message is sent several times and $m<\log_2(N)/8e^2$ ($28$ bytes with $e=3$), Coppersmith's short pad attack applies and recovers the message. See a description in Dan Boneh's 20 years of attacks on the RSA cryptosystem.

The question's padding format is also prone to a padding oracle attack. In these, the attacker submits ciphertexts $C_i$ to a device that deciphers using the private key and leaks information. In the simplest form, that can be leaking (by an error code or variation in execution timing) if ${C_i}^d\bmod N<2^{8(n+m)}$ as prescribed by the padding format (thanks to the leftmost 0x00). Leaking if the deciphered message is below some limit also qualifies (such leak is likely in application layers). With a moderate numbers of queries to such leaking decryption oracle, the attacker manages to decipher one message (or sign, if the key is also used for signature). There is no constraint on the messagel.
Note: encryption padding per PKCS#1 v1.5 is also prone to the issue. PKCS#1 V2.2 (OAEP) makes it easier to guard against it.

As pointed in an other answer, the format is malleable: a ciphertext for an unknown plaintext can be changed to a ciphertext that will deciper to a message related to the original in some meaningful way.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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