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

[Yawning Angel]

(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
-------------- 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/20160104/121fe31a/attachment.sig>