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

[Peter Schwabe]

Zhenfei Zhang <zzhang at securityinnovation.com> wrote:
> Hi Peter,

Hi Zhenfei, hi all,

> We are working on a constant-time implementation of NTRU. We expect to
> release the source code this summer. 

That's great news! Any thoughts on the license? Can you place it into
public domain?

> However, as far as I know, timing attacks are much more powerful
> against encryption algorithm (that uses long-lived key for multiple
> times), rather than KEMs (use ephemeral keys).  Our proposal treats
> NTRU as a KEM so I think the timing attack is not so useful.

It's tricky; I agree that if you get only a single timing trace with the
same key, it will be much harder to get useful information about the
key than in a public-key encryption (or signature) setting where the
private key is used many times. Then again, I also think that it will be
very hard to prove that it's impossible to extract useful information
about keys from timing on any platform.
Maybe more importantly, Tor does not only have to be concerned about
leaking the key, but also leaking de-anonymizing information. That's why
Isis and I sat down and wrote a constant-time version of the sampling of
the public polynomial in NewHope. 
My general take on this is that it's much easier to write constant-time
code than to deal with the fallout caused by software that is vulnerable
to timing attacks.

> Please see the attached for some benchmark results. 

Did the attachment get lost?

> We are working on the camera-ready version of the paper. The final
> version should be out soon.  Also note that we are using an IND-CCA-2
> secure version of NTRU. The performance can be further improved by
> switching to the IND-CPA secure version. IND-CPA is enough to provide
> channel security, provide that the ciphertext is accepted for only
> once for a given key. (This may open doors to some DoS attack.) As far
> as I can tell, the NewHope and NTRU-prime all uses CPA secure
> encryption algorithms.

Definitely true for NewHope. 


Here's what my answers would be to your questions:

> It would be nice to have a final decision on
> a. shall we use non-production form

Would be interesting to see benchmarks of both.

> b. shall we remove the IND-CCA-2 feature

Again, it would be interesting in a larger context to have benchmarks of
both; the Tor handshake should be fine with IND-CPA.

> c. shall we use ntru-743/887 to build a sufficiently large margin just like
> NTRUprime

Definitely. As I wrote in my previous mail, in NewHope we went for a
much larger margin than NTRUprime did; I would probably feel better with
887, but for long-term security (and this is what the whole thing is
about), 743 is a must-have.


Cheers,

Peter
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 811 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160526/b9b0f751/attachment-0001.sig>