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

[lukep]

Peter Schwabe <peter at ...> writes:

> 
> isis <isis at ...> wrote:
> 
> Hi all,
> 
> > 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.)
> 
> Still on coffee and with a size-84 Batcher sort and Yawning's 5q trick I
> now have an AVX2 implementation of NewHope that is faster than the
> original and does sampling of the polynomial a in constant time. Now I'm
> up for some stronger drinks...
> 

You may want to get more drinks in - there's a new eprint on IACR archive
that's claiming a faster generation of 'a' using the 5q / 16 bit trick:
https://eprint.iacr.org/2016/467.pdf

The other change they make is to replace SHAKE by SHA-256 and AES-256 on the
grounds that finding a backdoored 'a' would be implausible, although they no
longer have the security reduction. Also they're not considering timing attacks.

They get a speed-up of about 1.5x on AVX2. Personally I don't really care
about not having the security reduction for 'a' (there's still the proof in
the newhope paper for the rest of the key exchange). 

The bandwidth can be halved for n=512 vice n=1024 - this is the JarJar of
NewHope - maybe dubious by itself but could be strong enough in hybrid with
X25519 given that bandwidth is at a premium in Tor?


-- lukep