Hello,
On Thu, 31 Dec 2015 20:51:43 +0000 isis isis@torproject.org wrote: [snip]
I feel like there needs to be some new terminology here. It's certainly not post-quantum secure, but "quantum-safe" doesn't seem right either, because it's exactly the point at which the adversary gains appropriate quantum computational capabilities that it become *unsafe*. If I may, I suggest calling it "pre-quantum secure". :)
Post-quantum forward-secrecy is what I've been using to describe this property.
[snip]
However, if we were to go the route of using NTRU, we'd likely want to instead use Dan Bernstein's NTRU Prime parameters, in order to eliminate some of the inherent algebraic structure of the ideal lattice which might possibly be exploited. [0] [1]
That's a non-trivial amount of work, though I have issues with the parameter selection as well, that the authors of the proposal may be able to qualify.
As I recall, the product form parameter sets are extra encumbered. Apart from key/ciphertext size and a minor performance differential, is there any reason to not use one of the X9.98 parameter sets (Eg: EES613EP1)
Also, what is the current state of patents on NTRU? My understanding is that NTRU is dual-licenced as GPLv2+ and commercial, [2] however, Tor is currently BSD licenced. Would it be necessary to relicense Tor as GPLv2+? Will the GPL exceptions continue to be applied to further patents on optimisations and improvements/protections for NTRU?
There's a FOSS patent grant, and Tim Buktu has a 3BSD NTRU implementation. (NB: The only implementation I looked at in depth is the reference Java code.)
https://github.com/tbuktu/libntru
It additionally supports deciding how encumbered you want the library to be (support for the product form parameter sets can be disabled at compile time).
Note: Debian packaging of the library is stalled due to concerns over licensing, and the bug thread ends in a "take it to legal".
https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=802259
The worst case here from our perspective depending on what Debian Legal (or Fedora Legal etc etc etc) thinks about the whole thing is that we would need to feature gate (at compile time) NTRU support till 2017/2020 (depending on parameter set choices).
- quantum-safe authentication: there is no quantum-safe
authentication in this protocol. We believe that authentication can wait, as future (quantum) adversary cannot come back to present time and break authentication. Hence, we use ntor authentication to keep the proposal compact and simple. It will be a future work after this proposal.
Not to delay progress on making Tor post-quantum secure, but if we tackled both encryption and authentication in parallel, we'd better able to compare the advantages and disadvantages of schemes, given that we can take overhead fully into account, e.g. total added keysize(s). For example, if we were to add something like a McEliese CFS signature (code-based) or an XMSS signature (hash-based) to add authentication, on top of already using some lattice-based cryptosystem like NTRU, we would have two quite large keys, with one or both needing to be distributed, for each relay.
I personally don't think that any of the PQ signature schemes are usable for us right now, because the smallest key size for an algorithm that isn't known to be broken is ~1 KiB (SPHINCS256), and we probably can't afford to bloat our descriptors/micro-descriptors that much.
If we decide we want to add PQ authentication with one of the current primitives Right Now, we could do something like:
* Add a SPHINCS256 key to "the list of long term relay keys" and distribute it in descriptors/microdescriptors. (~1KiB binary, lots bigger b64ed).
* The responder signs all the public parameters with their SPHINCS key as part of the key exchange (Go find the SIGMA paper). (+41 KiB binary, for the signature).
But I would view that as premature (there's more important things that need to use PQ signatures first, like the consensus) due to primitive maturity/usability/overhead concerns.
Other changes that should/could be made to the proposal:
* "For 128 bits quantum security, use NTRU_EESS743EP1." should be "For 256 bits" (Section 2.3).
* We have the opportunity (and code in master) to start using the FIPS 202 primitives. Since we need to modify the ntor code to anyway, we should use SHA-3 and SHAKE256 instead of HMAC-SHA256 and HKDF-SHA256 respectively.
* Is it worth migrating our ECC to X448?
I'll be fleshing out the proposal to specify 0x0103 around newhope, since the hybrid construct would be similar past the details of the key exchange itself.
Regards,