For EIP-4844, Ethereum clients must possess the capability to compute and validate KZG commitments. Instead of each client developing their own cryptographic solutions, researchers and developers collaborated to create c-kzg-4844, a comparatively compact C library featuring bindings for more advanced programming languages. The objective was to establish a sturdy and effective cryptographic library that all clients could utilize. The Protocol Security Research team at the Ethereum Foundation had the chance to evaluate and enhance this library. This blog post will elaborate on some methods we implement to bolster the security of C projects.
Fuzz
Fuzzing is a dynamic code testing approach that entails supplying random inputs to identify bugs within a program. LibFuzzer and afl++ are two well-known fuzzing frameworks for C projects. Both are in-process, coverage-guided, evolutionary fuzzing engines. For c-kzg-4844, we opted for LibFuzzer, owing to our established integration with LLVM project’s other features.
Presented below is the fuzzer for verify_kzg_proof, one of the methods in c-kzg-4844:
#include "../base_fuzz.h" static const size_t COMMITMENT_OFFSET = 0; static const size_t Z_OFFSET = COMMITMENT_OFFSET + BYTES_PER_COMMITMENT; static const size_t Y_OFFSET = Z_OFFSET + BYTES_PER_FIELD_ELEMENT; static const size_t PROOF_OFFSET = Y_OFFSET + BYTES_PER_FIELD_ELEMENT; static const size_t INPUT_SIZE = PROOF_OFFSET + BYTES_PER_PROOF; int LLVMFuzzerTestOneInput(const uint8_t* data, size_t size) { initialize(); if (size == INPUT_SIZE) { bool ok; verify_kzg_proof( &ok, (const Bytes48 *)(data + COMMITMENT_OFFSET), (const Bytes32 *)(data + Z_OFFSET), (const Bytes32 *)(data + Y_OFFSET), (const Bytes48 *)(data + PROOF_OFFSET), &s ); } return 0; }
Upon execution, this is the resulting output. Should an issue arise, the input would be recorded to disk, and execution would halt. Ideally, reproducing the problem should be possible.
Additionally, there is differential fuzzing, a method where two or more implementations of the same interface are fuzzed concurrently, and the outputs are compared. For any specific input, if the outputs differ when they were expected to be the same, it signifies an error. This approach is quite prevalent in Ethereum as we prefer to maintain multiple implementations of the same functionalities. Such diversity enhances safety, ensuring that if one implementation has flaws, the others may not experience the same issues.
For KZG libraries, we established kzg-fuzz, which differentially fuzzes c-kzg-4844 (via its Golang bindings) and go-kzg-4844. Up to this point, no discrepancies have been noted.
Coverage
Subsequently, we utilized llvm-profdata and llvm-cov to produce a coverage report from executing the tests. This serves as an excellent means to confirm which code has been executed (“covered”) and tested. Refer to the coverage target in the Makefile of c-kzg-4844 for an illustration of how to generate this report.
When this target is executed (i.e., make coverage) a table is produced that provides a high-level summary of how much of each function has been executed. The exported functions are listed at the top, while the non-exported (static) functions appear at the bottom.
The above table exhibits considerable green, yet it also contains some yellow and red. To discern what is being executed and what is not, refer to the generated HTML file (coverage.html), which displays the complete source file and marks non-executed code in red. In this project’s instance, most of the non-executed code pertains to challenging-to-test error scenarios, including memory allocation failures. For example, here’s some code that hasn’t been executed:
At the commencement of this function, it verifies whether the trusted setup possesses sufficient size to carry out a pairing check. No test case supplies an invalid trusted setup, resulting in this section not being executed. Furthermore, since we solely test with the accurate trusted setup, the outcome of is_monomial_form consistently remains the same and fails to return the error value.
Profile
We do not urge this forall initiatives, but since c-kzg-4844 is a performance-critical library, we believe it’s essential to analyze its exposed functions and gauge their execution duration. This can assist in pinpointing inefficiencies that could potentially lead to DoS conditions for nodes. For this purpose, we opted to use gperftools (Google Performance Tools) rather than llvm-xray because we found it to offer more features and better usability.
The subsequent example offers a straightforward illustration that profiles my_function. Profiling functions by assessing which instruction is being processed intermittently. If a function executes rapidly enough, it might not be registered by the profiler. To mitigate this risk, it may be necessary to invoke your function numerous times. In this case, we call my_function 1000 instances.
#includeint task_a(int n) { if (n return task_a(n - 1) * n; } int task_b(int n) { if (n return task_b(n - 2) + n; } void my_function(void) { for (int i = 0; i if (i % 2 == 0) { task_a(i); } else { task_b(i); } } } int main(void) { ProfilerStart("example.prof"); for (int i = 0; i my_function(); } ProfilerStop(); return 0; }
Utilize ProfilerStart(“
Here lies the graph produced from the previous command:
Here is a larger instance derived from one of c-kzg-4844’s functions. The subsequent image displays the profiling graph for compute_blob_kzg_proof. Clearly, 80% of this function’s duration is dedicated to executing Montgomery multiplications. This is anticipated.
Reverse
Next, inspect your binary using a software reverse engineering (SRE) tool such as Ghidra or IDA. These utilities assist in comprehending how high-level constructs are transformed into low-level machine code. We find it beneficial to review your source code this manner; similar to how reading a document in an unfamiliar font compels your mind to interpret phrases distinctively. It’s invaluable to observe the types of optimizations your compiler performs. Although uncommon, there are instances when the compiler eliminates elements it considered superfluous. Stay vigilant for this; a situation like this did occur in c-kzg-4844, some of the tests were being optimized out.
When you analyze a decompiled function, it won’t possess variable names, intricate types, or annotations. This information is absent from the binary once compiled. It is up to you to reverse-engineer this. Often you’ll observe functions being inlined into a singular function, multiple variables being condensed into a single buffer, and the order of verifications varying. These are just optimizations by the compiler and are generally acceptable. It may be advantageous to compile your binary with DWARF debugging details; most SRE tools can scrutinize this section for enhanced outcomes.
For instance, this is what blob_to_kzg_commitment initially resembles in Ghidra:
With a bit of effort, you can reassign variable names and incorporate comments to enhance readability. Here’s what it may look like following a few minutes of effort:
Static Analysis
Clang comes packaged with the Clang Static Analyzer, a superb static analysis tool capable of detecting numerous issues that compilers might overlook. As the term “static” implies, it inspects code without executing it. While this process is slower than compiling, it is significantly quicker than “dynamic” analysis tools that run the code.
Here’s a straightforward example that neglects to release arr (alongside another issue which we will delve into later). The compiler will fail to recognize this, even with all warnings activated because, from a technical standpoint, this is entirely valid code.
#includeint main(void) { int* arr = malloc(5 * sizeof(int)); arr[5] = 42; return 0; }
The unix.Malloc verifier will detect that arr was never de-allocated. The phrase in the alert may appear somewhat unclear, yet it becomes logical upon reflection; the analyzer arrived at the return statement and observed that the memory had not been released.
Nevertheless, not all discoveries are this straightforward. Below is an observation made by Clang Static Analyzer in c-kzg-4844 upon its first assessment of the project:
When given an unusual input, it was feasible to shift this value by 32 bits which constitutes undefined behavior. The resolution was to constrain the input with CHECK(log2_pow2(n) != 0) to make this impossible. Well done, Clang Static Analyzer!
Sanitize
Sanitizers are dynamic examination utilities that augment (add instructions) to programs, enabling them to highlight issues during runtime. They prove especially beneficial for detecting frequent errors related to memory management. Clang is equipped with several sanitizers by default; below are the four we consider most beneficial and user-friendly.
Address
AddressSanitizer (ASan) is a rapid memory fault detector that can recognize out-of-bounds accesses, use-after-free, use-after-return, use-after-scope, double-free, and memory leaks.
Here is the identical example from earlier. It forgets to release arr and it will set the 6th element in a 5-element array. This serves as a straightforward instance of a heap-buffer-overflow:
#includeint main(void) { int* arr = malloc(5 * sizeof(int)); arr[5] = 42; return 0; }
When compiled with -fsanitize=address and executed, it will generate the following error message. This directs you toward a precise indication (a 4-byte write in main). You could analyze this binary in a disassembler to ascertain precisely which instruction (at main+0x84) is resulting in the problem.
In a similar fashion, here’s a case where it detects a heap-use-after-free:
#includeint main(void) { int *arr = malloc(5 * sizeof(int)); free(arr); return arr[2]; }
It informs you that there’s a 4-byte read of deallocated memory at main+0x8c.
Memory
MemorySanitizer (MSan) serves as a detector for uninitialized reads. Here is a straightforward case which accesses (and returns) an uninitialized value:
int main(void) { int array[2]; return array[0]; }
When compiled using -fsanitize=memory and run, it will present the following error notification:
Unpredictable Behavior
UndefinedBehaviorSanitizer (UBSan) identifies unpredictable behavior, which pertains to cases where the operation of a program is erratic and not dictated by the language standard. Common instances include accessing memory out-of-bounds, dereferencing an invalid pointer, reading variables that are not initialized, and overflowing a signed integer. For instance, incrementing INT_MAX is an example of unpredictable behavior.
#includeint main(void) { int b = INT_MAX; return b + 1; }
When compiled using -fsanitize=undefined and then executed, it will display the following error notification pinpointing the exact issue and its conditions:
Threading
ThreadSanitizer (TSan) identifies data races, which can take place in multi-threaded applications when two or more threads access a common memory location concurrently. This scenario introduces unpredictability and may result in undefined behavior. Below is an instance where two threads increment a global counter variable. Without any form of locking or semaphores, it is completely feasible for both threads to increment the variable simultaneously.
#includeint counter = 0; void *increment(void *arg) { (void)arg; for (int i = 0; i counter++; return NULL; } int main(void) { pthread_t thread1, thread2; pthread_create(&thread1, NULL, increment, NULL); pthread_create(&thread2, NULL, increment, NULL); pthread_join(thread1, NULL); pthread_join(thread2, NULL); return 0; }
When compiled using -fsanitize=thread and run, it will display the following error notification:
This error notification indicates that there exists a data race. In both threads, the increment function is concurrently writing to the same 4 bytes. It even specifies that the memory involved is the counter.
Valgrind
Valgrind is a formidable instrumentation framework designated for constructing dynamic analysis tools, renowned for detecting memory errors and leaks through its integrated Memcheck tool.
The next image illustrates the results obtained from executing c-kzg-4844’s tests utilizing Valgrind. The red box highlights a legitimate finding for a “conditional jump or move [that] depends on uninitialized value(s).”
This highlighted an edge case in expand_root_of_unity. If incorrect root of unity or width was supplied, it could result in the loop terminating prior to the initialization of out[width]. In such a case, the final validation would rely on an uninitialized value.
static C_KZG_RET expand_root_of_unity( fr_t *out, const fr_t *root, uint64_t width ) { out[0] = FR_ONE; out[1] = *root; for (uint64_t i = 2; !fr_is_one(&out[i - 1]); i++) { CHECK(i blst_fr_mul(&out[i], &out[i - 1], root); } CHECK(fr_is_one(&out[width])); return C_KZG_OK; }
Security Assessment
Once the development reaches a stable state, it is crucial to carry out thorough testing, and additionally, have your team manually scrutinize the codebase multiple times. Following this, it’s advisable to arrange a security assessment by a recognized security organization. While this won’t serve as a definitive endorsement, it indicates that your project possesses a certain level of security. It is important to remember that achieving perfect security is unattainable; there will always be potential vulnerabilities.
For the c-kzg-4844 and go-kzg-4844 projects, the Ethereum Foundation engaged Sigma Prime to perform a security assessment. They generated this documentation which outlines 8 findings. Among these, there is one critical vulnerability identified in go-kzg-4844, which was a significant discovery. The BLS12-381 library utilized by go-kzg-4844, gnark-crypto, contained a flaw that permitted invalid G1 and G2 points to be decoded successfully. Should this issue not have been rectified, it might have led to a consensus problem (a disagreement among different implementations) within Ethereum.
Bug Reward Program
If a weakness within your project poses the possibility of being exploited for advantage, similar to the situation with Ethereum, consider implementing a bug bounty initiative. This program enables security researchers, or indeed anyone, to report vulnerabilities in return for a financial reward. Typically, this is targeted toward findings that can demonstrate the feasibility of exploitation. If the bug bounty rewards are fair, those who identify bugs will alert you to the issue instead of leveraging it or selling it to a third party. It is advisable to launch your bug bounty initiative once the issues from the initial security assessment are addressed; ideally, the costs for the security review should be less than the payouts for the bug bounty.
Final Thoughts
Creating robust C projects, particularly in the vital fields of blockchain and cryptocurrencies, necessitates a comprehensive strategy. Considering the intrinsic vulnerabilities associated with the C programming language, an amalgamation of best practices and tools is imperative for crafting resilient software. We trust that the insights and experiences shared from our work with c-kzg-4844 will offer valuable guidance and recommended practices for others embarking on similar endeavors.
