Security Analysis of the NuID

Decentralized Identication Protocol

Jonathan Katz

1 Background

We provide an analysis of a decentralized identification protocol used by NuID. Relevant background is provided here, but we refer to the document describing the protocol for further details and discussion.

1.1 Requirements and Definitions

Recall that an identification protocol consists of algorithms (KeyGen; P; V) as follows:

The key-generation algorithm KeyGen takes as input a user’s secret information sk and outputs a corresponding public value pk.
The proof-generation algorithm P takes as input the secret information sk and a challenge (or "nonce") nonce, and outputs a proof.
The proof-verification algorithm V takes as input public information pk, a nonce nonce, and a proof, and outputs either 0 or 1 (indicating rejection or acceptance, respectively).

(There may also be public parameters, left implicit in the above, that can be used by any of the algorithms.) It is required that for all secrets sk, all public values pk output by KeyGen(sk), any nonce nonce, and any proof output by P(sk; nonce) it holds that V(pk; nonce;) = 1.

An identification protocol as above would be used in the following way:

A user runs KeyGen(sk) using their secret information sk in order to generate the public value pk. The user then appends pk to a ledger and receives a unique, persistent identifier ID derived from the ledger transaction.
When the user wishes to identify itself to some service, the user and service carry out the following steps:
- (a) The user sends their claimed identity ID to the service.
- (b) The service searches the ledger for the appropriate transaction (ID; pk). It then generates [ \pi \gets \mathcal{P} ]

1.2 Threat Model

The goal of the protocol is to prevent an attacker from being able to impersonate an honest user. We consider an attacker who may do any and all of the following:

Observe public transactions posted to the ledger.
Impersonate a service to a user.
Eavesdrop on executions of the identification protocol between a user and a service. (In fact, it is easy to see that eavesdropping is subsumed by being able to impersonate a service to a user, as long as the mechanism by which a service generates a nonce is public.)
Attempt to impersonate a user to a service.

Informally speaking, we require that even after doing the above it should remain infeasible for an attacker to falsely impersonate an honest user. We formalize this via a definition that gives the attacker access to various oracles modeling its ability to carry out the above attacks.

Definition 1: Fix some identification protocol = (KeyGen; P; V) and consider the following experiment involving an attacker A:

A secret value sk is chosen from some distribution D.
Compute pk = KeyGen(sk) and give pk to A.
A may repeatedly query a proof oracle P (sk; ) that allows it to specify an arbitrary nonce nonce and receive in return a proof computed using sk and nonce.
At some point, A requests a challenge nonce. In response, a nonce nonce is generated and given to A, who in turn outputs a proof. A succeeds if V(pk; nonce ;) = 1. Let Adv_1;D(A) denote the probability that A succeeds.

For a given identification protocol we would like to bound the probability with which an attacker A running for some specified amount of time succeeds. Note, however, that this is not possible unless two additional elements are specified: (1) the probability distribution D from which sk is chosen (if it is easy for the attacker to predict sk, then the attacker can trivially generate a valid proof); and (2) how nonce is generated (if it is generated in a predictable way, then the attacker can succeed by querying nonce to its proof oracle in step 3 of the attack). We will address the first point explicitly in our later analysis. Regarding the second point, we assume that services generate nonces from uniform-bit strings.

1.3 Candidate Protocol

Let H denote a cryptographic hash function, and let G be a cyclic group of prime order q with generator g. The protocol under consideration from the previous document is defined as follows:

KeyGen(sk) computes x := H(sk) and outputs pk := g^x.
P(sk; nonce) first computes x := H(sk). It then chooses uniform r in Z_q and sets A := g^r. Finally, it computes c := H(g^x; nonce; A) followed by s := c*x + r mod q. It outputs the proof (c; s).
V(pk; nonce; ), where = (c; s), works as follows: compute A := g^{s}/pk^c; then output 1 if and only if H(pk; nonce; A) = c.

2 Security Analysis

2.1 Zero Knowledge

We first prove that the protocol from Section 1.3 is zero knowledge when H is modeled as a random oracle. This means that an execution of the protocol leaks nothing about sk beyond what is already revealed by pk. This, in turn, implies that the attacker’s ability to interact with the proof oracle does not help the attacker determine sk or impersonate the user to a service. The fact that the protocol is zero knowledge greatly simplifies the security proof of the overall protocol.

To prove that the protocol is zero knowledge, we show how a simulator who is given the ability to program the hash function H (as is the case when H is modeled as a random oracle) can simulate proofs without knowing sk. The simulator—who is given pk and nonce but not sk—works as follows:

Choose uniform c; s in Z_q.
Set A := g^{s}/pk^c.
Program H(pk; nonce; A) to be equal to c. (If H(pk; nonce; A) is already defined, then this step causes a simulation failure. We show below that this occurs with negligible probability.)
Output the proof (c; s).

Let Collision denote the event that A was used in a previous hash query by the attacker or in a previously simulated proof. Since A is uniform, the probability that Collision occurs is at most [ \frac{q_H + q_P}{q}, ] where q_H is the number of H-queries made by the attacker and q_P is the number of previously simulated proofs. By a union bound, the probability that Collision ever occurs is thus at most [ \frac{q_P(q_H + q_P)}{q}. ] As we now show, if Collision does not occur then a proof output by the simulator is distributed identically to a proof generated by the real prover (who knows sk). To see this, note that when the real prover generates a proof (c; s) and Collision does not occur, we have:

the auxiliary value A is a uniform element of G;
H(pk; nonce; A) = c, where c is a uniform element of Z_q;
s is uniquely determined as s = c*x + log_g A.

On the other hand, for proofs generated by the simulator we have:

c is a uniform element of Z_q and H(pk; nonce; A) = c;
s = c*x + log_g A.

The fact that the protocol is zero knowledge means that in considering Definition 1 we may ignore step 3.

2.2 Proof of Knowledge

We also claim that the protocol is a proof of knowledge when H is modeled as a random oracle. Roughly speaking, this means that if an attacker is able to generate a valid proof relative to pk, then the attacker must know log_g pk.

The basic idea is as follows. (This intuition can be turned into a formal proof, as we do in Section 2.3, using standard techniques.) Consider an adversary who queries H(pk; nonce; A), receives in response a uniform value c, and then outputs a proof pi = (c; s) for which A = g^{s}/pk^{c}. We then rewind the adversary and return a second, uniform value c' in response to its query H(pk; nonce; A). If c' ≠ c and the attacker outputs a second proof pi' = (c'; s') for which A = g^{s'}/pk^{c'}, then we can compute log_g pk as follows. Since g^{s}/pk^{c} = A = g^{s'}/pk^{c'}, we have: [ \log_g pk = \frac{s - s'}{c - c'} \mod q.]

2.3 Reducing Security to Guessing the Secret

Here we consider a security definition that encapsulates the core of the identification protocol.

Definition 2: Consider the following experiment involving an attacker A:

A secret value sk is chosen from some distribution D.
Compute x := H(sk) and pk := g^x. Give pk to A.
A outputs a value x'. A succeeds if x' = x. Let Adv^2_D(A) be the probability that A succeeds.

Note that A succeeds if it guesses x; it is not required to guess sk. This is because knowledge of x is sufficient to impersonate the user. It is worth informally observing, however, that there are two ways A can determine x: either by guessing sk (in which case it can compute x = H(sk) and then verify that x is correct using pk), or by directly computing log_g pk.

The results of the previous two sections allow us to relate the success probability of an adversary attacking the identification protocol (i.e., with respect to Definition 1) to the success probability of an adversary guessing x (cf. Definition 2).

Proof. Fix some adversary A1 attacking the identification protocol (in the sense of Definition 1), making q_H queries to H and q_P queries to the proof oracle. Define Adv^1_D(A1). Let Succ denote the event that A1 outputs a valid proof and nonce is not one of the nonces used in A1’s queries to the proof oracle; define Adv^2(A1) as Pr[Succ]. We have the bound: [ Adv^2_D(A) \geq Adv^1_{\Pi,D}(A) - \frac{q_P}{2^{k}}\text{, and }\text{Adv}^2_D(A) \geq\mathsf{Adv}^1_{D}(A) - \frac{q_P}{2^{k}}.]

3 Hardness of Guessing the Secret

As noted earlier, an attacker can succeed in the above experiment (regardless of the distribution D) if it can guess sk or if it can solve the discrete-logarithm problem in G. We consider these two possibilities independently. For a distribution D over sk, define the min-entropy of D as:

[ H_1(D) = -\log\max_s Pr[sk = s].]

The min-entropy of x serves as a measure of how easy it is to guess sk when it is chosen according to D. In particular, there is a strategy for guessing sk in a single guess that succeeds with probability 2^{-H_1(D)} (and this is optimal); the probability of guessing sk in q_H guesses is at most q_H * 2^{-H_1(D)}. From this point of view, distributions with higher min-entropy are more secure for users in the sense that attackers are less likely to guess a user’s secret. For security of the identification scheme to hold, we also need to use a group in which the discrete-logarithm problem is hard. For a fixed cyclic group G of order q with generator g, and any algorithm A, define: [ Adv_{dlog}(A) = Pr[x \in Z_q; x' \gets A(g^x): x' = x].]

We say the discrete-logarithm problem is (t; \varepsilon)-hard (for this G and g) if for all A running in time at most t it holds that: [Adv_{dlog}(A) < \varepsilon.]

The following theorem shows that these are the only ways to determine x: 4 We can assume without loss of generality that A1 makes such a query.