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

[isis]

Yawning Angel transcribed 4.3K bytes:
> 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).

When there is also sufficient cryptanalysis of curve-isogeny-based
cryptosystems…

Also, I'm not understanding what SIDH would provide in an X25519+NewHope+SIDH
construction which is not already provided in the X25519+NewHope construction,
unless someday there are SIDH-based signatures.

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

Your point that an adversary with native-code execution on the client's
machine is capable to do worse makes sense.  However, given that there are
browser-based cache timing attacks (e.g. RowhammerJS) which give cache
eviction rates only negligably different to those of native-code exploits, I
would argue that Jeff's original concern that the timing attack presents a
distinguisher is actually a valid concern.

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

Nope, it would still not work to fix the timing attack.  Although, luckily, we
already wrote some constant time code for my sorting-network idea, and then,
with some coffee, Peter made it faster.  (Give us something stronger to drink,
and we'll probably come up with a way to get it even faster.)

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/888b96c8/attachment-0001.sig>