Score:2

Can you use RSA in “CBC mode”?

cn flag

Are there any security concerns with using RSA in “CBC mode”?

Specifically: if I use RSA encryption as my block cipher operation, and apply the standard CBC mode operations including a random IV, will the resulting cipher text provide the same level of theoretical security as the underlying RSA problem?

I am only considering RSA on its own. No padding scheme. I know traditionally RSA is insecure without proper padding, but in CBC mode I don’t see why the padding would be necessary (and it complicates the issue by introducing non-deterministic elements)

I also understand that CTR, CFB, and other block cipher modes that use the block encryption function for both encryption and decryption would fail horribly with RSA. Only concerned with CBC

cn flag
This is a hypothetical question. I am not implementing a system that is using RSA in this way. Just curious about the theory.
kelalaka avatar
in flag
possible duplicates of 1) [Can RSA (theoretically) be used as a block cipher?](https://crypto.stackexchange.com/q/32916/18298) 2) [What's the best block cipher mode of operation for RSA?](https://crypto.stackexchange.com/q/66314/18298) and more [RSA block cipher](https://crypto.stackexchange.com/search?q=RSA+block+cipher)
cn flag
This may have been asked in the past but all the threads I found on my initial search are about using RSA + OAEP in combination with some block cipher mode. That creates other complications. Mikero’s answer is nice since it fills in the blank for me about this specific scenario.
Score:5
us flag

This is a truly mad idea, so I applaud you for that. But it's seriously insecure. My interpretation of "RSA-CBC" would work like this:

$$ \begin{array}{l} \textsf{RSA-CBC}\Bigl( (N,e), m_1 \| m_2 \| \ldots \|m_\ell \Bigr): \\ \quad c_0 \gets \mathbb{Z}_N \\ \quad \mbox{for $i=1$ to $\ell$:} \\ \quad\quad c_i := (c_{i-1} + m_i)^e \bmod N \\ \quad \mbox{return } c_0 \| c_1 \| \ldots \| m_\ell \end{array}$$

Here each $m_i$ and each $c_i$ is a $\mathbb{Z}_N$-element. RSA-CBC chooses a random "IV" (element of $\mathbb{Z}_N$), then encrypts each plaintext block by adding the previous ciphertext block and then applying the RSA function.

So what's wrong with it? Suppose I see an encryption of some unknown plaintext. If I have a guess for $m_i$, then I can check whether my guess is correct via $c_i \overset?= (c_{i-1} + m_i)^e \bmod N$. I can indeed perform this check because the RSA exponent $e$ is public.

More generally, CBC doesn't work with public-key operations. Anyone can repeat the steps done during CBC encryption, if the block cipher is replaced by a public-key operation that anyone can perform.

cn flag
Beautiful. I knew there was something simple I was missing.
kelalaka avatar
in flag
Well, one can design this with secure PKCS and OAEP padding, too. $$c_i := (pad(c_{i-1} + m_i))^e \bmod N$$ (the reduced size of padding is omitted)
us flag
@kelalaka, $c_{i-1}+m_i$ is already a "full size" element of $\mathbb{Z}_N$, so I'm not sure what padding you could apply while still keeping the result in $\mathbb{Z}_N$.
kelalaka avatar
in flag
@Mikero one has to reduce the size of input of this scheme like 11-byte for PKCS#1 v1.5 padding ( see this for [OAEP](https://crypto.stackexchange.com/q/42097/18298) ) as I said (may be not clear, sorry for that). Then encryptions are secure as long as PKCS#1 v1.5 padding or OEAP is secure. Anyway, one has to use ECIES...
us flag
OK, then in that case the "CBC chaining" adds nothing. You might as well just do RSA-OAEP in "ECB" mode ;)
kelalaka avatar
in flag
Yes, the OAEP and PKCS are probabilistic encryptions, however, the CBC also provides some chaining that one might want. and, this should not be confused with authentication since one can already attack CBC with [bit flipping](https://crypto.stackexchange.com/q/66085/18298).
us flag
"If I have a guess for mi, then I can check" this applies in the same way for ECB. So your actual statement is, "CBC is no improvement" and the security gap, that allows the check of the guess comes from the public key being known to an attacker. Think, in a TLS protocol he won't have this.
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.