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 <[email protected]> wrote: > [email protected] 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 > [email protected] > https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev > >
_______________________________________________ tor-dev mailing list [email protected] https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
