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

[Yawning Angel]

On Thu, 12 May 2016 03:48:21 +0000
isis <isis at torproject.org> wrote:
[snippity[
> This is an interesting idea.  Let me just make sure I've understood
> correctly. In your idea, it goes like this?

Almost.

Let Seal(key, nonce, plaintext) be the forward
GCM-AES128/XChaCha20Poly1305/whatever encrypt operation, with the
specified key, nonce, and plaintext.

Let Unseal(key, nonce, ciphertext) be the reverse
GCM-AES128/XChaCha20Poly1305/whatever decrypt operation with the
specified key, nonce, and ciphertext.

Initiator                             Responder

SEED         := H(randombytes(32))
x, X         := X25519_KEYGEN()
a, A         := NEWHOPE_KEYGEN(SEED)

xZ           := EXP(Z,x)               // X25519 Scalar multiply (raw, later used in NTOR_SHAREDA)
kTmp         := H(tweak || xZ)
nonce        := randombytes(nonceSize) // Random nonce.

CLIENT_HDATA := X || nonce || Z || Seal(kTmp, nonce, ID || A) // If Seal does AEAD, also send Z as the AD

               --- CLIENT_HDATA --->

                                       zX    := EXP(X,z) // X25519 Scalar multiply (raw)
                                       kTmp  := H(tweak || zX)
                                       ID, A := Unseal(kTmp, nonce, CLIENT_HDATA[ciphertextOffset:]) // Abort if Unseal fails.

                                       y, Y           := X25519_KEYGEN()
                                       yX             := EXP(X, y) // X25519 Scalar multiply (raw) 
                                       NTOR_KEY, AUTH := NTOR_SHAREDB(zX,yX,Z,Y,ID,B) // No X25519 calls in here anymore.
                                       M, NEWHOPE_KEY := NEWHOPE_SHAREDB(A)

                                       kTmp'  := H(tweak || yX)    // Return AE key, could alternatively reuse kTmp, but this has better forward secrecy.
                                       nonce' := randombytes(nonceSize)
                                       SERVER_HDATA := Y || nonce || Seal(kTmp', nonce', AUTH || M)

                                       sk := SHAKE-256(NTOR_KEY || NEWHOPE_KEY)

               <-- SERVER_HDATA ----

xY := EXP(Y,x) // X25519 Scalar multiply (raw)
kTmp' := H(tweak || xY)
M, AUTH := Unseal(kTmp', nonce', SERVER_HDATA[cipherTextOffset':]) // Abort if Unseal fails.

NTOR_KEY    := NTOR_SHAREDA(xZ, xY, Y, Z, ID, AUTH) // No X25519 calls in here anymore either.
NEWHOPE_KEY := NEWHOPE_SHAREDA(M, a)
sk := SHAKE-256(NTOR_KEY, NEWHOPE_KEY)

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

Correct.  In a post quantum world, this is totally pointless,
especially since `Z` is publicly available from the microdescriptors,
but in the mean time it's extra authenticated, and extra sekrit.

> Did I understand the idea correctly?

Mostly.  There's no extra EXP() calls at all.  NTOR_SHAREDA/SHAREDB requires that we calculate:

 Client: EXP(Z,x), EXP(Y,x)
 Server: EXP(X,z), EXP(X,y)

The client uses EXP(Z,x), which we have to calculate anyway for ntor, to encrypt/authenticate `ID || A` of CLIENT_HDATA (and optionally Z).
(There isn't any point in including X in the AD, because if someone messes with X, Unseal() will fail).

The server uses EXP(X,y), which we have to calculate anyway for ntor, to encrypt/authenticate `AUTH || M`.

The only overhead is 2 calls to the AE(AD) construct, 2x random nonce
generation, and 2 calls into H().  If we want to be extra sneaky, we
could also do the NTRU handshake this way (and move the handshake
identifier into the encrypted envelope) so that only the recipient can
see which algorithm we're using as well (So: Bad guys must have a
quantum computer and calculate `z` to figure out which post quantum
algorithm we are using).

Regards,

-- 
Yawning Angel
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160512/687c00b2/attachment.sig>