[Cryptography] Mixing public key crypto systems?

[Jeff Burdges]

On Mon, 2016-03-28 at 12:50 -0700, Henry Baker wrote:
> Yes, I agree that the strength of the overall communication is
> limited by the weaker of the two protocols.
> 
> Nevertheless, you can't force someone to produce a public key
> in N different public key crypto systems.  They're going to
> publish 1,2,3, maybe, but not 10.

I think that's an issue only if you're talking about a legacy protocol
wrapped in TLS like HTTPS.  A new protocol can do anything you like,
but..

We have two abelian group based approaches, ordinary Diffie-Hellman
modulo a prime, and elliptic curve Diffie-Hellman.  It's always
reasonable to resolve conflicts over the prime or curve when designing
the protocol.  I hear OtR v4 will do both these key exchanges, but
that's probably anomalous.  

There won't be a monoculture in post-quantum public-key cryptography
anytime soon because nobody knows what post-quantum algorithms to use.
We've only three approaches though currently :
- Code based like McBits requires 1meg keys and 64k encryptions
- Ring-LWE lattice based systems like New Hope
- Super-singular isogeny based
I think non-abelian group based systems have mostly failed to work out.
And non-abelian alone might not save you from the QFT really.  I think
these post-quantum systems have an element of "computational dead end"
which may kinda push Shor towards Grover or something.  In SSI, it's a
groupoid of isogeny classes of elliptic curves, not so sure how to
describe it for the others.  Also, if anyone has made that "dead end"
observation more precise, then I'd love to hear about it. 

This leaves us with at most five realistic public key types one might
use in one protocol.  I'd expect the reasonable configurations would
be : 
 (1) ECDH plus Ring-LWE, probably New Hope
 (2) ECDH plus both Ring-LWE and SSI
 (3) ECDH per message plus McBits with keys published elsewhere
 (4) ECDH plus Ring-LWE and SSI, and optionally McBits with ...

In practice, any modern protocol should make all public key systems it
employs mandatory, except possibly McBits whose key size might require
it be optional.  In principle New Hope and SSI are small enough for
ephemeral keys, but not McBits really. 

In (4), two parties could communicate even when neither had a McBits
key, but that's less secure.  Assuming a ratchet like Axolotl, a McBits
key could exist on only one side in (3).  A ratchet lets you alternate
between New Hope and SSI in (2) too, making it as fast as (1).

Anyways, I expect "Alice uses X while Bob uses Y" issue is very specific
to super-generic protocols like TLS, and to McBits.  In particular (3)
creates a situation where "Alice and Carol can talk to Bob, but not to
each other, because only Bob has published a 1meg McBits key." 

Jeff

p.s.  I suppose the whole "crypto monoculture" discussion should really
be split into generic protocols like TLS that wrap legacy protocol, and
modern protocols like OtR that do one thing correctly.



-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: This is a digitally signed message part
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160330/23d705e7/attachment.sig>