Diogenes is an ambitious project to design and run a “ceremony” to generate an RSA modulus. The Ceremony is a multiparty computation (MPC) protocol of an unprecedented scale. Once completed, the generated modulus will be incorporated into a VDF protocol, which will be used as part of an unbiased random beacon in the Eth2.0 blockchain.
The Ligero Inc team leads the project with LigeroRSA, the code repository implementing Diogenes. It’s 21k C++ lines of code, not including external libraries.
Upon request of the VDF Alliance and the Ethereum Foundation, Zengo is reviewing Diogenes as a real-world cryptographic system. We’ve teamed up with Prof. Claudio Orlandi and Prof. Peter Scholl for the project.
In our first blog post, Diogenes Octopus, we described a potential attack vector that could have gained backdoor access to Ethereum 2.0 VDF. The attack required the central coordinator to collude with one of the participants.
In this post, we present a new attack named DogByte. This attack allows any passive observer to covertly learn the secrets p,q, completely breaking the security of the protocol.
The Diogenes protocol in a nutshell
The goal of the Diogenes protocol is to generate a bi-prime N=pq where p, q are 1024-bit primes, unknown to any parties. To this end, the parties run the following protocol:
- Each party samples random local secret shares p ᵢ, q ᵢ.
- The parties compute a joint public key.
- The parties encrypt their secret shares with the joint public key.
- A designated party, named the coordinator, combines all the ciphertexts and computes homomorphically an encryption of p = (p ₁ + p₂ + .. + p_n), q = (q ₁ + q₂ +…+ q_n) and N = p*q.
- The parties jointly decrypt to get a candidate N.
- The parties run tests to check that p and q are two primes (remember that no single party knows p,q, so all tests are run in a distributed fashion)
It’s possible that the protocol set out above might fail to produce a bi-prime N. Therefore, the steps are repeated many times in parallel to guarantee that at least one candidate will be valid (pass all tests). The protocol will naturally generate many “bad” candidates. This point should be kept in mind because it will be crucial to the attack.
Adding zero-knowledge to handle malicious behavior
The protocol above is correct, but it’s not yet secure. Nothing keeps a participant from cheating. For example, what happens if one party in the protocol runs the distributed primality tests on their secret input (step 6) but reports false results? Candidate N might be chosen while not an actual bi-prime.
Letting a malicious party participate in a protocol that assumes honest computation can be devastating: the malicious party can cause a DoS attack, learn secret inputs, or introduce bias.
The solution is conceptually simple.
Each step executed by each party must be accompanied by a proof for the correctness of the computation. Continuing our example, reporting a false result by a malicious party will get caught immediately because the proof for the correctness of the computation will fail. The protocol uses zero-knowledge (ZK) proofs to prevent exposure of secret inputs during each computation.
The protocol must run in under 20 minutes
The protocol designers faced another issue. Repeating the protocol and adding a ZK proof to each step is expensive and time-consuming. The spec required the protocol to run in under 20 minutes, so the following optimizations were suggested as a remedy:
- Delay all ZK proofs until the last step of the protocol.
- Produce a ZK proof only for the bi-prime candidates that survived all the tests.
- For the rest of the candidates: each party will simply reveal all the secret randomness used to derive the “bad” candidate. The check for correctness of computation will be carried out over the revealed values.
Since the parties’ inputs are independent and random, there is no risk in revealing “bad” candidates as the revealed values cannot leak anything about the random secrets used for the “good” candidates. On the other hand, the ZK proofs will guarantee that “good” candidates were computed correctly, without leaking any bits of its primes p,q.
Packing encryptions
There is a second important optimization used in the protocol. To understand it, we first need to explain the homomorphic encryption scheme.
The encryption scheme used is Ring-LWE (RLWE): the public key is a pair (a,b), and the private key is a secret s such that: b = a·s + e where e is a small noise term (and “·” represents inner product). In the case of RLWE, we work with polynomials: in fact: a, s, b, e are all polynomials of some degree (d). When we say that s, e are small, we mean that all the d+1 coefficients are small and bounded in the same way.
To encrypt a message m:
- Encode it as one coefficient of a polynomial
- Sample small noise polynomials x, y, z
- Compute c₁ = a·x+y
- Compute c₂ = b·x+z+m
C = (c₁,c₂) is the ciphertext. The computation is done over coefficients of the polynomials. But this encrypted scheme is very wasteful, using all those degree (d) polynomials for a single message. Moreover, the message is encoded as a single coefficient, which leaves all other coefficients to be 0 in the message polynomial.
Indeed, for encrypting multiple messages, there is an obvious optimization here, which is to “pack” the different messages into different slots (encode them to different coefficients). This optimization is used in Diogenes protocol: Each participant encrypts its private input, and all encryptions are packed to a single ciphertext.
When the two optimizations collide
Separately, the two optimizations provide considerable improvement to the efficiency of the protocol. However, as we will illustrate, having them together creates an unwanted side-effect: a complete leakage of the secret p,q!
If we assume the attacker gains access to the transcript of the protocol (which is public). By looking at the transcript, the attacker will be able to see the ciphertext, which is a packed encryption of all the parties’ contributions. Now, recall that since ZK proofs are expensive, any unnecessary proof is replaced by revealing the value in the clear. Concretely:
- The m coefficients vector (c₂) of size d will be revealed except for k slots belonging to “good” candidates
- The y coefficients vector (c₁) of size d will be revealed except for k slots belonging to “good” candidates
- The z coefficients vector (c₂) of size d will be revealed except for k slots belonging to “good” candidates
The x coefficients vector (c₂) is kept completely hidden. All of it is used as a witness in the ZK proofs.
The attacker’s target is to learn the k hidden message coefficients. The first thing to do is to recover the x vector. Now since:
- The locations of the known coefficients are public.
- Writing c₁,c₂ using linear algebra, each one produces d equations, d-k of them are error-free equations. In total, combining c₁,c₂, we have 2(d-k) error-free equations (equations without unknown y, z, m elements).
- Each of the equations is a linear combination of the secret vector x.
- 2(d-k) > d (size of vector x) in our protocol.
We can recover x in full using Gaussian elimination on d out of the 2(d-k) equations. Once we learned the x vector, we compute the k slots directly in the message vector that were kept hidden in the k equations from c₂. And just like that — we learn all the secrets in the protocol.
(In fact, the unknown message slots are masked with small noise elements from w vector. So, there is an additional rounding operation to remove the noise and get the clean message from each equation).
A toy example
To explain how the attack works more clearly, here is a short toy example with 3 parties. The ciphertext is two public vectors:
c₁ = [2.2, 2.1, 2.3]
c₂ = [4, 4.7, 5.8]
The public key, also known to all, is the two vectors:
a = [2, 4, 6]
b = [3, 5, 7]
The message vector is [m₁,m₂,m₃]. Let’s assume only m₃ represents a “good” candidate (information known to all). Therefore the parties reveal y₁=0.2, y₂ = 0.1 z₁ = 0.4, z₂ = 0.1, m₁ = 1 , m₂ = 2. The unknown secrets are: the x vector [x₁,x₂,x₃], y₃, z₃ and m₃.
Here are all the equations:
c₁₁ = 2.2 = 2×1 + 4×2 + 6x₃ + 0.2
c₁₂ = 2.1 = 2×1 + 4×2 + 6x₃ + 0.1
c₁₃ = 2.3 = 2×1 + 4×2 + 6x₃ + y₃
c₂₁ = 4 = 3×1 + 5x₂ + 7x₃ + 0.4 + 1
c₂₂ = 4.7 = 3×1 + 5x₂ + 7x₃ + 0.1 + 2
c₂₃ = 5.8 = 3×1 + 5x₂ + 7x₃ + z₃ + m₃
We first use the equation for c₁₁, c₁₂, c₂₁ to learn [x₁,x₂,x₃] = [0.3, 0,2, 0.1]. This is done using Gaussian elimination. Note that the c₂₂ equation could have been used as well.
We then plug x₁,x₂,x₃ into equation c₂₃ to get z₃ + m₃ = 3.1
Rounding to the closest integer, we get m₃ = 3, and we are done.
The aftermath, fix, and lessons learned
We responsibly disclosed the attack, and the authors of the paper are working on a fix. The fix will most likely be to not reveal any of the y, z, m slots for the “bad” candidates and use ZK for all. This will probably slow down the protocol by a few minutes.
While the paper does provide a security proof, all optimizations, including those discussed above, are not included in the paper’s security analysis.
Because the DogByte attack’s root cause is the unsafe usage of optimizations, the authors are now writing a full proof for the protocol that includes the optimizations.
As a quick side note, our attack considered the April 20th version of the Diogenes paper. Section 6.3 describes the optimization of revealing all the parties’ secret randomness used in the “bad” candidates computation.
Acknowledgements
We would like to thank the Ethereum Foundation, VDF Alliance, the Ligero team, Dmitry Khovratovich, Bernardo David, Riad Wahby, Mary Maller, Claudio Orlandi, Peter Scholl, and Ariel Nof for their work and continued dedication.
Stay tuned for part 3 🙂