Security of RSA for padding $\texttt{0x00|message|random_bytes}$ 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?
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;


How does PKCS 1.5 solve the insecureness of Textbook RSA?