[prop269] Further changes to the hybrid handshake proposal (and NTor)
Hello, After discussion with John Schanck and Trevor Perrin over the last month, we've decided to make some alterations to the specification for hybrid handshakes in Tor proposal #269. It seems that John, Trevor, and I are mostly in agreement about most of the construction. First, I'll try to summarise a list of changes and the reasoning/concerns which provoked them. For what it's worth, these concerns mostly involve highly theoretical problems surrounding whether we model a hash function with a random oracle or try to make some stronger claims to its properties, and aren't due to any real world attacks (assuming that hash functions do what you'd expect them to do and aren't something crazy like a NULL op or a pineapple slicing machine). Changes: 1. [NTOR] Inputs to HKDF-extract(SALT, SECRET) which are not secret (e.g. server identity ID, and public keys A, X, Y) are now removed from SECRET and instead placed in the SALT. Reasoning: *Only* secret data should be placed into the HKDF extractor, and public data should not be mixed into whatever entropic material is used for key generation. This eliminates a theoretical attack in which the server chooses its public material in such a way as to bias the entropy extraction. This isn't reasonably assumed to be possible in a "hash functions aren't probablistically pineapple slicers" world. Previously, and also in NTor, we were adding the transcript of the handshake(s) and other public material (e.g. ID, A, X, Y, PROTOID) directly into the secret portion of an HMAC call, the output of which is eventually used to derive the key material. The SALT for HKDF (as specified in RFC5869) can be anything, even a static string, but if we're going to be adding transcript material into the handshake, it shouldn't be in the entropy extraction phrase. 2. [NTOR] The authentication of transcript data, i.e. (ID, A, X, Y, EPK, C) where EPK is the public and ephemeral portion which the client sends in the post-quantum KEM, and C is the reconciliation data, is now distinctly separate from the production of SALT for the extractor, and is first HMACed separately (where the key is derived from the same HKDF extraction which produces the seed) before being included within the expansion phase. Reasoning: The idea is to avoid attempting to do context-binding (of the transcript, in this case) and entropy extraction at the same time, in order to have a stronger argument that the shared key used for authenticating the context is secure, whereas (before, in NTor) things were a bit murky. The use of auth_input in ntor was designed to prevent a certain type of collision attack (see [Zav12, SZW16]). However the auth_input countermeasure is unnecessary if the authentication tag is of length 2*LAMBDA. A collision attack on a random function of output length 2*LAMBDA has cost 2^LAMBDA. This change additionally avoids the collision attack. 3. The hashing of first SALT has been removed. (Or, alternatively, it's still there, assuming you're following the specification for HKDF extraction in RFC5869 to the T and hashing any incoming SALT longer than 32 bytes. If you're using something like SHAKE-256 or similar… well, it's not exactly clear or specified yet how to use SHAKE as a dropin replacement for a KDF. Joan is apparently writing something.) Reasoning: It was originally included due to concerns that a malicious adverary could potentially choose some SALT such that when passed into the HKDF-extractor, it would "nullify" the SECRET input rather than extracting from it. However, the HKDF-extractor is HMAC(SALT, SECRET) and we assume the HMAC's underlying hash function is not a machine which factors discrete logarithms or a slices pineapples. Were you to replace your own hash function with a pineapple slicer, you'd simply be creating a vulnerability for yourself, and thus it doesn't really make sense in Tor's case to hash the SALT first because we're not living in the horrible world where hash functions can turn out to be pineapple slicers. (And even if it were possible for them to be pineapple slicers, it personally still doesn't make sense to me why you'd want to protect against potential pineapple slicers by putting your data through a pineapple slicer twice.) Best regards, -- ♥Ⓐ isis agora lovecruft _________________________________________________________ OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35 Current Keys: https://fyb.patternsinthevoid.net/isis.txt
On Fri, Oct 14, 2016 at 2:45 PM, isis agora lovecruft <isis@torproject.org> wrote:
After discussion with John Schanck and Trevor Perrin over the last month, we've decided to make some alterations to the specification for hybrid handshakes in Tor proposal #269.
It seems that John, Trevor, and I are mostly in agreement about most of the construction.
Hi Isis, all, My main suggestion was to take a look at Noise: https://noiseprotocol.org Noise is a framework for DH-based (Ntor-like) key exchange protocols. You choose a "handshake pattern" plus your favorite crypto and it fills in the details. So this would save you from hand-crafting your key derivation and transcript hashing, as Noise specifies this (e.g. it uses a chain of HKDF for key derivation, similar to Signal, IPsec, or TLS 1.3). For Ntor + hybrid forward secrecy, you could choose something like: Noise_NKhfs_25519+NewHope_ChaChaPoly_SHA256 or: Noise_NKhfs_25519+NTRU_AESGCM_BLAKE2b etc. The names are a mouthful, but specify the whole protocol: NKhfs is a handshake pattern NK = (N)o client long-term key, (K)nown server long-term key hfs = hybrid forward secrecy 25519+NewHope = public-key algorithms ChaChaPoly = ChaCha20/Poly1305 for AEAD SHA256 = hash for transcript hashing and HKDF Some other benefits: * There are C and Java libraries that can implement this (with NewHope) by Rhys Weatherley, and hopefully more will pop up. * Saves design effort, because it's easy to change patterns to add client auth, or pre-shared keys, or certificates; or swap out crypto). * Also used by WhatsApp and WireGuard, so hopefully the libraries, tools, and design will continue to improve, benefiting other users. Noise can be hard to figure out because it's a toolkit, not a single protocol, but I'd be happy to answer questions about particular use cases. Of course, I also think Tor's existing Ntor, the current Tor proposals, and the changes Isis is mentioning, all seem fine. Trevor
On 14/10/16 22:45, isis agora lovecruft wrote:
1. [NTOR] Inputs to HKDF-extract(SALT, SECRET) which are not secret (e.g. server identity ID, and public keys A, X, Y) are now removed from SECRET and instead placed in the SALT.
Reasoning: *Only* secret data should be placed into the HKDF extractor, and public data should not be mixed into whatever entropic material is used for key generation. This eliminates a theoretical attack in which the server chooses its public material in such a way as to bias the entropy extraction. This isn't reasonably assumed to be possible in a "hash functions aren't probablistically pineapple slicers" world.
Previously, and also in NTor, we were adding the transcript of the handshake(s) and other public material (e.g. ID, A, X, Y, PROTOID) directly into the secret portion of an HMAC call, the output of which is eventually used to derive the key material. The SALT for HKDF (as specified in RFC5869) can be anything, even a static string, but if we're going to be adding transcript material into the handshake, it shouldn't be in the entropy extraction phrase.
Hi Isis, Sorry if this is a really stupid question, but there's something I've never fully understood about how RFC 5869 describes the requirements for the HKDF salt. Section 3.4 says: While there is no need to keep the salt secret, and the same salt value can be used with multiple IKM values, it is assumed that salt values are independent of the input keying material. In particular, an application needs to make sure that salt values are not chosen or manipulated by an attacker. As an example, consider the case (as in IKE) where the salt is derived from nonces supplied by the parties in a key exchange protocol. Before the protocol can use such salt to derive keys, it needs to make sure that these nonces are authenticated as coming from the legitimate parties rather than selected by the attacker (in IKE, for example this authentication is an integral part of the authenticated Diffie-Hellman exchange). As far as I can tell, the assumption in this example is that the attacker is not the other party in the key exchange - otherwise authenticating the nonces wouldn't tell us whether they were safe to include in the salt. If we're concerned with the server choosing its public material in such a way as to bias the entropy extraction, does that mean that in this case, the attacker is the server, and therefore the server's public material shouldn't be included in the salt? Again, probably just a failure on my part to understand the context, but I thought I should ask just in case. Cheers, Michael
Hi Michael, Michael Rogers wrote:
If we're concerned with the server choosing its public material in such a way as to bias the entropy extraction, does that mean that in this case, the attacker is the server, and therefore the server's public material shouldn't be included in the salt?
In a one-way authenticated key exchange we only need to consider adversaries that attempt to impersonate the server. So, yes, we're considering the case where the attacker plays the server role and we're saying that unauthenticated material from the server should not be included in the salt. Previous versions of prop269 included the server ephemeral shares in the salt, we've removed those in this version. The remaining values in the salt are: - the server's identity digest, - the server's onion key, and - ephemeral shares from the client. All of these values are authentic from the client's perspective. Since we're not including the server shares in the salt, we also had to switch from sending 'auth' to sending HMAC(auth, transcript) in the server response. Cheers, John
Quoting isis agora lovecruft <isis@torproject.org>:
Hello,
After discussion with John Schanck and Trevor Perrin over the last month, we've decided to make some alterations to the specification for hybrid handshakes in Tor proposal #269.
It seems that John, Trevor, and I are mostly in agreement about most of the construction.
First, I'll try to summarise a list of changes and the reasoning/concerns which provoked them. For what it's worth, these concerns mostly involve highly theoretical problems surrounding whether we model a hash function with a random oracle or try to make some stronger claims to its properties, and aren't due to any real world attacks (assuming that hash functions do what you'd expect them to do and aren't something crazy like a NULL op or a pineapple slicing machine).
Changes:
1. [NTOR] Inputs to HKDF-extract(SALT, SECRET) which are not secret (e.g. server identity ID, and public keys A, X, Y) are now removed from SECRET and instead placed in the SALT.
Reasoning: *Only* secret data should be placed into the HKDF extractor, and public data should not be mixed into whatever entropic material is used for key generation. This eliminates a theoretical attack in which the server chooses its public material in such a way as to bias the entropy extraction. This isn't reasonably assumed to be possible in a "hash functions aren't probablistically pineapple slicers" world.
Hi Isis, Perhaps my question is related to Michaels question, but above removing A, X, Y and server ID leaves the possibility of a person-in-the-middle who by manipulating public keys (resend 2A, instead of A, 2X instead of X, 2Y instead of Y) can force two (non-matching) session share the same value denoted SECRET, Does including these public values in the value SALT take care of such "attacks". RFC5869 Section 3.3 To Skip or not to Skip addresses that part, but I can't conciliate your statement that the server can choose its public material in a way to bias the entropy extractor. Or is this simply the same problem viewed from a different angle? Best BU -- http://cryptolounge.net
Hi BU, bustaoglu@cryptolounge.net wrote:
Perhaps my question is related to Michaels question, but above removing A, X, Y and server ID leaves the possibility of a person-in-the-middle who by manipulating public keys (resend 2A, instead of A, 2X instead of X, 2Y instead of Y) can force two (non-matching) session share the same value denoted SECRET, Does including these public values in the value SALT take care of such "attacks".
For the version in which A, X, Y, and ID were all in SALT, see [1] for a proof of security (tldr; yes putting these values in SALT instead of in the extractor secret input field prevents the attack you mention). The new version drops Y from SALT (A, X, and server ID are still included), but that's irrelevant because we've stopped relying on SALT to bind the derived keys to the transcript. In the new version the server response includes a MAC computed over the entire transcript. Non-matching sessions that compute the same session key will abort (with overwhelming probability). The proof from [1] goes through with a small modification to Game 5 of Lemma 4.3: show 'auth' is uniformly random; use PRF property to replace HMAC keyed by 'auth' with a random function; mention that matching MAC tags imply matching sessions or, with negl. probability, a collision in the random function.
RFC5869 Section 3.3 To Skip or not to Skip addresses that part, but I can't conciliate your statement that the server can choose its public material in a way to bias the entropy extractor. Or is this simply the same problem viewed from a different angle?
RFC5869 Section 3.3 is about skipping the call to HKDF-Extract... we don't do that. See [2] section 3 for more details on exactly what has changed from ntor. Cheers, John [1] https://www.degruyter.com/view/j/popets.2016.2016.issue-4/popets-2016-0037/p... [2] https://gitweb.torproject.org/torspec.git/tree/proposals/269-hybrid-handshak...
participants (5)
-
bustaoglu＠cryptolounge.net -
isis agora lovecruft -
John M. Schanck -
Michael Rogers -
Trevor Perrin