Cryptographie et entropie.

Dans beaucoup d'applications de cryptographie, il faut distinguer un ami d'un ennemi.  Un ami a des capacités qu'un ennemi ne possède pas, ou n'est pas supposé de posséder en ce qui concerne le traitement de données (par exemple, transformer un texte chiffré en texte clair).  Ceci est réalisé en donnant à l'ami une pièce d'information, une clé qui est inconnue à l'ennemi.  La distinction entre l'ami et l'ennemi est donc basée sur la connaissance que l'ami possède, et que l'ennemi ignore.  En d'autres termes, la clé doit posséder de l'entropie pour l'ennemi, et l'ami doit posséder l'information correspondante.  On peut comparer cela à l'état d'un observateur avant l'essai d'un processus aléatoire qui est la situation de l'ennemi, et l'état de l'ami, qui correspond à celui de l'observateur après l'essai.

La distinction entre un ami et un ennemi peut être mesuré par la quantité d'information que l'ami possède, ou par la quantité d'information dans la clé.  La quantité d'entropie de la clé déterminera la sécurité maximale atteignable par le système cryptographique.  La vraie sécurité peut être bien moindre à cause d'autres problèmes, mais en tout cas, le système ne peut pas être plus sûr que l'entropie de la clé.  Dépendant de l'application, cette quantité d'entropie doit être plus ou moins grande pour être suffisamment sûre.

Une façon qu'a l'ennemi pour obtenir la clé est en essayant de la deviner et d'essayer.  Si l'ennemi obtient une réaction ou un résultat qui indique s'il a bien deviné ou non, alors le système même est une source d'information de la clé à travers ces réponses.  Ainsi, l'ennemi peut extraire suffisamment d'information du système pour compenser l'entropie de la clé.

Si l'ennemi est limité dans le nombre d'essais ou de réponses qu'il peut obtenir (par exemple, en devinant un mot de passe sur un système interactif, il se peut que le nombre d'essais est limité), alors une quantité relativement modeste d'entropie dans la clé (ici, le mot de passe) peut être suffisant, car la quantité d'information que l'ennemi peut extraire du système est très limitée.  Par contre, si l'ennemi a une façon de tester autant de clés qu'il le souhaite, alors en tout cas, en principe, l'ennemi pourra extraire toute l'information de la clé.  Ce qui limitera, dans ce cas de figure, est la preuve de travail nécessaire pour obtenir cette quantité d'information.  En d'autres termes, une grande quantité d'entropie dans la clé demandera une grande quantité de travail du coté de l'ennemi - tellement large que par toute considération pratique, livrer une telle quantité de travail n'est pas envisageable.  C'est là-dessus que repose la sécurité de beaucoup de systèmes cryptographiques.

La méthode de deviner des clés, et d'obtenir une réponse du système indiquant si on a trouvé la bonne clé ou non, est appelée une attaque brute.

Dans la mesure où le système peut donner la réponse sur un essai de clé qui indique si la clé était la bonne ou non, le système finira en principe toujours par annuler l'entropie de la clé.  Mais il est aussi possible que le système ne donne pas la réponse "bonne" ou "fausse" clé.  Le système donne une réponse, mais il est impossible, de la réponse, de déterminer si la clé était bonne ou non.  Ce sont les seuls systèmes qui peuvent conserver totalement l'entropie de la clé.  Dans tout autre cas, en principe une attaque brute finira toujours par marcher. 

Dans tous les case, l'entropie réelle de la clé détermine la sécurité du système.

Considérons, par exemple, une entropie de 32 bits.   Avec 4 milliards d'essais, la clé sera trouvée avec certitude.  Si un ennemi peut essayer autant de clés qu'il souhaite, et si un essai prend une microseconde, en un peu plus qu'une heure, la clé sera trouvée.  Par contre, considérons une clé de 1024 bits.  Cette fois, le nombre d'essais est de 10^308.  C'est pour chaque particule élémentaire dans notre univers visible, de considérer chaque couple de particules élémentaires et d'essayer une clé pour chaque couple.  Si la seule attaque envisageable est l'attaque brute, il est totalement inimaginable de tester toutes les combinaisons, même si chaque essai ne nécessite qu'une infime quantité de travail.  Nous constatons facilement la différence de sécurité entre une clé avec une entropie de 32 bits, et une clé avec une entropie de 1024 bits.  Par contre, si l'ennemi n'a que 10 essais, alors même une clé de 32 bits est relativement sûre: seulement une chance en 400 millions que la clé sera trouvée.

La vraie entropie d'une clé est primordiale.  Mais pour que l'entropie de la clé soit vraie, il faut qu'il n'y ait aucun moyen de connaître la clé basée sur la façon dont la clé a été déterminée.  S'il est possible de répéter la procédure qui a généré la clé, bien sûr sa vrai ignorance est nulle.  C'est la différence entre la génération d'un nombre vraiment aléatoire et la génération d'un nombre pseudo-aléatoire.

Aléatoire statistique et pseudo-aléatoire

Considérez un grand tableau avec des nombres.  Il est possible de calculer des propriétés statistiques de ces nombres.  Par exemple, on peut calculer la moyenne de séries de 100 nombres successives dans le tableau.  On peut calculer des corrélations moyennes entre un nombre, et le nombre suivant.  Ou le nombre 5 places plus loin.   Il est possible que pour certains tableaux de nombres, une liste de propriétés statistiques sont parfaitement compatibles avec des ensembles de variables aléatoires relativement simples.  Dans ce cas, le tableau peut être utilisé comme si c'était une réalisation d'un essai tiré de cet ensemble.

Bien sûr, la meilleure façon d'obtenir un tel tableau de nombres ayant des propriétés statistiques d'un ensemble, c'est de les tirer effectivement d'un processus qui est sensé être décrit par cet ensemble.  Mais après le fait, la seule chose qui peut être vérifié du tableau, se sont ces propriétés statistiques.  L'origine "vraie" du tableau ne peut pas être décelée en ayant juste le tableau.  Si nous avons des moyens de calculer un tel tableau, qui satisfait des propriétés statistiques, cela serait équivalent au tirage réel de ce tableau d'un phénomène aléatoire, au moins pour ce qui concerne les propriétés statistiques.

Il y a des algorithmes qui peuvent justement calculer des tableaux de nombres avec des propriétés statistiques qui correspondent à celles d'ensembles de variables et processus aléatoires simples.  La plupart du temps, ces algorithmes sont inspirés de dynamique chaotique.  Bien sûr, certains tests statistiques ne marcheront pas.  Par exemple, le test statistique qui teste l'algorithme même ne marchera jamais (une vraie variable aléatoire ne suivra jamais exactement cet algorithme).  Mais pour la plupart des applications où on a besoin de nombres aléatoires, ces tests très particuliers n'ont aucune importance.  Sauf pour une application: la cryptographie !

La terminologie standard est qu'une série de nombres qui sont supposés être les tirages d'un processus aléatoire mais qui sont le résultat d'un calcul algorithmique, sont appelés des nombres pseudo-aléatoires.  Des nombres qui sont réellement le résultat d'un tirage d'un processus aléatoire sont appelés des nombres aléatoires (vraies).

Je voudrais modifier cette définition très légèrement, pour la simple raison qu'un tableau de nombres pseudo-aléatoires ne peut pas être distingué d'un tableau de nombres aléatoires si la seule chose qu'on connaît, c'est le tableau, et pas l'algorithme.  Il est effectivement toujours possible, après coups, de proposer un algorithme qui génère le tableau: un bête algorithme qui connaît le tableau, et recrache les nombres un par un.    Je voudrais donc élargir la classe des nombres pseudo-aléatoires par tous les tableaux de nombres qui sont potentiellement publiquement connues.  La raison pour la cryptographie est évidente.  L'ignorance d'un nombre aléatoire par l'ennemi doit être réelle.  Même si un nombre était un "vrai" nombre aléatoire par tirage, s'il est rendu publique, on ne peut plus affirmer qu'il soit ignoré !

La raison pour laquelle je précise cela est qu'il y a des tableaux publiques de "vraies nombres aléatoires".  Avant l'émergence d'ordinateurs bon marchés et puissants, ces tableaux étaient utiles pour des gens ayant besoin de nombres avec des propriétés statistiques (pour des simulations Monte Carlo par exemple).

Il y a des gens qui publient des nombres aléatoires publiques comme  random.org,mais pour une utilisation cryptographique, il faudrait les appeler pseudo-aléatoires.  Le fait même de les rendre publique réduit leur ignorance, leur entropie, à zéro.

Je dirai même: dépendre d'un parti tiers pour vous donner des nombres riche en entropie, est quelque part une contradiction logique, car il n'y a pas de moyen pour le client de vérifier combien ces nombres sont ignorés par l'ennemi.  Il sait déjà que l'entropie est zéro pour son fournisseur !

Donc: l'entropie réelle cryptographique ne peut être générée localement en privé.

Ceci peut paraître en contradiction avec la règle d'or de cryptographie, de n'utiliser que des techniques connues et publiques.  La raison est bien sûr que en cryptographie, sa puissance réside dans l'entropie des clés, qui doivent être totalement privés.  Le secret n'est pas dans la méthode, qui doit être robuste contre des attaques (et donc testée par beaucoup de gens).

Des générateurs pseudo-aléatoires cryptographiques.

Nous avons vu qu'il existe des algorithmes qui peuvent produire des tableaux de nombres qui ont des propriétés statistiques de variables aléatoires d'ensembles simples.  Bien sûr, tout le monde qui refait le calcul par cet algorithme, obtiendra le même tableau.  L'entropie de ce tableau est donc zéro.  En fait, la plupart de ces algorithmes peuvent générer des tableaux différents, en fonction d'un paramètre qui s'appelle la graine. On peut s'imaginer la graine comme le numéro du tableau qui sera généré. Chaque tableau peut être extrêmement long et l'algorithme peut en générer plusieurs: la graine nous dit lequel.  Si notre algorithme a, par exemple, la possibilité de générer 128 tableaux différents (chaque tableau contenant 4 milliards de nombres), la graine prendra une valeur de 1 à 128.  Si notre graine est 23, l'algorithme calculera les 4 milliards de nombres du tableau numéro 23.

Si nous ignorons la graine, nos nombres pseudo-aléatoires ont une entropie: celle de la graine !  Effectivement, en ignorant la graine, nous avons, pour chaque nombre du tableau, 128 possibilités.  Dans notre cas, les nombres du tableau auraient une entropie de 7 bit.  Seulement, après deux ou trois nombres du tableau, nous allons bien sûr pouvoir déterminer lequel des 128 tableaux correspond.  Une fois le tableau numéro 23 identifié, les nombres suivants n'ont plus d'entropie du tout: nous connaissons à l'avance tous les nombres qui vont être tirés.

Même si la graine introduit de l'entropie dans des nombres pseudo-aléatoires - l'entropie de la graine même - il est très facile de la perdre par les nombres mêmes, c'est à dire, quelques nombres indiquent quel tableau nous sommes en train de générer, et donc la graine.  Il y a certains algorithmes de générateurs pseudo-aléatoires, appelés cryptographiques, qui sont durcis contre ce problème.  Bien sûr le problème de base reste entier, mais le calcul nécessaire pour déduire la graine des nombres précédents est rendu tellement dur (nécessite tellement de travail) que c'est sur le plan computationnel que la détermination de la graine est rendu pratiquement impossible.  Ainsi, un générateur pseudo-aléatoire cryptographique est un générateur dont les nombres aléatoires successives ont l'entropie de la graine, sans la révéler.  La révélation serait trop coûteuse sur le plan des calculs à fournir.

La règle d'or est aussi valable ici: n'utilisez que des générateurs pseudo-aléatoires bien connues.

Comme nous venons de voir, les générateurs pseudo-aléatoires ne sont pas des sources d'entropie.  Au mieux, ce sont des transformateurs d'entropie.  Ils ont besoin d'une source d'entropie (la graine) pour générer d'autres nombres aléatoires qui possèdent, au mieux, la même entropie.  D'où vient donc l'entropie tellement essentielle d'un système cryptographique ?

Quelle source d'entropie faut-il utiliser alors ?

Il ne faut pas oublier quelle est la fonction principale de l'entropie dans un système cryptographique: c'est l'ignorance nécessaire de l'ennemi.  Ainsi, toute chose qui pourrait diminuer cette ignorance (entropie) doit être évitée.  C'est pour cela que nous avions déjà souligné la nécessité absolue que l'entropie cryptographique doit être générée localement et en privé.  Ensuite il faut la garder privé.  Il y a ces deux défis à relever dans l'entropie cryptographique.

Aucun calcul ne peut générer de l'entropie, contrairement à une erreur conceptuelle répandue.  L'entropie ne peut venir de l'observation ou de la mesure.  Dans la mesure où on a besoin de garantir que cette entropie reste vraie pour les ennemis (reste de l'ignorance pour les ennemis), il faut garantir qu'aucun ennemi n'ait accès à la même source d'entropie que celle qui est utilisée.  C'est pour cela que toute source publique d'entropie est une mauvaise idée dans l'utilisation cryptographique.  Les processus physiques sur lequels les mesures sont basées pour obtenir de l'entropie ne doivent pas être accessible à l'extérieur.

No computation can generate entropy.  This is often a conceptual mistake.  Entropy can only come about from measurement or observation.  In as much as one needs a guarantee that this will remain true entropy (true ignorance) for enemies, one needs to make sure that the enemy has no access to the same source of entropy as the one that is used.  This is why any publicly available process as a source of entropy, no matter how rich and powerful, is a bad idea.  The physical processes on which the measurements are based that are to generate entropy, shouldn't be accessible externally.

Les meilleures sources d'entropie sont:

• l'entropie thermodynamique
• l'entropie quantique

 Apart ces sources, il est aussi possible d'utiliser des procès complexes locaux de sources d'entropie, du moment où elles ne sont pas accessibles de l'extérieur.  En fait, le système Linux utilises le timing des entrées utilisateur (frappes de touches, mouvement de souris) comme source d'entropie.  Ces timings sont le résultat de processus complexes dans le cerveau et le système neurologique et musculaire de l'utilisateur.  Mais c'est une source très modeste d'entropie.  Elle peut être suffisante pour obtenir des clés avec une entropie de quelques milliers de bits.  Cela peut suffir pour une clé, mais c'est ouvert à la critique: dans quelle mesure est-ce réellement imprévisible ?  Dans quelle mesure est-ce que ce n'est pas accessible de l'extérieur ?  Se peut-il que des utilisateurs ont des timings très reproductibles ?  Cependant, pour beaucoup d'applications cette quantité d'entropie accumulée par le noyau Linux peut être suffisante.

Mais nous pouvons faire bien mieux.  Les meilleurs sources sont des sources thermodynamiques et quantiques locales, car elles sont supposées fondamentales.  S'il était possible de connaître de l'extérieur, l'état microscopique qui réduirait l'entropie thermodynamique d'un système local, cela voudrait dire qu'il serait possible de violer la deuxième loi de la thermodynamique.  S'il était possible de réduire de l'extérieur, l'entropie quantique, cela voudrait dire que la mécanique quantique et donc le principe d'incertitude de Heisenberg serait violé.  Bien qu'il y ait des réflexions philosophiques sur ces sujets, toute considération pratique implique qu'aucun ennemi va pouvoir en profiter en violant la deuxième loi de la thermodynamique ou le principe de Heisenberg.  Ce sont donc de vraies sources d'entropie. 

Les phénomènes quantiques comme la désintégration radioactive, ou la réflexion ou transmission d'un photon unique sur un miroir semi-transparent, sont de vraies sources d'entropie.  Personne ne peut les prévoir, même en principe.

Mais l'entropie thermodynamique, comme dans le bruit fondamental électronique, est aussi vraie et fondamentale.  En pratique, il est bien plus bon-marché et plus facile à mettre en oeuvre l'utilisation de bruit électronique fondamental comme source d'entropie qu'il est de faire des mesures quantiques.  En plus, le flux d'entropie d'une source de bruit électronique peut être, avec des moyens relativement simples, bien plus grand que le flux d'une source quantique.  Les sources quantiques sont des sources parfaites d'entropie, mais les sources thermodynamiques aussi.  Il y a des personnes qui prétendent que les sources quantiques sont meilleurs (afin de vous vendre des appareils très chers) ; cela n'est simplement pas vrai.  Les sources d'entropie thermodynamiques sont d'aussi bonnes sources que les sources d'entropie quantiques: les deux sont parfaits pour toute considération pratique.

S'il était possible, après date, de faire un calcul qui pourrait déterminer le micro-état d'une source d'entropie thermodynamique, ce qui est nécessaire pour réduire l'entropie de la source à zéro, cela voudrait dire qu'il serait possible de déduire aussi le micro-état de tout avec ce que ce système a interagi dans le passé.  Cela voudrait dire qu'on serait capable de calculer le micro-état de l'environnement complet.  S'ils peuvent faire cela, ils peuvent faire marcher le démon de Maxwell et violer la deuxième loi de la thermodynamique.  L'affirmation qu'une source thermodynamique serait moins fiable qu'une source quantique revient donc à dire que la deuxième loi de la thermodynamique serait plus facilement violable par un ennemi que les lois de la mécanique quantique.

Des générateurs pseudo-aléatoires cryptographiques ou des sources d'entropie physique ?

Le problème avec des sources d'entropie physique est qu'il faut un matériel dédié.  Ce matériel peut être bon-marché.  Entrop-x peut vous en fournir.  Mais il peuvent y avoir des situations où ce n'est pas pratique d'utiliser ces outils.  C'est dans une telle situation qu'il faut considérer si un générateur pseudo-aléatoire peut être utilisé.  Dans tous les cas où il est possible d'utiliser une source physique d'entropie, il ne faut pas hésiter: elles sont largement supérieures pour toute utilisation cryptographique, bien que dans beaucoup de cas, elles ne sont pas strictement nécessaires.  Cela dit, en matière de sécurité, est-il raisonnable de prendre un risque si le coût pour éviter ce risque est faible ?

Des sources basées sur du bruit électronique fondamental sont des sources parfaites d'entropie cryptographique, comme nous l'avons indiqué.  Leur flux d'entropie est en fait limité que par la nécessité de garantir qu'on utilise bien du bruit fondamental, et non des perturbations (qui peuvent être prévisibles, est disponible à l'extérieur etc...).  Ainsi, le rapport signal sur bruit de la source doit être considéré, où le bruit est le niveau maximal de perturbations et le signal est la puissance du bruit fondamental que nous voulons utiliser.  Le problème avec le bruit fondamental est que sa puissance est souvent très faible, et que la limite de perturbations que nous pouvons garantir n'est souvent pas loin sous cette puissance.  Pour être sûr, il ne faut donc pas espérer beaucoup de puissances de deux dans le rapport signal-bruit.  En utilisant la formule de Shannon, si nous avons une source de bruit fondamental de bande passante B, il devrait être possible d'obtenir un flux d'entropie de l'ordre de 10 B. 

Ainsi, des sources d'entropie de 1 Mb/s ou de 10 Mb/s sont très faciles à construire avec du matériel peu cher.  Avec du matériel plus avancé, les Gb/s sont réalisables.  Pour la plupart des applications cryptographiques, ces flux sont largement suffisants et l'efficacité d'utiliser un générateur pseudo-aléatoire peut être mis en question quand un tel matériel est disponible.

Corrompre des sources d'entropie cryptographique.

Comme argumenté, la sûreté d'un système cryptographique est entièrement dépendent de l'entropie des clés.  Dans la mesure où l'entropie de ces clés devient zéro ou petit pour un ennemi, la protection cryptographique devient inexistante, indépendant de sa sophistication ailleurs.  Si la source d'entropie est corrompue, cela peut rendre tout système qui en dépend dépourvu de toute sécurité.

La façon la plus évidente pour corrompre une source d'entropie est d'en faire une source de nombres aléatoires connues de l'ennemi.  Une technique peut être de prendre une graine riche en entropie de l'utilisateur, et de calculer une valeur hachée réduite à partir de cette graine ; ensuite d'utiliser cette valeur comme graine d'un générateur pseudo-aléatoire connu.  L'entropie des nombres sera l'entropie résiduelle du hash, qui sera très limitée.  Pour l'ennemi il sera relativement facile de mener une attaque brute passant par le jeu réduit des valeurs que peut prendre la graine réduite.  Le nombre de clés qui peuvent être générés par ce système est donc réduit et vulnérable à une attaque brute.  Par contre, pour la victime, il est extrêmement difficile de déceler une telle corruption de sa source.

Si on obtient une source d'entropie basée sur une source de bruit physique, mais dont les nombres aléatoires sont en réalité le résultat d'un générateur pseudo-aléatoire caché dans le logiciel qui gère le lien avec la source, ces nombres peuvent avoir une très faible entropie pour un ennemi.  Il peut donc être important de pouvoir vérifier soi-même si la source physique est réellement la source des nombres aléatoires qui sortent du système.

Un exemple.