<div dir="ltr"><div style="font-size:12.8px"><div><div>Hi Peter, <br><br></div>Thanks for such a nice overview of current discussions. Just want to <br></div>give a quick update on the NTRU.<span class="im"><br><br><br>> - NTRU is around for the longest time and has, even with high-security<br>> parameters, fairly short messages. However, existing software<br>> implementations (at least the ones in SUPERCOP) are highly vulnerable<br>> to timing attacks. Key generation (with protection to against timing<br>> attacks) is, as far as I can tell, fairly expensive.<br><br></span></div><div style="font-size:12.8px">We are working on a constant-time implementation of NTRU. We expect to <br></div><div style="font-size:12.8px">release the source code this summer. However, as far as I know, timing<br></div><div style="font-size:12.8px">attacks are much more powerful against encryption algorithm (that uses <br>long-lived key for multiple times), rather than KEMs (use ephemeral keys).<br></div><div style="font-size:12.8px">Our proposal treats NTRU as a KEM so I think the timing attack is not so<br></div><div style="font-size:12.8px">useful.<span class="im"><br><br>> What I'm missing in the discussion are benchmarks of NTRU and NTRUprime (in<br>> the context of key exchange).<br></span></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Please see the attached for some benchmark results. We are working on <br></div><div style="font-size:12.8px">the camera-ready version of the paper. The final version should be out soon.<br></div><div style="font-size:12.8px">Also note that we are using an IND-CCA-2 secure version of NTRU. The<br></div><div style="font-size:12.8px">performance can be further improved by switching to the IND-CPA secure<br></div><div style="font-size:12.8px">version. IND-CPA is enough to provide channel security, provide that the</div><div style="font-size:12.8px">ciphertext is accepted for only once for a given key. (This may open doors</div><div style="font-size:12.8px">to some DoS attack.) <span style="font-size:12.8px">As far as I can tell, </span><span style="font-size:12.8px">the NewHope and NTRU-prime all</span></div><div style="font-size:12.8px"><span style="font-size:12.8px">uses CPA secure encryption algorithms.</span></div><span class="im" style="font-size:12.8px"><div><br>> Would it help the discussion at this point to fix NTRU parameters, produce<br>> an optimized implementation of NTRU (not production-quality code for Tor, but<br>> something to obtain benchmarks) and compare performance of NewHope, NTRU, and<br>> NTRUprime in an ephemeral key exchange? This would be a nice project for a<br>> Ph.D. student.<br></div><div><br></div></span><div style="font-size:12.8px">It would be very interesting indeed. We need to fix the parameter sets for NTRU.<br></div><div style="font-size:12.8px">Currently we have <br></div><div style="font-size:12.8px">1. ntru-443 with product form, providing 128 <span style="font-size:12.8px">pre-quantum/post-quantum</span> security <br></div><div style="font-size:12.8px">2. ntru-743 with product form, providing 256 <span style="font-size:12.8px">pre-quantum</span> and >128 <span style="font-size:12.8px">post-quantum</span><span style="font-size:12.8px"> security</span></div><div style="font-size:12.8px">3. ntru-887 with non-product form, providing 256 <span style="font-size:12.8px">pre-quantum </span><span style="font-size:12.8px">security</span></div><div style="font-size:12.8px">And all of those parameter sets uses SHA256 rather than SHA-3 as suggested<br></div><div style="font-size:12.8px">by the community. <br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">It would be nice to have a final decision on<br></div><div style="font-size:12.8px">a. shall we use non-production form<br></div><div style="font-size:12.8px">b. shall we remove the IND-CCA-2 feature<br></div><div style="font-size:12.8px">c. shall we use ntru-743/887 to build a sufficiently large margin just like NTRUprime</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Cheers,</div><div style="font-size:12.8px">Zhenfei</div><div style="font-size:12.8px"><div class="" style="margin:2px 0px 0px"><div id=":1gq" class="" tabindex="0"><img class="" src="https://ssl.gstatic.com/ui/v1/icons/mail/images/cleardot.gif" style=""></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, May 24, 2016 at 6:32 PM, Peter Schwabe <span dir="ltr"><<a href="mailto:peter@cryptojedi.org" target="_blank">peter@cryptojedi.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><a href="mailto:bancfc@openmailbox.org">bancfc@openmailbox.org</a> wrote:<br>
<br>
Hi all,<br>
<span class=""><br>
> Some great developments in lattice-based crypto. DJB just released a paper<br>
> on NTRU Prime:<br>
<br>
</span>Let me just also throw in my 2 cents:<br>
<br>
As far as I can tell, there are now 5 approaches to post-quantum key<br>
exchange that are discussed (or at least have surfaced) in this thread:<br>
- NTRU<br>
- NewHope<br>
- NTRUprime<br>
- McEliece<br>
- SIDH<br>
<br>
In some of the posts I got the impression that there are considerations<br>
for some sort of "algorithm agility" in the key exchange. This can mean<br>
two things:<br>
- runtime algorithm agility, such that a client can choose what<br>
algorithm to use according to some strategy; or<br>
- upgrading algorithm agility, which means that for each version number<br>
of a client, it is very clear which algorithm it will use, but the key<br>
exchange supports (easy) upgrading to better algorithms with<br>
increasing version numbers.<br>
<br>
In my opinion, the second approach is extremely important, in particular<br>
because at the moment we certainly want some sort of PQ key exchange,<br>
but are quite uncertain about what approach will prove best in the long<br>
run.<br>
I'm not really sure whether anybody really suggested the first approach,<br>
but just in case, I think it's a terrible idea. If the decision of what<br>
algorithms to use is left to users, they will certainly end up making<br>
worse choices than experts; if it's left to randomness, users inevitably<br>
get the worst out of the set from time to time. I simply cannot think of<br>
any strategy that lets the user win here.<br>
<br>
Now, out of the 5 proposals, my impression is that McEliece with binary<br>
Goppa codes has been killed as an idea for key exchange in Tor and that<br>
whenever somebody mentions it again, Isis will just shout "KEYSIZE" to<br>
make sure that it remains dead.<br>
<br>
I can see good reasons for each of the first three (lattice-based)<br>
proposals:<br>
<br>
- NTRU is around for the longest time and has, even with high-security<br>
parameters, fairly short messages. However, existing software<br>
implementations (at least the ones in SUPERCOP) are highly vulnerable<br>
to timing attacks. Key generation (with protection to against timing<br>
attacks) is, as far as I can tell, fairly expensive.<br>
<br>
- NewHope is explicitely designed for ephemeral key exchange (not<br>
public-key encryption), i.e, for the operation that is required. It<br>
offers best performance and, as Isis pointed out, the paramters we<br>
propose have the largest security margin against all known attacks.<br>
Disadvantage (price to pay for the security margin): somewhat longer<br>
messages.<br>
<br>
- NTRUprime is much less conservative than NewHope in its parameter<br>
choices against known attacks but offers "defenses" against attacks<br>
that may or may not work against NewHope and NTRU.<br>
The advertisement of those defenses is a pretty good job of the<br>
marketing department: the wording suggests that NTRUprime is, at the<br>
same bit-security level, at least as secure as NTRU or NewHope, but<br>
then has those defenses as additional safeguards. This is not quite<br>
true: NTRUprime operates in a different mathematical structure, which<br>
may in the long run prove more secure, it may also prove less secure<br>
and it could turn out that the "defenses" against hypothetical attacks<br>
turn out to be weaknesses against other attacks.<br>
Having said that, I really like the ideas of the NTRUprime paper and<br>
much more often than not have Dan and Tanja been right with their<br>
intuition for cryptographic design.<br>
<br>
What I'm missing in the discussion are benchmarks of NTRU and NTRUprime (in<br>
the context of key exchange). For NTRUprime there is not even a proposal for<br>
ephemeral key exchange as needed in Tor; however, I assume that it's not too<br>
hard to replace NTRU operations (from the NTRU proposal) by NTRUprime<br>
operations. Also (please correct me if I'm wrong), for NTRU it's not clear<br>
what parameters to use and there is no optimized and timing-attack protected<br>
implementation.<br>
Would it help the discussion at this point to fix NTRU parameters, produce<br>
an optimized implementation of NTRU (not production-quality code for Tor, but<br>
something to obtain benchmarks) and compare performance of NewHope, NTRU, and<br>
NTRUprime in an ephemeral key exchange? This would be a nice project for a<br>
Ph.D. student.<br>
<br>
<br>
Now, then there is SIDH: I really like SIDH, not so much for the shorter<br>
public keys (that's nice, but it's not like a difference of an order of<br>
magnitude), but because of two other reasons:<br>
1.) It is a completely different approach and even if all<br>
non-standard lattice crypto falls, SIDH may survive.<br>
2.) It's offering the same functionality as (EC)DH right now; both<br>
parties can compute their public keys without having received the<br>
public key of the other party. This is a great feature for protocol<br>
design and for migrating existing DH-based protocols to a<br>
post-quantum setting.<br>
However, I don't think that SIDH is ready for use at the moment. The<br>
reason is not only that it's about 300x slower than ECC, the reason is<br>
that security is really not understood at all. While probably everybody<br>
in the crypto community expects some progress in lattice attacks over<br>
the next few decades, I don't think that anybody seriously expects a<br>
polynomial-time algorithm that breaks, for example, Ring-LWE with<br>
suitably chosen paramters. A polynomial-time algorithm to break SIDH<br>
would clearly be a major breakthrough with an immediate-accept at any of<br>
the big crypto venues, but I would not want to really bet anything<br>
important (like my life in freedom) against this happening.<br>
I talked to Michael Naehrig (co-author of the Crypto paper this year<br>
implementing SIDH) two days ago and mentioned that SIDH popped up in<br>
this discussion as a possible approach for Tor. His reaction was roughly<br>
along the lines of "We say in our paper that you shouldn't use this, and<br>
very certainly not in Tor".<br>
<br>
So, I hope that SIDH will survive in the long run, after serious<br>
cryptanalytic effort trying to break it; I hope that it will become<br>
faster by, say, a factor of 100 (that's not totally inconceivable,<br>
pairings took minutes to compute at the beginning, now we're below a<br>
millisecond) and if this happens then Tor should migrate to SIDH. Not<br>
now.<br>
<br>
As I said, just my 2 cents.<br>
<br>
Cheers,<br>
<br>
Peter<br>
<br>
<br>_______________________________________________<br>
tor-dev mailing list<br>
<a href="mailto:tor-dev@lists.torproject.org">tor-dev@lists.torproject.org</a><br>
<a href="https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev" rel="noreferrer" target="_blank">https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev</a><br>
<br></blockquote></div><br></div></div>