Has the Tor project considered using NTRU?

Question

The Tor Project is switching to ECC, a set of algorithms promoted by the NSA. People like Bruce Schneier have mentioned concerns about both NSA's promotion of this algorithm, as well as the chosen constants.

NTRU appears to have a variety of benefits, both performance wise and in the light of recent advancements regarding quantum computers.[1]

Are there any benefits of ECC over such an algorithm? If not, why isn't the Tor Project switching to NTRU in place of ECC?

[1] http://tbuktu.github.io/ntru/

Answer 1

There's now a specific proposal for NTRU: https://gitweb.torproject.org/torspec.git/tree/proposals/263-ntru-for-pq-handshake.txt

There's also an algorithm called "New Hope" that sounds to be a promising alternative: https://www.imperialviolet.org/2015/12/24/rlwe.html

... and apparently a new version on it's way called "Newest Hope". This from the winter 2016 tor dev meeting notes. Sounds like the plan is to implement both

Answer 2

I would say advantages of ECC are:

1. Performance—see Curve25519 performance on linked page
2. More analysis—this is debatable, but I would say ECC is better understood in the crypto community than lattices.
3. Spotty history of NTRU, which had to be revised several times, IIRC, based on cryptanalytic attacks.

I think there might also be patent issues around NTRU, but I'm not sure. Also, it's worth noting that it's the NIST curves that are the most suspect from the NSA standpoint; there is some chance that they can break all ECC, but there's not much evidence of this.

As far as the quantum computing, my feeling is that there is a very large gap between what is possible in QC today and what would be needed to break ECC in practice. Post-quantum algorithms are an important research subject, but I don't see a strong argument for deploying them at the moment.

Answer 3

(This is in regards to meee's response, but I don't have enough reputation points to add a comment)

They do include BSD and a bunch of other licenses in their FOSS license exception: https://github.com/NTRUOpenSourceProject/ntru-crypto/blob/master/FOSS%20Exception.md

So Tor should be able to use libntru which is BSD-licensed, but it might still not be a good idea. If, for example, somebody wanted to sell a Tor-ready home router, they would probably be asked for patent royalties. If I were the Tor people, I wouldn't consider NTRU until the basic patent expires in 2017.

Answer 4

I did further research on this.

NTRU appears to have an exception only for GPL code (there is a version by the company creating NTRU), but since Tor is BSD it won't fit well. (not true, see Tim Buktu's comment)

Also researching on this question it seems that at leas Jacob Appelbaum (Tor developer) did some research on this too: https://twitter.com/ioerror/status/381940375075569665

Also he forked CyaSSL on GitHub which supports it: https://github.com/ioerror/cyassl

Answer 5

NTRU for Tor is still being plugged: http://csrc.nist.gov/groups/ST/post-quantum-2015/papers/session3-zhang-paper.pdf

NTRU does sound to be faster than some other quantum-safe algs. NTRU protects against Shor's algorithm but the standard parameter sizes for NTRU are not safe against Grover's algorithm on a quantum machine. For 128-bit parameters there's a 112 bit attack to recover keys and an 80 bit attack to recover plaintext (ie. sender's identity). https://www.authorea.com/users/34470/articles/39844

Tor does need to be quantum-safe, what other quantum-safe algs might work for Tor?

Answer 6

One of the important features of elliptic curve Diffie-Hellman key exchanges using a curve like Curve25519 (which was created by Daniel Bernstein and not those people at NSA) is that it offers Perfect Forward Secrecy.

However, NTRU doesn't provide a Diffie-Hellman-like key exchange with Perfect Forward Secrecy. NTRU is a public key encryption scheme like RSA. Just as people who want perfect forward secrecy in TLS have stopped using RSA for keying, people should not want to use NTRU.

I have seen another Post Quantum Scheme that seems more like Diffie-Hellman and offers security against quantum computer attacks. It is called the Supersingular Isogeny Key Exchange. It first came out in 2011 from the University of Waterloo. Here is a link to its Wikipedia page:

http://en.wikipedia.org/wiki/Supersingular_Isogeny_Key_Exchange

One of the designers of this key exchange posted code for this scheme at:

https://github.com/defeo/ss-isogeny-software/

This key exchange seems to offer quantum security, perfect forward secrecy, and relatively small key sizes compared to other quantum secure key exchanges.