10
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – CodesInChaos
    Commented Jun 4, 2012 at 17:20
  • $\begingroup$ 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. $\endgroup$
    – CodesInChaos
    Commented Jun 4, 2012 at 17:20
  • $\begingroup$ @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. $\endgroup$
    – user541686
    Commented Jun 4, 2012 at 17:28
  • $\begingroup$ 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? $\endgroup$
    – fgrieu ♦
    Commented Jun 4, 2012 at 20:41
  • $\begingroup$ @fgrieu: Just because it was a handy scheme... I don't really mind that part if it's different though. $\endgroup$
    – user541686
    Commented Jun 4, 2012 at 21:01

3 Answers 3

Reset to default
15
+50
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ +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. $\endgroup$
    – user541686
    Commented Jun 4, 2012 at 17:32
  • $\begingroup$ @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. $\endgroup$
    – poncho
    Commented Jun 4, 2012 at 17:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jun 5, 2012 at 23:30
1
$\begingroup$

Just happened to read the question and decided to write short answer.

RSA is partially malleable (see http://en.wikipedia.org/wiki/Malleability_%28cryptography%29), it can be said that RSA provides efficient cryptography only if used very carefully. Therefore, RSA shall always be used via existing RSA padding schemes (see e.g. PKCS#1), because those have been carefully designed to be secure.

The scheme described here (zero padding) likely does not provide as good security with RSA as recommendable.

Anyway, the usage of intermediate symmetric key is actually not to remove reuse private key, its goal is instead: performance. Public key operations are generally very slow compared to symmetric cryptography.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I don't understand what you mean by "re-using the private key". Isn't the private key, well, private? How do you 're-use' a private key? $\endgroup$
    – user541686
    Commented Jun 4, 2012 at 17:03
  • $\begingroup$ Never mind (was thinking DSS). The scheme suggested can be ok, as long as proper padding scheme is used. Nevertheless, the appropriate restrictions of padding scheme shall be studied carefully and followed. $\endgroup$
    – MPN
    Commented Jun 4, 2012 at 17:15
  • $\begingroup$ I personally consider the importance of the issue of processing efficiency to have been highly exagerated and IMHO in reality the issue is a non-issue at least for the common people whose (in particular important) communications with one another are invariably of messages of fairly small volumes. Thus I have written an RSA software, including encryption with signature, in Python which, being commonly interpreted, is certainly slow in comparison with e.g. C. See mok-kong-shen.de Could it ever be a concern for the said kind of users whether the encryption processing time is 10 sec or 0.1 sec?? $\endgroup$
    – Mok-Kong Shen
    Commented May 2, 2017 at 9:53
0
$\begingroup$

If you came here like me because static code analysis flagged you with a security flaw for using ECB instead of CBC in code that looks like this:

Cipher c = Cipher.getInstance("RSA/ECB/OAEPWithSHA-1AndMGF1Padding","SunJCE");

You might have to explain to someone that it's just a Java syntax thing and that ECB or CBC don't really do anything because RSA isn't breaking the message into blocks.

Improve this answer
$\endgroup$
1
  • $\begingroup$ You point to and talk about some Java snippet. Since the Q doesn't mention Java anywhere, I'm not sure how this answers this 5 year old question if the described scheme is secure, what attacks would be possible on ECB mode, or how to make things safer. You probably should edit your answer to clarify that, answering the question too… if only, to avoid downvotes by other users. In case you missed it: the Q was asked 2012 and already hugs an accepted answer (with bounty reward) which indicates what kind of answer the asker expected to receive. TL;DR: Java is unrelated to this Q&A. $\endgroup$
    – e-sushi
    Commented Apr 30, 2017 at 6:37

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