[Cryptography] Signal double-ratchet vs. future breaks in ECC?

[Jason Cooper]

On Mon, Jul 30, 2018 at 06:10:50PM -0700, Jon Callas wrote:
> > On Jul 27, 2018, at 9:41 AM, Nemo <nemo at self-evident.org> wrote:
> > 
> > I asked this on the Crypto StackExchange but got no replies:
> > 
> >    https://crypto.stackexchange.com/q/60660/
> > 
> > I understand how a "double ratchet" protects both future and past
> > messages from one-time key compromise.
> > 
> > My question is what happens if the public key (ECC) algorithm is broken,
> > while the hash function(s), symmetric algorithm(s), and keys themselves
> > remain secure. (Consider a hypothetical mathematical breakthrough on
> > elliptic curves, or quantum computers becoming practical...)
> > 
> > Perhaps somebody here knows the answer or can explain why it is a dumb
> > question?
> 
> It’s not a dumb question. It shows that you are thinking more than many people are.
> 
> Here’s really a simple explanation:
> 
> Naively, you use an algorithm like DH or RSA to do “key exchange” where we exchange random bit strings and use them as keys. But you don’t *have* to use the thing you exchanged as a key, you could use it as – let’s call it a *credential* and you then derive a key from there.
> 
> If you’re using ECDH, you pretty much have to do this because you’re not exchanging a number, you’re exchanging a *point*, (x,y), and have to run that point through a KDF. (Strictly speaking, if you’re using integer DH or RSA, you’re also exchanging a point, it just happens to be a point on The Number Line and just as we all remember from elementary school, you can use points on The Number Line as if they were numbers. Or perhaps they really are numbers, but now we’re getting into Foundations of Mathematics which I adore as a subject, but it’s a digression.)
> 
> The double ratchet is really just a scheme for taking a credential and deriving a series of keys from that credential that has a bunch of desirable properties, but yes, if that initial credential exchange is compromised by any means from quantum computers to stupidity the whole security is blown. Game over.
> 
> And that’s why no one is answering that question because it’s a case of the abyss staring back.

Here's a generic scenario to help bring the point home:

Note: this is an engineering overview, not a rigorous mathematical
example.  :)

Let say Eve sniffs the wire and receives two ECDH(E) public keys P_a,
and P_b which belong to Alice and Bob, respectively.  Those public keys
are paired with the private keys, K_a and K_b.

Shared secret S_ab is calculated by Alice:

	S_ab = ECDH(K_a, P_b)

and Bob does:

	S_ab = ECDH(K_b, P_a)

The first session key may be derived by both Alice and Bob as follows:

	S_1 = KDF(S_ab, "session 1")

Alice  may then encrypt a message by:

	E_1 = AEAD(S_1, "this is a test message")

Bob has S_1, and so is able to decrypt E_1 to recover the plaintext.
Eve can sniff E_1, but doesn't have access to K_a nor K_b, so isn't able
to calculate S_ab, nor S_1.

However, if Eve has a sufficiently large QC, she can use P_a to recover
K_a.  Now, Eve can calculate S_ab from

	S_ab = ECDH(K_a, P_b)

>From there, she can calculate S_1, which will allow her to decrypt E_1.
And according to the specification of the target protocol, Eve will be
able to derive any key from S_ab that she needs.  And that's the Abyss
part, she obtained the lynch pin without physical or network attack.


hth,

Jason.