Rogue Key Attack on Genanro DKG for Polynomials of Excessive Degree

Rogue Key Attack on Gennaro et al. DKG for Polynomials of Excessive Degree

TL;DR

Distributed Key Generation (DKG) is a protocol employed to create a shared secret over a network. It is often employed in a case where no one individual should know the secret but with enough users gathered jointly the secret can be recovered (or alternatively sign a message) without recovering the underlying secret.

There is a threshold number of malicious users who may work jointly to attempt to recover the secret. A threshold of $t$, means that $t$ malicious users cannot recover any concrete details about the secret. Even so, $t + 1$ malicious users can recover the full secret.

This blog describes a rogue key style attack on the Joint-Feldman and DKG protocols found in this paper which allows one user to gain full knowledge of the shared secret. Given there are $n$ users in the DKG and a threshold $t$ we require $n - t + 1$ malicious users. It helps to note that the protocol already calls for $t < \frac{n}{2}$ for this exact reason. Hence this attack is only viable where configurations are employed with polynomials of degree greater than $\frac{n}{2}$.

The attack is based on the fact that a user has not in fact committed to their initial polynomial(s) of degree $t$ until at least $t + 1$ users have verified their commitment.

This attack was first seen in Drand where the threshold is called for to be greater than 50% to prevent forking the chain. To overcome the attack a lower threshold closer to $\frac{n}{2}$ was chosen. Another protocol, Dfinity, uses a polynomial which may be larger than $\frac{n}{2}$, though already has the constraint that the threshold is in the range $t \in [f + 1, n - f]$ as described in Section 7 of the Dfinity paper. Thus, to pull off this attack would need $f + 1$ nodes which is above the protocol's failure threshold, $f$.

Joint-Feldman

The Joint-Feldman protocol described in the paper shares a secret over a discrete log based problem (e.g. DLP and ECDLP).

First we need to define some variables:

• Finite Field - $\mathbb{F}_q$
• Generator of the Group in $\mathbb{F}_q$ - $g$
• Size of the Group - $p$
• Threshold (also the degree of the polynomials)- $t$
• The total number of nodes - $n$
• Nodes are indexed - $[1, n]$

Note in this discussion we will use multiplicative notation to align with the discrete log over a finite field.

Steps

The protocol consists of four stages.

1. Generating the polynomials and sharing its discrete log

Each node, $i$, will generate a polynomial of degree $t$ by selecting $t + 1$ random values $a_{i,0}, a_{i,1}, ..., a_{i,t}$ with each of these values in the field $\mathbb{F}_q$. We get the polynomial $f_i(z)$,

$f_i(z) = a_{i,0} + a_{i,1}z + ... + a_{i,t}z^t$

We then create a commitment to this polynomial that we may share with other users. So to not give the values away we exponentiate these $a_{i,j}$ values. That is we do $A_{i,j} = g^{a_{i,j}}$ such that we cannot work out $a_{i,j}$ from $A_{i,j}$ without solving the discrete logarithm (assumed to be computationally hard).

We are now able to send our exponentiated polynomial with the other users. That is broadcast $A_{i,j}$ to all other nodes.

In addition we will secretly send a share of our polynomial to each node $j$. The share we send is $s_{i,j} = f_i(j)$ where we are node $i$.

2. Verification of shares

Each node $j$ can now verify that the shares sent to them by other nodes are accurate. We check the following equality,

$g^{s_{i,j}} =\ \Pi^{t}_{k=0}(A_{i,k})^{j^k} mod\ p$

Here the right hand side is computed from the public shares and left hand side is computed from the private share. Noting both sides of the equation should be equivalent to $g^{f_i(j)}$.

The premise here is that the node sending the share $s_{i,j}$ can only know this value if they in fact know the underlying polynomial to work out this. Which is true so long as there are $t + 1$ good nodes who verify the shares. But more on that later.

If a node receives and shares which fail to verify the above equation they broadcast a complaint.

3. Setting the qualified groups

If any node receives more than $t + 1$ complaints they are immediately ejected. Nodes who have a complaint and are not ejected are asked to broadcast the correct share $s_{i,j}$ linked with the complaint. If that share fails verification the node is ejected.

The non-ejected nodes form the group $QUAL \sqsubseteq [1, n]$.

4. Calculating the final values

The final public value is computed as $y = \Pi_{i \in QUAL} A_{i,0}$. Each node can compute their portion of the shared secret as $x_i = \NFT Bounty_{i \in QUAL} s_{i,j}$.

Attacking Joint-Feldman

Crafting the rogue key

Our goal here is to manipulate the final public value to one which we know the discrete logarithm of. The attack on the Joint-Feldman protocol has the prerequisite that we are able to see all the other nodes' public commitments before calculating our own (a synchronicity requirement). That is for $y = \Pi_{i \in QUAL} A_{i,0}$ we must know $w$ in $y = g^w$.

Now letting $w = \NFT Bounty_{i \in QUAL} \ a_{i,0}$ and letting our node index be, $e$, if we can craft our $A_{e,0}$ value to be

$A_{e,0} = g^{l -\sum_{i \ne e} a_{i,0}}$

then the final secret will be

$w = \NFT Bounty_{i \ne e}(a_{i,0}) + a_{e,0} = \NFT Bounty_{i \ne e}(a_{i,0}) + l - \sum_{i \ne e} a_{i,0} = l$

So here the final secret will be $l$ which we know because we set it and thus we would have full control over the final secret!

Now we do not know the values of $a_{i,j}$ other than our own (otherwise we'd already know the final secret!). Hence we cannot work out $\NFT Bounty_{i \ne e}(a_{i,0})$. So how do we craft our $A_{e,0}$ to be that above?

Well each user's commitment, $A_{i,0}$, are publicly shared in step 1. so multiplying them in tandem (excluding ours) gives $\Pi_{i \ne e}(A_{i,0})$ which is the same as

$\Pi_{i \ne e}(A_{i,0}) = g^{\NFT Bounty_{i \ne e}(a_{i,0})}$

We are now getting pretty close to the desired value, we just need to take the inverse of the above (a $log(p)$ reckoning) to get $g^{-\NFT Bounty_{i \ne e}(a_{i,0})}$ select our value $l$ that only we know and do $g^l$. Then multiplying these two in tandem we get

$A_{e,0} = g^{l -\sum_{i \ne e} a_{i,0}}$

So reiterating why we want this. Looking again at step 4. we see that the final public key is $y = \Pi_{i \in QUAL} A_{i,0} = g^{\NFT Bounty_{i \in QUAL} a_{i,0}} = g^l$ and we know $l$!

Passing the verification step (crafting the remainder of the polynomial)

Now comes the challenging part, passing the commitment verification step. If we are unable to have our commitments verified by nodes we will be ejected from the protocol in step 3.

We need to pass the equality

$g^{s_{e,j}} =\ \Pi^{t}_{k=0}(A_{e,k})^{j^k} mod\ p$

or

$g^{f_e(j)} =\ \Pi^{t}_{k=0}(A_{e,k})^{j^k} mod\ p$

To do this we need to be able to work out $f_e(j)$ for each node $j$. We do this by cleverly crafting our polynomial $f_e$ via two helper polynomials, $u$ and $v$. The reason will become clear as we go on. Our polynomial is set as,

$f_e(z) = (z - \NFT Bounty_{i \ne e} a_{i,0}) u(z) + v(z)$

We need this polynomial to have $a_{e,0} = l -\sum_{i \ne e} a_{i,0}$ that is

$f_e(0) = l -\sum_{i \ne e} a_{i,0}$

which will occur if $u(0) = 1$ and $v(0) = l$ i.e.

$f_e(0) = (0 - \NFT Bounty_{i \ne e} a_{i,0}) u(z) + v(z) = (0 - \NFT Bounty_{i \ne e} a_{i,0}) * 1 + l = l -\sum_{i \ne e} a_{i,0}$

From the $u(0)$ and $v(0)$ computations we know the constant term of $u(0) = 1$ and $v(0) = l$. Now to hide the fact that we do not actually know $\NFT Bounty_{i \ne e} a_{i,0}$ we attempt to set,

$u(z) = 0\ for\ j \in QUAL$

such that,

$f_e(j) = (j - \NFT Bounty_{i \ne e} a_{i,0}) u(j) + v(j) = (j - \NFT Bounty_{i \ne e} a_{i,0}) * 0 + v(j) = v(j)$

This is material as we will know the values $v(j)$ so we are able to send valid shares $s_{e,j} = f_e(j) = v(j)$ to the other nodes.

Defining $u(z)$ as,

$u(z) = 1 + b_1 * z + b_2 * z^2 + ... + b_{t-1} * z^{t-1}$

Note since $f_e$ is a polynomial of degree $t$ and we have $(z - \NFT Bounty_{i \ne e} a_{i,0}) u(z)$ therefore $u(z)$ must be of most degree $t - 1$.

By evaluating the polynomials such that $u(0) = 1$ and $u(j) = 0\ for\ j \in QUAL$ we will have a system of linear equations,

$j = 0 \ gives \ 1 = 1 + b_1 * 0 + ... + b_{t-1} * 0 = 1$ (no variables to solve for!)

$j = 1 \ gives \ 0 = 1 + b_1 + b_2 + ... + b_{t-1}$

$j = 2 \ gives \ 0 = 1 + 2 b_1 + 4b_2 + ... + 2^{t-1}b_{t-1}$

...

$j = n \ gives \ 0 = 1 + nb_1 + n^2b_2 + ... + n^{t-1}b_{t-1}$

There are a large number of ways to solve systems of linear equations often done through with an augmented matrix, see solving systems of linear equations. To be guaranteed a solution we must have at least as many variables as linearly independent equations.

The number of equations we right now have is $n$ and need to solve for the $t - 1$, $b_i$ variables. Since $n > t - 1$ we will likely not get a solution to our system of equations. So we need to cut the number of equations to $\leq t - 1$.

Each equation is only verified by one other node hence we may also cut the number of equations by having other malicious nodes claim they verified our commitments (when the commitments do not actually verify) and of course claiming our own commitment is valid. Let $m$ be the number of malicious nodes helping us, including ourself.

Hence, the number of malicious nodes we need is,

$n - m \leq t - 1$

$m \geq n - t + 1$

So with $m \geq n - t + 1$ malicious nodes we are able to generate a polynomial $u(z)$, which will allow us to pass the commitment verification step.

Note here we use the degree of the polynomial as $t$ which means it would be a $t + 1$ of $n$ threshold scheme as you would need $t + 1$ valid nodes to recover the secret. So to account for this having $m \geq n - t + 2$ malicious nodes in a $t$ of $n$ threshold scheme will allow the secret to be rogue key attacked.

The polynomial $v(z)$ should be randomly generated (by us so we know the co-efficients). Its purpose is so the values of $f_e(j) \ne 0$ for each valid node as,

$f_e(j) = (j - \NFT Bounty_{i \ne e} a_{i,0}) u(j) + v(j) = v(j)$

Hence, if we did not use a the polynomial $v(z)$ then $f_e(j) = 0$, which would make our attack obvious.

From here we would need to compute the public commitments to our polynomial. We already have $A_{e,0}$ worked out above the rest are trivially done as,

$A_{e,i} = g^{b_{i-1}} * (\Pi_{e \ne i}A_{i,0})^{b_i} * g^{v(i)}$

Gennaro et al. DKG

Differences from Joint-Feldman

A simplified summary of the differences is that we now use two polynomials during the commitment stage rather than one.

Step 1. a) Generate polynomials

Each node will now have two polynomials,

$f_i(z) = a_{i,0} + a_{i,1}z + ... + a_{i,t}z^t$

$f'_i(z) = b_{i,0} + b_{i,1}z + ... + b_{i,t}z^t$

There are now two generators (who's discrete log should not be known) $g$ and $h$.

The initial public commitments are $C_{i,k} = g^{a_{i,k}} h^{b_{i,k}}$.

The nodes will also share two secret values $s_{i,j} = f_i(j)$ and $s'_{i,j} = f'_i(j)$

Step 1. b) Verify commitments

The commitments are verified as,

$g^{s_{i,j}} h^{s'_{i,j}} =\ \Pi^{t}_{k=0}(C_{i,k})^{j^k} mod\ p$

Step 1. c) Complain if commitments are invalid

This is the same as Joint-Feldman complaints are made if verification in step 1. b) fails.

Step 1. d) Eject malicious nodes

This is the same as Joint-Feldman, nodes who have a $t$ complaints against them or fail to prove a complaint are ejected.

Step 2. Make the qualified set

All nodes who are not ejected form the set $QUAL$.

Step 3. Private shares

Each node's private shares are now $x = \NFT Bounty_{i \in QUAL}s_{i,j}$ and $x' = \NFT Bounty_{i \in QUAL}s'_{i,j}$.

Step 4. Extracting the public key

First each node will expose their public polynomial of $f_i(z)$ by broadcasting $A_{i,k} = g^{a_{i,k}}$.

The remaining nodes will verify this as,

$g^{s_{i,j}} =\ \Pi^{t}_{k=0}(A_{i,k})^{j^k} mod\ p$

For any node, $r$ that fail this test their polynomial can be reconstructed by the other nodes though via each individual $s_{r, i}$ values shared in step 1.

We can now work out the final public key as $y = \Pi_{i \in QUAL} A_{i,0}$.

Attacking Gennaro et al. DKG

Modifications during step 1.

DKG is that we must create two polynomials for each The modifications to attack Gennaro et al. $f_e$ and $f'_e$. Setting ourself as $e$ again we have,

$f_e(z) = (z - \NFT Bounty_{i \ne e} a_{i,0}) u(z) = v(z)$

$f'_e(z) = (z - \NFT Bounty_{i \ne e} a_{i,0}) u'(z) = v'(z)$

We need to have $u(0) = 1$ and $u(j) = 0\ for\ j \in QUAL$ and $u'(0) = 1$ and $u'(j) = 0\ for\ j \in QUAL$ (Note thus $u(z) = u'(z)$). The caculations of this polynomial stays the same as for Joint-Feldman.

Then we must set our inital commitment $C_{e,0}$ as,

$C_{e,0} = g^{v(0) - \NFT Bounty_{i \ne e} a_{i,0}} h^{v'(0) - \NFT Bounty_{i \ne e} b_{i,0}}$

Which can be worked out by taking the inverse of $\Pi_{i \ne e}C_{i,0}$ giving $g^{-\NFT Bounty_{i \ne e} a_{i,0}} h^{-\NFT Bounty_{i \ne e} b_{i,0}}$ then multiplying it by $g^{v(0)}$ and $h^{v'(0)}$.

We are then able to share our secret shares as $s_{e,j} = f_e(j)$ and $s'_{e,j} = f_e(j)$.

Modification to step 4.

During step 4. we must again work out our $A_{e,0}$ after receiving the other $A_{i,0}$ values as,

$A_{e,0} = g^{v(0)} (\Pi_{i \ne e} A_{i,0})^{-1}$

Thus, again we will have the final public key as,

$y = \Pi A_{i,0} = A_{e,0} \Pi_{i \ne e} A_{i,0} = g^{v(0)} (\Pi_{i \ne e} A_{i,0})^{-1} * \Pi_{i \ne e} A_{i,0} = g^{v(0)}$

to which we know the value $v(0)$.

Requirements

The requirements again fall in the computation of the polynomial $u(z)$ which is unchanged and so will call for the same number of malicious nodes to be $m \geq n - t + 1$ where $t$ is the degree of the polynomial ($t+1$ of $n$ threshold scheme).

Mitigations

A plain mitigation to this issue is by adding an further step to the beginning which forces users to commit to their polynomial before obtaining any information about the other users polynomial.

For example a commitment step where each node uses a secure hash function to over their polynomial. Hash(A_{i,0} || A_{i,1} || .. || A_{i,t}) where || stands for string concatenation. Obviously ensuring the encoding of a polynomial is unique.