[tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope

[lukep]

Yawning Angel <yawning at ...> writes:

> 
> Implementing the infrastructure to allow runtime selection of a PQ
> handshake, and actually doing any PQ handshake are required to really
> investigate these sort of issues instead of arguing over algorithms...
> 

Right. It's probably too premature to make a final, definitive choice of PQ
algorithm since any of them could be broken mathematically. The possibility
of backdoors in newhope (at least two different ways to do it) makes me
nervous. SIDH is (perhaps?) too slow now but computers will get faster. NTRU
is patented for the moment, but that will expire soon. It's all a tradeoff
between security / cpu cycles / bandwidth and that tradeoff is bound to
change over time.

So we should have a protcol that allows a hybrid of X25519 for classical
security plus one or more (or even zero, until we want to "switch it on") of
the PQ algorithms. Use EXP(Z,x) to protect the choice of PQ algorithms and
the actual PQ public key(s). Combine the X25519 shared secret and (all) the
PQ shared secret(s) in one SHAKE-256 calculation to give sk.

We'd need to think about what choice of PQ algorithms the client is allowed
to make and what the server would accept. The risk is that we go down a
rabbit-hole of TLS-style algorithm negotiation to agree on algorithm choices
that are acceptable to both - we want it to "just work" without argument.
But if we don't allow some choice, then we may find that the protocol is too
slow, or the bandwidth too cumbersome, or we panic when one of the PQ
algorithms is broken.

> [snip]
> > In other words, I'd expect our future trust in Ring-LWE and SIDH to
> > evolve in different ways.  And counting papers will not be
> > informative. 
> 
> Yeah probably.  I can envision having no choice but to use SIDH
> sometime in the future (or vice versa).  It's an evolving field, and my
> current mindset is "pick one or two that probably won't kill the network
> (CPU/network/whatever)", integrate it in a way that is easy to switch
> at a later point, and deploy it.

The important thing now is surely to get the protocol right so that we can
slot algorithms in or out (then pick one or two that we actually want to
integrate)


-- lukep