FCMP++ Integration Audit Overview

[j-berman]

I'm proposing a multi-phase audit, where each subsequent phase builds off the blocks of the prior.

Audit 1a: Crypto

Below are PR's we would like audited for this phase. For each PR, we include Audit Goals. It is our intent that by achieving the Audit Goals, the audit would answer the question "Is the linked PR fit for use in Monero?" If auditors have any additional insights that can help answer that question for each PR, and those insights do not relate to something explicitly stated in the linked PR's Audit Goals, then we would appreciate the insight nonetheless.

Note that most of the PR's build off each other by cherry-picking commits. An auditor may find it easier to review each commit sequentially, rather than each PR as a whole.

• Faster transparent amount commitments
  • rct::zeroCommitVartime
  • Audit Goals:
    • Is the cryptographic algorithm used in the function sound from a cryptographic standpoint?
    • Is the code implemented correctly? For example, in addition to auditing cryptographic security, we would also hope that an audit would catch an issue like this one that was in the code originally.
• Batch inverse
  • fe_batch_invert
  • fe_equals
  • Audit Goals:
    • Is the cryptographic algorithm used in each function sound from a cryptographic standpoint?
    • Is the code implemented correctly assuming the cryptography is sound?
    • Are the functions constant time?
• Torsion clearing
  • clear_torsion
  • get_valid_torsion_cleared_point
  • rct::verPointsForTorsion
  • mul8_is_identity
  • Audit Goals:
    • Is the cryptographic algorithm used in each function sound from a cryptographic standpoint and achieve their stated objective? For example, does the algorithm in clear_torsion adequately "clear torsion" from a cryptographic standpoint etc.
    • Is the code in each function implemented correctly assuming the above is true?
    • Are clear_torsion and mul8_is_identity constant time?
• Unbiased key image generator
  • Audit Goals:
    • Verify the rationale shared in Replace Monero's hash-to-point function with the FCMP++ Upgrade monero-project/research-lab#142 that Monero's existing hash-to-point function is in fact biased (the function named biased_hash_to_ec in the PR). If you can prove that the existing hash-to-point function is not actually biased as posited in that issue, then we do not need this PR and that is a satisfactory conclusion for this "Unbiased key image generator" item.
    • If you concur with the rationale of that issue that the existing hash-to-point may be biased, then we also have the following additional goals:
      • Does the unbiased_hash_to_ec function achieve the stated goal of being "unbiased"? By this we mean:
        • Does the implementation match Elligator 2 as specified in the Elligator paper: https://eprint.iacr.org/2013/325.pdf ? We are aware the implementation does not match the IRTF specification.
        • Is the algorithm utilized in the function unbiased from a cryptographic security standpoint?
        • Is the algorithm utilized in the function collision resistant?
        • Does the code perform as claimed assuming the cryptographic protocol utilized in the function is unbiased?
    • We hope answering the above questions will answer "is the PR fit for use in Monero." If you have additional insights that can help answer that question, that would also be appreciated.
• fe_reduce_vartime
  • Audit Goals:
    • Is the rationale shared in the comment valid rationale for introducing fe_reduce_vartime?
    • Is fe_reduce_vartime sound from a cryptographic standpoint?
    • Is the code introduced by the PR implemented correctly assuming the cryptography is sound?
• ed25519 -> wei conversion
  • point_to_ed_derivatives
  • ed_derivatives_to_wei_x_y
  • fe_ed_derivatives_to_wei_x_y
  • Audit Goals:
    • Do the functions correctly implement the specification detailed in section E.2 of the paper linked: https://www.ietf.org/archive/id/draft-ietf-lwig-curve-representations-02.pdf
    • Do the constants introduced (fe_a, fe_a_inv_3, fe_c) match the constants specified in the paper?
    • Is fe_ed_derivatives_to_wei_x_y constant time?
• Ed25519 -> X25519 conversion
  • ge_p3_to_x25519
  • edwards_bytes_to_x25519_vartime
  • Audit Goals:
    • Do the functions correctly derive the X25519 x-coordinate from an Ed25519 point from a cryptographic standpoint?
    • Is the code in each function implemented correctly assuming the above is true?

Audit 1b: Integrated Crypto

Below are PR's we would like audited for this phase. For each PR, we include Audit Goals. It is our intent that by achieving the Audit Goals, the audit would answer the question "Is the linked PR fit for use in Monero?" If auditors have any additional insights that can help answer that question for each PR, and those insights do not relate to something explicitly stated in the linked PR's Audit Goals, then we would appreciate the insight nonetheless.

Note that most of the PR's build off each other by cherry-picking commits. An auditor may find it easier to review each commit sequentially, rather than each PR as a whole.

• Converting outputs to tuples in prep for insertion to the curve tree merkle tree
  • output_to_tuple
  • output_to_pre_leaf_tuple
  • Audit Goals:
    • Verify that none of O, I, C can have torsion, and contain correct identity checks, both from a cryptographic standpoint and correctly implemented coding standpoint.
    • Verify the claim that no output or commitment detectable as a valid receive on the Monero blockchain today (or at any point in the past) would cause output_to_tuple to throw. This is critical because it means that an output that is detectable as a valid receive under existing/prior rules would not be spendable after FCMP++ goes into effect.
      • This excludes exceptional cases, such as when the person who creates the address chooses one specifically to cause conflicts (e.g. with a torsioned spend key, or a spend key proportional to a specific rerandomization of the view key), or cases with negligible statistical probability. The basic goal is to determine if a malicious actor could feasibly prevent an honest user from being able to spend a validly detectable received output by maliciously constructing outputs, or if an honest user could naturally end up crafting such an output.
• Rust FFI + constructing Selene scalar object from byte representation
  • selene_scalar_from_bytes
  • SeleneScalar
  • Audit Goals:
    • Verify this SeleneScalar struct is the correct C representation of this Rust object (the helioselene crate exposes that object as Field25519 here).
    • Verify that the function fcmp_pp::tower_cycle::selene_scalar_from_bytes calls selene_scalar_from_bytes in fcmp++.h safely from a runtime and memory standpoint.
    • Verify that the selene_scalar_from_bytes in lib.rs is implemented correctly from a runtime and memory standpoint, and calls read_F in a safe manner from the same standpoint as well as a cryptographically secure standpoint.
    • Verify that the Rust FFI layer is set up in a manner that is fit for production use in Monero (fcmp++.h, the CMake file that builds the Rust static lib that is called from the C++, lib.rs, and the C++ callers).
• ed25519 outputs -> curve tree leaves
  • outputs_to_leaves
  • Audit Goals:
    • Verify that outputs_to_leaves is implemented correctly both from a cryptographic standpoint and memory/runtime standpoint.

Audit 2: Curve Tree Building

The exact scope of this phase 2 may be adjusted, but the following is the generally expected scope:

• Tower cycle implementation and hash_grow flow
  • We want to make sure the functions highlighted in the PR description are implemented correctly, and the Rust FFI C structs are properly compatible with their respective Rust objects.
• point_to_cycle_scalar
• get_tree_extension
• get_leaf_layer_grow_instructions
• hash_children_chunks
• set_next_layer_extension
• get_grow_layer_instructions
• get_next_layer_extension

Audit 3: Consensus Integration

The exact scope of this phase 3 may be modified, but the following is the generally expected scope:

advance_tree
grow_tree
trim_block
trim_tree
get_last_path
handle_fcmp_tree
batch_verify_fcmp_pp_txs

• batchVerifyFcmpPpProofs
  // Make sure the block uses the correct FCMP++ tree root and n tree layers

---

Out of scope (slated for future optional audit):

• Torsion check
  • torsion_check_vartime
  • get_valid_torsion_cleared_point_fast

[UkoeHB]

Unbiased key image generator

Another goal is to verify that the C++ and Rust unbiased Hp() functions are equivalent (which may simply involve verifying that the C++ implementation is fully Elligator2-spec-compliant - note that the original CryptoNote implementers made no mention of Elligator anywhere (would also need to double-check that the Rust Elligator2 dependency is locked to a properly audited version of that crate)).

Verify the claim that no output or commitment detectable as a valid receive on the Monero blockchain today (or at any point in the past) would cause output_to_tuple to throw. This is critical because it means that an output that is detectable as a valid receive under existing/prior rules would not be spendable after FCMP++ goes into effect.

Of note here is that onetime addresses are not required to be in the l subgroup, but out-of-subgroup points can still theoretically be signed by brute forcing a challenge that's a multiple of h. However, default Monero wallets shouldn't be able to detect such outputs because spendkey checks in scanning code use bytewise lookups. Similarly, it's unlikely that decompression failures can be detected as valid receives. But 'shouldn't' and 'unlikely' are just that - questions for the audit.