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 used to create a shared secret over a network. It is often used in a case where no one individual should know the secret but with enough users gathered together 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 together to attempt to recover the secret. A threshold of $t$, means that $t$ malicious users cannot recover any concrete details about the secret. However, $t + 1$ malicious users can recover the entire 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 is important to note that the protocol already requires $t < \frac{n}{2}$ for this exact reason. Hence this attack is only viable where configurations are used 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 required 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 require $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 calculate $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 mod\ p$})^{j^k
Here the right hand side is calculated from the public shares and left hand side is calculated 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 calculate 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}$ associated 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 calculated as $y = \Pi_{i \in QUAL} A_{i,0}$. Each node can calculate their portion of the shared secret as $x_i = \Sigma_{i \in QUAL} s_{i,j}$.
Attacking Joint-Feldman
Crafting the rogue key
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). Our goal here is to manipulate the final public value to one which we know the discrete logarithm of. That is for $y = \Pi_{i \in QUAL} A_{i,0}$ we must know $w$ in $y = g^w$.
Now letting $w = \Sigma_{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 = \Sigma_{i \ne e}(a_{i,0}) + a_{e,0} = \Sigma_{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 calculate $\Sigma_{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 together (excluding ours) gives $\Pi_{i \ne e}(A_{i,0})$ which is the same as
$\Pi_{i \ne e}(A_{i,0}) = g^{\Sigma_{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)$ calculation) to get $g^{-\Sigma_{i \ne e}(a_{i,0})}$ select our value $l$ that only we know and do $g^l$. Then multiplying these two together 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^{\Sigma_{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 mod\ p$})^{j^k
or
$g^{f_e(j)} =\ \Pi^{t}{k=0}(A mod\ p$})^{j^k
To do this we need to be able to calculate $f_e(j)$ for each node $j$. We do this by cleverly crafting our polynomial $f_e$ using two helper polynomials, $u$ and $v$. The reason will become clear as we go on. Our polynomial is set as,
$f_e(z) = (z - \Sigma_{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 - \Sigma_{i \ne e} a_{i,0}) u(z) + v(z) = (0 - \Sigma_{i \ne e} a_{i,0}) * 1 + l = l -\sum_{i \ne e} a_{i,0}$
From the $u(0)$ and $v(0)$ calculations we know the constant term of $u(0) = 1$ and $v(0) = l$. Now to hide the fact that we do not actually know $\Sigma_{i \ne e} a_{i,0}$ we attempt to set,
$u(z) = 0\ for\ j \in QUAL$
such that,
$f_e(j) = (j - \Sigma_{i \ne e} a_{i,0}) u(j) + v(j) = (j - \Sigma_{i \ne e} a_{i,0}) * 0 + v(j) = v(j)$
This is important 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 - \Sigma_{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 numerous ways to solve systems of linear equations often done through using 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 currently 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 reduce the number of equations to $\leq t - 1$.
Each equation is only verified by one other node hence we may also reduce 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$
Therefore 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 - \Sigma_{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 calculate the public commitments to our polynomial. We already have $A_{e,0}$ calculated 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) = bz^t$} + b_{i,1}z + ... + b_{i,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} mod\ p$}(C_{i,k})^{j^k
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 = \Sigma_{i \in QUAL}s_{i,j}$ and $x' = \Sigma_{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 mod\ p$})^{j^k
For any node, $r$ that fail this test their polynomial can be reconstructed by the other nodes though using each individual $s_{r, i}$ values shared in step 1.
We can now calculate the final public key as $y = \Pi_{i \in QUAL} A_{i,0}$.
Attacking Gennaro et al. DKG
Modifications during step 1.
The modifications to attack Gennaro et al. DKG is that we must create two polynomials for each $f_e$ and $f'_e$. Setting ourself as $e$ again we have,
$f_e(z) = (z - \Sigma_{i \ne e} a_{i,0}) u(z) = v(z)$
$f'e(z) = (z - \Sigma) u'(z) = v'(z)$} a_{i,0
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 remains the same as for Joint-Feldman.
Then we must set our inital commitment $C_{e,0}$ as,
$C_{e,0} = g^{v(0) - \Sigma_{i \ne e} a_{i,0}} h^{v'(0) - \Sigma_{i \ne e} b_{i,0}}$
Which can be calculated by taking the inverse of $\Pi_{i \ne e}C_{i,0}$ giving $g^{-\Sigma_{i \ne e} a_{i,0}} h^{-\Sigma_{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 calculate 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 calculation of the polynomial $u(z)$ which is unchanged and so will require 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 simple mitigation to this issue is by adding an additional 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 || represents
string concatenation. Obviously ensuring the encoding of a polynomial is unique.