As part of our effort to deploy quantum resistant cryptography, we are happy to announce the release of the first quantum resilient FIDO2 security key implementation as part of OpenSK, our open source security key firmware. This open-source hardware optimized implementation uses a novel ECC/Dilithium hybrid signature schema that benefits from the security of ECC against standard attacks and Dilithium’s resilience against quantum attacks. This schema was co-developed in partnership with the ETH Zürich and won the ACNS secure cryptographic implementation workshop best paper.

Quantum processor

As progress toward practical quantum computers is accelerating, preparing for their advent is becoming a more pressing issue as time passes. In particular, standard public key cryptography which was designed to protect against traditional computers, will not be able to withstand quantum attacks. Fortunately, with the recent standardization of public key quantum resilient cryptography including the Dilithium algorithm, we now have a clear path to secure security keys against quantum attacks.

While quantum attacks are still in the distant future, deploying cryptography at Internet scale is a massive undertaking which is why doing it as early as possible is vital. In particular, for security keys this process is expected to be gradual as users will have to acquire new ones once FIDO has standardized post quantum cryptography resilient cryptography and this new standard is supported by major browser vendors.

Hybrid signature: Strong nesting with classical and PQC scheme

Our proposed implementation relies on a hybrid approach that combines the battle tested ECDSA signature algorithm and the recently standardized quantum resistant signature algorithm, Dilithium. In collaboration with ETH, we developed this novel hybrid signature schema that offers the best of both worlds. Relying on a hybrid signature is critical as the security of Dilithium and other recently standardized quantum resistant algorithms haven’t yet stood the test of time and recent attacks on Rainbow (another quantum resilient algorithm) demonstrate the need for caution. This cautiousness is particularly warranted for security keys as most can’t be upgraded – although we are working toward it for OpenSK. The hybrid approach is also used in other post-quantum efforts like Chrome’s support for TLS.

On the technical side, a large challenge was to create a Dilithium implementation small enough to run on security keys’ constrained hardware. Through careful optimization, we were able to develop a Rust memory optimized implementation that only required 20 KB of memory, which was sufficiently small enough. We also spent time ensuring that our implementation signature speed was well within the expected security keys specification. That said, we believe improving signature speed further by leveraging hardware acceleration would allow for keys to be more responsive.

Moving forward, we are hoping  to see this implementation (or a variant of it), being standardized as part of the FIDO2 key specification and supported by major web browsers so that users’ credentials can be protected against quantum attacks. If you are interested in testing this algorithm or contributing to security key research, head to our open source implementation OpenSK.

Finding and mitigating security vulnerabilities is critical to keeping Internet users safe.  However, the more complex a system becomes, the harder it is to secure—and that is also the case with computing hardware and processors, which have developed highly advanced capabilities over the years. This post will detail this trend by exploring Downfall and Zenbleed, two new security vulnerabilities (one of which was disclosed today) that prior to mitigation had the potential to affect billions of personal and cloud computers, signifying the importance of vulnerability research and cross-industry collaboration. Had these vulnerabilities not been discovered by Google researchers, and instead by adversaries, they would have enabled attackers to compromise Internet users. For both vulnerabilities, Google worked closely with our partners in the industry to develop fixes, deploy mitigations and gather details to share widely and better secure the ecosystem.

What are Downfall and Zenbleed?

Downfall (CVE-2022-40982) and Zenbleed (CVE-2023-20593) are two different vulnerabilities affecting CPUs – Intel Core (6th – 11th generation) and AMD Zen2, respectively. They allow an attacker to violate the software-hardware boundary established in modern processors. This could allow an attacker to access data in internal hardware registers that hold information belonging to other users of the system (both across different virtual machines and different processes). 

These vulnerabilities arise from complex optimizations in modern CPUs that speed up applications: 

1. Preemptive multitasking and simultaneous multithreading enable users and applications to share CPU cores, while the CPU enforces security boundaries at the architecture level to stop a malicious user accessing data from other users. 

2. Speculative execution allows the CPU core to execute instructions from a single execution thread without waiting for prior instructions to be completed.

3. SIMD enables data-level parallelism where an instruction computes the same function multiple times with different data.

Downfall, affecting Intel CPUs, exploits the speculative forwarding of data from the SIMD Gather instruction. The Gather instruction helps the software access scattered data in memory quickly, which is crucial for high-performance computing workloads performing data encoding and processing. Downfall shows that this instruction forwards stale data from the internal physical hardware registers to succeeding instructions. Although this data is not directly exposed to software registers, it can trivially be extracted via similar exploitation techniques as Meltdown. Since these physical hardware register files are shared across multiple users sharing the same CPU core, an attacker can ultimately extract data from other users. 

Zenbleed, affecting AMD CPUs, shows that incorrectly implemented speculative execution of the SIMD Zeroupper instruction leaks stale data from physical hardware registers to software registers. Zeroupper instructions should clear the data in the upper-half of SIMD registers (e.g., 256-bit register YMM) which on Zen2 processors is done by just setting a flag that marks the upper half of the register as zero. However, if on the same cycle as a register to register move the Zeroupper instruction is mis-speculated, the zero flag doesn’t get rolled back properly, leading to the upper-half of the YMM register to hold stale data rather than the value of zero. Similar to Downfall, leaking stale data from physical hardware registers expose the data from other users who share the same CPU core and its internal physical registers. 

Comparison

How did we protect our users?

Vulnerability research continues to be at the heart of our security work at Google. We invest in not only vulnerability research, but in the community as a whole in order to encourage further research that keeps all users safe. These vulnerabilities were no exception, and we worked closely with our industry partners to make them aware of the vulnerabilities, coordinate on mitigations, align on disclosure timelines and a plan to get details out to the ecosystem. 

Upon disclosures, we immediately published Security Bulletins for both Downfall and Zenbleed that detailed how Google responded to each vulnerability, and provided guidance for the industry. In addition to our bulletins, we posted technical details for insights on both Downfall and Zenbleed. It’s imperative that vulnerability research continues to be supported by the industry, and we’re dedicated to doing our part to helping protect those that do this important work.

Lessons learned 

These long existing vulnerabilities, their discovery and the mitigations that followed have provided several lessons learned that will help the industry move forward in vulnerability research, including: 

• There are fundamental challenges in designing secure hardware that requires further research and understanding.

• There are gaps in automated testing and verification of hardware for vulnerabilities. 

• Optimization features that are supposed to make computation faster are closely related to security and can introduce new vulnerabilities, if not implemented properly.

As Downfall and Zenbleed, suggest, computer hardware is only becoming more complex everyday, and so we will see more vulnerabilities, which is why Google is investing in CPU/hardware security research. We look forward to continuing to share our insights and encourage the wider industry to join us in helping to expand on this work. 

Want to learn more?

Downfall will be presented at Blackhat USA 2023 on August 9 at 1:30pm. You can also read more about Zenbleed on this advisory.

Pixel Binary Transparency

With Android powering billions of devices, we’ve long put security first. There’s the more visible security features you might interact with regularly, like spam and phishing protection, as well as less obvious integrated security features, like daily scans for malware. For example, Android Verified Boot strives to ensure all executed code comes from a trusted source, rather than from an attacker or corruption. And with attacks on software and mobile devices constantly evolving, we’re continually strengthening these features and adding transparency into how Google protects users. This blog post peeks under the hood of Pixel Binary Transparency, a recent addition to Pixel security that puts you in control of checking if your Pixel is running a trusted installation of its operating system. 

Supply Chain Attacks & Binary Transparency

Pixel Binary Transparency responds to a new wave of attacks targeting the software supply chain—that is, attacks on software while in transit to users. These attacks are on the rise in recent years, likely in part because of the enormous impact they can have. In recent years, tens of thousands of software users from Fortune 500 companies to branches of the US government have been affected by supply chain attacks that targeted the systems that create software to install a backdoor into the code, allowing attackers to access and steal customer data. 

One way Google protects against these types of attacks is by auditing Pixel phone  firmware (also called “factory images”) before release, during which the software is thoroughly checked for backdoors. Upon boot, Android Verified Boot runs a check on your device to be sure that it’s still running the audited code that was officially released by Google. Pixel Binary Transparency now expands on that function, allowing you to personally confirm that the image running on your device is the official factory image—meaning that attackers haven’t inserted themselves somewhere in the source code, build process, or release aspects of the software supply chain. Additionally, this means that even if a signing key were compromised, binary transparency would flag the unofficially signed images, deterring attackers by making their compromises more detectable.

How it works

Pixel Binary Transparency is a public, cryptographic log that records metadata about official factory images. With this log, Pixel users can mathematically prove that their Pixels are running factory images that match what Google released and haven’t been tampered with.

The Pixel Binary Transparency log is cryptographically guaranteed to be append-only, which means entries can be added to the log, but never changed or deleted. Being append-only provides resilience against attacks on Pixel images as attackers know that it’s more difficult to insert malicious code without being caught, since an image that’s been altered will no longer match the metadata Google added to the log. There’s no way to change the information in the log to match the tampered version of the software without detection (Ideally the metadata represents the entirety of the software, but it cannot attest to integrity of the build and release processes.)

For those who want to understand more about how this works, the Pixel Binary Transparency log is append-only thanks to a data structure called a Merkle tree, which is also used in blockchain, Git, Bittorrent, and certain NoSQL databases. The append-only property is derived from the single root hash of the Merkle tree—the top level cryptographic value in the tree. The root hash is computed by hashing each leaf node containing data (for example, metadata that confirms the security of your Pixel’s software), and recursively hashing intermediate nodes. 

The root hash of a Merkle tree should not change, if and only if, the leaf nodes do not change. By keeping track of the most recent root hash, you also keep track of all the previous leaves. You can read more about the details in the Pixel Binary Transparency documentation. 

Merkle Trees Proofs

There are two important computations that can be performed on a Merkle tree: the consistency proof and inclusion proof. These two proofs together allow you to check whether an entry is included in a transparency log and to trust that the log has not been tampered with.

Before you trust the contents of the log, you should use the consistency proof to check the integrity of the append-only property of the tree. The consistency proof is a set of hashes that show when the tree grows, the root hash only changes from the addition of new entries and not because previous entries were modified.

Once you have established that the tree has not been tampered with, you can use the inclusion proof to check whether a particular entry is in the tree. In the case of Pixel Binary Transparency, you can check that a certain version of firmware is published in the log (and thus, an official image released by Google) before trusting it.

You can learn more about Merkle trees on Google’s transparency.dev site, which goes deeper into the same concepts in the context of our Trillian transparency log implementation. 

Try It Out

Most Pixel owners won’t ever need to perform the consistency and inclusion proofs to check their Pixel’s image—Android Verified Boot already has multiple safeguards in place, including verifying the hash of the code and data contents and checking the validity of the cryptographic signature. However, we’ve made the process available to anyone who wants to check themselves—the Pixel Binary Transparency Log Technical Detail Page will walk you through extracting the metadata from your phone and then running the inclusion and consistency proofs to compare against the log.

More Security to Come

The first iteration of Pixel Binary Transparency lays the groundwork for more security checks. For example, building on Pixel Binary Transparency, it will be possible to make even more security data transparent for users, allowing proactive assurance for a device’s other executed code beyond its factory image. We look forward to building further on Pixel Binary Transparency and continually increasing resilience against software supply chain attacks.