1
$\begingroup$

We know that a short message encrypted with RSA can easily be brute forced.

Lets say Bob encrypts a message containing just "Hi" and encrypts it with Alice's public key. Anyone can try encrypting all possible combinations of very short messages using Alice's public key until they get a match.

What i am wondering is can the identity of a very short message be somehow forged?

Lets say Bob encrypts many one and two character messages with his private key. Could the attacker somehow forge a new one or two character message so that it seems like it came from Bob?

Of course, in these cases we are talking about no padding being added or any other changes.

$\endgroup$
5
  • $\begingroup$ Welcome to Crypto.SE! In general, textbook RSA is malleable given the nature of modular arithmetic. i.e Given encryption of $m$ and $m'$ ($c$ and $c'$) we can get encryption of $mm'$ which is $c*c'$. Other than that note that given that RSA is a public key system, it is usually assumed that the public key is known to everyone. $\endgroup$ Sep 13, 2021 at 17:46
  • $\begingroup$ So if I understood correctly, if Bob has previously sent messages "a" and "b" an attacker could successfully forge message "ab"? What about an entirely new message such as "c"? $\endgroup$
    – Peter2223
    Sep 13, 2021 at 17:54
  • $\begingroup$ Note here that $ab$ refers to multiplication and not to a concatenation. However, given the encryption of $2$, it is possible to do bit shifting and create new ciphertexts by concatenation. As for an entirely new message, note again that the public key probably is given to everyone and not just Bob. Therefore, no clever manipulation is actually needed. The attacker can only encrypt for themselves. $\endgroup$ Sep 13, 2021 at 17:58
  • $\begingroup$ I am talking about an entirely new message encrypted with Bob's private key. A message encrypted with his private key would confirm his identity. Is it possible forge a new message so that it looks like it came from a private key. $\endgroup$
    – Peter2223
    Sep 13, 2021 at 18:03
  • 2
    $\begingroup$ Oh, I was mistaken given the use of a private key to encrypt. This is not really standard practice. The appropriate tool would be a digital signature(not the same as encrypting with the secret key). Anyway, some forgery would be using the same tricks as written before. Have a look at this answer crypto.stackexchange.com/questions/20085/… $\endgroup$ Sep 13, 2021 at 18:09

1 Answer 1

2
$\begingroup$

We know that a short message encrypted with RSA can easily be brute forced.

A short message encrypted with textbook RSA can easily be brute forced. The problem is not that the message is short. A much longer message chosen in a small set (like the identity of a person on the public class roll) can also be brute-forced by the same technique. The problem is low-entropy message combined with the use of textbook RSA encryption (with no random padding).

Bob encrypts (..) messages with his private key.

That "encrypts" is erroneous terminology for applying the transformation $m\mapsto f(m)=m^d\bmod n$ where $(n,d)$ is Bob's RSA private key. That does not encrypt, since that term designates transforming a message in order to make it unintelligible to adversaries, and here anyone can undo the transformation using the public $(n,e)$. The term "encrypts" must be changed to "transforms" or "signs". The result $f(m)$ of that operation is the textbook RSA signature of message $m$ by Bob's private key.

Could the attacker somehow forge a new one or two character message so that it seems like it came from Bob?

Yes. The basic tool used is the multiplicative property of function $f$: for all $m_1,m_2$ it holds $f(m_1\cdot m_2\bmod n)\ =\ f(m_1)\cdot f(m_2)\bmod n$. Thus an adversary knowing the textbook RSA signature of messages $m_1$ and $m_2$ can find the textbook RSA signature of message $m_1\cdot m_2\bmod n$, or ${m_1}^i\cdot{m_2}^j\bmod n$ for any pair of integers $i,j$.

For messages constrained to have a meaning, a possibility is to have $m_1\cdot m_2=m_3\cdot m_4$ which allows to compute the textbook RSA signature of $m_4$ from that of $m_1$, $m_2$ and $m_3$, as $f(m_4)\ =\ f(m_1)\cdot f(m_2)\cdot f(m_3)^{-1}\bmod n$.

$\endgroup$
4
  • $\begingroup$ Thanks for the answer! As i understood an attacker couldn't forge a new signed message consisting of elements that were not signed before? For example if the message containing just the letter "c" in this case was never transmitted, but other letters were, an attacker couldn't forge a signature for it? $\endgroup$
    – Peter2223
    Sep 13, 2021 at 21:46
  • $\begingroup$ @Peter2223: uh, no. Sorry I used the common notation that $u\,v$ is the product of $u$ and $v$, and you understood concatenation (often noted $u\mathbin\|v$ ). Now I changed to $u\cdot v$ to make it clearer we multiply. What I mean is that if the messages signed encode to the integers $m_1=7$ and $m_2=8$, then the adversary can find the signature of the message encoding to integer $7\cdot8=56$ (and also $7\cdot7\cdot7\cdot8\cdot8=21952$). This is more difficult with meaningful messages, but that trick can be pulled. $\endgroup$
    – fgrieu
    Sep 13, 2021 at 21:56
  • $\begingroup$ Yeah, i am not coming at this topic with a lot of knowledge about encryption. I am making a program that needs to test the "identity" of a file being sent. I figured to hash the file and then sign it with raw rsa. But sha-256 is only 64 characters and i read that rsa is not very safe with short messages without random padding. Since the receiving machine cant share the random algorithm, i am unable to add random padding, and adding predetermined padding sounds like it would not be very effective. How secure would sha-256 signed with raw rsa 2048 be? $\endgroup$
    – Peter2223
    Sep 13, 2021 at 22:02
  • $\begingroup$ @Peter2223: that would I believe be on the unsafe side of the limit where the Desmedt and Odlyzko attack could apply (there is a question about that attack). Your application calls for signature, with some well-thought signature padding. Because I don't get what "cant share the random algorithm" means, I can't tell if RSASSA-PSS (randomized signature padding), RSASSA-PKCS1-v1_5 (deterministic signature padding, lacking a security proof), or ISO/IEC 9796-3 scheme 2 or 3 would be adequate. $\endgroup$
    – fgrieu
    Sep 13, 2021 at 22:24

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.