7
$\begingroup$

Assume AES gets a devastating attack making it unusable. Is it possible to use RSA in a secure way that can encrypt data in bulk?

I can't see how RSA (assuming OAEP padding) can be used in normal block cipher modes. Its output is likely not pseudorandom, so it can't be used in CTR, OFB, or CFB mode. Its output is too large to be fed back in, so it can't be used in CBC mode. Using it in ECB mode would have the problem that blocks can be moved, duplicated, deleted, and replaced just like if you use ECB on a normal block cipher.

I've seen this sort of thing asked before, but the answers are always along the lines of "RSA isn't a block cipher, so you shouldn't". This won't be used in practice, it's just a thought experiment.

Improve this question
$\endgroup$
8
  • $\begingroup$ Are you considering RSA with the public key made public, as in RSA? If yes, the main theoretical problem is that at least one of decryption or encryption requires nothing secret. $\endgroup$
    – fgrieu ♦
    Feb 19, 2016 at 6:53
  • $\begingroup$ @fgrieu What do you mean exactly? Yes, the public key is made public, but what do you mean that at least one encryption or decryption requires nothing secret? $\endgroup$
    – Daffy
    Feb 19, 2016 at 6:55
  • $\begingroup$ In textbook RSA, encryption requires nothing secret (the public key is all that's needed). In a block cipher, encryption requires the secret key. That makes a huge difference, with important consequences. For example, when OFB, CFB, or CTR block cipher modes are used, ability to encrypt blocks at will (with the right key) implies ability to decrypt the whole message. Related: if an encryption system is deterministic and requires nothing secret for encryption, then it is insecure. $\endgroup$
    – fgrieu ♦
    Feb 19, 2016 at 7:04
  • $\begingroup$ @fgrieu I realize that textbook RSA would be insecure for this purpose, so I'm proposing using RSA with OAEP padding as a block cipher. Not exactly, though, because a real block cipher uses a single secret key. RSA with OAEP will have a secret key and a public key, just as RSA usually does. $\endgroup$
    – Daffy
    Feb 19, 2016 at 7:10
  • 2
    $\begingroup$ there are many other secure block ciphers, what kind of scenario would exist where they would not be considered before something that is not a block cipher? $\endgroup$
    – Richie Frame
    Feb 19, 2016 at 8:37

2 Answers 2

Reset to default
3
$\begingroup$

No. With the assumption that the RSA public key is public (as assumed), RSA can not be used as a generic substitute of a block cipher.

Main issue is that RSA encryption is either

  • A public function; that's when there is a deterministic and reversible transformation of the message before applying the raw public-key function $x\to x^e\bmod N$ usually used for encryption (including with the transformation a big-endian conversion from bitstring to integer as in most variants of textbook RSA); it follows that in use of the hypothetical RSA-based block cipher to build a cipher in CTR, OFB, or CFB mode of operations, where encryption and decryption both use the block cipher in encryption mode, anyone could decipher. If we try to fix this by using RSA decryption for the block encryption, we run into other problems, including that anyone can decipher for a cipher in CBC mode of operation.

  • Not a (deterministic) function; that's when there is random padding as in RSAES-OAEP or RSAES-PKCS1-v1_5. It follows decryption is impossible in CTR, OFB and CFB modes.

There are other issues, including that $n$-bit RSA on bit messages can encrypts at most $n-1$ bits into $n$-bits; but that one can be solved by cycle-walking.

Update: A different question is whether we can build a secure cipher based on RSA, without a block cipher. We can, inasmuch as RSA can be secure without a block cipher (which is part, perhaps in disguise, of hashes and Mask Generation Functions used in secure RSA encryption). For example, we break the message into 190-octet blocks except the last which can be shorter, then encipher each block with RSAES-OAEP, with 2048-bit key and SHA-256 in the padding and MGF (RSAES-OAEP has a maximum message capacity of the modulus size in octets, minus two hashes, minus 2 octets, and that's 190 octets for our parameters). That's a secure (non-authenticated) cipher, but one only vaguely comparable to a block cipher in ECB mode:

  • there is a size overhead of over 25%, versus none for large messages using ECB;
  • it is secure under chosen-plaintext attack, when ECB is not;
  • anyone can encipher any message with any content (including some portions of unknown but genuine messages if desired), when access to an encryption oracle is required for that in ECB.
Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ IMHO OP's main issue is to use RSA to encrypt data in bulk (s. his 1st paragraph), not to use a RSA-based block cipher to built another cipher in CTR or other modes of operations. I have done thus exactly what OP asked in Example 3 of my software s13.zetaboards.com/Crypto/topic/7234475/1 $\endgroup$
    – Mok-Kong Shen
    Feb 19, 2016 at 11:38
  • $\begingroup$ @Mok-Kong Shen So, you are using RSA symmetrically as CTR-Hash? $\endgroup$
    – Sam Ginrich
    Jan 7, 2022 at 15:13
3
$\begingroup$

I can't see how RSA (assuming OAEP padding) can be used in normal block cipher modes. Its output is likely not pseudorandom, so it can't be used in CTR, OFB, or CFB mode. Its output is too large to be fed back in, so it can't be used in CBC mode. Using it in ECB mode would have the problem that blocks can be moved, duplicated, deleted, and replaced just like if you use ECB on a normal block cipher.

You're right about the CBC, OFB and CFB modes. Using RSA as drop in replacement will be troublesome anyway, because it would run into practical issues besides the security related ones already mentioned by fgrieu. Will the padding mode be compatible with such large block sizes? Will the implementations? What about buffers created to be about the same size of the plaintext input?

ECB in my opinion has the best cards. The main issue with ECB is that repeating plaintext blocks will be seen as repeating plaintext blocks by an attacker. This problem however is not present if you'd use RSA with e.g. OAEP padding. OAEP padding already has a random component, so you would not be able to see the repeating pattern.

You also state that ECB allows blocks to be "moved, duplicated, deleted, and replaced". This is however not just a property of ECB mode; it's a property of any mode that doesn't include integrity protection and authentication. You can simply remove this problem by authenticating the ciphertext with a digital signature - the asymmetric equivalent of a MAC. If you assume that you've distributed the full key pair to both parties you may even get away with using the same key pair as the padding would protect you against most if not all attacks.

Using RSA in ECB/OAEP mode of course has huge drawbacks with regards to performance, key management and overhead. It could also drain the secure random generator of the system. Furthermore, it seems that a symmetric cipher like AES is a whole lot more going for it with regards to security. So you'd probably downgrade your security level rather than upgrading it.

So yes, ECB is kind-of possible. You should not be able to encrypt multiple messages if it wasn't. Anybody implementing such a scheme would be considered out of hens mind by the cryptographic community though - and rightly so.

In the comments you further explain that

... but the idea is to use it similarly to how we use block ciphers today, as to avoid #1.

This would be impossible. Raw / textbook RSA is horribly insecure. You'd have to perform padding. Using the cipher in block mode of operation doesn't work. Furthermore, there is a problem with the highest bit of the input. With RSA you can deterministically encrypt something of size N - 1. N - 1 will not be on a bit boundary. That means that you'll always have a single bit of overhead. So even if it was possible to create a secure mode, you still could not use it as drop-in replacement.

ECB mode for textbook RSA is often used in textbook examples of RSA encryption with very small primes. After all of the above I hope I don't have to explain how horribly insecure that mode is; it breaks not just one but all of the rules.

Improve this answer
$\endgroup$
0

Your Answer

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

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