4

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/

2

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

6

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.

  • But the performance (other than key generation) appears to be better on NTRU. – meee Jun 6 '14 at 8:36
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.

2

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

2

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?

1

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.

  • 3
    Forgive me if I am wrong, but isn't Perfect Forward Secrecy independent of the cryptographic algorithm in use (other than being a form of public key cryptography maybe)? – meee Oct 18 '14 at 10:24
  • 1
    You are correct. However, getting perfect forward secrecy with some cryptographic algorithms is harder than with others. In the case of NTRU you can get forward secrecy but you have to do two exchanges of information. First each side of the exchange has to generate a public key. Then they have to exchange public keys. THEN (and this is the additional step) the users have to encrypt their random values using the other sides public key and send that. A Diffie-Hellman key exchange allows you to establish a random key with only one pass. – luiz carvalho Oct 19 '14 at 17:16
  • 1
    In Diffie-Hellman or the Supersingular Isogeny Key Exchange. You exchange random information in the first pass and don't need to do a second pass. NTRU can fit in many of the places one would use RSA. It isn't a great fit for replacing Diffie-Hellman or elliptic curve Diffie-Hellman. The Supersingular Isogeny Key exchange or other key exchange is better for that. See the Wikipedia page on Post Quantum Cryptography for more. – luiz carvalho Oct 19 '14 at 17:23
  • The wikipedia page claims that SIDH keys are small enough for them to fit into tor cells. Is this claim correct? – Chiffa Jun 14 '17 at 16:45
  • @Chiffa For the so-called "compressed SIDH keys", yes it is. – forest Feb 17 at 11:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.