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

Wed May 25 15:23:43 UTC 2016

Hi Peter,

Thanks for such a nice overview of current discussions. Just want to
give a quick update on the NTRU.

> - NTRU is around for the longest time and has, even with high-security
>   parameters, fairly short messages. However, existing software
>   implementations (at least the ones in SUPERCOP) are highly vulnerable
>   to timing attacks. Key generation (with protection to against timing
>   attacks) is, as far as I can tell, fairly expensive.

We are working on a constant-time implementation of NTRU. We expect to
release the source code this summer. 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.

> What I'm missing in the discussion are benchmarks of NTRU and NTRUprime
(in
> the context of key exchange).

Please see the attached for some benchmark results. 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.

> Would it help the discussion at this point to fix NTRU parameters, produce
> an optimized implementation of NTRU (not production-quality code for Tor,
but
> something to obtain benchmarks) and compare performance of NewHope, NTRU,
and
> NTRUprime in an ephemeral key exchange? This would be a nice project for a
> Ph.D. student.

It would be very interesting indeed. We need to fix the parameter sets for
NTRU.
Currently we have
1. ntru-443 with product form, providing 128 pre-quantum/post-quantum
 security
2. ntru-743 with product form, providing 256 pre-quantum and >128
post-quantum security
3. ntru-887 with non-product form, providing 256 pre-quantum security
And all of those parameter sets uses SHA256 rather than SHA-3 as suggested
by the community.

It would be nice to have a final decision on
a. shall we use non-production form
b. shall we remove the IND-CCA-2 feature
c. shall we use ntru-743/887 to build a sufficiently large margin just like
NTRUprime

Cheers,
Zhenfei

On Tue, May 24, 2016 at 6:32 PM, Peter Schwabe <peter at cryptojedi.org> wrote:

> bancfc at openmailbox.org wrote:
>
> Hi all,
>
> > Some great developments in lattice-based crypto. DJB just released a
> paper
> > on NTRU Prime:
>
> Let me just also throw in my 2 cents:
>
> As far as I can tell, there are now 5 approaches to post-quantum key
> exchange that are discussed (or at least have surfaced) in this thread:
> - NTRU
> - NewHope
> - NTRUprime
> - McEliece
> - SIDH
>
> In some of the posts I got the impression that there are considerations
> for some sort of "algorithm agility" in the key exchange. This can mean
> two things:
> - runtime algorithm agility, such that a client can choose what
>   algorithm to use according to some strategy; or
> - upgrading algorithm agility, which means that for each version number
>   of a client, it is very clear which algorithm it will use, but the key
>   exchange supports (easy) upgrading to better algorithms with
>   increasing version numbers.
>
> In my opinion, the second approach is extremely important, in particular
> because at the moment we certainly want some sort of PQ key exchange,
> but are quite uncertain about what approach will prove best in the long
> run.
> I'm not really sure whether anybody really suggested the first approach,
> but just in case, I think it's a terrible idea. If the decision of what
> algorithms to use is left to users, they will certainly end up making
> worse choices than experts; if it's left to randomness, users inevitably
> get the worst out of the set from time to time. I simply cannot think of
> any strategy that lets the user win here.
>
> Now, out of the 5 proposals, my impression is that McEliece with binary
> Goppa codes has been killed as an idea for key exchange in Tor and that
> whenever somebody mentions it again, Isis will just shout "KEYSIZE" to
> make sure that it remains dead.
>
> I can see good reasons for each of the first three (lattice-based)
> proposals:
>
> - NTRU is around for the longest time and has, even with high-security
>   parameters, fairly short messages. However, existing software
>   implementations (at least the ones in SUPERCOP) are highly vulnerable
>   to timing attacks. Key generation (with protection to against timing
>   attacks) is, as far as I can tell, fairly expensive.
>
> - NewHope is explicitely designed for ephemeral key exchange (not
>   public-key encryption), i.e, for the operation that is required. It
>   offers best performance and, as Isis pointed out, the paramters we
>   propose have the largest security margin against all known attacks.
>   Disadvantage (price to pay for the security margin): somewhat longer
>   messages.
>
> - NTRUprime is much less conservative than NewHope in its parameter
>   choices against known attacks but offers "defenses" against attacks
>   that may or may not work against NewHope and NTRU.
>   The advertisement of those defenses is a pretty good job of the
>   marketing department: the wording suggests that NTRUprime is, at the
>   same bit-security level, at least as secure as NTRU or NewHope, but
>   then has those defenses as additional safeguards. This is not quite
>   true: NTRUprime operates in a different mathematical structure, which
>   may in the long run prove more secure, it may also prove less secure
>   and it could turn out that the "defenses" against hypothetical attacks
>   turn out to be weaknesses against other attacks.
>   Having said that, I really like the ideas of the NTRUprime paper and
>   much more often than not have Dan and Tanja been right with their
>   intuition for cryptographic design.
>
> What I'm missing in the discussion are benchmarks of NTRU and NTRUprime (in
> the context of key exchange). For NTRUprime there is not even a proposal
> for
> ephemeral key exchange as needed in Tor; however, I assume that it's not
> too
> hard to replace NTRU operations (from the NTRU proposal) by NTRUprime
> operations. Also (please correct me if I'm wrong), for NTRU it's not clear
> what parameters to use and there is no optimized and timing-attack
> protected
> implementation.
> Would it help the discussion at this point to fix NTRU parameters, produce
> an optimized implementation of NTRU (not production-quality code for Tor,
> but
> something to obtain benchmarks) and compare performance of NewHope, NTRU,
> and
> NTRUprime in an ephemeral key exchange? This would be a nice project for a
> Ph.D. student.
>
>
> Now, then there is SIDH: I really like SIDH, not so much for the shorter
> public keys (that's nice, but it's not like a difference of an order of
> magnitude), but because of two other reasons:
> 1.) It is a completely different approach and even if all
>     non-standard lattice crypto falls, SIDH may survive.
> 2.) It's offering the same functionality as (EC)DH right now; both
>     parties can compute their public keys without having received the
>     public key of the other party. This is a great feature for protocol
>     design and for migrating existing DH-based protocols to a
>     post-quantum setting.
> However, I don't think that SIDH is ready for use at the moment. The
> reason is not only that it's about 300x slower than ECC, the reason is
> that security is really not understood at all. While probably everybody
> in the crypto community expects some progress in lattice attacks over
> the next few decades, I don't think that anybody seriously expects a
> polynomial-time algorithm that breaks, for example, Ring-LWE with
> suitably chosen paramters. A polynomial-time algorithm to break SIDH
> would clearly be a major breakthrough with an immediate-accept at any of
> the big crypto venues, but I would not want to really bet anything
> important (like my life in freedom) against this happening.
> I talked to Michael Naehrig (co-author of the Crypto paper this year
> implementing SIDH) two days ago and mentioned that SIDH popped up in
> this discussion as a possible approach for Tor. His reaction was roughly
> along the lines of "We say in our paper that you shouldn't use this, and
> very certainly not in Tor".
>
> So, I hope that SIDH will survive in the long run, after serious
> cryptanalytic effort trying to break it; I hope that it will become
> faster by, say, a factor of 100 (that's not totally inconceivable,
> pairings took minutes to compute at the beginning, now we're below a
> millisecond) and if this happens then Tor should migrate to SIDH. Not
> now.
>
> As I said, just my 2 cents.
>
> 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/20160525/e0fd18ba/attachment.html>