SipHash
Série 7 – corrigé

Le corrigé de cette série vous est fourni sous la forme d'une archive Zip incluant le code fourni dans l'énoncé. Les solutions aux principaux exercices sont brièvement décrites ci-dessous.

Pour pouvoir écrire le corps du constructeur, il faut tout d'abord ajouter à la classe State ses attributs, qui sont bien entendu les quatre entiers de 64 bits \(v_0\) à \(v_3\). En Java, ces attributs ont naturellement le type long.

En plus de ces attributs, nous avons choisi d'en ajouter deux autres, statiques, qui donnent les valeurs de \(c\) et de \(d\), afin de clarifier un peu le code, mais il s'agit d'un détail.

Une fois ces attributs ajoutés, il suffit de les initialiser conformément à ce qui est dit dans l'énoncé :

private final static class State {
  private final static int C = 2, D = 4;
  private long v0, v1, v2, v3;

  public State(long k0, long k1) {
    v0 = k0 ^ 0x736f6d6570736575L;
    v1 = k1 ^ 0x646f72616e646f6dL;
    v2 = k0 ^ 0x6c7967656e657261L;
    v3 = k1 ^ 0x7465646279746573L;
  }

  // … autres méthodes
}

La méthode sipCompress est une simple traduction en Java de la description de la phase de compression, ou plutôt de l'une de ses étapes. On suppose à ce stade l'existance d'une méthode sipRound permettant de « faire un tour ».

Notez que nous faisons usage, dans cette méthode et celles qui suivent, des opérateurs combinant opération arithmétique et affectation. Par exemple, au lieu d'écrire :

v3 = v3 ^ m;

nous écrivons :

v3 ^= m;

Il ne s'agit que d'un raccourci de notation, la signification de ces deux énoncés étant rigoureusement la même.

public void sipCompress(long m) {
  v3 ^= m;
  for (int i = 0; i < C; ++i)
    sipRound();
  v0 ^= m;
}

La méthode sipFinalize n'est quant à elle qu'une traduction en Java de la description de la phase de finalisation donnée dans l'énoncé. Elle utilise bien entendu également la méthode sipRound.

public long sipFinalize() {
  v2 ^= 0xFF;
  for (int i = 0; i < D; ++i)
    sipRound();
  return v0 ^ v1 ^ v2 ^ v3;
}

Finalement, la méthode sipRound effectue les 14 opérations correspondant à un tour.

private void sipRound() {
  v0 += v1;
  v2 += v3;
  v1 = rotateLeft(v1, 13);
  v3 = rotateLeft(v3, 16);
  v1 ^= v0;
  v3 ^= v2;
  v0 = rotateLeft(v0, 32);
  v2 += v1;
  v0 += v3;
  v1 = rotateLeft(v1, 17);
  v3 = rotateLeft(v3, 21);
  v1 ^= v2;
  v3 ^= v0;
  v2 = rotateLeft(v2, 32);
}

La première chose à faire pour cet exercice est d'écrire une méthode permettant de charger tous les mots d'un fichier, ce qui a déjà été fait à plusieurs reprises dans le cours et constitue une bonne révision des techniques d'entrée/sortie. Cette méthode, nommée loadWords, ressemble à ceci :

Collection<String> loadWords(String fileName)
    throws IOException {
  Collection<String> words = new ArrayList<>();
  try (BufferedReader r = new BufferedReader(
    new InputStreamReader(
      new FileInputStream(fileName), UTF_8))) {
    String w;
    while ((w = r.readLine()) != null)
      words.add(w);
  }
  return words;
}

Une fois cette méthode écrite, il est facile de l'utiliser pour charger tous les mots du fichier mots_1.txt et de déterminer, au moyen de largestCollision, le plus grand ensemble de mots ayant une collision de hachage avec la méthode hashCode de String :

public static void main(String[] args) throws IOException{
  Collection<String> words = loadWords("mots_1.txt");
  Set<String> javaCollisions =
    largestCollision(words, String::hashCode);
  // … suite
}

Pour SipHash, les choses sont un tout petit peu plus complexes, puisqu'il faut choisir une clef, transformer la chaîne en tableau d'octets, créer une instance de SipHasher_2_4, appeler sa méthode hash et finalement transformer le résultat en entier de type int.

Pour faciliter les choses, ces différentes opérations ont été regroupées dans une méthode auxiliaire nommée sipHashString, qui utilise la même clef que celle utilisée dans le test unitaire fourni :

private static final byte[] KEY_BYTES =
  new byte[] { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };
private static final SipKey KEY =
  new SipKey(KEY_BYTES);
private static final SipHasher_2_4 SIPHASHER_2_4 =
  new SipHasher_2_4(KEY);

private static int sipHashString(String s) {
  return (int)SIPHASHER_2_4.hash(s.getBytes(UTF_8));
}

Une fois cette méthode écrite, il est trivial de l'utiliser pour déterminer les collisions de SipHash-2-4 et de les afficher à côté de celles de Java. La méthode main complète est donc :

public static void main(String[] args) throws IOException{
  Collection<String> words = loadWords("mots_1.txt");
  Set<String> javaCollisions =
    largestCollision(words, String::hashCode);
  Set<String> sipHashCollisions =
    largestCollision(words, Main::sipHashString);
  System.out.printf("Collisions hashCode    : %3d (%s)%n",
                    javaCollisions.size(),
                    javaCollisions);
  System.out.printf("Collisions SipHash-2-4 : %3d (%s)%n",
                    sipHashCollisions.size(),
                    sipHashCollisions);
}

En exécutant ce programme, on obtient le résultat suivant, ou un autre équivalent c-à-d avec la même taille de collision maximale :

Collisions hashCode    :   2 ([aï, es])
Collisions SipHash-2-4 :   2 ([ressautâmes, poussiéreuses])

Ce résultat indique que aussi bien l'algorithme utilisé par la méthode hashCode de String que SipHash-2-4 n'ont pas de grave problème de collision sur ce fichier, qui contient quand-même 336 531 mots français. Il faut d'ailleurs noter que si la totalité des 64 bits produits par SipHash-2-4 étaient pris en compte, il n'y aurait aucune collision sur cette ensemble de mots.

Toutefois, en modifiant ce programme pour qu'il lise les mots du second fichier, mots_2.txt, on obtient le résultat suivant (nettement simplifié pour des raisons de présentation) :

Collisions hashCode    : 940 ([JAU_<~, I`V@<~, I_t^[~, …])
Collisions SipHash-2-4 :   1 ([JB6_?!])

Dans ce cas, l'algorithme de la méthode hashCode de String a un comportement catastrophique, puisque tous les 940 mots de ce second fichier ont la même valeur de hachage.

Bien entendu, ces mots ont justement été choisi de manière à ce que ce soit le cas. Mais la possibilité de provoquer ainsi volontairement des collisions de hachage est potentiellement dangereuse, car elle rend possible une attaque nommée hash flooding.

Brièvement, l'idée de cette attaque est la suivante : admettons que l'on sache qu'une application Web quelconque, par exemple un dictionnaire français en ligne, est écrite en Java. Admettons de plus qu'elle stocke tous les mots recherchés récemment dans un ensemble de type HashSet, pour une raison quelconque.

On peut alors effectuer rapidement un grand nombre de recherches sur cette application, en choisissant volontairement des « mots » ayant la même valeur de hachage. Ces mots seront tous stockés dans l'ensemble HashSet, qui théoriquement offre une opération d'ajout ayant une complexité de O(1). Malheureusement, cela n'est vrai que si les collisions de hachage sont rares ! Si tous les éléments de l'ensemble ont la même valeur de hachage, alors cet ajout a une complexité de O(n), où n est la taille de l'ensemble. Si on s'arrange pour ajouter un grand nombre de mots en collision, et que chaque insertion a une complexité de O(n), l'application Web deviendra très vite inutilisable car totalement occupée par l'insertion de ces mots dans l'ensemble HashSet.

En quoi SipHash est-elle supérieure dans ce cas ? D'une part, étant donnée sa structure, la recherche de collisions de hachage est beaucoup plus difficile que pour la méthode hashCode de String. D'autre part, rien n'interdit à l'application Web de choisir une nouvelle clef aléatoire à chaque démarrage, et dès lors de changer la fonction de hachage utilisée ! Tant et aussi longtemps que l'attaquant ne connaît pas cette clef, il ne peut pas générer une liste de mots ayant la même valeur de hachage, et ne peut donc reproduire l'attaque ci-dessus.