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

[Yawning Angel]

On Sat, 7 May 2016 19:41:59 +0000 (UTC)
lukep <lukep at tutanota.com> wrote:
> Thanks isis for this, it looks really good, I look forward to seeing a
> similar protocol for SIDH! (and X25519+NEWHOPE+SIDH !)

When there is a sufficiently fast SIDH implementation, it might be worth
considering (MS Research's is less slow than prior attempts at this,
but misses the mark).

On Sat, 07 May 2016 22:51:27 +0200
Jeff Burdges <burdges at gnunet.org> wrote:
> 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.  

I think that being in the position to gather the timing information
required on the client side means the adversary has won already, so I'm
not seeing the issue here apart from an abstract theoretical sense.

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

For clarity regarding what the code does now:

The reference code generates excess output from the initial SHAKE call,
and samples from that, and incrementally squeezes out an additional
block one at a time as required (Enough for 1344 elements, with each
additional squeeze providing 21 elements).

(The rejection sampling algorithm is somewhat wasteful since it discards
 2 bits of input per sample as well, but what's done now is easier to
 implement.)

> I've no idea if an maybe an arithmetic coding scheme would be more
> efficient.
> 
> > 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. 
> 
> If bandwidth is an issue, then a could be derived from the ECDH
> handshake, thereby making it zero cost. 

Err.  I'm not sure how that will work without rejection sampling that
exposes timing information, maybe I'm missing something.

I had a brief discussion with Dr. Schwabe regarding using
deterministic `a` generation for unrelated reasons, with something time
based being tossed around, but requiring a global clock isn't that
great, and leaks clock skew information (Though I would use something
like H(tweak | unixTime / 3600), which is rather coarse...), and as a
peace of mind thing, I do prefer randomizing `a` on a per-connection
basis.

But anyway like I said, I don't think this is an issue.

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/20160507/2e4ffe3f/attachment.sig>