Peter Schwabe <peter@...> writes:
isis <isis@...> 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