Score:0

RSA security when using short messages

cn flag

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.

Marc Ilunga avatar
tr flag
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.
Peter2223 avatar
cn flag
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"?
Marc Ilunga avatar
tr flag
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.
Peter2223 avatar
cn flag
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.
Marc Ilunga avatar
tr flag
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 https://crypto.stackexchange.com/questions/20085/which-attacks-are-possible-against-raw-textbook-rsa
Score:1
ng flag

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

Peter2223 avatar
cn flag
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?
fgrieu avatar
ng flag
@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.
Peter2223 avatar
cn flag
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?
fgrieu avatar
ng flag
@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](https://crypto.stackexchange.com/q/51680/555) 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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.