roca.c

/* roca.c - ROCA (CVE-2017-15361) fingerprint checker.
 * Written by Rob Stradling (based on https://github.com/crocs-muni/roca/blob/master/roca/detect.py)
 * Copyright (C) 2017-2018 Sectigo Limited
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <stdio.h>
#include <string.h>

#include "openssl/bn.h"
#include "openssl/evp.h"
#include "openssl/x509.h"

#if OPENSSL_VERSION_NUMBER < 0x10100000L	/* < 1.1.0 */
	#define EVP_PKEY_get0_RSA(evp_pkey)	((evp_pkey)->pkey.rsa)
	static void RSA_get0_key(
		const RSA* r,
		const BIGNUM** n,
		const BIGNUM** e,
		const BIGNUM** d
	)
	{
		if (n != NULL)
			*n = r->n;
		if (e != NULL)
			*e = r->e;
		if (d != NULL)
			*d = r->d;
	}
#endif

#define ROCA_PRINTS_LENGTH	17
static unsigned char g_primes[ROCA_PRINTS_LENGTH] = {
	11, 13, 17, 19, 37, 53, 61, 71, 73, 79, 97, 103, 107, 109, 127, 151, 157
};
BIGNUM* g_prints[ROCA_PRINTS_LENGTH];
BIGNUM* g_one = NULL;


void rocacheck_init()
{
	memset(g_prints, '\0', sizeof(BIGNUM*) * ROCA_PRINTS_LENGTH);
	BN_dec2bn(&g_prints[0], "1026");
	BN_dec2bn(&g_prints[1], "5658");
	BN_dec2bn(&g_prints[2], "107286");
	BN_dec2bn(&g_prints[3], "199410");
	BN_dec2bn(&g_prints[4], "67109890");
	BN_dec2bn(&g_prints[5], "5310023542746834");
	BN_dec2bn(&g_prints[6], "1455791217086302986");
	BN_dec2bn(&g_prints[7], "20052041432995567486");
	BN_dec2bn(&g_prints[8], "6041388139249378920330");
	BN_dec2bn(&g_prints[9], "207530445072488465666");
	BN_dec2bn(&g_prints[10], "79228162521181866724264247298");
	BN_dec2bn(&g_prints[11], "1760368345969468176824550810518");
	BN_dec2bn(&g_prints[12], "50079290986288516948354744811034");
	BN_dec2bn(&g_prints[13], "473022961816146413042658758988474");
	BN_dec2bn(&g_prints[14], "144390480366845522447407333004847678774");
	BN_dec2bn(&g_prints[15], "1800793591454480341970779146165214289059119882");
	BN_dec2bn(&g_prints[16], "126304807362733370595828809000324029340048915994");

	BN_dec2bn(&g_one, "1");
}


void rocacheck_cleanup()
{
	int i;

	BN_free(g_one);
	for (i = 0; i < ROCA_PRINTS_LENGTH; i++)
		BN_free(g_prints[i]);
}


int BN_bitand_is_zero(
	const BIGNUM* a,
	const BIGNUM* b
)
{
	int i;

	for (i = 0; i < BN_num_bits(a); i++)
		if (BN_is_bit_set(a, i) && BN_is_bit_set(b, i))
			return 0;

	return 1;
}


int main() {
	X509* t_x509 = NULL;
	EVP_PKEY* t_publicKey = NULL;
	const BIGNUM* t_modulus = NULL;
	BN_CTX* t_ctx = NULL;
	BIGNUM* t_prime = NULL;
	BIGNUM* t_temp = NULL;
	BIGNUM* t_result = NULL;
	int i;
	int ret = 0;

	rocacheck_init();

	t_x509 = d2i_X509_fp(stdin, NULL);
	if (!t_x509) {
		fprintf(stderr, "Failed to parse DER certificate\n");
		goto label_exit;
	}

	t_publicKey = X509_get_pubkey(t_x509);
	if ((!t_publicKey) || !((EVP_PKEY_id(t_publicKey) == EVP_PKEY_RSA)
				|| (EVP_PKEY_id(t_publicKey) == EVP_PKEY_RSA2))) {
		fprintf(stderr, "Certificate's public key algorithm is not RSA\n");
		goto label_exit;
	}

	RSA_get0_key(EVP_PKEY_get0_RSA(t_publicKey), &t_modulus, NULL, NULL);
	if (!t_modulus) {
		fprintf(stderr, "Failed to extract RSA modulus\n");
		goto label_exit;
	}

	t_ctx = BN_CTX_new();
	t_prime = BN_new();
	t_temp = BN_new();
	t_result = BN_new();
	for (i = 0; i < ROCA_PRINTS_LENGTH; i++) {
		BN_set_word(t_prime, g_primes[i]);
		if (!BN_mod(t_temp, t_modulus, t_prime, t_ctx)) {
			fprintf(stderr, "BN_mod failed\n");
			goto label_exit;
		}
		if (!BN_lshift(t_temp, g_one, BN_get_word(t_temp))) {
			fprintf(stderr, "BN_lshift failed\n");
			goto label_exit;
		}
		if (BN_bitand_is_zero(t_temp, g_prints[i])) {
			fprintf(stderr, "No fingerprint found\n");
			goto label_exit;
		}
	}

	printf("Fingerprint found!\n");

label_exit:
	if (t_result)
		BN_free(t_result);
	if (t_temp)
		BN_free(t_temp);
	if (t_prime)
		BN_free(t_prime);
	if (t_ctx)
		BN_CTX_free(t_ctx);
	if (t_publicKey)
		EVP_PKEY_free(t_publicKey);
	if (t_x509)
		X509_free(t_x509);

	rocacheck_cleanup();

	return ret;
}

The only primes that matter are 11,13,17,19,37,53,61,71,73,79,97,103,107,109,127,151,157 (and the corresponding masks). All other entries are of the form (1<<prime) - 2, which is useless and just a waste of cycles.

Addendum: here's a simpler deobfuscated version, which explicitly precalculates the match lists from the underlying relations, and without the red herring entries: https://gist.github.com/marcan/fc87aa78085c2b6f979aefc73fdc381f

Thanks @marcan! I've removed the red herring entries from this gist.