[Cryptography] We need a new encryption algorithm competition.

[ianG]

Clarity-failure, here's a rewrite of the ideas.

On 19/03/2014 18:06 pm, Jerry Leichter wrote:
> 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?

Assume that the client has a public/private key pair and wants to do
regular discussions with a server.  Assume also that the public key of
the server has been acquired by a safe method.

The normal conceptual method of talking to the server is called
request-response model (RR).  It's used in REST, HTTP, and a squillion
other systems.

In order to do secure RR, there are approximately two methods.  The
first method is for the client to pick a symmetric secret key, encrypt
it to the server's PK, then encrypt the request using the secret key,
append these two packets together and send them to the server.  This is
what I meant by "single request-response-PK-encrypted model".

This is good because it is easy to code up.  Yet it also suffers: CPU
performance, brittleness.  e.g., Jerry says,


> 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


So in response to this sort of issue (and brittle really is a good word
because there are many issues) the 'wiser' method from cryptography
schools is to do this:

Encrypt a secret key with the PK as before, send that as a
"shared-secret key exchange request" to the server.  The server can then
probably munge that key (concat, hash or DH) and send back a reply from
which both parties derive an agreed single shared secret.

Then, in future exchanges, all requests are encrypted with the shared
secret (derivative thereof) and responses likewise.

Now, this is fast for crypto, and it takes the pressure off PK, etc by
only using it once a day (say).  So it is the wiser choice, from a
crypto standpoint.

But, the iceberg under the waterline is the code complexity of having to
deal with all the states of the session.  The 'session' method is an
order of magnitude more code than the previous 'singleton' method,
IMHO/experience, mostly because the former is state free, or
state-freer.  To see this, you also have to factor in PK changes, net
loss, server loss, timeouts on sessions, IP agility, bugs, user
impatience, etc.

So when I saw curveCP, there was an element in it of reducing the states
and of using PK to do all the encryption.  Thereby eliminating
substantial complexity.


> 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.

However, on further looking it turns out that curveCP does not do quite
what I imagined:

http://curvecp.org/packets.html

It replaces the secret key in the session with *an ephemeral EC key*
which we can see as a sacrificial lamb.  Counterpoint being that it
still goes through the handshake, which is still fairly costly in
code/state terms but is certainly simplified over the comparison with
say TCP/TLS.

(When I find the original paper not slides
http://cr.yp.to/talks/2010.12.28/slides.pdf I'll be able to confirm that.)



So where are we with the wider picture?  Here's my take.  There is now a
developing understanding that the old TCP/TLS path to universal and
happy security isn't going to serve us well into an aggressive future.
For many reasons, and regardless of criticisms, it may just be that it
is out of date.  We know much more than we did back then.

There are a few brave souls daring the disparagement of the priesthood
and experimenting to replace all of TCP/TLS with ground-up designs.  The
ones I know of that are fairly advanced (code, trials etc) are:  QUIC,
CurveCP and my own stuff.  I only include my own stuff because I'm me.

It is in these experiments that we will discover what works.  It isn't
in theoretical discussions, because the space is too complicated for
theory to predict, beyond a certain complexity limit, theory just
becomes another weapon for the various pundits to bash each other, it
doesn't actually inform us a group.  Only running code and working
successes will do that (yes, the RFC/WG concept does get many things
right, which we can steal).

This is why I support PHB's experiment, even though I disagree with his
assumptions.  This week, he seeks a new encryption algorithm but really
what we are doing (I think) is seeking a new security approach.

Full circle then, it would be pretty fantastic to have a competition to
bring all these ideas together, so we can knock our heads together
gladiator style and find out what we can.



iang