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