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@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@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
(Note: Snipping liberally for brevity)
On Mon, 4 Jan 2016 11:56:54 -0500 Zhenfei Zhang zzhang@securityinnovation.com wrote:
- 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".
- 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,
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@schwanenlied.me wrote:
(Note: Snipping liberally for brevity)
On Mon, 4 Jan 2016 11:56:54 -0500 Zhenfei Zhang zzhang@securityinnovation.com wrote:
- 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".
- 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@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
-
Yawning Angel -
Zhenfei Zhang