Posted by Pedro Barbosa, Security Engineer, and Daniel Bleichenbacher, Software Engineer

Paranoid is a project to detect well-known weaknesses in large amounts of crypto artifacts, like public keys and digital signatures. On August 3rd 2022 we open sourced the library containing the checks that we implemented so far (https://github.com/google/paranoid_crypto). The library is developed and maintained by members of the Google Security Team, but it is not an officially supported Google product.

Why the Project?

Crypto artifacts may be generated by systems with implementations unknown to us; we refer to them as “black boxes.” An artifact may be generated by a black-box if, for example, it was not generated by one of our own tools (such as Tink), or by a library that we can inspect and test using Wycheproof. Unfortunately, sometimes we end up relying on black-box generated artifacts (e.g. generated by proprietary HSMs).

After the disclosure of the ROCA vulnerability, we wondered what other weaknesses may exist in crypto artifacts generated by black boxes, and what we could do to detect and mitigate them. We then started working on this project in 2019 and created a library to perform checks against large amounts of crypto artifacts.

The library contains implementations and optimizations of existing work found in the literature. The literature shows that the generation of artifacts is flawed in some cases - below are examples of publications the library is based on.

• Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung, and Christophe Wachter. (2012). Ron was wrong, Whit is right. Cryptology ePrint Archive, Paper 2012/064;

• Nadia Heninger, Zakir Durumeric, Eric Wustrow, and J. Alex Halderman. (2012). Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices. USENIX Associations;

• Daniel J. Bernstein, Yun-An Chang, Chen-Mou Cheng, Li-Ping Chou, Nadia Heninger, Tanja Lange, and Nicko van Someren. (2013). Factoring RSA keys from certified smart cards: Coppersmith in the wild. Cryptology ePrint Archive, Paper 2013/599;

• Joachim Breitner and Nadia Heninger. (2019). Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies. Cryptology ePrint Archive, Paper 2019/023.

As a recent example, CVE-2022-26320 found by Hanno Böck, confirmed the importance of checking for known weaknesses. Paranoid has already found similar weak keys independently (via the CheckFermat test). We also believe the project has potential to detect new vulnerabilities since we typically attempt to generalize detections as much as we can.

Call for Contributions

The goal of open sourcing the library is to increase transparency, allow other ecosystems to use it (such as Certificate Authorities - CAs that need to run similar checks to meet compliance), and receive contributions from external researchers. By doing so, we’re making a call for contributions, in hopes that after researchers find and report crypto vulnerabilities, the checks are added into the library. This way, Google and the rest of the world can respond quickly to new threats.

Note, the project is intended to be light in its use of computational resources. The checks must be fast enough to run against large numbers of artifacts and must make sense in real world production context. Projects with less restrictions, such as RsaCtfTool, may be more appropriate for different use cases.

In addition to contributions of new checks, improvements to those that already exist are also welcome. By analyzing the released source one can see some problems that are still open. For example, for ECDSA signatures in which the secrets are generated using java.util.random, we have a precomputed model that is able to detect this vulnerability given two signatures over secp256r1 in most cases. However, for larger curves such as secp384r1, we have not been able to precompute a model with significant success.

In addition to ECDSA signatures, we also implemented checks for RSA and EC public keys, and general (pseudo) random bit streams. For the latter, we were able to build some improvements on the NIST SP 800-22 test suite and to include additional tests using lattice reduction techniques.

Preliminary results

Similar to other published works, we have been analyzing the crypto artifacts from Certificate Transparency (CT), which logs issued website certificates since 2013 with the goal of making them transparent and verifiable. Its database contains more than 7 billion certificates.

For the checks of EC public keys and ECDSA signatures, so far, we have not found any weak artifacts in CT. For the RSA public key checks with severities high or critical, we have the following results:

Some of these certificates were already expired or revoked. For the ones that were still active (most of the CheckGCD ones), we immediately reported them to the CAs to be revoked. Reporting weak certificates is important to keep the internet secure, as stated by the policies of the CAs. The Let's Encrypt policy, for example, is defined here. In another example, Digicert states:

Certificate revocation and certificate problem reporting are an important part of online trust. Certificate revocation is used to prevent the use of certificates with compromised private keys, reduce the threat of malicious websites, and address system-wide attacks and vulnerabilities. As a member of the online community, you play an important role in helping maintain online trust by requesting certificate revocations when needed.

What is next?

We plan to continue analyzing Certificate Transparency, and now with the help of external contributions, we will continue the implementation of new checks and optimization of those existing.

We are also closely watching the NIST Post-Quantum Cryptography Standardization Process for new algorithms that make sense to implement checks. New crypto implementations carry the possibility of new bugs, and it is important that Paranoid is able to detect them.