Super-Encryption

[Amir Herzberg]

Matt, in your note below you explained finally what you really want: a 
secure combination of encryption and signature. I explain below why your 
current scheme is insecure. There are simple secure designs. With Yitchak 
Gertner, a student, we recently proved security of one such practical 
design, which is essentially Sign_sender ( Encrypt_RSA_receiver (message), 
PublicKey_receiver). I've just uploaded the draft journal version to 
http://eprint.iacr.org/ so you should be able to see it in a day or so 
(comments very welcome as I want to finish and submit it to journal soon). 
Your scheme is using the Sign-then-Encrypt order, which may not be secure 
for some (possibly weird) encryption schemes, although may be secure 
standard schemes such as RSA (but I don't think this was proven yet). But 
as I mentioned, your specific scheme is definitely insecure, details below.

Best regards,

Amir Herzberg
Computer Science Department, Bar Ilan University
Lectures: http://www.cs.biu.ac.il/~herzbea/book.html
Homepage: http://amir.herzberg.name

At 16:25 15/12/2003,  Matt wrote:
>Quoting Ben Laurie <ben at algroup.co.uk>:
>
> > I don't see any value added by cipher1 - what's the point?
>
>The message is encrypted, i.e, cipher1, then cipher1 is encrypted yeilding
>cipher2.
>
>Since symmetric_key1 of cipher1 is RSA_Encrypt(sender's private key), access
>to sender's public key can decrypt cipher1(must be *this* sender).

So (as I said before...) here you are trying to authenticate the sender - 
using RSA to sign, not to encrypt. I again suggest you use the right 
terminology i.e. call is a signature (since this is what you do!). Notice 
also that for secure usage, there may be some small differences in the 
preprocessing for encryption vs. for signature with RSA.

And I believe you didn't understand (and answer) Ben's point. I'll try to 
clarify. Here's the sequence you suggested:
>(1) Encrypt message with symmetric key algorithm, i.e., cipher1

That's the part that appears unnecessary.

>(2) RSA_Encrypt (SHA1(message) + symmetric key) with sender's RSA private key
This is where you actually mean RSA_Sign. And why sign `symmetric key` ? 
Since the attacker will know this key, why not simply sign just `message` 
(or SHA1(message) if you want... normally we consider hashing as part of 
the signature process, i.e. I'll prefer to write Sign_RSA_SHA1(message)).

>(3) Encrypt cipher1 with symmetric key algorithm, i.e., cipher2

So here one would expect you to simply encrypt the message, i.e. 
cipher2=AES_symmkey2(message); Ben asks (and I agree), what gain do you 
have by encrypting cipher2? As I mentioned, one could hope for gain in 
confidentiality, e.g. when using different encryption schemes, but not when 
the first key (`symmetric key`) is revealed as in your protocol...

>(4) RSA_Encrypt (symmetric key2) with receiver's RSA public key

So steps 3 and 4 are `classical` hybrid encryption of cipher1. Hybrid 
encryption is a standard technique so I prefer to write it as one step, 
i.e. Encrypt_RSA_AES_receiverPK(message), or in your 
case,  Encrypt_RSA_AES_receiverPK(cipher1).

>(5) Send super-encrypted message

Woops! what does the message consist of ? It is quite clear from the steps 
above and below (omitted), that it contains both 
cipher2=Encrypt_RSA_AES_receiverPK(cipher1) and also RSA_Sign_sender 
(SHA1(message) + symmetric key). Now this is a good example of why it is 
good NOT to confuse signature with encryption... since it is quite obvious 
that the attacker gets to see SHA1(message). This is not desirable. First 
of all, SHA1 (or any hash) is not required to preserve complete 
confidentiality (e.g. in the standard, the goal is only stated as being a 
one-way function). So attacker may be able to learn something about message 
from SHA1(message). As a practical example, suppose there is a very small 
set of possible messages, say `buy XXX for YYY' where XXX, YYY are from 
relatively small sets. Then clearly the attacker can simply compute 
SHA1(m') for all possible messages m' and identify the message sent. So 
this is a real possible exposure to confidentiality.

Also, you wrote...

>Since symmetric_key2 of cipher2 is RSA_Encrypt(receiver's public key), only
>the receiver can decrypt cipher2.
>
>As was pointed out to me, the process of decrypting cipher2, yields an
>encrypted message, i.e., cipher1, that can forwarded on behalf of the 
>original
>sender. This is not necessarily undesirable.  However, SHA1(message) is to
>ensure that cipher1 has not be altered in transport.  Therefore, the receiver
>knows three items.
>(1) The sender who originated the message.
>(2) The receiver is the intended receiver.

This (item 2) is not correct. The message may have been sent to Eve (and 
encrypted using Eve's public key), but then Eve re-encrypted symmetric key 
2 (or cipher1 itself) with the public key of another party say Bob, and 
sent the message to Bob; Bob has no way of knowing that the intended 
receiver (by the original sender) was Eve.

>(3) The message was not altered during transport.
>
>Thx,
>
>-Matt
>
>---------------------------------------------------------------------
>The Cryptography Mailing List
>Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com