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

[Zhenfei Zhang]

Hi all,

Thanks for all the comments. Sorry I wasn't able to reply immediately.
Please allow
me to summarize the comments. I see mainly the following questions.

1. Quantum-safe authentication.
As Yawning has pointed out,

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

This is also the reason we wanted to roll out QSH first and add the
quantum-safe
signature schemes later. We have several good candidate for quantum-safe
encryption algorithms. But for signatures, they are not mature imho.

Another reason that we did not include authentication is due to the attack
model.
As I have mentioned (but probably didn't explain very clearly) in previous
email, we
are facing two types of attackers. Attacker type I, passive attacker at
present, who
cannot break classical authentication nor encryption, record the data
anyway, and
decrypt it when quantum computer become available in future. Attack type
II, active
attacker who tries to attack the authentication while the communication is
taking
place. This attack will be possible in future when quantum computer
arrives. But for
now, they will not be successful.

As we believe that there does not exist a general purpose quantum computer
at
present (and maybe several years away), we have time to deal with attacker
type II.
But the attacker type I is the real threat at the present day. Our proposal
is to address
this threat.

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.

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.

> 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]

As for NTRU-Prime, I am not aware there is a specific instantiation of this
parameter sets, nor
any paper that considers the security of a specific parameter set. Also,
this NTRU-Prime would
require some extensive scrutiny before we can use it.

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.

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.

4. Misc.
> Post-quantum forward-secrecy is what I've been using to describe this
> property.

We will use this terminology. Thanks.

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


> * "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.

> I'm a little confused about what exactly is meant by "disaster
resilience" here.

We will remove "disaster resilience".

Those are most comments I saw. Sorry if I missed some of your comments.
Please let me know
if you have questions that I failed to answer.

Happy new year to everyone.

Cheers,
Zhenfei


On Sun, Jan 3, 2016 at 8:32 PM, Ryan Carboni <ryacko at gmail.com> wrote:

> Wasn't there a transition period in migrating from RSA to ECC?
>
> Maybe I'm just confused. Or you are confused. But I think it is best plan
> for a five or ten year transition period.
>
> _______________________________________________
> 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/ce4f0bd0/attachment.html>