[Cryptography] We need a new encryption algorithm competition.

[Ralf Senderek]

On Thu, 20 Mar 2014, Jerry Leichter wrote:

> The Goldwasser/Micali/Tong paper shows why you should not encrypt semantically
> meaningful messages using an asymmetric key system.  The fact that anyone
> can send a message using the same public key means it's possible to turn
> the recipient into an oracle for information about the message, which
> may leak enough information to allow the message to be decrypted.
> That's why, *independent of performance considerations*, it's best to
> use an asymmetric key system to establish keying information for a
> symmetric key system.  When used this way, the data sent is random
> and not directly meaningful to the recipient, so it's harder
> (probably not impossible, but much harder) to turn the recipient into
> an oracle.

Which brings us to the question how hard it is to turn the recipient into
an oracle.

Sending PK-encrypted ciphertext is not a problem in itself, the problem
starts, when the sender learns anything about the results of the
decryption and when he can turn that knowledge into a plan for submitting
new crafted ciphertext to learn more. Careless handling of decryption
results by users is not an oracle, the oracle that works is a build-in
mechanism that can be used many times because it's automated and
independent of user action.

And because of this nature it also applies to AES. I recall an assignment
in Dan Boneh's excellent online cryptography course, where the university
provided an AES implementation that could be queried as an oracle.
Students using this oracle could decrypt an AES-128 encrypted ciphertext
without the need to recover the AES-key, simply by sending crafted
ciphertext that probed the padding at a certain character position and
learned whether their ciphertext was accepted as well-padded plaintext
or not. At a rate of 256 oracle requests, they could decrypt AES one
character at a time. So implementation matters, and denying any
information about decryption success is a very good idea.
This would have had worked as well if the plaintext was random (looking).

To answer the above question, it might be necessary to look for built-in
mechanisms in any scheme (symmetric or asymmetric) that leak decryption
success. Good concepts are important, but we're only really secure
when we have (and understand) the whole thing.

       --ralf