[tor-dev] Post-quantum proposals #269 and #270

[lukep at tutanota.com]

5. Aug 2016 15:07 by isis at torproject.org:


> lukep at 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



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160808/39fba879/attachment.html>