Des générateurs pseudo-aléatoires théoriquement solides sont-ils utilisés dans la pratique?

17

Pour autant que je sache, la plupart des implémentations de la génération de nombres pseudo-aléatoires utilisent des méthodes telles que les registres de rétroaction à décalage linéaire (LSFR), ou ces algorithmes "Mersenne Twister". Bien qu'ils passent de nombreux tests statistiques (heuristiques), il n'y a aucune garantie théorique qu'ils semblent pseudo-aléatoires pour, disons, tous les tests statistiques efficacement calculables. Pourtant, ces méthodes sont utilisées sans discernement dans toutes sortes d'applications, allant des protocoles cryptographiques au calcul scientifique en passant par la banque (probablement). Je trouve quelque peu inquiétant que nous ayons peu ou pas de garantie que ces applications fonctionnent comme prévu (car toute sorte d'analyse aurait probablement supposé un vrai caractère aléatoire en entrée).

D'un autre côté, la théorie de la complexité et la cryptographie fournissent une théorie très riche de la pseudo-aléatoire, et nous avons même des constructions candidates de générateurs de pseudo-aléatoire qui tromperaient TOUT test statistique efficace que vous pourriez trouver, en utilisant des fonctions unidirectionnelles candidates.

Ma question est: cette théorie a-t-elle fait son chemin dans la pratique? J'espère que pour des utilisations importantes de l'aléatoire, telles que la cryptographie ou le calcul scientifique, des PRG théoriquement solides sont utilisés.

En passant, je pourrais trouver une analyse limitée de la façon dont les algorithmes populaires tels que le tri rapide fonctionnent lorsque vous utilisez les LSFR comme source de hasard, et apparemment, ils fonctionnent bien. Voir les «algorithmes randomisés et nombres pseudo-aléatoires» de Karloff et Raghavan .

Henry Yuen
la source
3
Il existe même un PRG universel - il est sécurisé s'il existe des PRG sécurisés.
Voulez-vous dire des PRG cryptographiques? Si oui, alors ne savons-nous pas que les PRG (cryptographiques) sont équivalents aux OWF?
Henry Yuen
2
Oui. kkkk2 remplir les sorties k+1 bits, et sortir le xor de ces sorties TM. (Tout comme la recherche universelle de Levin, cela ne peut pas être utilisé dans la pratique.)
1
les résultats liés au caractère aléatoire requis pour le hachage sont peut-être plus pertinents pour la pratique: des familles d'indépendance bornées classiques aux résultats plus récents comme Mitzenmacher-Vadhan (l'indépendance par paire + une entropie en entrée donne une pseudo-aléatoire suffisante pour les sondes linéaires et les filtres de floraison) ou le Patrascu -Thorup résultats sur le hachage de tabulation.
Sasho Nikolov
1
"Pourtant, ces méthodes sont utilisées sans discernement dans toutes sortes d'applications, allant des protocoles cryptographiques ...". J'espère que non. Mersenne Twisters ne doit pas être utilisé pour la cryptographie car ils ne sont pas cryptographiquement solides, bien qu'il puisse y avoir des variantes .
Mike Samuel

Réponses:

13

La notion de générateurs pseudo-aléatoires "théoriquement solides" n'est pas vraiment bien définie. Après tout, aucun générateur pseudo-aléatoire n'a de preuve de sécurité. Je ne sais pas si nous pouvons dire qu'un générateur pseudo-aléatoire basé sur la dureté de la factorisation de grands entiers est "plus sûr" que, disons, en utilisant AES comme générateur pseudo-aléatoire. (En fait, on a le sentiment qu'il est moins sûr, car nous connaissons des algorithmes de factorisation quantique mais pas des algorithmes quantiques pour briser l'AES.)

Nous avons des preuves mathématiques pour différents résultats de composition, en disant que si vous composez des chiffrements par blocs ou des fonctions de hachage de certaines manières, vous pouvez obtenir des générateurs pseudo-aléatoires ou une fonction pseudo-aléatoire. Certains de ces résultats sont largement utilisés dans la pratique, par exemple HMAC . Mais il est vrai que les résultats qui atteignent un PRG et commencent simplement en supposant que le composant de base est une fonction unidirectionnelle simple ne sont pas assez efficaces pour être utilisés pour les applications (et cela est au moins en partie inhérent). Donc, généralement, nous devons assumer une fonction PRG / stream cipher / block-cipher / hash comme une primitive de base et commencer à en construire d'autres. Le problème ne concerne pas vraiment l'analyse asymptotique, car pratiquement toutes les réductions cryptographiques (à l'exception peut-être du PRG universel de Levin) peuvent être concrétisées et donner ainsi des garanties concrètes sous des hypothèses concrètes.

Mais même si elles ne sont pas basées sur des fonctions à sens unique, il y a un sens dans lequel les constructions telles que AES sont "théoriquement solides" parce que: (1) Il existe des conjectures formelles concernant leur sécurité. (2) Il y a du travail pour essayer de réfuter ces conjectures, et aussi d'en tirer des implications.

Et en effet, les gens sont conscients que pour de nombreuses applications, il ne serait pas intelligent d'utiliser des PRG tels que LSFR qui ne satisfont pas (1) et (2) ci-dessus.

Boaz Barak
la source
1
Je suppose que vous vouliez créer un lien vers l'un des documents de Jonathan Katz en place vers sa page Web. Btw, aimeriez-vous que nous fusionnions cela avec votre autre compte ?
Kaveh
9

Vous semblez confondre théorie et pratique. Un générateur pseudo-aléatoire théoriquement solide ne convient pas pour une utilisation pratique pour plusieurs raisons:

  • C'est probablement très inefficace.
  • La preuve de sécurité est uniquement asymptotique, et donc pour le paramètre de sécurité particulier utilisé, le générateur pseudo-aléatoire peut être facile à briser.
  • Toutes les preuves de sécurité sont conditionnelles, donc dans un certain sens, elles ne satisfont même pas la notion de sécurité théorique.

Contrairement à cela, les générateurs pseudo-aléatoires réels sont rapides et se déclinent en différentes saveurs en fonction de leur utilisation. Pour une utilisation non cryptographique, presque tout autre chose qu'un simple LFSR fera le travail - pas de manière prouvable, mais dans la pratique (ce qui est plus important pour les personnes utilisant des choses en réalité).

Pour une utilisation cryptographique, les gens essaient d'être plus intelligents. À ce stade, votre critique est logique: nous ne pouvons pas savoir qu'un générateur pseudo-aléatoire utilisé est "sûr", et en effet certains anciens ont été cassés, par exemple RC4 tel qu'il est utilisé dans WEP. Cependant, pour les raisons indiquées ci-dessus, l'utilisation d'un générateur pseudo-aléatoire théoriquement (conditionnellement) n'est malheureusement pas une solution réaliste. Au lieu de cela, la communauté cryptologique s'appuie sur un «examen par les pairs» - d'autres chercheurs qui tentent de «casser» le système (leur définition du moment où un chiffre est rompu est très large).

Enfin, dans les applications où l'argent peut être investi et la sécurité est suffisamment importante - disons les codes nucléaires - les gens utilisent du bruit généré physiquement (passé par un extracteur de hasard), même si cela n'est pas au-delà des critiques théoriques.


Lorsque les chercheurs rédigent des propositions de subvention ou des introductions à des articles, ils affirment souvent que leur recherche se rapporte et informe la pratique. Qu'ils y croient ou que ce soit du bout des lèvres, je ne sais pas (et cela peut dépendre du chercheur), mais vous devez être conscient que la connexion est grandement exagérée dans les milieux universitaires, pour des raisons évidentes.

Une chose qui nous limite en tant que chercheurs en mathématiques est notre attachement dogmatique à la preuve formelle. Vous mentionnez l'analyse d'algorithmes randomisés alimentés par de simples générateurs pseudo-aléatoires. Ce type d'analyse ne peut être étendu aux problèmes du monde réel, car ils sont tout simplement trop compliqués. Et pourtant, dans la pratique, les gens résolvent tout le temps même des problèmes difficiles avec des méthodes éclairées.

Les problèmes du monde réel sont mieux compris avec un œil plus scientifique et expérimental. Ils sont mieux résolus du point de vue de l'ingénierie. Ils inspirent la recherche théorique et en sont parfois informés. Comme l'a dit Dijsktra, l'informatique (théorique) ne concerne pas vraiment les ordinateurs, pas plus.

Yuval Filmus
la source
Merci pour votre réponse, Yuval. Cependant, je ne crois pas entièrement que les constructions de générateurs pseudo-aléatoires à partir de la cryptographie soient pratiquement inefficaces. Pour autant que je sache, personne n'a fait d'étude à ce sujet.
Henry Yuen
2
Je suis également en désaccord avec l'affirmation générale selon laquelle les générateurs pseudo-aléatoires standard suffisent à des "fins quotidiennes". Comme le récent document "Ron avait tort, Whit avait raison" l'a montré, une génération de pseudo-aléatoire défectueuse a conduit à des vulnérabilités embarrassantes pour un nombre non négligeable de personnes. Cette analyse particulière était assez simple; combien d'applications «réelles» peuvent souffrir de vulnérabilités plus subtiles car les LSFR ne sont pas adéquats? Si les frais de calcul supplémentaires nécessaires pour des PRG théoriquement solides ne sont pas si importants, pourquoi ne pas les utiliser?
Henry Yuen
1
Les LSFR @HenryYuen ne sont pas utilisés pour des applications cryptographiques dans un système moderne et décent. (Bien sûr, il existe des systèmes mal conçus, comme le GSM qui est enseigné dans les cours d'introduction comme comment ne pas le faire.) Les problèmes trouvés dans le papier "Ron avait tort, Whit a raison" n'étaient pas de la qualité de PRNG eux-mêmes, mais avec la qualité de la collecte d'entropie.
Gilles 'SO- arrête d'être méchant'