Project Paranoid

Overview

Paranoid project checks for well known weaknesses on cryptographic artifacts such as public keys, digital signatures and general pseudorandom numbers. This library contains implementations and optimizations of existing work found in the literature. The existing work showed that the generation of these artifacts was flawed in some cases. The following are some 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;

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

• 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;

• Joachim Breitner and Nadia Heninger. (2019). Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies;

Goal

The goal is to increase the confidence in cryptography use cases inside and outside Google.

When dealing with asymmetric encryption, crypto artifacts usually are:

1. Generated by one of our own tools (e.g., at Google we use for example boringssl or tink); or,
2. Generated by third party tools that we have access to (so these tools can be, for example, checked for vulnerabilities using wycheproof); or,
3. Generated by third party tools and/or hardware or software black boxes that we do not have access to.

With Paranoid, any cryptographic artifact can be tested, but its primary motivation is to detect the usage of weak third party hardware or software black boxes. Hence, Paranoid can be used even if we are not able to inspect the source code (situation 3. listed above).

The project aims to detect known vulnerabilities as well as unknown ones. E.g., it tries to identify vulnerabilities caused by programming errors or the use of weak proprietary random number generators. Detecting new vulnerabilities is of course much more difficult than detecting known ones. Such detections may require large sets of artifacts or find weak ones only with a low probability.

Therefore, we are very interested to receive feedback and learn about the cryptographic library that generated weak cryptographic artifacts (See call for contributions ). The project is constantly work in progress. After learning about weak implementations the plan is to analyze and add detections targeting them.

Getting Started

Documentation for the current implemented checks is located at docs. The documentation will be populated with more content over time.

To learn how to use the checks, you can look at the examples folder or the unit tests (*test.py files). The examples demonstrate testing different crypto artifacts.

Installation

Clone the repository:

$ git clone https://github.com/google/paranoid_crypto.git && cd paranoid_crypto

NOTE: The commands below have been tested on Debian stable version (bookworm). Make sure you will be using python3.11 or newer.

Install dependencies:

$ sudo apt update && sudo apt install python3 python3-full python3-pip python3-pybind11 python3-fpylll python3-gmpy2 protobuf-compiler

Create and activate a virtual environment:

$ python3 -m venv --system-site-packages ~/paranoid-venv

$ source ~/paranoid-venv/bin/activate

NOTE: If you know what you are doing, you can instead skip to the next step and use --break-system-packages switch for pip.

Install paranoid_crypto python package:

$ python3 -m pip install .

To check whether the installation was successful, you can run the unit tests. For example:

``` $ cd paranoid_crypto && python3 -m unittest discover -b -p "*test.py"

.................................................................................................................................................................................................................................................................................................................

Ran 305 tests in 314.660s

OK ```

Docker

Alternatively, if you want to run it in a container, you can use our provided Dockerfile as shown below.

NOTE: Make sure you have docker installed.

After cloning the repository, build the docker image:

$ docker build -t paranoid-img .

Create and start the container:

$ docker run --name paranoid-container -it paranoid-img paranoid-user@6191368b26b8:~$

To check whether the installation was successful, you can run the unit tests. For example:

``` paranoid-user@6191368b26b8:~$ cd paranoid_crypto && python3 -m unittest discover -b -p "*test.py"

.................................................................................................................................................................................................................................................................................................................

Ran 305 tests in 307.555s

OK ```

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 as of September 2022. For the Paranoid 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:

| TestName | Potentially Related CVEs | Severity | Number of Weak Artifacts | |:------------------------:|:----------------------------:|:-----------------:|:----------------------------:| | CheckOpensslDenylist | CVE-2008-0166 | SEVERITYCRITICAL | 3989 | | CheckROCA | CVE-2017-15361 | SEVERITYHIGH | 2875 | | CheckGCD | - | SEVERITYCRITICAL | 1860 | | CheckFermat | CVE-2022-26320 | SEVERITYCRITICAL | 36 | | CheckContinuedFractions | - | SEVERITYCRITICAL | 16 | | CheckBitPatterns | - | SEVERITYCRITICAL | 6 | | CheckPermutedBitPatterns | - | SEVERITYCRITICAL | 6 | | CheckKeypairDenylist | CVE-2021-41117 | SEVERITYCRITICAL | 4 | | CheckPollardpm1 | - | SEVERITY_CRITICAL | 1 |

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 Certificate Authorities to be revoked.

ABOUT

This library is developed and maintained by members of Google Security Team, but this is not an officially supported Google product. If you want to contribute, please read CONTRIBUTING and send us pull requests. You can also report bugs or file feature requests.

If you use Paranoid in your research, you can cite it using the following BibTeX: @software{Barbosa_Bleichenbacher_Paranoid_Crypto_2022, author = {Barbosa, Pedro and Bleichenbacher, Daniel}, license = {Apache-2.0}, month = {8}, title = {{Paranoid Crypto}}, url = {https://github.com/google/paranoid_crypto}, year = {2022} }