Like a Hot Knife Through Butter

More or less recently, an interesting line of attacks against software has been revisited, namely Hash-DoS, or, in a nutshell, exploiting weak hash functions used in a hash table implementation to trigger a denial-of-service.

To the best of my knowledge, this problematic has been exposed as early as in 1998 in Phrack by Solar Designer, then variants have been discussed by Crosby and Wallach at USENIX 2003, formally defining algorithmic complexity attacks, by Klink and Wälde during 28c3 in 2011, applying the idea on PHP, Python, Java, Ruby, etc. and more recently by Aumasson, Bernstein and Bosslet (see their slides at Appsec Forum 2012, and their upcoming talk at 29c3), showing that the proposed solutions, essentially randomizing the hash function, were not always as effective as expected.

Technically, this kind of attacks consists in generating a large number of colliding inputs for the hash table. Hence, instead of a having a O(1) average access time to a stored element, one can force the hash table to have a O(n) one. If one is willing to explore all the elements in the hash table, the worst-case complexity becomes O(n^2) instead of O(n). Be able to generate multi-collisions (i.e., multiple inputs, not just two, mapping to the same output), in practice hence depends on the properties of the hash function transforming elements to a key.

In this short post, I’d like to show how hash-DoS can be applied to the btrfs file-system with some astonishing and unexpected success. Btrfs, while still in development stage, is widely considered as being a viable successor of ext4, and an implementation of it is already part of the Linux kernel. According to this page,

Directories are indexed in two different ways. For filename lookup, there is an index comprised of keys:

Directory Objectid BTRFS_DIR_ITEM_KEY 64 bit filename hash

The default directory hash used is crc32c, although other hashes may be added later on. A flags field in the super block will indicate which hash is used for a given FS.

The second directory index is used by readdir to return data in inode number order. This more closely resembles the order of blocks on disk and generally provides better performance for reading data in bulk (backups, copies, etc). Also, it allows fast checking that a given inode is linked into a directory when verifying inode link counts. This index uses an additional set of keys:

Directory Objectid BTRFS_DIR_INDEX_KEY Inode Sequence number

The inode sequence number comes from the directory. It is increased each time a new file or directory is added.

Knowing how trivial it is to compute multi-collisions for a CRC-based hash, I did not resist to play a bit. Roughly speaking, computing a CRC of an n-bit message M consists in interpreting the message as a polynomial M(x) of degree n-1 over \mathrm{GF}(2), dividing it by the CRC defining polynomial P(x), and taking the remainder, hence writing something like \mathrm{CRC} = M(x) - Q(x)\cdot P(x). Obviously, adding any multiple of P(x) to the message M(x) will generate a collision. For the gory details, see this page.

I basically found two different attacks:

  • I computed the time to create 4000 empty files in the same directory whose names were randomly chosen. This takes about 0.2 seconds. The box used is a Fedora distribution within a VM (and btrfs was a loopback-ed device).

    Then, I computed the time to create those 4000 empty files in the same directory, whose names were however chosen in order to hash to the same CRC32C value. This operation fails after 5 (!) seconds and creating only 61 files. In other words, this first attack allows an adversary, in a shared directory scenario, to avoid that a victim creates a file with a known-in-advance name. According to the btrfs maintainer, Chris Mason, 

Collisions are a known issue with any of the hash based directories. […] The impact of the DOS is that a malicious user is able to prevent the creation of specific file names. For this to impact other users on the system, it must be done in directories where both the malicious user and the victim user have permission to create files. The obvious example is /tmp, but there are other cases that may be more site-specific. Group writable directories have other security issues, and so we picked the hash knowing this kind of DOS was possible. It is good practice to avoid the shared directories completely if you’re worried about users doing these kinds of attacks.

  • A bit annoyed by this answer, I tried harder and found the following: I have created several files with random names in a directory (around 500). The time required to remove them is negligible. Then, I have created the same number of files, but giving them only 55 different crc32c values. The time required to remove them is so large that I was not able to figure it out and killed the process after 220 minutes (!). The python script I used is the following, and borrows some code from StalkR:

    More exactly, I mounted a 1GB btrfs file system on a loopback device:

    In the exploit script, just put the variable  hack = False  to generate random empty filenames or  hack = True  to generate colliding filenames and hence trigger the phenomenon. Here is a screenshot of what I obtained:

Given the result, it looks like that playing with collisions is much more likely to trigger an infinite loop than just a complexity increase; at least, the btrfs code surely does not expect to handle many collisions.

Essentially, to thwart both attacks, I would recommend to use a modern lightweight hash algorithm, such as SipHash, instead of CRC32C. Another alternative is to avoid using data structures that have a high worst-case complexity, like hash tables, for storing data that can potentially be manipulated by malicious users. Sacrificing a bit of average-case performance, data structures like red-black trees have a guaranteed search time in O(\log(n)) (I learned this while reading the source code of nginx).

For the record, this vulnerability has been announced to the btrfs maintainer Chris Mason on November 14th, 2012, who acknowledged the bug, but then did not answer any of my e-mails. and mentioned that

 My plan is to get this fixed for the 3.8 merge window. We’re juggling a lot of patches right now but I expect to fix things then.

[UPDATE OF 17/12/2012] As several readers of this post have noticed, and I would like to warmly thank them for their feedback, the second attack does NOT generate an infinite loop within the btrfs code, but merely within the bash expansion code which is responsible to expand the command line rm *. This can be seen in the above screenshot, as the CPU is burnt in userland, and not in the kernel. Hence, what I thought to be a complexity attack against the btrfs file system is actually a (less glamorous) complexity attack against bash.

This said, after having communicated this unfortunate glitch to the btrfs maintainer Chris Mason, he kindly answered me the following:

You’ve found a real problem in btrfs though. Changes since I tested the crc overflow handling have made us not deal with our EOVERFLOW error handling completely right, and there are cases where we force the FS readonly when we shouldn’t. So this is a valid bug, I’m just waiting on some review of my fix, which will get backported to a number of kernels.

To summarize, the message I wanted to pass through this post remains still valid: if one uses a weak hash function, like it is the case in the btrfs file system, one should assume that malicious users can generate zillions of collisions, and one should write accordingly robust code able to handle those collisions in an efficient way.

Another possibility consists in using a lightweight cryptographic hash function that translates the search for multi-collision in a hard task. The security/performance tradeoff to find here is definitely a delicate and hard decision to take.

Finally, the first described attack, i.e., make impossible the creation of a given file within a shared directory, keeps still valid.

Workshop final du projet Obfuscator

J’ai le plaisir d’organiser le workshop de clôture du projet HES-SO/RCSO “Obfuscator”, mené conjointement par l’HEIG-VD et l’EIA-FR entre 2010 et 2012. Ce projet avait pour but d’explorer le domaine de l’obfuscation logicielle à des fins de protection contre le reverse-engineering et autres menaces. Les résultats de nos recherches seront présentés, et nous évoquerons quelques perspectives futures.

Le workshop aura lieu lundi 3 décembre 2012, dès 16h30, salle E03 à l’HEIG-VD, route de Cheseaux 1, à Yverdon-les-Bains.



  • 16h30-17h00: Mot de bienvenue, présentation du contexte
  • 17h00-17h45: Obfuscation logicielle avec LLVM
  • 17h45-18h00: Pause
  • 18h00-18h45: Protection de binaires ARM
  • 18h45-19h00: Perspectives et conclusion

Ce workshop sera suivi d’un apéro. Pour des questions de logistique, merci de bien vouloir confirmer votre présence d’ici le 28 novembre 2012 par e-mail et n’hésitez pas à faire circuler cette invitation !

Pascal Junod (HEIG-VD) et Jean-Roland Schuler (EIA-FR)


Vol de Données Confidentielles au SRC

Ces derniers temps, les vols de données informatiques confidentielles ont souvent fait les grands titres des médias helvétiques, principalement dans le contexte du vol de données bancaires. La semaine passée, c’est le Service de Renseignement de la Confédération qui a confessé qu’un de ses employés, apparemment un informaticien ayant des fonctions d’administrateur système, avait été arrêté juste avant qu’il ne soit en position de vendre au plus offrant des montagnes de données ayant trait au secret-défense helvétique.

Ironie du sort, c’est en voulant ouvrir un compte à numéro dans la filiale bernoise (!) d’une banque helvétique (!!) que l’employé malhonnête s’est fait remarquer, puis dénoncer aux services compétents. Les mécanismes de détection de cas de blanchiment d’argent de cette banque semblent donc avoir été efficaces, au moins dans ce cas-là.

Cela me donne l’opportunité de commenter certains aspects avec l’œil du spécialiste en sécurité informatique.

[caveat emptor]: je ne possède évidemment pas plus d’information sur cette affaire que ce qui a paru dans les médias ces derniers jours. J’ai également remarqué que les explications données dans la Sonntagszeitung de ce dimanche et dans le Matin Dimanche comportaient quelques différences. Je pars donc du principe que les informations publiques reflètent la réalité.

Source des Données et Contrôle d’Accès

La Sonntagszeitung mentionne que l’employé était responsable du système de stockage sur lesquels les analystes du SRC stockent leurs rapports et les informations annexes, en plus d’avoir accès à un réseau de partage d’information sécurisé avec d’autres services de renseignements étrangers:

Er war zuständig für die Datenspeicher, auf denen die Mitarbeiter Informationen zur Bedrohungslage der Schweiz und ihre Analysen speichern. […] Er hatte auch Zugriff auf das speziell gesicherte Netzwerk, über das ausländische Geheimdienste wie der deutsche BND oder die amerikanische CIA ihre Informationen senden.

Les informations mémorisées dans ce système de stockage ont clairement une valeur inestimable. Ce système de stockage n’a cependant pas été la cible de l’employé. Peut-être ne possédait-il pas tous les droits d’accès nécessaires, l’information étant chiffrée. Peut-être ce système de stockage était-il bien protégé et surveillé. On ne le sera probablement jamais. D’après la Sonntagszeitung, l’employé a plutôt copié le contenu du serveur de messagerie, plus d’autres données annexes devant lui permettre d’accéder aux informations sensibles chez lui:

In seinem Büro im dritten Stock des Nachrichtendienstes kopiert der Informatiker zunächst den gesamten Mailserver des NDB innerhalb des speziell gesicherten internen SILAN-Netzes. Damit gelangt er auch an Mails des militärischen Nachrichtendienstes (Mil ND) und der Führungs- und Unterstützungsbasis der Armee (FUB). […]

Mit den Mails gelangt er an unzählige Anhänge: vertrauliche Berichte an den Bundesrat, geheime Berichte ausländischer Polizei- und Nachrichtendienste über Terroristen, Waffenhändler und laufende nachrichtendienstliche Operationen. Das Mail-System ist gegen aussen abgeschottet, deshalb ist es nicht verschlüsselt. Im internen Mail-Verkehr spiegeln sich mehrere Jahre Schweizer Geheimdienstarbeit. Neben dem Mail-Server kopiert er auch das Verzeichnis seiner Abteilung und Zugangsinformationen und Passwörter – damit er das Material zu Hause überhaupt sichten kann.

Comme l’indique très bien l’article, le trésor se trouve dans les pièces attachées: comme dans toute organisation, les employés du SRC utilisent leur messagerie pour échanger sur leurs rapports, les discuter, les affiner, bref, travailler.

La phrase qui me plaît le plus est mise en évidence ci-dessus: la messagerie n’était pas chiffrée, étant donné qu’elle est isolée de l’extérieur. Le lien de cause à effet est donné par le journaliste, mais je devine qu’il ne doit pas être loin de la vérité. Cette constatation est à mettre en lumière avec le fait bien connu dans le monde de la sécurité informatique que deux tiers à trois quarts des attaques sont perpétrées par des insiders.

Dans le but de protéger un système IT, il est possible de mettre en œuvre un certain nombre de mesures techniques visant à se protéger contre les attaques internes, principalement envers les employés disposant de droits étendus sur les systèmes qu’ils administrent: chiffrement des données, que cela soit au niveau système de fichiers, des entrées d’une base de données ou de la messagerie, par exemple, ou encore partage de secret k-out-of-n, etc.

Cependant, il est également bien connu que ces mesures techniques ne peuvent pas résoudre tous les problèmes de sécurité, ceci étant d’autant plus vrai si l’on souhaite que les utilisateurs soient capables de travailler dans des conditions acceptables tout en respectant un budget raisonnable.

Monitoring et Mécanismes d’Alerte, ou: Quis custodiet ipsos custodes?

Une composante essentielle de toute stratégie de sécurité visant à se protéger contre des attaques internes est le monitoring et la remontée d’alertes. Partant du principe que la sécurité à 100% n’existe pas, on souhaitera au moins détecter le plus rapidement possible une intrusion ou une fuite de données, dans le but d’y mettre fin et d’en réduire les impacts le plus rapidement possible.

Une condition nécessaire pour qu’un système de surveillance fasse correctement son boulot est qu’il soit administré indépendamment, bref qu’une séparation des rôles soit implémentée. La Sonntagszeitung mentionne que l’employé connaissait la façon de ne pas réveiller ce système d’alerte, tandis que le Matin Dimanche nous apprend «qu’au moins un script [de surveillance ?] a été modifié».

Sécurité Physique

Une autre composante de la sécurité générale d’un système IT est sa sécurité physique. S’il est possible de voler physiquement des disques durs contenant des informations confidentielles simplement en entrant dans une salle de calcul, toutes les mesures mentionnées ci-dessous sont vouées à l’échec. Apparemment, cet employé avait la possibilité, peut-être même la permission d’entrer et de sortir avec des disques durs externes dans son sac à dos, ce qui suggère que les procédures en relation avec la sécurité physique de ces données confidentielles laissent pour le moins à désirer.

Gestion des Ressources Humaines

Finalement, on touche au nœud de l’affaire: cet employé était manifestement un employé «à problèmes»: absentéisme fréquent et prolongé, soupçon de mobbing par les collègues et son chef, etc.

Une certaine confiance dans ses employés est inévitable au fonctionnement de toute organisation, et cela a souvent été relevé par les (ex-)dirigeants du SRC. Néanmoins, une mauvaise gestion des ressources humaines peut facilement accélérer, voir encourager un employé aigri à commettre l’irréparable. A posteriori, cela semble révéler un dysfonctionnement majeur entre les personnes responsables de la gestion des ressources humaines et celles responsables de la sécurité des données.

En conclusion

L’enquête parlementaire livrera probablement ses conclusions d’ici quelques mois, et les responsabilités vis-à-vis de ce fiasco devront être définies. Je ne serais pas surpris que soient mentionnées les coupes budgétaires récurrentes et autres manques de moyens à disposition du SRC pour mener à bien sa mission, l’argent restant encore et toujours le nerf de la guerre.

Le côté positif de cette affaire est la (relative) transparence avec laquelle le SRC a communiqué sur cette triste affaire: cela aura au moins le mérite de sensibiliser encore un peu plus, s’il en était besoin, les entreprises et les administrations suisses quant à la problématique du vol de données en particulier, et de la sécurité informatique en général.