# 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: 1. 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. 2. 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`: 1. A secret value `sk` is chosen from some distribution `D`. 2. Compute `pk = KeyGen(sk)` and give `pk` to `A`. 3. `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`. 4. 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: 1. Choose uniform `c; s` in `Z_q`. 2. Set `A := g^{s}/pk^c`. 3. 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.) 4. 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`: 1. A secret value `sk` is chosen from some distribution `D`. 2. Compute `x := H(sk)` and `pk := g^x`. Give `pk` to `A`. 3. `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.