Quel générateur RNG, et pour quel usage ?

Suite à la rédaction d’un article généraliste sur l’entropie Linux, j’ai pris contact avec Ron de chez BitBabbler. S’en est suivi une conversation très intéressante sur la génération de nombres aléatoires et leur usage. L’expérience de Ron est très impressionnante mais c’est son humilité qui m’a le plus impressionné, j’en retiens que dans ce secteur aucune vérité ne peut être considérée comme acquise et l’esprit critique est de mise.

Ron a d’ailleurs insisté pour expliquer le contexte : les informations qui suivent sont issues d’une conversation informelle et basées sur sa propre expérience. Il ne faut donc rien prendre pour argent comptant, et d’ailleurs un lecteur compétent se rendra compte que le sujet est juste effleuré.

Que pensez-vous de RTL-SDR comme source de nombres aléatoires  ?

Il est toujours difficile de répondre à la question « est-ce que X est suffisant » en général, puisque cela dépend des besoins spécifiques dans ses moindres détails.

Pour expérimenter et apprendre, n’importe quel périphérique est bon à partir du moment où il rentre dans votre budget. Même un très mauvais générateur aléatoire peut vous apporter beaucoup, car vous pourrez appliquer des tests, et déterminer ceux qui sont fiables pour rechercher des failles, ainsi que ceux qui ne le sont pas du tout.

Il est plus difficile de tirer des conclusions de ces tests si votre source aléatoire de base est bonne et que vous n’arrivez pas à faire échouer le moindre test. Vous n’avez alors aucun retour quant à l’utilité et les caractéristiques des tests en eux-mêmes.

Quels sont les types de tests couramment utilisés ?

Beaucoup de personnes semblent penser que la transposition d’un flux aléatoire en une image est un bon test. Mais c’est en réalité plutôt inutile pour la plupart des sources matérielles. Cela peut aller pour la recherche de séquences répétitives dans un algorithme pseudo-aléatoire (PRNG) naïf, mais cela fait bien longtemps que les algorithmes PRNG se revendiquent comme étant cryptographiquement forts.

Les tests statistiques sont plus forts, ils seront en mesure de trouver les failles ne pouvant pas être détectées à l’œil sur une série de données dite aléatoire.

Si je sais cela, ce n’est que parce que nous avons cherché par tous les moyens de trouver une bonne méthodologie de recherche de failles. Les tracés image ont toujours semblé une bonne idée, avant que les générateurs matériels réussissent d’autres tests relativement simples.

L’analyse de spectre simple (simple spectrum analysis) est légèrement meilleure, mais pas encore à la hauteur pour être un outil de détection de failles performant, même certaines relativement évidentes.

Et du coup, quel test empirique utiliser pour quel utilisation ?

Plus encore, la notion de « suffisant » est subjective, elle fait appel à des choses inter-dépendantes. Le critère pour un générateur cryptographiquement fort, c’est l’impossibilité pour un attaquant de deviner ce qu’il produit. Ainsi, même une chaîne de bits qui ne réussit pas les tests d’aléatoire peut constituer une « bonne » entropie, du moment que vous l’exploitez sur une longueur réduite afin d’empêcher qu’un attaquant n’exploite ses failles, et qu’il ne sache pas comment vous l’avez obtenue.

Le critère pour un générateur cryptographiquement fort, c’est l’impossibilité pour un attaquant de deviner ce qu’il produit

Vous pourriez bien lancer des dés pipés, cela n’appauvrit pas vos résultats du moment que votre attaquant ignore que votre entropie est plus chargée en « six » par rapport à un résultat naturel. Une chaîne aléatoire pourra bien ressembler à ceci par moments, sur une longueur réduite. Mais vous ne pouvez faire ceci raisonnablement qu’une seule fois avant de changer pour une autre source d’entropie, fusse-t-elle biaisée également.

Bien sur en crypto, la meilleure source aléatoire est une source qui reste imprévisible même en connaissant tout sur son fonctionnement, ce qui est par exemple le cas d’un matériel open-hardware. Il reste des cas d’usage où une méthode inférieure restera suffisante.

la meilleure source aléatoire est une source imprévisible, même en connaissant tout sur son fonctionnement

A l’inverse, il existe des cas de figure qui requièrent de meilleures garanties que celles qui sont crypto-essentielles. Ceux qui utilisent l’entropie pour des analyses statistiques ou du machine learning ont vraiment besoin d’éviter tout biais et toute faille algorithmique, sous peine de fausser leurs résultats. Peu importe si la sortie aléatoire est prévisible ou pas, il aura quand même altéré les résultats.

Et il existe aussi des cas de figure où la réussite aux tests statistiques ne constitue pas une garantie que la sortie ne puisse être devinée. Par exemple les décimales de Pi réussissent ces tests, mais en connaissant la séquence, on pourra deviner le prochain bit à 100%. Autre exemple, n’importe quelle donnée (comme un compteur incrémental) passée à travers une fonction de hash forte (même une faible comme MD5) réussira ces tests alors qu’il n’existe pas de vraie entropie à l’origine. C’est d’ailleurs ce qui fait qu’une fonction de hachage est forte : elle ne peut pas être inversée pour deviner la donnée d’entrée, mais en devinant la donnée d’entrée, on pourra savoir ce qu’elle retourne comme résultat et donc casser la protection qui repose sur elle.

Pour un dispositif qui capte le bruit atmosphérique, cela devrait aller alors ?

C’est précisément là que les récepteurs RF pêchent pour une utilisation RNG. En théorie on peut les positionner sur une fréquence « vide » et le signal reçu ressemblera à un bruit blanc, la source d’entropie idéale. Là où les choses se compliquent, c’est que le signal ne sera absolument jamais « vide ». Bien sur, on pourrait blinder le récepteur RF pour l’isoler du monde extérieur, mais c’est quelque chose dont peu de personnes connaissent la vraie difficulté.

Une cage de Faraday c’est du papier alu et un élastique… non ?

Si vous faites l’effort de tester vos réalisations sans supposer qu’elles fonctionnent, vous pouvez apprendre beaucoup en construisant une cage de Faraday. Même en connaissant les principes théoriques, il est impossible de construire une cage de Faraday du premier coup, elle fuira comme une passoire.

Et je n’ai pas encore évoqué comment isoler le bruit provenant du circuit RF et de ses oscillateurs, ni comment se débarrasser du bruit de l’ordinateur auquel il est connecté.

De la même manière, ce qui vous est présenté comme une « protection RFID » pour les cartes de crédit ou les passeports, ne vous protégera pas vraiment. Au mieux elles réduiront la portée, et au pire elles ne feront rien du tout. On se rend compte de ce genre de choses par l’expérimentation.

Mon RTL-SDR, qu’est-ce que je peux en faire ?

Il y a au minium deux choses intéressantes à faire. La première, c’est de savoir si le flux passe les tests statistiques. La seconde, c’est de chercher à savoir la quantité d’entropie qui a réellement été captée en entrée.

Même si la fréquence était libre, comment savoir qu’elle va le rester ? L’ouverture d’une porte de micro-ondes (exemple ici), ou l’utilisation d’un moteur électrique bruité sont autant de bruitages potentiels.

J’ai regardé rapidement le code du RTL-SDR et il tente de débiaiser le flux d’entrée. Ce flux est « blanchi » grâce à un algorithme Von-Neumann, et parfois également crypté par AES. Cela est bien la preuve que le signal d’entrée n’est pas connu pour être un bruit blanc idéal tel qu’on le trouve sur une fréquence libre. Je n’ai pas testé à quel point l’algorithme de Von-Neumann est bon, il l’est probablement.

Du coup, la chose à faire avec le rtl-sdr, ce serait de le paramétrer sur une fréquence occupée et de voir si la sortie du rtl-sdr passe les tests statistiques. Normalement le signal d’entrée contiendra un peu d’entropie quand même, et donc un attaquant qui enregistrerait au même moment devrait trouver un résultat différent.

Si les tests sont concluants, c’est bien mais on en revient au même point. Cela n’est pas une garantie que le signal d’entrée contenait assez d’entropie. Il pourrait y en avoir « beaucoup », tout comme « presque pas ».

Cela dit, cela restera probablement mieux que de déverser /dev/urandom dans /dev/random sous Linux. C’est quelque chose à proscrire si on a besoin d’un minimum de garanties.

C’est quand même un outil qui permettra d’apprendre beaucoup pour pas cher, avec des applications très diverses en dehors de l’entropie. J’en ai moi-même quelque uns, que je n’ai jamais d’ailleurs utilisés comme source d’entropie.

L’aléatoire, c’est un domaine de niche où on peut apprendre encore beaucoup en expérimentant des choses qui n’ont pas encore été testées au point de pouvoir les casser.

Il est facile de ne pas voir de motif redondant dans un échantillon, pour peu que vous vouliez qu’il soit aléatoire. Ce qui est intéressant, c’est quand vous pouvez en détecter vous-même après que quelqu’un d’autre l’ait fait. Il s’agit de prouver que vous tests veulent bien dire ce que vous voulez leur faire dire, ou éventuellement de prouver que les tests des autres n’ont pas été interprétés correctement.

Le SDR est un bon outil pour cela, parce que son fonctionnement couplé à un ordinateur permet de se positionner dans des cas de figure où vous savez que la donnée d’entrée est biaisée, et de le montrer par vos tests statistiques. Une fois cela réalisé, vous pourrez changer de fréquence jusqu’à ce que vos tests soient négatifs.

Il est important de calibrer vos tests, et d’avoir une idée de leurs limites et comportements. Parce qu’il existe des choses qui n’ont pas l’air aléatoires mais qui le sont (un lapin dans les nuages, le visage de jésus dans un mur fissuré, une pièce de monnaie qui tombe du même coté, etc). Tout comme il existe des choses qui ont l’air aléatoires alors que les mathématiques sous-jacentes prouvent le contraire. Nos propres expérimentations nous ont montré que pas mal de choses sont contre-intuitives dans ce domaine, jusqu’à ce que nous arrivions à les expliquer.

Faire tout cela sera bien plus facile et moins coûteux que ce que nous avons nous-même fait avec des permutations dans les circuits matériels pour aboutir au Bitbabbler.