Fastcrypto DKG and TBLS Audit Summary by Common Prefix

**Audit Commit:** c9083bc **Audited Files:** 1. `fastcrypto-tbls/src/dkg.rs` 2. `fastcrypto-tbls/src/dl_verification.rs` (except `verify_triplets`, `verify_deg_t_poly` and `verify_equal_exponents`) 3. `fastcrypto-tbls/src/ecies.rs` 4. `fastcrypto-tbls/src/nizk.rs` 5. `fastcrypto-tbls/src/nodes.rs` 6. `fastcrypto-tbls/src/polynomial.rs` 7. `fastcrypto-tbls/src/random_oracle.rs` 8. `fastcrypto-tbls/src/tbls.rs` 9. `fastcrypto-tbls/src/types.rs` ### Medium 1. `dkg.rs [L306]`: `process_message` doesn't check that the message being processed is unique for the sender and that the sender has a non-zero weight. This can lead to potential DOS attacks by parties even with zero weight. 1. `dkg.rs [L401, L463]`: It is unclear when the `merge` and `process_confirmations` message should be called by the higher-level protocol. On the protocol level, both of these functions should be called by all the parties exactly at the same first message when messages with sufficient weight have been accumulated. This has to be implemented carefully by the higher level protocol, specifically if the previous step has async computation (e.g., multiple `process_message` being executed asynchronously before `merge`). This could lead to race conditions where the messages that join the final set differ for different parties. 1. `dkg.rs [L471]`: The check that `minimal_threshold` is at least `t` does not guarantee a quorum of signers will be able to form. The adversary can fill the first `t` slots, and then allow a single honest party with good shares. If we assume all other honest parties have bad shares, the adversary can always break liveness. As the documentation mentions, the check should test against `t+f`. ### Low 1. `polynomial.rs [L36], dl_verification.rs [L53, L82, L115]`: `usize` to `u32` type conversions might be unsafe if the code runs on a 64-bit machine. Max `u32` is not an astronomical number and can be overflowed when indexing a large number of items, even with each item taking up multiple bytes. 1. `nodes.rs [L154]`: The types are tightly tied to the magical constants in the code: `1000`, which is used as an upper limit for the number of nodes, and `40`, which is the upper bound for the reduction divisor. The `sum` in the reduce function is of type `u16` (maximum`65535`). Based on the above constants and the code, the sum can be a maximum of `39000` (`1000` users, with each, having the maximum possible remainder `mod 40`). This is safe, but if either of the above-mentioned constants is increased by ~1.6x, the `sum` variable will overflow. 1. `nodes.rs [L151]`: The `t` param in the reduce function should be of type `u32`. It should be of the same type as the `total_weight`. Also, in `Party` struct, `t` is a `u32`. 1. `nodes.rs [L124]`: The `share_ids_of` function currently brute forces over all the potential share IDs and filters that of the given party ID. This operation requires O(`total_weight` * log(`nodes`)). This function is called over all the nodes in the `create_message` function. As all the shares of the node are sequential, a cleaner approach would be to find the index of party ID in the `nodes_with_nonzero_weight` and then use that to get the range of share IDs from the `accumulated_weights`. This would be significantly cheaper as the complexity doesn't scale with the `total_weight`. 1. `dl_verification.rs [L44]`: `verify_poly_evals` should use the Fiat-Shamir heuristics to make the function deterministically checkable. As is, `get_random_scalars` may theoretically produce values that fail on one system but pass on others. We recommend hashing the entire set of evals, polynomial and a separate index for each output, and appropriate domain separator strings. 1. `dl_verification.rs [L185]`: `get_random_scalars` should use the `rand` trait of `Scalar` to generate a random scalar instead of manually deserializing a random `u64`. 1. `ecies.rs [L126]`: AES CTR Mode is used in a non-standard way (with fixed zero IV). Current usage ensures that each ElGamal/DH ephemeral key is only used once, so there is no AES key+IV reuse. However, the resulting code may be fragile (e.g., if communications over different shares are not properly batched as they are now). Additionally, the documentation should mention using AES in place of the RO construction for ElGamal. ### Informational 1. `polynomials.rs [L95]`: `get_lagrange_coefficients_for_c0` doesn't need the complete `Eval` objects; just the indexes of the evaluations should be sufficient. It might be worth fixing the interface so that the coefficients can be computed or cached based on indexes (without evaluations). 1. `polynomials.rs [L143]`: `get_lagrange_coefficients_for_c0` can return the common numerator instead of dividing, and in the `recover_c0`, the numerator can be multiplied to the final result. This saves `t` scalar multiplications. 1. `nodes.rs`: It is not required to store and maintain the `total_weight` in the `Nodes` struct as the `total_weight` will always be equal to the last entry of `accumulated_weight`. The `total_weight` getter function can be augmented to return the last entry of `accumulated_weight`. 1. `nodes.rs, dkg.rs`: The name `total_weight` is used more than twice in different contexts. Initially it is used inside `nodes.rs` to represent the sum of all weights in the protocol. In `dks.rs` it is used in `L408` to refer to the weight of the first message set (I1), and later in `L481` to refer to the size of the second message set (I2). 1. `nodes.rs [L157]`: The `for` loop can be reversed, and a `break` statement can be used when the `if` statement is entered for the first time. For all cases where a reduction is possible, we will break earlier and not iterate over the initial factors. 1. `tbls.rs [L39]`: `partial_sign_batch` can perform precomputation with regards to `h` to improve performance. Since the same `h` value is used for each share, we can afford to use large amounts of precomputation. This can be based on the `multiplier/windowed.rs` code. Alternatively, BLST also supports setting a window manually via `blst_[p1/p2]s_mult_wbits_precompute` 1. `nizk.rs [L17, L112]`: Consider consolidating NIZK code so that Pedersen and Schnorr proofs share the same code, which would accept a vector of inputs (with `length=1` for Schnorr and `length=2+` for Perdersen and variants). 1. `nizk.rs [L186]`: The final check for the NIZK can be sped up by refactoring to one side and using multi-multiplication. ``` Currently we check: *e1 + *e2 * c == *e3 * z which can be rewritten as: *e1 == *e3 * z + *e2 * (-c) ``` 1. `tbls.rs [L94]`: aggregate function performs unnecessary cloning of the `partials` iterator. The `unique_by` combinator creates a hashmap internally to perform the uniqueness check, and cloning leads to the work being performed twice. Here is a cleaner way to do this: ```rust let unique_partials = partials .unique_by(|p| p.borrow().index) .take(threshold as usize) .collect_vec(); if unique_partials.len() != threshold as usize { return Err(FastCryptoError::NotEnoughInputs); } ```  ### Informational / Model Clarifications 1. `nodes.rs L151`: The weight reduction is not specified outside of the code. The property seems to be that if there exists 2f+delta+1 weight out of 3f+delta+1 in the hands of honest users before compression, then (1) after compression with $d$, honest users will hold at least roundup((2f+1)/d) and dishonest ones will hold at most rounddown(f/d). As a trivial example, suppose we have 5 honest participants each with 20 stake, and 1 adversarial with 40. Also suppose we allow a `delta` of 5. A single application of reduce with that delta is safe (as 100-5 = 95 is greater than 2*40+1). The resulting shares are then 5 honest users with 1 share and 1 dishonest with 2. Reducing again, will allow a reduction with 2 as the lost shares are “only” 5 which is allowable. In general, repeated applications of reduce should not be possible. First, as delta is expressed as an absolute value, its real measure in terms of initial stake is multiplied by the previous reduction scalar (in the above, the delta of 5 in the second round, actually allows for 100 initial stake to be destroyed). Even with delta expressed as a percentage (e.g. 3%), the (worst case) loss is incremented with each round. Fortunatelly, even repeated applications do not break safety: if the adversary does not hold `t` shares at the start, he will not hold `t` (reduced) shares at the end. This is due to the shares being rounded down when divided, whereas the threshold value `t` is rounded up. In the above, a value of `t=85` would reduce to 3 in the first instance and to 2 in the second. 1. `dkg.rs`: The higher-level protocol shouldn't predicate uptime rankings, rewards, or similar metrics based on participation in signing w.r.t. the final aggregate key. This is because the adversary can force an honest user out of the final set of participants by sending them bad shares and delaying their complaint until enough parties have replied for Phase 3 to end. If we wish to increase participation in signing, we might want to extend Phase 3 to allow for complaints from all users. 1. The current protocol allows for situations where the derived keys rely on only 1 honest party (e.g., $f$ out of $f+1$ members of $I_1$ are corrupted). While this is theoretically fine in the static corruption model, in a real-world situation where this 1 honest party is later corrupted, the secret key would be exposed to the adversary. For example, this could happen if this party no longer has an economic incentive to behave honestly and/or protect its protocol randomness and transcript.