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

[isis]

Jeff Burdges transcribed 2.6K bytes:
> On Sat, 2016-05-07 at 19:41 +0000, lukep wrote:
> > It's hard to guarantee that any fixed, finite amount of SHAKE
> > output will be sufficient for any rejection sampling method
> > like gen_a.
>  
> Isn't some small multiple usually enough?  I think 1024 is large enough
> to tend towards the expected 42%ish failures. 
> 
> Also, can't one simply start the sampling over from the beginning if one
> runs out? 

Yes, you can safely start the sampling over from the beginning without giving
anything away, other than "the seed was bad".

> > Or let a be a system-wide parameter changing say on a daily basis?
> 
> I mentioned using the Tor collaborative random number generator for a in
> my other message, but only as feint to get to the meat of my argument
> that Isis and Peter's proposal sounds optimal.  I think rotating a
> network wide a would get messy and dangerous in practice. 

Peter and I also discussed generating `a` from the Tor shared randomness, but
ultimately I feel squeamish about the potential anonymity-set segregations.

> If bandwidth is an issue, then a could be derived from the ECDH
> handshake, thereby making it zero cost. 

That would add an extra RT to the handshake, since the handshakes could no
longer happen in parallel (in my construction, they're actually literally
side-by-side, in the same CREATE2V cell).  Separating the handshake would also
mean we'd need some new cell types to handle the fact that the handshake would
take 2 RTs, since Tor's design now assumes ---CREATE*--> then <---CREATED*---.

Also, deriving `a` "somehow" from the shared X25519 secret is a bit scary
(c.f. the §3 "Backdoors" part of the NewHope paper, or Yawning's PoC of a
backdoored NewHope handshake [0]).

[0]: https://git.schwanenlied.me/yawning/newhope/src/nobus/newhope_nobus.go

Best,
-- 
 ♥Ⓐ isis agora lovecruft
_________________________________________________________
OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35
Current Keys: https://fyb.patternsinthevoid.net/isis.txt
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 1240 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160508/a5f98e7d/attachment.sig>