SSTIC 2017 – Indexation « full-bin » de fichiers binaires avec Binacle

Olivier Chatail Conférences

Le SSTIC

Le SSTIC (Symposium sur la sécurité des technologies de l’information et des communications)  est une conférence Française qui s’est déroulée du 7 au 9 juin 2017 dans la ville de Rennes pour sa 15e édition.

Des consultants de Devoteam y ont participé et ont souhaité partager des résumés sur les sujets suivants :

  • WSUS pendu – Romain Coltel & Yves Le Provost
  • Désobfuscation binaire : Reconstruction de fonctions virtualisées – Jonathan Salwan, Marie-Laure Potet & Sébastien Bardin
  • CrashOS : Recherche de vulnérabilités système dans les hyperviseurs – Anaïs Gantet
  • Binacle : indexation « full-bin » de fichiers binaires – Guillaume Jeanne

 

Indexation « full-bin » de fichiers binaires

Guillaume Jeanne, du Bureau Failles et Signatures de l’ANSSI est venu présenter une nouvelle approche pour l’indexation « full-bin » de fichiers binaires.
Le terme d’indexation « full-bin » fait référence à l’indexation « full-text » utilisée par de nombreuses technologies pour la recherche de chaîne de caractère en base de donnée.

Pour illustrer le concept, un exemple simplifié de déroulement pour l’indexation « full-text » par index inversé :

  • Association d’un identifiant (index) à chaque source d’information
  • Sélection des mots « importants » == exclusion des mots de liaison par exemple
  • Création d’une liste qui affecte à chaque mot « important » les index correspondant (les sources dans lesquelles ces mots se trouvent)

Les travaux présentés lors de cette conférence ont pour objectif de transférer ce concept à l’indexation de contenu binaire.
Les applications sont nombreuses pour ce type de recherche dans la réponse à incident :

  • Adresses IP, entrées DNS, éléments cryptographiques..
  • Réutilisation de fonctions (crypto & génération d’aléatoire) et binaires patchés
  • Blocs binaires similaires entre certains fichiers (variantes malware & identification de groupes d’attaquants)

 

Découpage par n-grammes

L’application de cette technique aux fichiers binaires ne se fait pas aisément étant donné qu’il n’y a pas de séparation naturelle entre les contenus binaires.
La solution théorique développée à ce problème de séparation est le découpage du contenu en blocs de n-grammes.
L’indexation se fait donc sur des blocs de taille fixe n octets et se décale (glisse) de m octets.

Illustration du concept de n-grammes par Guillaume Jeanne

 

Etat de l’art

L’état de l’art réalisé dans cette étude concerne l’adaptation de la théorie des n-grammes aux technologies suivantes :

  • Base de données relationnelle MySQL : problème de passage à l’échelle
  • Base de données LMDB transactionnelle : problème de passage à l’échelle
  • BigGrep : problèmes d’usage comme la nécessité de soumettre un grand nombre de fichier à la fois ou le manque de mise à jour des indexes

A l’issue de cet état de l’art Guillaume Jeanne a décidé d’implémenter sa solution en s’inspirant des filtres de Bloom.
Ces structures probabilistes permettent d’être certain qu’un élément est absent d’un ensemble mais possèdent un taux de faux positifs non négligeable.
Un de ses avantages est de pouvoir effectuer des tests d’appartenance en O(1).
Ces propriétés combinées permettent de s’en servir pour économiser des requêtes coûteuses en base de données : avant de requêter une très grosse base, la présence de l’objet souhaité est testée avec un filtre de Bloom.

 

L’outil Binacle

Implémenté en Rust, structure de type Hashtable mappée en mémoire (inspiré de LMDB).
La base est constituée d’un en-tête qui permet la correspondance entre chaque n-grammes et sa liste, dans le corps de la base.
Cette liste contient les identifiants des documents contenant le n-grammes (similitude avec l’index inversé).
Chaque liste a une taille fixe et quand celle ci est atteinte, une nouvelle liste (de taille doublée) est créée avec comme premier élément un pointeur vers la liste précédente.

La taille de n-grammes optimale après expérimentation est n=28 bits, ce qui correspond à un en-tête d’environ 1.34 Go et un taux de faux positifs considéré correct.
L’insertion en base d’un fichier se fait par le découpage en n-grammes de 28 bits donc, avec une fenêtre glissante d’un octet.
La recherche se fait par découpage en ensembles de n-grammes puis recherche et croisement des indexes remontés (ce qui induit une non-certitude sur les résultats).

Afin d’illustrer les avantages de cette implémentation, les performances de Yara ont été comparées aux performances de Binacle (pré-recherche) plus Yara (recherche).
Le résultat, sur des recherches « simples », montre un gain de performance allant jusqu’à plus de 2000%.

Présentation des résultats par Guillaume Jeanne

Cependant, le gain de performance apparaît comme variable et directement dépendant du set et de la recherche, ce qui mitige les résultats présentés.

Merci à Guillaume Jeanne pour cette présentation et la qualité de ses travaux.

Liens et références :