Certificate Transparency : comment traiter une liste de 18 milliards de certificats ?

Certificate Transparency : traiter une liste de 18 milliards de certificats
Lucas
mai 03, 2022

Nous avons vu dans un précédent article ce qu’est Certificate Transparency, une base de données publique qui contient plus de 18 milliards de certificats TLS.

Nous allons maintenant voir tous les problèmes qui ont été rencontrés lors de l’écriture d’un programme capable de construire une base de données de noms de domaines valides ou qui l’ont été, à partir d’une quantité de données aussi importante.

Cyberwatch construit une liste de sous-domaines pour un nom de domaine donné, à partir de Certificate Transparency

Notre objectif est, à partir de Certificate Transparency, de pouvoir identifier l’ensemble des sous-domaines associés à un nom de domaine.

Nous allons pour cela traiter l’ensemble des données de Certificate Transparency, et stocker :

  • le nom de domaine ;
  • l’éventuel sous-domaine identifié ;
  • la première date d’apparition du sous-domaine ;
  • la dernière date de validité d’un certificat pour le sous-domaine.

Notons que ces deux derniers champs ne sont stockées qu’à des fins d’analyses statistiques complémentaires.

La quantité de certificats stockée dans Certificate Transparency nécessite des méthodes spécifiques

Les données issues de nos travaux seront stockées dans une base de données PostgreSQL, dont le format est :

ColumnTypeCollationNullableDefault
basecharacter varying(255)
subdomaincharacter varying(255)
first_seenbigint
last_seenbigint
Schéma de la base de données utilisée pour le stockage des résultats de Certificate Transparency

Estimons rapidement l’espace disque nécessaire au stockage de la base de données. Pour une première estimation minimale, supposons que chaque certificat ne contient qu’un seul nom de domaine, et qu’en moyenne ce nom de domaine fasse 20 caractères.

Chaque ligne de notre table est alors composée de deux champs `bigint` d’une taille de 8 octets chacun, et de 20 octets en moyenne pour le nom de domaine, mais aussi du PageHeaderData de 24 octets pour chaque ligne.

Pour une base de 18 milliards d’entrées, l’espace requis est alors de :

18e9 lignes * (8+8+20+24) octets = 1.08 To

Soit plus de 1 téraoctet !

De plus, pour accélérer les requêtes de recherches sur le champ base, qui est lié au nom de domaine principal, nous aurons besoin d’ajouter un index.

D’après des tests réalisés sur une partie seulement des données, la taille nécessaire pour stocker l’index représente environ 25% de la taille de la base de données. Une telle taille n’est pas acceptable dans notre cas d’utilisation. Heureusement, il y a plusieurs pistes pour optimiser les données. 

Certificate Transparency contient des informations redondantes liées aux renouvellements des certificats et qui permettent d’optimiser le traitement des données

Identification des contraintes de performances

Parmi les 18 milliards d’entrées de Certificate Transparency, beaucoup de données sont redondantes. En effet, chaque certificat a une date d’expiration, et doit ensuite être à nouveau généré. Chaque renouvellement produit ainsi une entrée de plus, avec des informations identiques. Ceci est particulièrement vrai pour les certificats émis par Let’s Encrypt, qui ne sont valables que 3 mois.

Pour réduire la taille en espace disque, notre première approche a été de modifier la table pour rendre le couple subdomain / base unique.

Cette optimisation a une conséquence importante sur nos performances lors de l’écriture d’une entrée dans la base de données. En effet, à chaque insertion d’une ligne, le moteur de base de données doit vérifier la contrainte d’unicité sur la clé et maintenir l’index à jour.

Quand la table contient quelques centaines de lignes, il n’y a pas d’impact sur les performances. En revanche, lorsque la base commence à faire plusieurs giga-octets, chaque insertion prend presque une seconde.

Ceci n’est pas acceptable car :

  • Il faudrait alors plusieurs années pour traiter l’ensemble des données une première fois ;
  • L’insertion de nouveaux certificats serait plus lente que le rythme de création et d’ajout des nouvelles données dans Certificate Transparency.

Un changement de stratégie s’impose. Nous souhaitons à la fois garder l’unicité d’un sous-domaine pour économiser de l’espace disque, et permettre d’ajouter rapidement en base de données les nouvelles entrées.

Découpler les mécanismes d’insertion et de déduplication permet d’atteindre un temps de traitement raisonnable

La solution vient du fait qu’il n’est pas nécessaire d’avoir une unicité stricte. Au lieu de réaliser la vérification de l’unicité lors de l’ajout dans la base de données, opération qui nécessite de comparer la nouvelle entrée avec toutes les entrées déjà présentes dans la base, les ajouts sont réalisés sans vérifier la contrainte d’unicité. Ensuite, de manière régulière, les données sont dédupliquées. 

Pour ajouter les données, il est alors possible de réaliser les insertions de manière groupée. Ceci améliore grandement les performances de l’ajout des domaines en base.

L’ajout en base de données est réalisé depuis le programme python grâce à la fonction execute_values de la librairie psycopg2

def save_domains(db_conn, domains):
    """Save a list of domains to the database."""
    db_cur = db_conn.cursor()
    execute_values(
        db_cur,
        "INSERT INTO domains (domain, first_seen, last_seen, etld) VALUES %s;",
        domains
    )
    db_conn.commit()

Cette fonction permet d’ajouter jusqu’à 10 000 lignes par requête SQL. La limite est arbitraire et correspond à notre cas d’usage : nous ne voulons pas stocker trop de tuple python en mémoire avant de les ajouter dans la base de données.

Déduplication périodique des indexation des données

Les domaines extraits des certificats sont donc ajoutés dans une table qui ne dispose d’aucune contrainte d’unicité, et qui n’est pas indexée.

Pour économiser l’espace disque, il faute maintenant dédupliquer les données, et pour que les requêtes SQL soient rapides, il faut que la table soit indexée.

Il faut donc utiliser plusieurs tables. 

Voici comment nous procédons : à une fréquence choisie, le moteur de parcours des données de Certificate Transparency est stoppé pour réaliser la déduplication.

Pour dédupliquer les données, nous créons une nouvelle table à partir d’une requête SQL. Il y a un peu de logique à maintenir pour garder les champs `first_seen` et `last_seen` cohérents. Lors de la déduplication, nous gardons les extrema identifiés. 

CREATE TABLE uniques_domains AS (
  SELECT 
    subdomain,
    MIN(first_seen) as first_seen,
    MAX(last_seen) as last_seen,
    base
  FROM domains GROUP BY subdomain, base
);

Nous ne souhaitons pas garder les données dupliquées, donc nous écrasons la table existante et la remplaçons par cette nouvelle table. 

DROP TABLE IF EXISTS domains;
ALTER TABLE uniques_domains RENAME TO domains;

Nous avons maintenant une table contenant des données uniques qui ne va plus être altérée avant la prochaine déduplication autrement que par l’ajout de nouvelles données.

Nous pouvons alors relancer le moteur de parcours des données de Certificate Transparency. 

Nous ne pouvons pas en même temps indexer les données directement sur la table domains fraichement dédupliquée, parce que l’ajout des données en serait ralenti. La table est donc copiée vers une nouvelle table. 

CREATE TABLE indexable_domains AS (SELECT * FROM domains); 

Cette nouvelle table est ensuite indexée : 

CREATE INDEX IF NOT EXISTS base_idx ON indexable_domains (base);

La table est ensuite exploitable pour identifier les sous-domaines liées à un domaine précis.

Une optimisation de traitement qui permet d’économiser plusieurs centaines de Go

L’ordre de grandeur du fichier final est de 150 Go, contre 1 To au début.

Cette approche permet ainsi d’avoir un moteur fiable et stable, mais aussi performant pour répondre aux nombreuses requêtes des utilisateurs.

Utilisez notre moteur de découverte pour identifier vos sous-domaines avec Cyberwatch Vulnerability Manager

Le module Cyberwatch Vulnerability Manager de notre plateforme vous permet de lancer un scan de découverte sur un nom de domaine, afin d’identifier les sous-domaines associés.

Cette approche repose sur des énumérations par force brute, et sur Certificate Transparency.

Demandez vite une démonstration de nos produits via le formulaire dédié !

Extrait du module de découverte d’actifs
Exemple de résultats obtenus

Vous avez des questions ?

Vous souhaitez une démonstration ?

Contactez-nous et nos experts reviendront vers vous sous 24h.

Votre demande