[Cryptography] We need a new encryption algorithm competition.

[Jerry Leichter]

On Mar 19, 2014, at 8:26 AM, ianG <iang at iang.org> wrote:
> Well, DJB in curveCP makes a very good point:  Now that EC is fast
> enough for the average app to ignore the cost, why not move to a pure
> single request-response-PK-encrypted model?  Instead of the older
> performance-dominated model of PK-signed-key-setup + RR-key-encrypted?
The classic paper on this is:

Goldwasser, S., Micali, S., and Tong, P. Why and How to Establish a Private Code on a Public Network. Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS'82), Chicago, Illinois, pages 134-144, October 1982

Unfortunately, it doesn't appear to be available on-line anywhere.  Summary (of just part if the paper - it's been many years since I read it):  The ability for anyone to send a message using the same public key is a significant weakness, which can be leveraged.  An attack outlined in the paper:  Suppose I agree to a protocol in which answers to yes/no questions are determined by the bottom bit of a random encrypted message.  You've captured a message encrypted with my public key and wish to decrypt it.  You notice that I often send a message to a friend; he replies shortly after, and then I either leave my office and join him for lunch, or stay in my office and don't dine with him that day.  So you guess that I send out a "how about lunch" message, and you respond with a yes/no response.

So the next time you see me send out an apparent "how about lunch?" message, you send me the message you captured, and watch what I do.  If I promptly leave for lunch, you know you "said" Yes, so the bottom bit of the encrypted message is 1; otherwise it's 0.  You've turned my lunch habits into an oracle for the bottom bit of any message encrypted with my public key.

What's the good of a one-bit oracle?  In the case of RSA, it completely destroys security:  Using the fact that RSA is multiplicative, if you know the bottom bit of the encrypted message, it's possible to "shift the message right" by one bit, discarding the bit you already know.  Now repeat until you've read off the message, one bit at a time.

No, this isn't a practical attack against a realistic protocol.  The paper is a theory paper, and what it's showing is that even under the assumption the RSA is "secure" in the sense that there's no practical way, as an abstract problem, to invert the encryption, unless you design your protocols carefully, you can be attacked.  Over the intervening years we've found many more attacks confirming this general fact.

In general, asymmetric encryption is very brittle.  It's not just performance that argues against its use for encrypting semantically meaningful information!

I haven't looked at the cryptographic details of curveCP.  DJB certainly knows about these results, and I assume any protocol he designs would avoid the pitfalls.  But I would advise anyone who thinks "Oh, let's use ECC throughout and stop all this nonsense with session keys" to proceed with extreme caution.
                                                        -- Jerry

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4813 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140319/81cb951a/attachment.bin>