5. Aug 2016 15:07 by isis@torproject.org:
lukep@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.
Thanks - that wasn't clear to me, although I can see that they are aiming in the same direction. I agree with the principle of separating out the handshake from the protocol for modularity, but I don't think that's quite been achieved and there's some overlap/confliction between the two of them. For example in how the hybrid secret key is computed.
In #269, in the hybrid DH-KEM handshake it's computed as:
s0 := H(DH_MUL(A,x))
s1 := DH_MUL(Y,x)
s2 := KEM_DEC(C, esk)
secret := s0 | s1 | s2
On the other hand in #270, in the X25519-Newhope handshake it's computed as:
NTOR_KEY := NTOR_SHAREDA(x, X, Y, Z, ID, AUTH)
NEWHOPE_KEY := NEWHOPE_SHAREDA(M, a)
sk := SHAKE-256(NTOR_KEY || NEWHOPE_KEY)
As it stands, secret and sk are computed in a contradictory manner; these could be reconciled so they are the same, but if you are trying to write modular proposals the handshake algorithm should only be specified in one document. I think the method of computing the secret should be specified in #270 (only), and the protocol (depending on a call to the DH-KEM key exchange) should be specified in #269.
Also see >> https://eprint.iacr.org/2016/717.pdf%3E%3E , 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.
It was two separate statements really. Having flexibility on choice of algorithm is a good idea. Some weird scheme which is based on NTRU has been broken. If I had a point, it was "new research can come to light which casts doubt on certain choices of algorithms, so it's better to have a protocol that doesn't tie you to one algorithm". Sorry for the confusion.
-- lukep