[tor-dev] Quantum-safe Hybrid handshake for Tor

[Yawning Angel]

Hello,

On Thu, 31 Dec 2015 20:51:43 +0000
isis <isis at 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).

> > 2. 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,

-- 
Yawning Angel
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160101/04bceca1/attachment.sig>