In March, Trail of Bits engineers traveled to the vibrant (and only slightly chilly) city of Toronto to attend Real World Crypto 2024, a three-day event that hosted hundreds of brilliant minds in the field of cryptography. We also attended three associated events: the Real World Post-Quantum Cryptography (RWPQC) workshop, the Fully Homomorphic Encryption (FHE) workshop, and the Open Source Cryptography Workshop (OSCW). Reflecting on the talks and expert discussions held at the event, we identified some themes that stood out:

1. Governments, standardization bodies, and industry are making substantial progress in advancing post-quantum cryptography (PQC) standardization and adoption.
2. Going beyond the PQC standards, we saw innovations for more advanced PQC using lattice-based constructions.
3. Investment in end-to-end encryption (E2EE) and key transparency is gaining momentum across multiple organizations.

We also have a few honorable mentions:

1. Fully homomorphic encryption (FHE) is an active area of research and is becoming more and more practical.
2. Authenticated encryption schemes with associated data (AEADs) schemes are also an active area of research, with many refinements being made.

Read on for our full thoughts!

How industry and government are adopting PQC

The community is preparing for the largest cryptographic migration since the (ongoing) effort to replace RSA and DSA with elliptic curve cryptography began 25 years ago. Discussions at both the PQ-dedicated RWPQC workshop and the main RWC event focused on standardization efforts and large-scale real-world deployments. Google, Amazon, and Meta reported initial success in internal deployments.

Core takeaways from the talks include:

• The global community has broadly accepted the NIST post-quantum algorithms as standards. Higher-level protocols, like Signal, are busy incorporating the new algorithms.
• Store-now-decrypt-later attacks require moving to post-quantum key exchange protocols as soon as possible. Post-quantum authentication (signature schemes) are less urgent for applications following good key rotation practices.
• Post-quantum security is just one aspect of cryptographic agility. Good cryptographic inventory and key rotation practices make PQ migration much smoother.

RWPQC featured talks from four standards bodies. These talks showed that efforts to adopt PQC are well underway. Dustin Moody (NIST) emphasized that the US government and US industries aim to be quantum-ready by 2035, while Matthew Campagna (ETSI) discussed coordination efforts among 850+ organizations in more than 60 countries. Stephanie Reinhardt (BSI) warned that cryptographically relevant quantum computers could come online at the beginning of the 2030s and shared BSI’s Technical Guideline on Cryptographic Mechanisms. Reinhardt also cautioned against reliance on quantum key distribution, citing almost 200 published attacks on QKD implementations. NCSC promoted the standalone use of ML-KEM and ML-DSA, in contrast to the more common and cautious hybrid approach.

While all standards bodies support the FIPS algorithms, BSI additionally supports using NIST contest finalists FrodoKEM and McEliece.

Deidre Connelly, representing several working groups in the IETF, talked about the KEM combiners guidance document she’s been working on and the ongoing discussions around KEM binding properties (from the CFRG working group). She also mentioned the progress of the TLS working group: PQC will be in TLS v1.3 only, and the main focus is on getting the various key agreement specifications right. The LAMPS working group is working on getting PQC algorithms in the Cryptographic Message Syntax and the Internet X.509 PKI. Finally, PQUIP is working on the operational and engineering side of getting PQC in more protocols, and the MLS working group is working on getting PQC in MLS.

The industry perspective was equally insightful, with representatives from major technology companies sharing some key insights:

• Signal: Rolfe Schmidt gave a behind-the-scenes look at Signal’s efforts to incorporate post-quantum cryptography, such as their recent work on developing their post-quantum key agreement protocol, PQXDH. Their focus areas moving forward include providing forward-secrecy and post-compromise security against quantum attackers, achieving a fully post-quantum secure Signal protocol, and anonymous credentials.
• Meta/Facebook: Meta demonstrated their commitment to PQC by announcing they are joining the PQC alliance. Their representative, Rafael Misoczki, also discussed the prerequisites for a successful PQC migration: cryptography libraries and applications must support easy use of PQ algorithms, clearly discourage creation of new quantum-insecure keys, and provide protection against known quantum attacks. Moreover, the migration has to be performant and cost-efficient.
• Google: Sophie Schmieg from Google elucidated their approach toward managing key rotations and crypto agility, stressing that post-quantum migration is really a key rotation problem. If you have a good mechanism for key rotation, and you are properly specifying keys as both the cryptographic configuration and raw key bytes rather than just the raw bytes, you’re most of the way to migrating to post-quantum.
• Amazon/Amazon Web Services (AWS): Matthew Campagna rounded up the industry updates with a presentation on the progress that AWS (AWS) has made towards securing their cryptography against a quantum adversary. Like most others, their primary concern, is “store now, decrypt later” attacks.

Even more PQC: Advanced lattice techniques

In addition to governments and industry groups both committing to adopting the latest PQC NIST standards, RWC this year also demonstrated the large body of work being done in other areas of PQC. In particular, we attended two interesting talks about new cryptographic primitives built using lattices:

• LaZer: LaZer is an intriguing library that uses lattices to facilitate efficient Zero-Knowledge Proofs (ZKPs). For some metrics, this proof system achieves better performance than some of the current state-of-the-art proof systems. However, since LaZer uses lattices, its arithmetization is completely different from existing R1CS and Plonkish proof systems. This means that it will not work with existing circuit compilers out of the box, so advancing this to real-world systems will take additional effort.
• Swoosh: Another discussion focused on Swoosh, a protocol designed for efficient lattice-based Non-Interactive Key Exchanges. In an era when we have to rely on post-quantum Key Encapsulation Mechanisms (KEMs) instead of post-quantum Diffie-Hellman based schemes, developing robust key exchange protocols with post-quantum qualities is a strong step forward and a promising area of research.

End-to-end encryption and key transparency

End-to-end (E2E) encryption and key transparency were a significant theme in the conference. A few highlights:

• Key transparency generally: Melissa Chase gave a great overview presentation on key transparency’s open problems and recent developments. Key transparency plays a vital role in end-to-end encryption, allowing users to detect man-in-the-middle attacks without relying on out-of-band communication.
• Securing E2EE in Zoom: Researcher Mang Zhao shared their approach to improving Zoom’s E2EE security, specifically protecting against eavesdropping or impersonation attacks from malicious servers. Their strategy relies heavily on Password Authenticated Key Exchange (PAKE) and Authenticated Encryption with Associated Data (AEAD), promising a more secure communication layer for users. They then used formal methods to prove that their approach achieved its goals.
• E2EE adoption at Meta: Meta/Facebook stepped up to chronicle their journey in rolling out E2EE on Messenger. Users experience significant friction while upgrading to E2EE, as they suddenly need to take action in order to ensure that they can recover their data if they lose their device. In some cases such as sticker search, Meta decided to prioritize functionality alongside privacy, as storing the entire sticker library client-side would be prohibitive.

Honorable mentions

AEADs: In symmetric cryptography, Authenticated Encryption Schemes with Associated Data (AEADs) were central to discussions this year. The in-depth conversations around Poly1305 and AES-GCM illustrated the ongoing dedication to refining these cryptographic tools. We’re preparing a dedicated post about these exciting advancements, so stay tuned!

FHE: The FHE breakout demonstrated the continued progress of Fully Homomorphic Encryption. Researchers presented innovative theoretical advancements, such as a new homomorphic scheme based on Ring Learning with Rounding that showed signs of achieving better performance against current schemes under certain metrics. Another groundbreaking talk featured the HEIR compiler, a toolchain accelerating FHE research, potentially easing the transition from theory to practical, real-world implementations.

The Levchin Prize winners for 2024

Two teams are awarded the Levchin Prize at RWC every year for significant contributions to cryptography and its practical uses.

Al Cutter, Emilia Käsper, Adam Langley, and Ben Laurie received the Levchin Prize for creating and deploying Certificate Transparency at scale. Certificate Transparency is built on relatively simple cryptographic operations yet has an outsized positive impact on internet security and privacy.

Anna Lysyanskaya and Jan Camenisch received the other 2024 Levchin Prize for developing efficient Anonymous Credentials. Their groundbreaking work from 20 years ago is becoming more and more relevant as more and more applications use them.

Moving forward

The Real World Crypto 2024 conference, along with the FHE, RWPQC, and OSCW events, provided rich insights into the state of the art and future directions in cryptography. As the field continues to evolve, with governments, standards bodies, and industry players collaborating to further the nuances of our cryptographic world, we look forward to continued advancements in PQC, E2EE, FHE, and many other exciting areas. These developments reflect our collective mission to ensure a secure future and reinforce the importance of ongoing research, collaboration, and engagement across the cryptographic community.

By Max Ammann

Fuzzing—a testing technique that tries to find bugs by repeatedly executing test cases and mutating them—has traditionally been used to detect segmentation faults, buffer overflows, and other memory corruption vulnerabilities that are detectable through crashes. But it has additional uses you may not know about: given the right invariants, we can use it to find runtime errors and logical issues.

This blog post explains how Trail of Bits developed a fuzzing harness for Fuel Labs and used it to identify opcodes that charge too little gas in the Fuel VM, the platform on which Fuel smart contracts run. By implementing a similar fuzzing setup with carefully chosen invariants, you can catch crucial bugs in your smart contract platform.

How we developed a fuzzing harness and seed corpus

The Fuel VM had an existing fuzzer that used cargo-fuzz and libFuzzer. However, it had several downsides. First, it did not call internal contracts. Second, it was somewhat slow (~50 exec/s). Third, it used the arbitrary crate to generate random programs consisting of just vectors of Instructions.

We developed a fuzzing harness that allows the fuzzer to execute scripts that call internal contracts. The harness still uses cargo-fuzz to execute. However, we replaced libFuzzer with a shim provided by the LibAFL project. The LibAFL runtime allows executing test cases on multiple cores and increases the fuzzing performance to ~1,000 exec/s on an eight-core machine.

After analyzing the output of the Sway compiler, we noticed that plain data is interleaved with actual instructions in the compiler’s output. Thus, simple vectors of instructions do not accurately represent the output of the Sway compiler. But even worse, Sway compiler output could not be used as a seed corpus.

To address these issues, the fuzzer input had to be redesigned. The input to the fuzzer is now a byte vector that contains the script assembly, script data, and the assembly of a contract to be called. Each of these is separated by an arbitrarily chosen, 64-bit magic value (0x00ADBEEF5566CEAA). Because of this redesign, compiled Sway programs can be used as input to the seed corpus (i.e., as initial test cases). We used the examples from the Sway repository as initial input to speed up the fuzzing campaign.

The LibAFL-based fuzzer is implemented as a Rust binary with subcommands for generating seeds, executing test cases in isolation, collecting gas usage statistics of test cases, and actually executing the fuzzer. Its README includes instructions for running it. The source code for the fuzzer can be found in FuelLabs/fuel-vm#724.

Challenges encountered

During our audit, we had to overcome a number of challenges. These included the following:

• The secp256k1 0.27.0 dependency is currently incompatible with cargo-fuzz because it enables a special fuzzing mode automatically that breaks secp256k1’s functionality. We applied the following dependency declaration in fuel-crypto/Cargo.toml:20:
  

  Figure 1: Updated dependency declaration

• The LibAFL shim is not stable and is not yet part of any release. As a result, bugs are expected, but due to the performance improvements, it is still worthwhile to consider using it over the default fuzzer runtime.
• We were looking for a way to pass in the offset to the script data to the program that is executed in the fuzzer. We decided to do this by patching the fuel-vm. The fuel-vm writes the offset into the register 0x10 before executing the actual program. That way, programs can reliably access the script data offset. Also, seed inputs continue to execute as expected. The following change was necessary in fuel-vm/src/interpreter/executors/main.rs:523:
  

  Figure 2: Write the script data offset to register 0x10

Additionally, we added the following test case to the seed corpus that uses this behavior.

Using fuzzing to analyze gas usage

The corpus created by a fuzzing campaign can be used to analyze the gas usage of assembly programs. It is expected that gas usage strongly correlates with execution time (note that execution time is a proxy for the amount of CPU cycles spent).

Our analysis of the Fuel VM’s gas usage consists of three steps:

1. Launch a fuzzing campaign.
2. Execute cargo run --bin collect <file/dir> on the corpus, which yields a gas_statistics.csv file.
   • Examine and plot the result of the gathered data using the Python script from figure 4.
3. Identify the outliers and execute the test cases in the corpus. During the execution, gather data about which instructions are executed and for how long.
   • Examine the collected data by grouping it by instruction and reducing it to a table which shows which instructions cause high execution times.

This section describes each step in more detail.

Step 1: Fuzz

The cargo-fuzz tool will output the corpus in the directory corpus/grammar_aware. The fuzzer tries to find inputs that increase the coverage. Furthermore, the LibAFL fuzzer prefers short inputs that yield a long execution time. This goal is interesting because it could uncover operations that do not consume very much gas but spend a long time executing.

Step 2: Collect data and evaluate

The Python script in figure 4 loads the CSV file created by invoking cargo run --bin collect <file/dir>. It then plots the execution time vs. gas consumption. This already reveals that there are some outliers that take longer to execute than other test cases while using the same amount of gas.

Step 3: Identify and analyze outliers

The Python script in figure 6 performs a linear regression through the data. Then, we determine which test cases are more than 1,000ms off from the regression and store them in the inspect variable. The results appear in figure 7.

Finally, we re-execute the corpus with specific changes applied to gather data about which executions are responsible for the long execution. The changes are the following:

• Add let start = Instant::now(); at the beginning of function instruction_inner.
• Add println!("{:?}\t{:?}", instruction.opcode(), start.elapsed().as_nanos()); at the end of the function.

These changes cause the execution of a test case to print out the opcode and the execution time of each instruction.

The outputs for Fuel’s opcodes are shown below:

The above evaluation shows that the opcodes MCLI, SCWQ, K256, SWWQ, and SRWQ may be mispriced. For SCWQ, SWWQ, and K256, the results were expected because we already discovered problematic behavior through fuzzing. Each of these issues appears to be resolved (see FuelLabs/fuel-vm#537). This analysis also shows that there might be a pricing issue for SRWQ. We are unsure why MCLI shows in our analysis. This may be due to noise in our data, as we could not find an immediate issue with its implementation and pricing.

Lessons learned

As the project evolves, it is essential that the Fuel team continues running a fuzzing campaign on code that introduces new functionality, or on functions that handle untrusted data. We suggested the following to the Fuel team:

• Run the fuzzer for at least 72 hours (or ideally, a week). While there is currently no tooling to determine ideal execution time, the coverage data gives a good estimate about when to stop fuzzing. We saw no more valuable progress of the fuzzer after executing it more than 72 hours.
• Pause the fuzzing campaign whenever new issues are found. Developers should triage them, fix them, and then resume the fuzzing. This will reduce the effort needed during triage and issue deduplication.
• Fuzz test major releases of the Fuel VM, particularly after major changes. Fuzz testing should be integrated as part of the development process, and should not be conducted only once in a while.

Once the fuzzing procedure has been tuned to be fast and efficient, it should be properly integrated in the development cycle to catch bugs. We recommend the following procedure to integrate fuzzing using a CI system, for instance by using ClusterFuzzLite (see FuelLabs/fuel-vm#727):

1. After the initial fuzzing campaign, save the corpus generated by every test.
2. For every internal milestone, new feature, or public release, re-run the fuzzing campaign for at least 24 hours starting with each test’s current corpus.¹
3. Update the corpus with the new inputs generated.

Note that, over time, the corpus will come to represent thousands of CPU hours of refinement, and will be very valuable for guiding efficient code coverage during fuzz testing. An attacker could also use a corpus to quickly identify vulnerable code; this additional risk can be avoided by keeping fuzzing corpora in an access-controlled storage location rather than a public repository. Some CI systems allow maintainers to keep a cache to accelerate building and testing. The corpora could be included in such a cache, if they are not very large.

Future work

In the future, we recommended that Fuel expand the assertions used in the fuzzing harness, especially for the execution of blocks. For example, the assertions found in unit tests could serve as an inspiration for implementing additional checks that are evaluated during fuzzing.

Additionally, we encountered an issue with the required alignment of programs. Programs for the Fuel VM must be 32-bit aligned. The current fuzzer does not honor this alignment, and thus easily produces invalid programs, e.g., by inserting only one byte instead of four. This can be solved in the future by either using a grammar-based approach or adding custom mutations that honor the alignment.

Instead of performing the fuzzing in-house, one could use the oss-fuzz project, which performs automatic fuzzing campaigns with Google’s extensive testing infrastructure. oss-fuzz is free for widely used open-source software. We believe they would accept Fuel as another project.

On the plus side, Google provides all their infrastructure for free, and will notify project maintainers any time a change in the source code introduces a new issue. The received reports include essential important information such as minimized test cases and backtraces.

However, there are some downsides: If oss-fuzz discovers critical issues, Google employees will be the first to know, even before the Fuel project’s own developers. Google policy also requires the bug report to be made public after 90 days, which may or may not be in the best interests of Fuel. Weigh these benefits and risks when deciding whether to request Google’s free fuzzing resources.

If Trail of Bits can help you with fuzzing, please reach out!

¹ For more on fuzz-driven development, see this CppCon 2017 talk by Kostya Serebryany of Google.