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

[Zhenfei Zhang]

Thanks Yawning.

> Agreed.  I like the QSH design, though I still want to use FIPS 202
> (SHA-3/SHAKE) instead of HMAC-SHA256/HKDF-SHA256, due to "Since we're
> changing things anyway, we may as well future proof here too".

Yes. Will put that in the request too. Sorry missed this comment in
previous email.

> Client side for Tor is somewhat deceptive because Hidden Services act
> as the client when connecting to the Rdv point, so we do care about
> performance there too.  I fully expect that the gains that we will get
> from separate work due to improved threading will pay for the CPU cost
> increases here, but I'll need to do some benchmarking to be certain.

Thanks. I didn't know that.

Cheers,
Zhenfei

On Mon, Jan 4, 2016 at 1:26 PM, Yawning Angel <yawning at schwanenlied.me>
wrote:

> (Note: Snipping liberally for brevity)
>
> On Mon, 4 Jan 2016 11:56:54 -0500
> Zhenfei Zhang <zzhang at securityinnovation.com> wrote:
> > 2. On NTRU vs NTRU-Prime vs R-LWE and others.
> > The QSH is modular designed to suite any quantum-safe encryption
> > algorithm. So we can chose any one we want for trail. And
> > furthermore, we can also hybrid, say ECC, NTRU and R-LWE, to give a
> > bit more confidence in case one of the quantum-safe encryption
> > algorithm turns out to be not quantum safe, or broken.
>
> Hybridizing all 3 probably will get somewhat expensive (though not
> prohibitively so), nickm and I have branches to thread the client side
> circuit build crypto which will help mask the performance penalty of
> this proposal in general (not yet merged, shouldn't require changes to
> your branch).
>
> > That been said, we chose NTRU for several reasons. NTRU is more
> > mature than R-LWE from our point o view. NTRU has a full spec, a
> > reference implementation, and is standardized by several bodies;
> > while for R-LWE, since it enables many interesting cryptographic
> > primitives, such as FHE, there has been many different parameter
> > proposals, which leads to some kind of confusion as to which one
> > should reference to.
>
> At the current time, if I had to pick one, I'd use the newhope variant
> of Peikert's KEM scheme (And in fact was going to amend the proposal
> to specify that as the Ring-LWE primitive).
>
> The BCNS proposal has gotten slightly more scrutiny, but it's slower,
> has larger keys, and provides a lower security level than newhope.
>
> > We are happy to roll out any above encryption algorithm as you see
> > fit. But our proposal is mainly about the QSH approach. I think the
> > best option for now is to buildin a QSH for Tor, with a flexible
> > API that allows us to switch between algorithms when fit. And for now
> > use any quantum-safe encryption algorithm that is ready to be used.
> > After all, any QS encryption is better than nothing.
>
> Agreed.  I like the QSH design, though I still want to use FIPS 202
> (SHA-3/SHAKE) instead of HMAC-SHA256/HKDF-SHA256, due to "Since we're
> changing things anyway, we may as well future proof here too".
>
> > 3. License
> > I am sorry I am not familiar with the license. But my general feeling
> > is that Security Innovation is willing to let Tor to use NTRU for
> > free. We just need to work out the suitable license to make this
> > happen.
>
> I'm glad to hear that.  My main concern here is that if, say Debian
> Legal thinks that the existing FOSS patent wavier is insufficient to
> allow NTRU to be included in Debian packages till 2017, this will
> significantly hamper the relay side uptake of the safer primitives due
> to the Debian monoculture on our relays.
>
> I can do the Ring-LWE work, since the QSH primitive is modular so that
> there will be options for people that have more stringent
> license/patent policies than we do.
>
> If I were to prioritize handshake selection, I would lean towards
> NTRU + Ring-LWE, over NTRU, over Ring-LWE based on what the
> peer supports.
>
> > > 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)
> >
> > Yes we can use non-product form polynomials, if everyone agrees on it.
> > Non-product form polynomials will make key generation and decryption
> > a bit slower, but those cost are on the client side. It has no impact
> > on the load of server side.
>
> Client side for Tor is somewhat deceptive because Hidden Services act
> as the client when connecting to the Rdv point, so we do care about
> performance there too.  I fully expect that the gains that we will get
> from separate work due to improved threading will pay for the CPU cost
> increases here, but I'll need to do some benchmarking to be certain.
>
> > > * "For 128 bits quantum security, use NTRU_EESS743EP1." should be
> > >   "For 256 bits" (Section 2.3).
> >
> > NTRU_EESS743EP1 provides 256 classical security and 128 bits quantum
> > security. Please see
> > https://eprint.iacr.org/2015/708.pdf
> > for arguments of those security levels.
>
> Ah gotcha, I haven't seen that paper and I was going off the initial
> estimates, thanks for the clarification.
>
> Regards,
>
> --
> Yawning Angel
>
> _______________________________________________
> tor-dev mailing list
> tor-dev at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160104/d4afead1/attachment.html>