[tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope

[isis]

Yawning Angel transcribed 2.5K bytes:
> Hello,
> 
> My tinfoil hat went crinkle in the night[0], and I had an additional
> thought here. Should we encrypt the `CLIENT_NEWHOPE` and
> `SERVER_NEWHOPE` values using <AE construct of your choice> and
> something derived from `EXP(Z,x)`/`EXP(X,z)`?
> 
> It doesn't have perfect forward secrecy (compromise of `z` would allow
> the adversary to decrypt all previous ciphertexts), but it's better
> than nothing.
> 
> CPU-wise it's 1 additional KDF call (assuming you squeeze out the
> forward and return symmetric keys at once), 1 extra CSPRNG call (for
> the IV), and 2 AE calls. And `len(IV) + len(Tag)` bytes of extra
> traffic in each direction in terms of extra network overhead, both
> which I think are relatively cheap.

This is an interesting idea.  Let me just make sure I've understood correctly.
In your idea, it goes like this?

 Initiator                             Responder

 SEED         := H(randombytes(32))
 x, X         := X25519_KEYGEN()
 a, A         := NEWHOPE_KEYGEN(SEED)
 CLIENT_HDATA := ID || Z || EXP(Z, X || A)

               --- CLIENT_HDATA --->

                                       y, Y           := X25519_KEYGEN()
                                       X, A           := EXP(z, X || A)
                                       NTOR_KEY, AUTH := NTOR_SHAREDB(X,y,Y,z,Z,ID,B)
                                       M, NEWHOPE_KEY := NEWHOPE_SHAREDB(A)
                                       SERVER_HDATA   := Y || AUTH || M
                                       sk := SHAKE-256(NTOR_KEY || NEWHOPE_KEY)

               <-- SERVER_HDATA ----

 NTOR_KEY    := NTOR_SHAREDA(x, X, Y, Z, ID, AUTH)
 NEWHOPE_KEY := NEWHOPE_SHAREDA(M, a)
 sk := SHAKE-256(NTOR_KEY, NEWHOPE_KEY)

I think I see what you're saying.

In the case of the currect context, it doesn't make much sense: an adversary
with a fully opeerational quantum computer can, in polynomial time, decrypt
the Curve25519 encryption to the ntor-onion-key ("Z" here) and then have
trivial access to the rest of the handshake.

However, moving forward, since we intend to switch to AE(AD) ciphers at the
circuit level, this makes absolute sense.  This costs us two extra modular
exponentiations now, but, in the future, with an AEAD cipher, we should be
able to put `X` into the associated data and have the the handshake's
authentication be implicit from the first round.  Moving forward, this is
worth the extra two modular exponentiations on either side, since it causes
extra (exponential) computational effort for a classical adversary, until the
time of a quantum adversary (in which it still causes polynomial effort to
decrypt the handshake).  For such a minor expense as two exp(), we can cause
exponential expense for a classical adversay, and polynomial expense for a
quantum adversary — which makes this worthwhile.

Did I understand the idea correctly?

Best Regards,
-- 
 ♥Ⓐ isis agora lovecruft
_________________________________________________________
OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35
Current Keys: https://fyb.patternsinthevoid.net/isis.txt
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 1240 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160512/41d3816f/attachment-0001.sig>