Imprimer

Introduction

Nous avons indiqué que l'entropie est un concept fondamental dans la cryptographie, car la cryptographie est basée sur l'ignorance de la part de l'ennemi.  Il est donc utile de se poser la question comment l'entropie est modifiée par les deux primitives que nous avons discuté: les chiffrements par bloc et les fonctions de compression.  Dans ce qui suit, nous n'allons pas considérer une fonction de hachage ou un chiffrement par bloc particulier, mais leurs versions "idéales".  D'une certaine façon, c'est en fait la façon dont un élément primitif traite l'entropie qui détermine en quelle mesure il se rapproche de l'idéal.

Le flux d'entropie dans une fonction de compression

Considérons d'abord une fonction de compression avec une compression 1-1 (comme la primitive dans Keccak).  Mais supposons, pour commencer, que la fonction agit sur un ensemble bien plus petit: supposons qu'elle prenne un bloc de 16 bits, et rend un bloc de 16 bits.  Idéalement, la fonction est une permutation qui "a l'air aléatoire", mais qui a une spécification algorithmique ce qui ne la rend pas aléatoire pour de vraie, dans le sens qu'elle n'est pas une fonction tirée au hasard dans l'univers des permutations sur l'ensemble {0,1,2,.... 216-1} et une distribution uniforme, de la même façon que tout algorithme de longueur finie ne peut pas générer un nombre aléatoire sur les réels, mais seulement sur un petit sous-ensemble nombrable de ceux-ci.

Comme c'est une permutation, qui est mathématiquement donc réversible, l'entropie de la sortie est exactement égal à l'entropie de l'entrée.

Pour chaque entrée, il y a exactement une sortie, ainsi la probabilité d'obtenir une sortie donnée est exactement celle de l'entrée et donc l'entropie de la distribution de la sortie est exactement celle de l'entrée puisque les deux distributions sont identiques.  Dans notre exemple, si l'entrée a une entropie de 16 bits (si le mot d'entrée est totalement aléatoire et imprévisible) alors la sortie aura aussi une entropie de 16 bits.

Il faut aussi noter que si l'entrée n'a que 2 bits d'entropie (par exemple, parce qu'il n'y a 4 valeurs possibles et équiprobables, même si elles sont codés sur 16 bits), alors la sortie n'aura que 2 bits d'entropie (il n'y aura que 4 possibles sorties, elles aussi, équiprobables).  Une fonction de compression ne peut pas "ajouter" de l'entropie.

Considérons maintenant une vrai fonction de compression.  Une fonction triviale pourrait être: un bloc d'entrée de 16 bits est réduit en une sortie de 4 bits, en supprimant les 12 premiers bits de l'entrée.  Quelle est l'entropie des 4 bits de sortie ?  Si l'entropie d'entrée est totale (donc 16 bits), alors, les 4 bits de sortie seront aussi d'entropie totale: 4 bits.  Si par contre, l'entrée n'a que 4 bits d'entropie, (donc il y a 16 mots possibles à l'entrée, même si ces mots sont codés sur 16 bits), combien d'entropie aura la sortie ?  A priori, "il y a suffisamment de place" dans la sortie pour garder les 4 bits d'entropie de l'entrée, mais bien sûr, ce ne sera pas le cas, car la fonction qui prend les 16 mots possibles de l'entrée ne sera pas nécessairement une bijection sur l'ensemble des 16 sorties possibles.  Il y a une certaine probabilité que deux entrées seront projetés sur la même sortie, et que d'autres sorties ne seront jamais atteints.  Ainsi, même si la probabilité des 16 mots d'entrée sont égales (c'est pourquoi l'entrée a une entropie de 4 bits), les 16 mots de sortie ne sont pas équiprobables (certains auront plus de probabilité qu'un 16ième, et d'autres auront 0 chance) et leur entropie est donc plus faible que 4 bits.

Nous pouvons en fait estimer combien d'états de sortie seront inoccupés si la fonction est "aléatoire" au lieu d'être une permutation aléatoire.  S'il y a N états possibles de sortie, et il y a M états d'entrée, alors si une sortie est "tirée aléatoirement" pour chaque entrée, nous avons la probabilité qu'un seul tirage va donner une sortie spécifique égale à 1/N.  La probabilité de ne pas être tiré est donc (N-1)/N.  Si la fonction "tire" de façon aléatoire une sortie pour chaque entrée différente (sans tenir compte des tirages précédents - c'est ce qui diffère la fonction de la bijection), alors la probabilité pour un état de sortie de ne jamais être tiré sera de [ (N-1)/N]M .   Le nombre d'états de sortie qui ne seront donc jamais tirés est donc: N [ (N - 1) / N ]M .

Dans le cas où N = M, tous les deux égal à 16, dans notre exemple, nous avons que la probabilité pour un état de sortie de ne pas apparaître est N [ (N - 1) / N ]N, ce qui, pur N "grand", tend vers N/e.  Pour N = 16, la formule exacte nous donne 5.7.  Nous nous attendons donc que sur les 16 états de sortie possible, seulement 10 seront sollicités.  Ainsi, il y a une perte d'entropie:

La perte d'entropie peut être estimée à log2 (1- 1/e) = 0.7 bits si nous avons pleine entropie de sortie et une fonction aléatoire au lieu d'une permutation.

Notez que dès que nous avons un peu plus d'entropie à l'entrée que ce qui est possible à la sortie, cette perte devient négligeable.  Si, dans notre exemple, nous avions 5 bits d'entropie à l'entrée (tandis que la sortie n'est capable que de fournir 4 bits au plus), alors le nombre d'états de sortie non-sollicités est 16 [15/16]32 = 2.  Donc 14 des 16 sorties seront atteint avec juste 1 bit de plus d'entropie à l'entrée.  Cela coûtera 0.2 bits d'entropie des 4 possibles (la sortie aura donc 3.8 bits d'entropie).  Avec 2 bits d'entropie en plus à l'entrée, cela devient: 16 [15/16]64 = 0.26 et nous pouvons considérer que la sortie sera en "pleine entropie" de 4 bits.

Considérons maintenant le cas où nous avons plus de bits de sortie que d'entropie d'entrée.  Si nous avons 4 bits d'entropie à l'entrée et 5 bits de sortie, alors on peut s'attendre à ce que 32 [31/32]16 - 16 = 3.25 des 16 possibles sorties ne seront pas atteint.  Quand nous avons 6 bits de sortie, il faut s'attendre à ce que 64[63/64]16 - 48 = 1.7 des 16 états possibles ne seront pas atteint.  Ainsi, dès que nous avons plus que 2 bits de plus à la sortie que d'entropie à l'entrée, nous pouvons négliger la perte d'entropie par la fonction de "compression", et l'entropie d'entrée est donc conservée.

En conclusion, ce n'est donc que quand l'entropie d'entrée est proche de l'entropie de sortie maximale que nous avons une perte de 0.7 bits quand notre fonction est bien une fonction aléatoire et non une bijection.

En d'autres termes, en très bonne approximation, nous avons:

La fonction de compression dans Keccak étant une fonction réversible et donc une bijection, elle garde l'entropie d'entrée.  Par contre, si nous prenons qu'une partie de la sortie, cette même fonction devient une vraie fonction aléatoire (et non une bijection).  On pourrait se demander si la réversibilité de la fonction 1-1 pour obtenir une permutation (et donc pour éviter toute collision) est un avantage suffisant comparé à la faiblesse cryptographique qu'on introduit en rendant cette fonction réversible.

Une vraie fonction de compression se comporte idéalement comme une fonction aléatoire ; ainsi nos conclusions s'appliquent aussi aux fonctions de compression.

L'aspect important d'une fonction de compression est qu'elle peut "concentrer l'entropie".  En d'autres termes, une fonction de compression peut "blanchir" des sources d'entropie non-parfaites, en acceptant le prix à payer de perdre de l'entropie.

Effectivement, supposons que nous avons une source d'entropie qui est loin d'être blanche, c'est à dire, une source qui génère beaucoup de bits corrélés.  Supposons que nous avons une source d'entropie qui a une véritable entropie de 10 bits par mot, mais qui génère des mots de 64 bits.  Si nous utilisions les mots de 64 bits tel quel, nous aurions beaucoup de bits corrélés, ce qui peut ne pas être acceptable dans l'application que nous avons en vue.  Mais si nous passons ces mots de 64 bits dans une fonction de compression qui ne sort que 6 bits, alors, selon le raisonnement présenté ci-dessus, ces 6 bits auront essentiellement 6 bits d'entropie.  De nos 10 bits d'entropie diluées en 64 bits, nous avons extrait 6 bits d'entropie concentrée qui sont uniformément aléatoires.  Nous avons donc maintenant 6 bits "purs", mais nous en avons perdu 4 (au départ nous avions une entropie de 10, et à la sortie, il n'en restent que 6).  Si nous avions pris une fonction de compression qui sort 10 bits, ces 10 bits auraient une entropie de 9.3 bits.  Cela veut dire qu'il restent des faibles corrélations entre ces bits.  Dépendant de l'application, cela peut être acceptable ou non.

Une application typique est la génération de mots de passe de haute entropie à partir de "phrases de passe".  Des phrases de passe sont une chaîne de caractères qui font une "phrase": une séquence de mots.  Cette phrase n'a pas nécessairement une signification sémantique ou même une structure syntaxique correcte, mais c'est des mots.  Si les caractères sont codés sur 8 bits, alors une phrase de passe contenant 10 mots avec en moyenne 5 caractères et un blanc contiendra 60 caractères, ou 480 bits.  Mais, bien sûr, l'entropie d'une telle phrase de passe est bien plus faible.  Seulement, pour un être humain, se souvenir d'une "phrase de passe" de 10 mots est plus facile que de se souvenir d'une série plus petite de caractères totalement arbitraires.  Il peut cependant être judicieux de vouloir extraire un mot de passe "blanc" de cette phrase de passe.  Supposons que les mots sont tirés d'un dictionnaire de 8000 mots.  Cela veut dire que chaque mot, s'il est choisi au hasard, a une entropie de 13 bits (mais est codé sur 48 bits).  Notre phrase de passe aura donc une entropie de 130 bits, codé sur 480 bits.  Si nous avons une fonction de hachage qui sort sur 128 bits, nous pouvons, de notre phrase de passe de 480 bits, construire un mot de 128 bits ayant essentiellement 128 bits d'entropie ; un mot "blanc".  Chaque bit dans le mot de 128 bits de sortie n'a aucune corrélation avec un autre bit, et est distribué avec 50% de chance d'être 0, et 50% d'être 1.  Nous avons perdu 2 bits d'entropie dans le processus, mais il n'y a presque plus de corrélation entre les bits du mot de passe de 128 bits qui en sort.

Une autre application évidente de cette technique de "blanchiment" est le générateur de nombres aléatoires.

Le flux d'entropie dans les chiffrements à bloc

D'une certaine façon, nous pouvons considérer un chiffrement à bloc comme une fonction de compression qui comprime la clé et le texte en clair en un texte chiffré.  La réversibilité du chiffrement fait que, pour une clé donnée, la relation entre le texte en clair et le texte chiffré est une permutation.  Ainsi, pour une clé donnée, l'entropie du texte en clair et le texte chiffré est identique.  Effectivement, pour une clé donnée, un chiffrement en bloc agit comme une fonction de compression 1-1 qui est une permutation.

Mais du point de vu de l'attaquant, qui ne connaît pas la clé (qui possède donc de l'entropie pour lui), les choses sont différentes.  L'entropie de texte chiffré, pour un attaquant, est grossièrement:

Cela dit, ce n'est vrai que si on utilise la clé que une seule fois !

Si (comme c'est bien sûr l'idée) il y a réutilisation de la clé pour plusieurs chiffrements en bloc, ce qu'on vient d'énoncer reste vraie, mais il faut maintenant considérer l'ensemble de tous les textes en clair qui est codé avec la même clé.  Alors, c'est quasiment toujours le deuxième cas qui l'emporte.  

Prenons un exemple, avec un chiffrement en bloc qui a des blocs de données de 512 bits, et une clé de 256 bits.  supposons que la clé a une réelle entropie de 100 bits et supposons que nous chiffrons des blocs qui ont une réelle entropie de 450 bits (c'est déjà beaucoup !).  Pour un seul chiffrement, le nombre de bits dans le texte chiffré étant 512, et 100 + 450 = 550 étant plus grand, le texte chiffré est donc "parfaitement blanc".  Par contre, si le bloc de texte clair n'avait que 50 bits d'entropie (si c'est du texte, c'est plus réaliste), alors l'entropie de sortie ne serait que de 100 (clé) + 50 (texte en clair) = 150 bits.

Mais supposons que nous chiffrons 1000 blocs de ce style avec la même clé, et des blocs de 450 bits d'entropie.  L'entropie totale du texte en clair est maintenant 450 000 bits.  La (seule) clé en a 100.  La somme est donc 450 100 bits d'entropie, alors que la sortie a une capacité de 512 000 bits.  Ainsi, l'entropie du texte chiffré est de 450 100 bits.  Il semble que notre chiffrement n'a rajouté que 0.1 bits d'entropie par bloc ! 

Mais ce n'est pas ainsi qu'il faut voir les choses.  Notre clé a ajouté 100 bits d'entropie au flux total de données.  Cela veut dire qu'il y a 2100 différentes façons de chiffrer ce flux, une pour chaque clé.  Ces 100 bits d'entropie restent mélangés à tous les bits du texte chiffré.  La sécurité du chiffrage réside dans ce mélange qui est dans la pratique, irréversible, pas dans le rajout d'entropie pour chaque bit chiffré (comme c'est le cas du masque unique).