[tor-dev] Post-quantum proposals #269 and #270

Fri Aug 5 15:07:54 UTC 2016

lukep at tutanota.com transcribed 3.2K bytes:
> Great to see the community making progress with post-quantum handshakes.

Hello,

Thanks! :)

> But I'm wondering what's going to happen with Proposals #269 and #270. #269
> seems to allow any post-quantum algorithm to be used in the hybrid with
> NTRUEncrypt and NewHope being specified as two options (presumably other
> options like SIDH or Mceliece could also be used). #270 is more specific, a
> hybrid of x25519 and NewHope. NewHope seems to be in the lead but do we want
> to rule others - so a flexible proposal like #269 might be better. #269 and
> #270 look as if they would not be compatible with each other so what's the
> process for deciding between them?

In the proposal-status document, [0] I described proposal #269 as "a
generalised protocol for composing X25519 key exchanges with post-quantum
ones" and proposal #270 as "a hybrid handshake based on the ntor handshake and
the NewHope post-quantum key exchange.  Currently needs revision to specify
how this proposal depends upon prop#269."

So it's not an either-or situation for proposals #269 and #270 — they are
entirely compatible and #269 is meant to provide modularity.  Proposal #269
emerged because there was a lot of duplicated material in both #263 (the first
NTRU handshake proposal) and #270 (the NewHope handshake proposal), and
neither #263 or #270 had a security reduction.  We assume that both attacks
and schemes for (R-)LWE cryptosystems will improve dramatically within the
next five or so years, and we would like to have the agility provided by #269
to alter the concrete instantiation should the situation change drastically,
for better or for worse.

Further, just to clarify some things: proposal #269 does not "allow any
post-quantum algorithm."  In §2.5 of "Circuit extension handshakes for Tor:
achieving forward secrecy in a quantum world" by John Schanck, William Whyte,
and Zhenfei Zhang [1] it's mentioned that the post-quantum KEM portion of a
hybrid, transitionally post-quantum secure handshake must provide
indistinguishability under chosen-plaintext attack (IND-CPA security).  There
are other, additional assumptions about the pre-quantum one-way-authenticated
side of the handshake, but these assumptions hold for ntor (with some very
trivial modifications which do not ultimately effect the security of ntor
either way).

As for the suggestion of McEliece, I've already explained why McEliece isn't
suitable for use in Tor. [2]

For the repeated suggestion of SIDH, [3] I expect we'll soon see concrete
details and improvements to the attacks mentioned in (and which they establish
"direct validation" measures to defend against in §9 of) "Efficient algorithms
for supersingular isogeny Diffie-Hellman" by Craig Costello, Patrick Longa,
and Michael Naehrig. [4]  E.g. if an adversary sends a supersingular curve E
and linearly independent points P and Q, such that Bob calculates an isogeny
ɸ: E → E' with small-degree, there could potentially be ways to utilise the
kernel of the isogeny from one handshake to learn information about the shared
j-invariant computed in another handshake.  Side note: it's a mystery to me
why the NSA and the Microsoft Research teams are jumping through hoops to
validate public SIDH keys, when they could just have the requirement that the
keys must be ephemeral (at the cost of some efficiency).  Basically, there's a
whole bunch of swinging axes, poison darts, rolling boulders, and various
other death traps and doom which come into play when you take a random
elliptic curve as your key, and I expect another ten years of papers which
slowly work to enumerate all of them.

> Also see https://eprint.iacr.org/2016/717.pdf, a comparison of attacks on
> NTRU. It doesn't break NTRU but it does break (some versions of) YASHE which
> is a FHE scheme based on NTRUEncrypt. In the conclusion it recommends
> transforming NTRU-like algorithms into ring-LWE like algorithms, and
> dismissing the former since they are known to be weaker. I still think a
> flexible protocol rather than all eggs in the NewHope basket is a Good
> Thing.

I'm not sure I follow the reasoning here.  What I hear you saying is: "Some
really weird schemes which use NTRU in an unsafe way are broken, ergo we
should remain open to schemes other than NewHope."  That still doesn't make
sense to me.

Technically, that paper presents a subfield lattice attack on "overstretched"
NTRU. "Overstretched" simply means that the modulus q is larger than usual,
relative to the size of the secret key.  To be really clear, this doesn't
break normal usage of NTRU, but only breaks scheme which do really weird
things with NTRU (like the fully-homomorphic encryption scheme you mentioned).

However, the Kirchner-Fouque paper does have consequences for NTRU Prime.
Rather than parrot him, I'm just going to quote Chris Peikert from a
discussion of this paper on another mailing list some weeks ago:

Christopher J Peikert transcribed 8.4K bytes:
> Today eprint has two new papers on topics recently discussed on this list.
>
> Kirchner and Fouque http://eprint.iacr.org/2016/717 give improved variants
> of subfield attacks on NTRU, and compare them to standard lattice
> basis-reduction attacks.  (Recall that the subfield attacks work
> increasingly well as the parameters become more "overstretched," i.e., as
> the modulus q grows relative to the size of the secret key.)
>
> One of Kirchner-Fouque's main claims (enabled by new analysis of NTRU
> lattices) is that standard basis-reduction attacks actually perform as well
> as, or even better than, the subfield attacks.  A consequence is that the
> standard attacks apply just as well to NTRU Prime, which was designed to
> have no non-trivial subfields.
>
> The authors offer many interesting conclusions:
>
> We conclude that the shortest vector problem over module lattices seems
> strictly easier than the bounded distance decoding.
>
> (NTRU is as example of the former; Ring-LWE of the latter.)
>
> Since the practical cost of transforming a NTRU-based cryptosystem into a
> Ring-LWE-based cryptosystem is usually small, especially for key-exchange
> (e.g. [3]), we recommend to dismiss the former, in particular since it is
> known to be weaker (see [40, Section 4.4.4]).
>
> (Caveat: [40, Section 4.4.4] shows that for appropriate parameters and
> formalizations of the problems, NTRU <= search-RLWE.  The reduction is not
> so tight in terms of error sizes, but there are many plausible avenues for
> improvement.)
>
> There is much more in the paper, and a lot to digest and verify.  It should
> be noted that the authors have a strong track record of cryptanalysis of
> lattice crypto.

[0]: https://gitweb.torproject.org/torspec.git/tree/proposals/proposal-status.txt
[1]: https://eprint.iacr.org/2015/287
[2]: https://lists.torproject.org/pipermail/tor-dev/2016-May/010964.html
[3]: https://twitter.com/isislovecruft/status/761560658370555904
[4]: https://eprint.iacr.org/2016/413

-- 
 ♥Ⓐ isis agora lovecruft
_________________________________________________________
OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35
Current Keys: https://fyb.patternsinthevoid.net/isis.txt
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 1240 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160805/ac2cb424/attachment.sig>