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

[Zhenfei Zhang]

Hi Peter,

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

I am not 100% sure but I think it will be the same as the current NTRU
implementation.

> Did the attachment get lost?
Sorry. Here are the data extracted from our paper. The final version will
be ready in a
couple of days.

The data are based on ntru-443 with CCA-2. By moving to CPA, we may be able
to
save say 30% of computation. The ntru-743 is roughly 2.5x slower than
ntru-443.

Cheers,
Zhenfei




On Thu, May 26, 2016 at 1:35 AM, Peter Schwabe <peter at cryptojedi.org> wrote:

> 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
>
> _______________________________________________
> tor-dev mailing list
> tor-dev at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160526/fb62bdf9/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tor.png
Type: image/png
Size: 83455 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160526/fb62bdf9/attachment-0001.png>