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

[Yawning Angel]

On Thu, 12 May 2016 20:31:56 +0200
Jeff Burdges <burdges at gnunet.org> wrote:

> On Thu, 2016-05-12 at 15:54 +0200, Peter Schwabe wrote:
> > Can you describe a pre-quantum attacker who breaks the non-modified
> > key
> > exchange and does not, with essentially the same resources, break
> > the modified key exchange? I'm not opposed to your idea, but it
> > adds a bit of complexity and I would like to understand what
> > precisely the benefit
> > is.  
> 
> Assuming I understand what Yawning wrote :
> 
> It's about metadata leakage, not actual breaks.
> 
> If Tor were randomly selecting amongst multiple post-quantum
> algorithms, then a malicious node potentially learns more information
> about the user's tor by observing the type of the subsequent node's
> handshake. 
> 
> In particular, if there is a proliferation of post-quantum choices,
> then it sounds very slightly more dangerous to allow users to
> configure what post-quantum algorithms they use without Yawning's
> change. 

Indeed, nailed it in one.

My tinfoil hat crinkles less with the idea that people need to drill
through X25519/an AEAD construct before they can start trying to break
the PQ handshake (serializing the process somewhat, instead of being
able to work on breaking each component of the hybrid construct in
parallel)[0].

Most of my thoughts in this area stem from writing an obfuscated
transport recently where I do use early encryption + padding to hide
the algorithms used for the handshake.

As a side note, if `Z` wasn't a value that the bad guys could pull out
of the microdesc consensus, we could avoid sending it on the wire (and
use the ephemeral/static derived keys for both directions) and really
win (only `X` and say... `SHA3-256(Z)` (for disambiguation) available
to the attacker means that we win, period regardless of space aliens),
but alas we need to distribute `Z` somehow, so this is somewhat moot
(so ephemeral/static in the forward direction, ephemeral/ephemeral
in the reverse is better for forward secrecy reasons).

Regards,

-- 
Yawning Angel

[0]: Even at the advent of quantum computers, I assume machine time
will be a limited resource at first (till I can buy a RasPi 3000 "Now
it's Quantum" off Amazon), and the idea of nameless suits from the
government's crypto-industrial complex squabbling over machine tasking
makes me feel warm and fuzzy inside.
-------------- 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/20160512/f801696f/attachment.sig>