[messaging] Post-quantum forward-secrecy

[Trevor Perrin]

On Wed, Aug 5, 2015 at 7:35 AM, Jeff Burdges <burdges at gnunet.org> wrote:
>
> Question : Can we design a post-quantum ratchet like Axolotl?  It could
> use NTRU or perhaps another approach.
>
>
> Here would be my naive approach :
>
> Afaik, any "two step" ratchet like Axolotl, Axolotl without hash
> iteration, etc. needs to communicate the curve25519 public key that
> updates the ratchet for the current message in a header outside the body
> of the message itself.
>
> If we leave this key unencrypted, then an attacker with information on
> weaknesses in a sizable portion of the curve25519 key space could
> examine a conversation history in parallel to discover how much of the
> conversation they could potentially decipher, and then choose to spend
> their resources attacking all those keys, again in parallel.

As an aside, discrete log is "random self-reducible" - if you can
solve a "sizeable portion" of instances, you can solve all of them.


> [...] There might be simpler ways to do effectively the same
> things too.


You could do an expensive post-quantum calculation alongside an EC key
agreement, hash the results, and then use the shared secret as input
to a ratcheting protocol.

If you wanted the ratchet protocol to also do an OTR/Axolotl-like "DH"
step but with post-quantum added, you could consider a few things:
 - Perform the PQ+ECDH steps in parallel, to keep the complexity
manageable, i.e. consider the combination of new PQ and new EC keys as
a single "thing"
 - Maybe perform PQ+ECDH updates less frequently, i.e. instead of
Alice and Bob ping-ponging new PQ+EC keys as fast as they can, defer
introducing a new key until some time has elapsed, to amortize costs
 - Separate the notion of "I'm acknowledging your last update" from
"here is my new PQ+EC key", so that Bob could tell Alice to stop
re-sending her last update keys (to save space) prior to sending his
next key.


Trevor