[Cryptography] Mixing public key crypto systems?

[Ray Dillinger]

On 03/27/2016 05:25 PM, Henry Baker wrote:
> Inspired by the 'monoculture' thread, I'm curious as to whether it is
> possible to mix different public key crypto systems.
> 
> For example, Alice might use some version of RSA, while Bob might use
> some version of El Gamal.
> 
> Alice posts her public key in her chosen PK system; Bob posts his 
> public key in his chosen PK system.  Each has to use the type of 
> encryption chosen by the addressee of the message.
> 
> Does everything still work?

You could in principle build a system that didn't trust in the security
of any particular ciphersuite.  You could even do it with good security,
although by most people's standards the resulting system would suck.

The issue is that if the whole is to *NOT* be as weak as the weakest
link, then it will certainly be far less efficient than the strongest.

The protocols would be complicated (and therefore subject to bugs in
design and implementation) in a way different from all the complexities
introduced by ciphersuite negotiation in the committee-designed systems
we've seen, exactly because they must be explicitly designed to DISALLOW
ciphersuite negotiation.

BOTH sides in every protocol would pick ciphers and keys completely
independent of the other.  Security must be preserved even if only one
participant selects secure ciphers.

As far as protocols are concerned you just have one cipher suite. Its
keys, hashes, signatures, ciphertexts, etc, are completely opaque blobs
which can be any length.

A key might be formatted something like  AES512:key:foo or
RSA8192:pubkey:foo or EC256kp1:privkey:foo instead of just being
presented as binary string foo after protocol negotiation.  Internally
to the system you dispatch on methods per cipher, but this is at a
completely different layer than the protocol itself, and the choice of
cipher must not affect the protocol in any way.

This allows someone to present a stupid key for a stupid cipher, to
someone else who has security requirements greater than that stupid key
with that stupid cipher provide.  The only way to ensure that the
transaction is not done using whichever cipher is the weakest link is to
ensure instead that BOTH systems are used, that all protocol messages
are subject to superencryption, and protocol transactions which require
both participants to be using the same cipher system must be done twice;
once using A superencrypted with B, and once using B superencrypted with
A. Naturally both must succeed.  And this "wasteful" thing must happen
even if both clients want to use the SAME system because otherwise you
get cipher negotiations into the protocols.

That's horrible because under absolutely every circumstance it will more
than double the compute, memory, time, and, most threateningly, the
complexity overhead of the  resulting system.  But it's the only way
AFAIK to foil the attacks on the weakest link that will happen whenever
a weakest link is discovered, while also not trusting any particular
ciphersuite.

It is also less robust to noisy channels, means that protocols
between clients with different sets of ciphers implemented or enabled
will fail hard whenever someone wants to use one on which the clients
disagree, and makes it completely futile to choose a cipher in hopes of
limiting the overhead involved. If someone presents a 64kbit RSA key to
your mobile device or Internet-of-targets thermostat, then it either
uses a 64kbit RSA key, in addition to whichever key it picked, or it
fails hard.

Finally of course it opens the way to DoS attacks where compute-
expensive hashes and ciphers are used as a force multiplier.

				Bear

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160328/7ccfdaa9/attachment.sig>