Algorithmes Data-Invariant

Un algorithme est Data-Invariant si son temps d'exécution est le même peu importe les valeurs auxquelles il s'applique. Ce concept est cousin de celui des algorithmes de complexité constante, ou $O(1)$, sans toutefois représenter exactement le même concept. Pour un attaquant d'un système sécurisé, constater le temps requis pour exécuter un calcul est une information précieuse, ce que les fonctions Data-Invariant cherchent à éviter. Utile pour les systèmes temps réel et pour des systèmes de sécurité.

Typiquement, un algorithme Data-Invariant est implémenté de manière à ce que le code machine correspondant ne contiennt aucun branchement, mais une implémentation où le nombre de de branchements est le même peu importe les données convient aussi.

Exemple : comparaison de chaînes de caractères

L'algorithme suivant est un exemple classique d'une fonction comparant deux chaînes de caractères et retourne true seulement si elles sont identiques (même longueur, et caractères identiques aux mêmes positions). Nous avons utilisé une signature à la C, où le nombre de caractères à comparer est suppléé par le code client, dans le but de simplifier l'exposé; ce n'est pas une saine pratique en général.

La version de gauche est plus rapide car elle se termine dès qu'une différence entre les deux paramètres est constatée, mais a le défaut qu'on pourrait, en l'appelant en fixant l'un des paramètres et en faisant varier l'autre, on pourrait utiliser les variations de temps d'exécution pour déduire de l'information sur le paramètre fixé. Dans le cas où ce paramètre contient une information secrète, un attaquant sournois pourrait réduire l'ensemble des possibilités à explorer pour briser ce secret.

La version de droite est telle que le nombre de tests sera strictement dépendant du nombre de caractères à tester; les valeurs des caractères dans les chaînes n'influencera pas le temps d'exécution.

bool comparer_chaines(const char *s0, const char *s1, size_t size) {
   for(size_t i = 0; i < size; ++i)
      if (s0[i] != s1[i])
         return false;
   return true;
}

bool comparer_chaines(const char *s0, const char *s1, size_t size) {
   int resultat = 1;
   for(size_t i = 0; i < size; ++i)
      resultat &= static_cast<int>(s0[i] == s1[i]);
   return resultat != 0;
}

Ceci présume que les opérations primitives dans le corps d'une itération (affectation d'un entier à un entier; comparaison de deux bytes; évaluation d'un et bit à bit entre deux entiers) sont elles-mêmes Data-Invariant, ce qui devrait être le cas en pratique.

Notez qu'il faut être prudents en écrivant une fonction Data-Invariant. Par exemple, cette version serait incorrecte :

bool comparer_chaines(const char *s0, const char *s1, size_t size) {
   bool resultat = true;
   for(size_t i = 0; i < size; ++i)
      if (s0[i] != s1[i])
         resultat = false;
   return resultat;
}

La raison du caractère incorrect de cette version est que le nombre de branchements choisis y est influencé par les données dans les chaînes de caractères. Le nombre d'itérations ne dépend que du paramètre size, mais le temps d'une itération est influencé par les données. La version correcte, plus haut, ne souffre pas de ce défaut.

Cette version serait aussi incorrecte (merci à Jean-Christophe Grondin pour me l'avoir fait remarquer) :

bool comparer_chaines(const char *s0, const char *s1, size_t size) {
   bool resultat = true;
   for(size_t i = 0; i < size; ++i)
      resultat = resultat && (s0[i] == s1[i]);
   return resultat;
}

La raison pour celui-ci est que plusieurs langages, dont C et C++, escamotent l'évaluation de l'opérande de droite quand le résultat de l'expression est connu après évaluation de l'opérande de gauche (dans le cas de l'opérateur &&, si l'opérande de gauche est faux, l'opérande de droite n'est pas évalué).

Lectures complémentaires

Quelques liens pour enrichir le propos.

• Travaux visant à mener à l'inclusion dans le standard de C++ d'un type std::constant_time_value<T> : http://open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4145.html
• Techniques de programmation susceptibles de mener à des algorithmes Data-Invariant : https://cryptocoding.net/index.php/Coding_rules
• Pour un coup d'oeil sur les difficultés associées à l'écriture d'algorithmes Data-Invariant, voir ce questionnement associé au domaine de la cryptographie : https://github.com/weidai11/cryptopp/issues/146