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

[Peter Schwabe]

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

-------------- 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/20160525/4433fd4b/attachment-0001.sig>