[Cryptography] Is it time for a revolution to replace TLS?

[Jerry Leichter]

On May 15, 2014, at 4:24 AM, Guus Sliepen <guus at sliepen.org> wrote:
> Usually when one says "pre-shared key" one means a key for a symmetric
> cipher. However, the problem with those is that they are supposed to be
> kept secret, and that means it is hard to pre-share them over public
> communication channels.
It's *impossible* to share them over public channels.  That's exactly the point!  Sharing a key over an *existing trusted encrypted connection that runs over a public channel* works fine, of course.

> Conversely, when one mentions asymmetric keys it
> is usually associated with a PKI. In case of VPNs, I would argue that
> the best solution is to have pre-shared public keys; it is much easier
> to exchange those over public communication channels,
Sharing a public key over a public channel is meaningful only if you have a way to authenticate that it came from who you think it came from.  That's a problem just as hard as keeping the shared key secret as it's being transmitted.

> and if you use
> ephemeral Diffie-Hellman key exchange signed with those public keys, you
> get PFS, something that is not possible with pre-shared symmetric keys.
That's false.  PFS has a mystique around it, but in fact it's trivial to produce in a symmetric system, as I showed on this list not long ago.  Suppose you and I share a secret initial key K.  The operations are then:

	Send(M):
		E = E(K, M); K = H(K);

	Receive(E):
		M = D(K, E); K = H(K);

where H is a one-way hash function, and the operation of assigning to K irretrievably destroys the old value.

Practical implementations can adjust this.  The size of M, for example, is a security choice; it could be as small as a single block for a block cipher, or as large as you are comfortable with.  It's just necessary that the receive know where M ends.  (Ideally that information is inside the plaintext so an attacker can't even tell when the key changes.)

In practice, K is a session key, negotiated using a DH combined with a "negotiation shared secret" never used for anything else.

If you are concerned about key recovery attacks that work against some encrypted messages (and which would allow an attacker to "walk forward" from a recovered key), you can replace the key updates by:

	Initialize:
		i = 0;
		MS = master secret;

	Update:
		i = i + 1;
		K = H(MS, i);

Sending i along in the clear is safe and allows the receiver to decrypt messages out of order and recover from lost ones.

Here H is your favorite keyed one-way hash.  (MS remains unique per connection to avoid having to save i across connections.)
                                                        -- Jerry