Last month, hundreds of cryptographers descended upon Tokyo for the first Real World Crypto Conference in Asia. As in previous years, we dispatched a handful of our researchers and engineers to present and attend the conference.
What sets RWC apart from other conferences is that it strongly emphasizes research, collaborations, and advancements in cryptography that affect real-world systems. This year, we happened to notice a couple items that we’ll highlight. First, many talks detailed the painstaking process that is secure cryptographic protocol development. Second, PQC is on the rise and is steadlily advancing from theory into practice. Lastly, sometimes the most interesting cryptographic flaws aren’t even cryptographic flaws: bad RNGs and multi-threading can just as easily break your cryptography.
Our EDHOC presentation
Trail of Bits cryptographer Marc Ilunga spoke (paper, video, slides) about his research analyzing the security of the Ephemeral Diffie-Hellman Over COSE (EDHOC) protocol. EDHOC is a lightweight key exchange protocol similar to TLS but more compact. In collaboration with other researchers, Marc’s work verified multiple security properties of the EDHOC protocol and even identified theoretical security issues that led to updates made to the EDHOC standard.
The talk highlighted how the LAKE working group openly called the community to analyze EDHOC and benefited from many insights, making the protocol safer and better overall. With high-assurance cryptography on the rise, more tools are available to assist with this task. For instance, the presentation on HACSPEC (paper, slides, video) paves the way for high assurance standards for cryptography. It provides tools to specify cryptographic specifications that can further be formally verified.
Invite your friends and adversaries to your protocol party!
Our talk echoed a common theme at the conference, encouraging people to collaborate with researchers and stakeholders to analyze crypto and protocols instead of rolling their own. Many cryptographic protocols, such as End-to-End-Encryption (E2EE) messengers, have been broken in recent years with varying levels of impact. Notable examples include Telegram in 2022, Bridgefy, and Threema (paper, slides, video). These examples have something in common: missing formal analysis. The lesson is that Telegram, Bridgefy, and Threema should not have rolled out their crypto! But to be fair, deployment of a new and ad-hoc protocol is hardly uncommon. The first formal analysis of the highly acclaimed Signal protocol came after the Signal app was already deployed. Even then, further analysis was needed to capture other security aspects.
On its own, the phrase “Don’t roll your crypto” isn’t helpful. Someone has to roll some crypto at some point. The case of Threema shows that an application that uses all the right cryptographic primitives can still be broken. One lesson from the EE2E messaging world is that, perhaps, it doesn’t matter who rolled what. What’s important is the analysis that was performed against the protocol. Formal analysis and good old cryptanalysis of a protocol are necessary to get confidence in a new protocol.
Don’t roll your protocol alone! Use all the tools available to you. If you are unfamiliar with one of these tools, use the army of friends willing to apply these tools against your protocol. If you’d like to learn more about how to analyze these protocols and the tools available, book a call to discuss with one of our cryptographers. Our doors are always open!
Post-quantum cryptography is steadily advancing
NIST announced the post-quantum cryptography (PQC) standard candidates last year, so it did not come as a huge surprise that PQC was a big topic of discussion at RWC. In addition to the RWC conference this year, an additional Real World PQC workshop was run alongside RWC to cover additional topics.
PQC is steadily advancing, with standards for the first primitives expected to emerge over the coming years. However, as the talks indicate this year, many challenges are ahead for the post-quantum world. First, implementing these schemes in real systems is challenging, with many unknown and unforeseen issues. In addition to this, more PQC primitives and protocols are needed. Designing more advanced primitives securely and effectively across many use cases will be challenging. Here are some interesting discussions of these challenges.
A talk from Google described applying PQC to their Application Layer Transport Security (ALTS) protocol. ALTS is an authentication protocol, similar to TLS, that Google uses to secure communication within its infrastructure, such as data centers. Threat modeling shows that this is where PQC is most urgently needed, so Google decided to implement NTRU-HRSS, a lattice-based post-quantum cryptosystem, for ALTS even before the NIST standardization process was complete. This talk presented some implementation issues that occurred; for instance, the public key and ciphertext for this cryptosystem were 9-10 times larger than the existing ALTS algorithms, allocating large HRSS keys on the stack resulted in stack overflows for some architectures, and performance in practice didn’t align with the expected benchmarks. However, with some adjustments, they managed to integrate NTRU-NRSS into ALTS within their requirements.
Cloudflare also presented a talk describing an internal PQC project. Cloudflare supports Privacy Pass, a cryptographic protocol that allows users to prove they are humans and not bots across many websites without revealing unnecessary private information about themselves. To achieve this, Privacy Pass uses advanced cryptographic primitives known as blind signatures and anonymous credentials. Unfortunately, the NIST standardization process does not have any candidates for advanced primitives such as these, so Cloudflare designed its own post-quantum scheme that was based on Dilithium, a digital signature candidate selected by NIST. The result was surprisingly efficient: ~300ms prover time and ~20ms verifier time, with a proof size of ~100KB. It’s exciting to see post-quantum cryptography applied to more advanced cryptographic primitives and protocols such as Privacy Pass.
NXP presented work that implemented the Dilithium PQC candidate on an embedded device. For embedded devices, protecting against side-channel attacks becomes vitally important. This talk identified a gap in the research around Dilithium. Compared with another candidate, Kyber, protecting against side channels in Dilithium has received little attention. NXP’s work identified some improvements to state-of-the-art mitigations. Their work also noted that much of the runtime was spent protecting the implementation by invoking the Keccak hash function, and on their embedded devices, a significant speedup could be obtained if these were replaced with calls to a True Random Number Generator (TRNG). However, using a TRNG instead of Keccak would violate the specification, which is a great example of why these standardization processes are difficult and time-consuming. Designing a system that will run securely and optimally across many different platforms and use cases is difficult.
PQC in other talks
While the NIST PQC standardization effort focuses on cryptographic primitives, these primitives will eventually have to be used in protocols. Updating existing protocols to include post-quantum resilient primitives is nontrivial, as explained in the context of the IETF at RWPQC (slides).
Since the post-quantum candidates are relatively young by cryptographic standards, only some people trust their resistance against attacks. More than one candidate has been broken by the dreaded laptop running in a weekend. Therefore, they are preferably a hybrid approach, alongside their classical counterparts, to ensure the best of both worlds regarding security. (You would need to break both primitives to attack the protocol.)
Several protocol updates were presented at RWPQC and RWC using this approach, starting with a post-quantum variant of the Noise protocol framework (video, slides) for constructing key exchange protocols. Furthermore, lightning talks at RWC and RWPQC introduced Rosenpass, a post-quantum variant of the Wireguard protocol for constructing VPNs.
Cryptographic failures are often non-cryptographic
Previous years of Real World Crypto featured non-cryptographic errors breaking prominent cryptographic schemes. This year was no exception: multiple talks demonstrated fatal non-cryptographic attacks on cryptographic hardware, protocols, and schemes.
Cryptography is a powerful tool for solving many problems in software; many years of research and cryptanalysis have given us a powerful suite of primitives that can, for example, safely encrypt and protect our data. But software is still only as strong as its weakest link, and a secure encryption scheme is useless when an attacker can easily bypass it entirely, as we will see in some of the talks from this year:
In Framing Frames: Bypassing Wi-Fi Encryption by Manipulating Transmit Queues (paper, slides, video), Mathy Vanhoef presented two new variants on a well-known class of weaknesses in the 802.11 standards, which include WPA/2 and WPA/3. The first variant completely bypasses Wi-Fi encryption by tricking an access point (AP) into insecurely “encrypting” buffered packets with an all-zero key or otherwise undefined key context. So, rather than developing some complex and novel cryptographic attack against the encryption scheme, this bug tricks an AP into using an empty encryption key.
The second variant involves bypassing client isolation, a common feature of wireless networks intended for use by untrusted clients (e.g., public hotspots and global networks like eduroam). APs that offer client isolation rely on ad-hoc synchronization between two nominally decoupled layers of the 802.11 stack: the security layer, which uses 802.1X identities, and the packet routing layer, which uses IP addresses and device MACs. By observing this dependency between decoupled layers, an attacker can insert a request with a spoofed MAC and, when timed correctly, trick the AP into encrypting the incoming response with a newly generated key. The result is that the attacker cannot only spoof the victim’s MAC (ordinarily just a denial of service) but also decrypt incoming traffic intended for the victim. This attack does not rely on any sort of novel cryptographic attack. It’s easy to trick the AP into decrypting things for you instead!
These two new variants are not particularly similar in procedure or scenario but are similar in origin: ambiguity within the specification with respect to extended functionality (client isolation) or optimizations (packet buffering) regularly offered by vendors. Together, these cleanly represent one of the biggest challenges to the value of formal modeling: the model under-proof must be correct and complete for actual device behavior. As we know from the world of compiler optimizations, observably equivalent behavior is not necessarily safe for all observers — the same basic truth applies to protocol design!
Weak RNGs and weak testing are a toxic combination
In Randomness of random in Cisco ASA (slides, video), Benadjila and Ebalard stepped through their investigation of many duplicated ECDSA keys and nonces observed while testing a large X.509 certificate corpus. When evaluating ~313,000 self-signed ECDSA certificates originating from Cisco ASA boxes, 26% (~82,000) had duplicated ECDSA nonces, and 36% (~113,000) had duplicated ECDSA keys. Additionally, of approximately 200,000 self-signed RSA certificates, 6% (~12,000) had duplicated RSA moduli.
RNG failures from poor RNG selection or poor entropy sourcing have a long and storied history across hardware and software vendors, including Cisco’s ASAs (RWC 2019). The presenters immediately narrowed in on 2019’s disclosure as a likely source, indicating that the previous disclosure and fix were insufficient and potentially deployed without meaningful testing.
Correct construction and use of cryptographically secure pseudo-random number generators (CSPRNGs) are subtle and difficult, with catastrophic failure modes. At the same time, CSPRNG construction and use are well-trodden problems: the sharp edges in the NIST SP-800 90A DRBGs are well understood and documented, and strong seeding has always been a requirement regardless of underlying CSPRNG construction. Much like the talk about bypassing Wi-Fi encryption, the failures here are fundamentally at the design and software development lifecycle layers rather than low-level cryptographic flaws. The takeaway is to maintain a strong test suite covering both the happy and sad code paths and incorporate the best practices regarding the software development lifecycle to prevent reintroducing old bugs or code issues.
It takes a village
Real World Crypto 2023 taught us that old and new cryptographic techniques and protocols benefit most when a diverse set of researchers and analyses are involved. Even after passing several rounds of scrutiny, implementations should be monitored regularly. Whether transferring data, setting up RNGs, or applying PQC, misinterpretations and errors can compromise data integrity and privacy. We are grateful to all the researchers that presented at this year’s RWC conference, who have dedicated so much effort toward securing the world we live in, and we are proud to be active members of this community.