[Cryptography] We need a new encryption algorithm competition.

[Nico Williams]

On Wed, Mar 19, 2014 at 1:06 PM, Jerry Leichter <leichter at lrw.com> wrote:
> [...]
> 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.

Eh, this is if you know the one bit of the plaintext encrypted with
RSA, but that plaintext is generally a randomly chosen key for a
symmetric cryptosystem used to protect the real plaintext of the
message.  Here you've determined the plaintext of a 1-bit message (or
of 1 bit of a longer message), but not one bit of the "plaintext" fed
to RSA.  That's not relevant here.

Ian's concern is that using the same pair of ECDH key pairs repeatedly
makes it easier to recover the private keys or the session keys.  To
be sure, any PK cryptosystem where you "encrypt to" a public key that
is literally public... is subject to chosen plaintext attacks (by
definition) and therefore had better be resistant to them...

Nico
--