SipHash
Série 7

Pour mémoire, le but d'une fonction de hachage est de transformer des données quelconques — chaînes de caractères, entiers, images, etc. — en un nombre entier de taille fixe, souvent 32, 64 ou 128 bits. Ces fonctions de hachage ont de nombreuses utilisations, parmi lesquelles la mise en œuvre de certains types de collections comme les ensembles de type HashSet en Java.

En Java, la méthode hashCode, disponible sur n'importe quel objet car définie dans Object, permet de déterminer la valeur de hachage de cet objet. Beaucoup de classes redéfinissent cette méthode afin d'utiliser une technique de hachage qui leur est propre. Par exemple, la classe String redéfinit hashCode et calcule la valeur de hachage \(h\) de la chaîne à laquelle on l'applique au moyen de la formule suivante :

\[ h = 31^{n-1}\,c_0 + 31^{n-2}\,c_1 + \cdots + c_{n - 1} \]

où \(c_0, c_1, \ldots, c_{n - 1}\) sont les \(n\) caractères de la chaîne qui, en Java, sont aussi des entiers. Ce calcul est fait au moyen d'entiers de type int en Java, donc d'entiers de 32 bits en complément à deux. Le résultat est donc toujours un entier de 32 bits, compris entre \(-2^{31}\) et \(2^{31} - 1\) (inclus).

Par exemple, en Java, la chaîne AN a la valeur de hachage 2093, car le caractère A correspond à l'entier 65 et le caractères N à l'entier 78, donc :

\[ h = 31\cdot 65 + 78 = 2093 \]

Bien entendu, il est possible de hacher les chaînes de caractères au moyen d'autres fonctions de hachage, parmi lesquelles SipHash.

Contrairement à ce qui a été dit jusqu'à présent, SipHash ne désigne pas une seule fonction de hachage, mais bien une famille de telles fonctions. En effet, l'algorithme SipHash est configuré au moyen de trois paramètres, et à chaque triplet de paramètres correspond une fonction différente. Ces paramètres sont :

• \(c\), le nombre de « tours » de la phase dite de compression,
• \(d\), le nombre de « tours » de la phase dite de finalisation,
• \(k\), une clef de 128 bits.

Le concept de tours, et la signification des phases de compression et de finalisation sont décrits plus bas. Dans le cadre de cette série, nous fixerons les paramètres \(c\) et \(d\) à 2 et 4 respectivement, valeurs souvent choisies en pratique car consistuant un bon compromis entre bonnes performances et qualité du hachage. Nous désignerons parfois par le terme « SipHash-2-4 » cette variante.

Le paramètre \(k\) pourra quant à lui varier. A chaque valeur de cette clef correspond une autre fonction de hachage de la famille SipHash, puisque les valeurs de hachage produites par SipHash dépendent de la clef utilisée. L'utilité de cette clef sera expliquée dans le corrigé de cette série.

Pour hacher une séquence d'octets, SipHash commence par les regrouper en groupes de huit et à transformer chacun de ces groupes en un entier de 64 bits. Dans le cas où la séquence ne comporte pas un multiple de huit octets, des octets nuls sont ajoutés à la fin pour que ce soit le cas. Les détails de cette partie ne nous concernent pas ici, car nous l'avons programmée pour vous, et les personnes intéressées par les détails se reporteront donc à la section 2 de l'article susmentionné.

Une fois cette transformation faite, on peut considérer que SipHash prend en entrée une séquence d'entiers de 64 bits, et ne la décrire qu'en termes de ce type d'entiers.

La séquence d'entiers de 64 bits fournie en entrée à SipHash est notée \(m\) ci-dessous, sa longueur \(w\), et ses éléments \(m_0, \ldots, m_{w-1}\). (Cette notation suit celle de la spécification de SipHash).

Le calcul de la valeur de hachage de la séquence \(m\) se fait en lisant ses éléments l'un après l'autre et en modifiant en fonction un état interne composé de quatre entiers de 64 bits nommés \(v_0\), \(v_1\), \(v_2\) et \(v_3\). La valeur initiale de cet état est déterminée ainsi :

\begin{align*} v_0 &= k_0\oplus\mathtt{736f6d6570736575_{16}}\\ v_1 &= k_1\oplus\mathtt{646f72616e646f6d_{16}}\\ v_2 &= k_0\oplus\mathtt{6c7967656e657261_{16}}\\ v_3 &= k_1\oplus\mathtt{7465646279746573_{16}} \end{align*}

où \(\oplus\) représente le ou exclusif bit à bit et \(k_0\) et \(k_1\) sont les deux moitiés de la clef \(k\), obtenues selon une technique qui ne sera pas décrite ici, le code vous étant fourni.

Après cette phase d'initialisation, l'état est progressivement modifié par la phase dite de compression. Elle consiste à itérer sur les éléments de la séquence \(m\) et à modifier à l'étape \(i\) la valeur de \(v_3\) ainsi :

\[ v_3 = v_3\oplus m_i \]

à la suite de quoi \(c\) (ici 2) tours sont effectués, chacun consistant à appliquer 14 modifications successives à l'état, décrites plus bas. Cela fait, la valeur de \(v_0\) est modifiée ainsi :

\[ v_0 = v_0\oplus m_i \]

et le prochain élément de la séquence est traité de la même manière, jusqu'au dernier.

Une fois le dernier élément de la séquence traité par la phase de compression, la phase de finalisation transforme une dernière fois l'état, de la manière suivante. Tout d'abord \(v_2\) est modifié ainsi :

\[ v_2 = v_2\oplus \mathtt{ff_{16}} \]

puis \(d\) (ici 4) tours sont effectués. Finalement, la valeur de hachage \(h\) de la séquence est déterminée ainsi :

\[ h = v_0\oplus v_1\oplus v_2\oplus v_3 \]

Comme cela a été mentionné, chaque tour de la phase de compression ou de finalisation consiste à enchaîner 14 modifications d'état, qui sont :

\begin{align*} v_0 &= v_0 + v_1\\ v_2 &= v_2 + v_3\\ v_1 &= v_1\lll 13\\ v_3 &= v_3\lll 16\\ v_1 &= v_1\oplus v_0\\ v_3 &= v_3\oplus v_2\\ v_0 &= v_0\lll 32\\ v_2 &= v_2 + v_1\\ v_0 &= v_0 + v_3\\ v_1 &= v_1\lll 17\\ v_3 &= v_3\lll 21\\ v_1 &= v_1\oplus v_2\\ v_3 &= v_3\oplus v_0\\ v_2 &= v_2\lll 32 \end{align*}

où \(\lll\) représente une rotation à gauche, et non pas un simple décalage comme la notation pourrait le laisser penser !

Pour mémoire, la rotation est similaire au décalage si ce n'est que les bits « éjectés » d'un côté (ici, à gauche) du vecteur de bits sont réintroduits de l'autre (ici, à droite). Cette opération sur les bits est totalement équivalente à l'opération de rotation effectuée sur les chaînes de caractères dans la série sur la transformée de Burrows-Wheeler.