[tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
isis at torproject.org
Thu May 12 03:48:21 UTC 2016
Yawning Angel transcribed 2.5K bytes:
> My tinfoil hat went crinkle in the night, 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?
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?
♥Ⓐ isis agora lovecruft
Current Keys: https://fyb.patternsinthevoid.net/isis.txt
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 1240 bytes
Desc: Digital signature
More information about the tor-dev