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

[Yawning Angel]

On Mon, 16 May 2016 20:54:42 +0200
Jeff Burdges <burdges at gnunet.org> wrote:

> Just a a couple questions :
> 
> Is SIDH costing 100 times the CPU such a big deal, assuming it's
> running on another thread?  Can it be abused for DOS attacks for
> example?  Is that CPU time needed for symmetric crypto?  etc.  If so,
> is it worth restricting to your guard node? 

Yes.  Even if it's multithreaded (and the client side circuit build
crypto currently is not, though will be shortly), though this obviously
"depends" on what each node is doing.

Eg:

 * Client side performance is totally irrelevant up until the moment
   it becomes a busy HS (Eg: facebookcorewwwi.onion) in which case, it
   matters a huge deal (the X25519 scalar mult montgomery ladder has
   been a prominent feature in all of our profiling attempts for quite
   a while).

 * Relay side performance is totally irrelevant up until the moment it
   offers a lot of bandwidth, because the way our path selection weighs
   things right now, circuit builds will be weighted by consensus
   fraction.

We used to have a slower handshake, and it was causing issues (TAP and
that stupid botnet).  Maybe I'm being over-cautious here.  Maybe even
the hybrid construct is too slow.  Maybe bandwidth matters more.

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...

> Is New Hope's 3+ times the bandwidth a big deal?  I suppose circuit
> building does not occupy much bandwidth, so no.  

It might.  Sending bytes isn't free in terms of CPU either.  The
NTRUEncrypt based construct is fast and has shorter keys.

> > I don't think SIDH is really something to worry about now
> > anyway...  
> 
> If you like, I could ask Luca de Feo if he imagines it getting much
> faster, but I suspect his answer would be only a smallish factor, like
> another doubling or so. 
> 
> Assuming we stick to schemes with truly hybrid anonymity, then I
> suspect the anonymity cost of early adoption is that later parameter
> tweaks leak info about a user's tor version.  We can always ask the
> MS SIDH folk, Luca, etc. what parameters could be tweaked in SIDH to
> get some idea. 

Agree here, though there is an auto updater for a reason, and if we
we end up being overly concerned about that we won't even be using
X25519....

[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.

> Imho, almost anyone protecting user-to-user communications should
> hybrid ECDH, Ring-LWE, and SIDH all together, as users have CPU
> cycles to burn. Tor is user-to-volunteer-server though, so the
> economics are different. 

Dunno, I think this depends entirely on "how much money does the person
operating the server have to throw at adding more CPU" vs "how many
connections/sec does it need to sustain.

I think doing something like SIDH on a massively popular website (say,
hypothetically it gets added to TLS) would get expensive really
quickly, but then again, it's VC monopoly money that's paying for it
anyway, and it's not like they ever need to turn a profit right?
(*cough* Twitter *cough*).

Regards,

-- 
Yawning Angel
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160516/350a4154/attachment.sig>