Is RSA in a ECB-like-mode safe for bulk encryption?

Let's say I would like to communicate with my friend using asymmetric/public-key encryption, e.g. RSA.

(Note: I do realize that in practice this is done through an intermediate symmetric key, but this question assumes we only use asymmetric encryption.)

Say I try to do this: I slice up my data into 2n-byte blocks (padding with zeros [edit: padding appropriately] if necessary), append the block index to the block (to prevent the same plaintext from turning into the same ciphertext), then use my friend's public key to encrypt each block separately.

Is this a secure scheme, or does the fact that I'm re-using the key make it susceptible to some kind of attack? If so, is it used in practice in any existing algorithms? If not, is there any way to make it safe, aside from using a symmetric key?

-
Why do you want to use such a scheme? I don't see an advantage of this scheme over hybrid crypto. If you're worried about per message size overhead, just use an EC-DH based scheme. –  CodesInChaos Jun 4 '12 at 17:20
What kind of integrity requirements do you have? Do you sign the messages or use a MAC? Without that, an active attacker can replace parts of the message with his own data. –  CodesInChaos Jun 4 '12 at 17:20
@CodeInChaos: It's just an encryption question -- I'm not worried about a per message overhead (as long as it's fixed), and I haven't worried about authenticity yet (I don't think signing would be a problem here). I'm just asking about the encryption part for now. –  Mehrdad Jun 4 '12 at 17:28
Why "splice up data into $2^n$-byte blocks" rather than the maximum allowed by the combination of the RSA random padding scheme used, the inclusion of the block number, and the public modulus size, which will likely combine into a block size that is not a power of two? –  fgrieu Jun 4 '12 at 20:41
@fgrieu: Just because it was a handy scheme... I don't really mind that part if it's different though. –  Mehrdad Jun 4 '12 at 21:01

Well, reusing a key isn't a problem; after all, RSA keys are generally used many times.

However, if you fix the padding, there does exist one other potential problem; message malleability.

To example, suppose Alice sends two messages to Bob, $X_1, X_2$ and $Y_1, Y_2$. To send these, Alice actually sends:

$E(X_1), E(X_2)$

$E(Y_1), E(Y_2)$

Now, Eve can't modify each individual block (RSA with proper padding prevents that); what she can do is mix-and-match blocks, as so:

$E(X_1), E(Y_2)$

This would decrypt at $X_1, Y_2$, which might not be what Alice and Bob whats.

If you are silly enough to use RSA encryption in this manner, you do need something that binds the blocks together (or alternatively does some sort of integrity checking on the entire message).

As for whether people ever do this in practice, well, no they don't -- not because of security, but because it's so inefficient; using the RSA algorithm to communicate a symmetric key, and using that symmetric key to encrypt the message is far more efficient.

-
+1 thanks for the explanation. Just a question: do you happen to know any ballpark numbers on just how inefficient a scheme like RSA is? (e.g. in KB/s or something, or how many times slower than symmetric encryption, for a typical-sized key.) Just as a rule of thumb -- anything within an order of magnitude is great. –  Mehrdad Jun 4 '12 at 17:32
@Mehrdad: Well, while performance is pretty platform specific; for general numbers, we can look at cryptopp.com/benchmarks.html . According to that page, AES can be done at about 100MByte/second, while RSA decryption with a 1K key takes 1.46msec per 1kbit; or about 0.085MByte/second (not accounting for the fact that padding cuts into the 1kbit/message); that gives us about a factor of 10,000 or so. Note that this is, in a number of ways, an apples-to-oranges comparison; the real factor may be quite larger. –  poncho Jun 4 '12 at 17:42
Oh dang, ok thanks. :) –  Mehrdad Jun 4 '12 at 17:45
AES-128 has a much larger security margin than RSA 1024, so the facter will be larger. Note that the problem with message mallability is possibly even larger with symmetric ciphers such as AES. Message integrity is always a good thing. Try e.g. AES in GCM mode, then encrypt the random AES key to avoid this. –  owlstead Jun 5 '12 at 23:30
Looking back at this question, I think that the order of the blocks does not matter much. If you are worried about that, then you need some sort of integrity protection anyway, just like you would if you were using any symmetric cipher. Because of the random padding, at least the plain text is relatively safe compared to e.g. AES in ECB mode. –  owlstead Jan 3 at 20:40