Authentication protocols are used to verify that network connections are not being monitored through a man-in-the-middle attack (MitM). But the commonly used constructions for authentication—often some framework surrounding a digital signature—reveal considerable amounts of identifying information to the participants. This information can potentially be used to track otherwise anonymous users around the network and correlate users across multiple services, if keys are reused.
Ultimately, key-based authentication protocols are trying to answer the question, "Does the remote party know the corresponding private key for an identity key we accept?" A protocol which answers this question and nothing else would naturally provide for undetectable authentication—just make its usage mandatory and use random keys when no identity is expected. Such a protocol would also provide no avenue for leaking any identifying information beyond the absolute minimum needed to achieve authentication.
We define a secret authentication protocol as a protocol that allows a challenger (C) to establish whether its peer (the responder, R) in an encrypted but unauthenticated connection possesses the private key corresponding to one of several acceptable public keys, with the following properties:
- Correctness When R authenticates using the private key corresponding to a public key acceptable C, the protocol succeeds.
- Soundness R cannot make the protocol succeed without using the private key corresponding to a public key acceptable to C.
- Challenger privacy R learns nothing about which keys are acceptable to C.
- Responder privacy C learns nothing about which key R possesses, apart from whether its corresponding public key is acceptable.
Note that this protocol only teaches C something. If R also wants to establish C's identity, the same protocol can be run a second time with the roles of R and C reversed.
These properties are useful in the context of optional authentication. Sometimes ephemeral encryption is automatic and mandatory but authentication is opportunistic: if an end-point expects a known identity it will authenticate, otherwise it won't and only get resistance against passive observation.
In this configuration, when the attempt at authentication is observable to an active attacker, a selective interception attack is possible that evades detection:
- When no authentication is requested on a connection, the MitM maintains the connection and intercepts it.
- When authentication is requested, the MitM innocuously terminates the connection, and blacklists the network address involved so it will discontinue intercepting retried connections.
Challenger privacy allows improving upon this vulnerability. Whenever no authentication is desired, it is possible to run the protocol with a set of arbitrarily chosen keys (and ignore the inevitably failed authentication). Due to challenger privacy, R cannot distinguish this from the protocol with relevant keys. When a MitM is present, he acts as R (but with no relevant private keys). As a result, a MitM learns exactly as much as R would before the authentication completes in an unintercepted protocol run, which includes distinguishing these cases. This means that the MitM is forced to either drop all connections (and become powerless) or risk being detected on every connection.
Note that challenger privacy goes much further than just being unable to recognize keys. It also means R cannot learn whether two separate protocol runs (in separate connections) were for overlapping keys, whether or not those keys are known to R.
As unauthenticated connections are an explicit use case, private authentication protocols assure R's privacy in the unauthenticated case. Responder privacy implies that C cannot learn whether two separate protocol runs (in separate connections) were with peers that possess the same private key, effectively preventing C from surveilling its unauthenticated peers and following them around.
Responder privacy also implies that C does not learn which of its acceptable public keys R's private key corresponded to. To see why this may be useful, note that the anti-surveillance property from the previous paragraph breaks down whenever C can run many instances of the protocol with separate acceptable keys, for a large set of (e.g. leaked) keys that may include R's public key. In order to combat this, R can limit the number of independent protocol runs it is willing to participate in. If C could learn which acceptable public key R's private key corresponded to, this would need to be a limit on the total number of keys in all protocol runs combined, rather than the total number of protocol runs. If C has hundreds of acceptable public keys, and R is one of them, R must support participating in a protocol with hundreds of acceptable keys—but doesn't have to accept participating in more than one protocol run.
If only challenger privacy is desired, a simple solution would be to just have R send its public key with a corresponding digital signature of the connection's session id (which is assumed to be the result of a Diffie-Hellman style negotiation). C can verify this signature, and decide if he accepts the key. Since C does not send anything, this clearly has challenger privacy, but fails terribly at responder privacy: C learns the public key of every peer. Even if the public key is replaced by a session-salted hash, C can still learn the key through mechanisms like public key recovery. And even if a signature scheme that does not support key recovery is used, C can verify the signature against an arbitrarily large set of leaked public keys, allowing him to follow peers around.
If only responder privacy is desired, and there is only a single acceptable key, another simple solutions exists. C could tell R which public key is acceptable, and R only responds with a signature if there is a match. Clearly C does not learn anything about R's key, but conversely, this fails terribly at challenger privacy.
Countersign is a secret authentication protocol that requires a single roundtrip. C sends a challenge, and R responds to it. C then analyses the reponse to see if authentication succeeded.
It assumes an encrypted but unauthenticated connection already exists between the two participants, for example using a Diffie-Hellman negotiation to set up a shared key. We also assume a unique session id exists, only known to the participants, and containing entropy from both.
The scheme is parametrized by the choice of an additive group in which the DDH assumption holds, with independent generators G and M, and a hash function H. All lowercase variables are integers modulo the group order, while all uppercase variables are group elements. We transparently treat the output of hash functions as integers.
- C sends (D, C) = (dG, yG - H(dP || s)M), where d and y are random integers, P is the acceptable public key, and s is the session id.
- R sends (V, W) = (qG, q(C + H(pD || s)M)), where q is a random integer, and p is the private key.
- C verifies whether W = yV and V≠0.
In the full version, the number of acceptable public keys n is known to R, and may be larger than one.
- C computes and sends the challenge:
- Generate a random ephemeral ECDH key d.
- Generate a random authentication key y.
- For i = 0..n-1, compute hi = H(dPi || s), where Pi are the acceptable keys.
- Compute the coefficients a0...an-1 of the polynomial a0 + a1x + a2x2 + ... + an-1xn-1 + xn = (x - h0)(x - h1)...(x - hk-1).
- Compute the public ephemeral ECDH key D = dG.
- Compute C0 = yG + a0M.
- For i = 1...n-1:
- Generate a random blinding factor bi.
- Compute Bi = biG.
- Compute Ci = yBi + aiM (or equivalently, Ci = biC0 + (ai - a0bi)M).
- Construct a proof that the Bi and Ci points were computed honestly:
- Generate random numbers k1 and k2.
- Compute e = H(k1G || k1C0 + k2M || s).
- Compute s1 = k1 + H(e || 1)b1 + H(e || 2)b2 + ... + H(e || n-1)bn-1.
- Compute s2 = k2 + H(e || 1)a1 + H(e || 2)a2 + ... + H(e || n-1)an-1 - a0(s1 - k1).
- Send the challenge (D, C0, (B1, C1), (B2, C2), ..., (Bn-1, Cn-1), e, s1, s2).
- R computes and sends the response:
- Verify the proof:
- Compute R1 = s1G - H(e || 1)B1 - H(e || 2)B2 - ... - H(e || n-1)Bn-1.
- Compute R2 = s1C0 + s2M - H(e || 1)C1 - H(e || 2)C2 - ... - H(e || n-1)Cn-1.
- Verify that e = H(R1 || R2 || s).
- Compute h = H(pD || s)
- Generate random number q.
- Compute V = q(G + hB1 + h2B2 + ... + hn-1Bn-1).
- Compute W = q(C0 + hC1 + h2C2 + ... + hn-1Cn-1 + hnM).
- Send the response (V, W).
- Verify the proof:
- C verifies the response:
- The authentication is succesful if W = yV and V≠0.
At a high level, the first layer of the protocol consists of performing an ECDH negotation between an ephemeral challenger-generated key and the acceptable keys on one side, and the private key on the other side. This reduces the problem to a Private Set Intersection problem between the ECDH outcomes, where the challenger only learns whether an non-empty intersection exists, but not what it is. The rest of the protocol is a solution to that problem which is private in a malicious setting.
In the single-key scenario, that protocol is essentially a simplified version of SPAKE2, where the ECDH outcome is used as the "password". Instead of using the outcome of the algorithm as a shared secret, the responder sends his result to the challenger. The challenger then compares it with his own outcome, and accepts if they are equal.
In the multi-key scenario, the construction from Section 4.4 of Efficient Private Matching and Set Intersection is used. This describes a protocol for Private Matching for set cardinality using a homomorphic encryption scheme (here instantiated using ElGamal encryption). As the scheme is only secure in a semi-honest model, we add a zero-knowledge proof that the challenge was constructed honestly.
In this section we dissect the steps of the algorithm, and how they fit together.
ECDH The first step in the protocol is C generating an ephemeral ECDH key d, and combining it with every acceptable public key Pi. This results in one shared secret hi between C and every possible acceptable key. R tries to compute the same shared secret h, but is only able to construct an h that equals one of C's hi values if R has the private key corresponding to an acceptable public key. The session id is mixed into the computation of hi and h to prevent replays.
Unfortunately, R cannot directly send this shared secret or use it as encryption key, as this would let C test what key was used, breaking responder privacy.
Polynomial Instead, C constructs a monic polynomial that has all hi values as roots, and no other roots. This polynomial is f(x) = a0 + a1x + a2x2 + ... + an-1xn-1 + xn. The goal is to have R evaluate this polynomial, and send the result back. This prevents C from learning which of the acceptable keys R used. Of course, we can't just send this polynomial directly—it would reveal which hi values we're looking for, and be trivial to forge a zero response.
ElGamal encryption Let's call EncY(X, b) = (bG, X + bY) an ElGamal encryption of X with blinding factor b and public key Y. Verifying whether something is an encryption of a particular value requires knowing the discrete logarithm y for which Y = yG. However, ElGamal encryptions are homomorphic, permitting linear arithmetic on encrypted values: pointwise adding of encryptions together gives an encryption of the sum, and multiplying both elements of an encryption with an integer gives the encryption of the multiplication of the value with that integer.
Encrypted polynomial Instead of sending f(x) directly, C chooses a secret y value with associated public key Y = yG, and creates encryptions of f(x)'s coefficients multiplied by M using it: the (Bi, Ci) = EncY(aiM, bi) pairs which are sent to R. Due to the homomorphic properties, R can evaluate the encrypted polynomial and obtain an encryption of f(h)M. To prevent C from knowing what value h R evaluated the polynomial in, R multiplies the result of the evaluation with a random number q, and obtains (V, W) in the protocol above. If it was an encryption of zero, the multiplication with v just turns the encryption into a different encryption of zero. If it was an encryption of a nonzero number, the multiplication turned it into a random nonzero number. So now C can accept the response if it turns out to be an encryption of zero, using the private key y. Note that not even the public key Y can be known to R, as it would permit forging an acceptable response.
Optimizations As f(x) is monic, the coefficient for xn is always 1, and doesn't need sending. Furthermore, the ElGamal blinding factors bi are only necessary to hide relations between the different ai values, so it is sufficient for only n-1 bi values to be secret. We therefore choose b0 = 1, removing the need to send B0 (which becomes implicitly equal to G).
Zero-knowledge proof Unfortunately, there is nothing that forces the challenger to reuse the same y key for each of the polynomial's coefficients. If he doesn't, the ratio between V and W will depend on what value of h R evaluated the polynomial in. This would let C test which of the acceptable public keys was used. To prevent this, we introduce a zero-knowledge proof that all Ci values (except for i=0), after subtracting a secret multiple of M, have a discrete logarithm w.r.t. C0 equal to the discrete logarithm of Bi w.r.t. G. The e, s1, and s2 values above constitute the proof.
Full version, "Compute the coefficients[...]" end should be "n-1" not "m-1"