Différence entre la théorie et la pratique de la sécurité et de la cryptographie?

Quelles différences intéressantes y a-t-il entre la théorie et la pratique de la sécurité et de la cryptographie?

Le plus intéressant sera bien sûr des exemples qui suggèrent de nouvelles voies de recherche théorique basées sur l'expérience pratique :).

Les réponses peuvent inclure (mais sans s'y limiter):

• Exemples où la théorie suggère que quelque chose est possible mais qu'il n'est jamais utilisé dans la pratique
• Exemples où la théorie suggère que quelque chose est sûr qui ne l'est pas dans la pratique
• Les exemples de quelque chose largement utilisé dans la pratique ont peu de théorie derrière.

...

Caveat

Si votre réponse est essentiellement de la forme «La théorie concerne l'asymptotique, mais la pratique ne l'est pas», alors soit la théorie devrait être vraiment centrale, soit la réponse devrait inclure des exemples spécifiques où l'expérience pratique sur des instances du monde réel diffère des attentes basées sur sur la théorie.

Je connais un exemple: l'évaluation de circuits sécurisés. Très puissant en théorie, mais trop compliqué pour être utilisé dans la pratique, car cela impliquerait de prendre votre code, de le dérouler dans un circuit, puis de faire une évaluation sécurisée de chaque porte une à la fois.

Oh mon garçon, par où commencer.

Le gros est définitivement les boîtes noires. Les chercheurs en cryptographie font des histoires sur des choses comme le problème d'instabilité du modèle Oracle aléatoire. Les chercheurs en sécurité sont à l'autre extrême et aimeraient que tout soit utilisable comme boîte noire, pas seulement les fonctions de hachage. C'est une source constante de tension.

Pour illustrer, si vous regardez l'analyse formelle des protocoles de sécurité, par exemple la logique BAN , vous verrez que le chiffrement symétrique est traité comme un «chiffrement de bloc idéal». Il y a une distinction subtile ici - la logique BAN (et d'autres techniques d'analyse de protocole) ne prétend pas être des preuves de sécurité; ce sont plutôt des techniques pour trouver des failles. Par conséquent, il n'est pas strictement vrai que le modèle de chiffrement idéal soit impliqué ici. Cependant, il est empiriquement vrai que la plupart des analyses de sécurité ont tendance à se limiter au modèle formel, donc l'effet est le même.

Nous n'avons même pas encore parlé des pratiquants. Ces gars n'ont généralement même pas la moindre idée que les primitives de crypto ne sont pas destinées à être des boîtes noires, et je doute que cela changera jamais - des décennies d'essayer de se battre dans la tête n'ont fait aucune différence.

Pour voir à quel point le problème est grave, considérez cet avis de sécurité relatif à l'exonération de signature des API. Le bug est en partie dû à l'attaque d'extension de longueur dans la construction Merkle-Damgard (qui est vraiment quelque chose de vraiment basique), et affecte Flickr, DivShare, iContact, Mindmeister, Myxer, RememberTheMilk, Scribd, Vimeo, Voxel, Wizehhive et Zoomr. Les auteurs notent qu'il ne s'agit pas d'une liste complète.

Je pense que les pratiquants méritent la part du lion de la responsabilité de cette triste situation. D'un autre côté, peut-être que les théoriciens de la cryptographie doivent également repenser leur position. Leur ligne a été: "les boîtes noires sont impossibles à construire; nous n'allons même pas essayer." Pour ce que je dis, puisqu'il est clair que vos constructions vont de toute façon être (mal) utilisées comme boîtes noires, pourquoi ne pas au moins essayer de les rendre aussi proches que possible des boîtes noires?

Le document Merkle-Damgard Revisited est un excellent exemple de ce dont je parle. Ils étudient la notion de sécurité selon laquelle "la fonction de hachage de longueur arbitraire H doit se comporter comme un oracle aléatoire lorsque le bloc de construction de longueur fixe est considéré comme un oracle aléatoire ou un chiffrement de bloc idéal". Ce type de recherche théorique peut être extrêmement utile dans la pratique.

Passons maintenant à votre exemple d'évaluation de circuit. Je vous prie de ne pas être d'accord avec votre raisonnement. Ce n'est pas comme si vous preniez un binaire compilé et le transformiez aveuglément en circuit. Au lieu de cela, vous appliqueriez l'évaluation du circuit uniquement à la fonction de comparaison sous-jacente, ce qui est généralement assez simple. Fairplay est une implémentation de l'évaluation de circuits. Un de mes collègues qui a travaillé avec lui me dit que c'est étonnamment rapide. S'il est vrai que l'efficacité est un problème avec l'évaluation des circuits (et je connais des cas concrets où elle a été rejetée pour cette raison), elle est loin d'être incontournable.

La deuxième raison pour laquelle je ne suis pas d'accord avec vous est que si vous pensez à certains des scénarios typiques de la vie réelle dans lesquels vous pourriez éventuellement vouloir effectuer une évaluation de circuit inconsciente - par exemple, lorsque deux sociétés cherchent à fusionner - les coûts de calcul impliqués sont insignifiants par rapport à l'effort humain global et au budget.

Alors pourquoi personne n'utilise-t-il en pratique une évaluation générique des fonctions sécurisées? Grande question. Cela m'amène à ma deuxième différence entre la théorie et la pratique: la confiance existe réellement dans la pratique! Tout ne doit pas être fait dans le modèle paranoïaque. L'ensemble des problèmes que les gens veulent réellement résoudre en utilisant la cryptographie est beaucoup, beaucoup plus petit que ce que les cryptographes imaginent.

Je connais quelqu'un qui a démarré une entreprise en essayant de vendre des services de calcul multipartites sécurisés à des clients d'entreprise. Devinez quoi - personne ne le voulait. La façon dont ils abordent ces problèmes consiste à signer un contrat spécifiant ce que vous pouvez et ne pouvez pas faire avec les données, et que vous détruirez les données une fois que vous aurez fini de les utiliser aux fins prévues. La plupart du temps, cela fonctionne très bien.

Mon dernier point de différence entre la théorie et la pratique concerne l'ICP. Les documents cryptographiques collent souvent une phrase quelque part disant "nous supposons une ICP". Malheureusement, les certificats numériques pour les utilisateurs finaux (par opposition aux sites Web ou aux employés dans un contexte d'entreprise, où il existe une hiérarchie naturelle) ne se sont jamais matérialisés. Cet article classique décrit l'hilarité qui s'ensuit lorsque vous demandez à des gens normaux d'utiliser PGP. On me dit que le logiciel s'est beaucoup amélioré depuis lors, mais les problèmes de conception et d'architecture sous-jacents et les limites humaines ne sont pas très différents aujourd'hui.

Je ne pense pas que les cryptographes devraient faire quoi que ce soit différemment en raison de ce manque d'ICP du monde réel, sauf pour être conscient du fait qu'il limite l'applicabilité dans le monde réel des protocoles cryptographiques. Je l'ai jeté parce que c'est quelque chose que j'essaie de réparer.

La réponse de Randomwalker est très bonne. Mon écart préféré entre la théorie et la pratique est le modèle d'oracle aléatoire. Cela semble une heuristique très sécurisée dans la pratique (en supposant que les gens ne font pas quelque chose de stupide et au moins font correctement l'extension de la longueur, voir également la réponse de randomwalker), mais nous n'avons pas de résultats théoriques positifs à ce sujet. En fait, tous les résultats théoriques de cette heuristique sont négatifs. Je pense que c'est une grande question de recherche et j'espère qu'un jour des résultats positifs intéressants sur ce modèle seront prouvés.

En ce qui concerne l'obfuscation pour autant que je sache, même dans la pratique, bien qu'il soit largement utilisé, l'obfuscation n'est pas considéré comme aussi sûr que le cryptage, et il n'est pas considéré comme prudent d'utiliser l'obfuscation pour cacher un secret à long terme et très sensible. (Par opposition au chiffrement utilisant un oracle aléatoire, que les gens sont tout à fait à l'aise d'utiliser pour cela.) Donc, dans ce sens, l'écart entre la théorie et la pratique n'est pas aussi grand. (c'est-à-dire que l'obscurcissement est un domaine extrêmement intéressant que nous sommes loin de comprendre à la fois en théorie et en pratique.)

Le chiffrement homomorphique et la communication multipartite sécurisée sont deux des grandes découvertes récentes en cryptographie qui n'ont pas encore été suffisamment étudiées pour être pratiques: des efforts de recherche comme PROCEED vont dans ce sens pour identifier le type de modèle de programmation que nous pourrions utiliser pour écrire ceci sorte de calcul, ainsi que de trouver des optimisations pour les algorithmes cryptographiques de base qui les font fonctionner dans un délai raisonnable. C'est un phénomène assez courant en cryptographie: nous commençons avec des algorithmes (relativement) simples qui prennent beaucoup de temps à exécuter, puis les cryptographes passent des années à utiliser les mathématiques pour optimiser de plus en plus les algorithmes.

Exemples où la théorie suggère que quelque chose est possible mais qu'il n'est jamais utilisé dans la pratique:

Il est assez facile de trouver des exemples de choses qui sont résolues en théorie mais (1) sont trop inefficaces pour être utilisées dans la pratique ou (2) personne ne se soucie de lui. Exemples: (1) preuves (génériques) à connaissance nulle, (2) signatures indéniables. En fait, regardez n'importe quelle conférence sur la cryptographie et au moins la moitié des articles tomberont probablement dans l'une de ces catégories.

Exemples où la théorie suggère que quelque chose est sûr qui ne l'est pas dans la pratique:

Cette question est un peu vague, donc je ne sais pas si cela y répond - mais il existe de nombreux exemples de schémas `` prouvés sécurisés '' qui sont brisés dans la pratique parce que la définition de la sécurité ne correspond pas au scénario de déploiement. Au cours des dernières années seulement, il y a eu des attaques contre (des variantes prouvables de) SSH et IPSec, entre autres.

Des exemples de quelque chose dans une utilisation pratique répandue ont peu de théorie derrière cela:

Je suppose que vous voulez dire dans le monde de la cryptographie, pas dans le monde de la sécurité générale. Un bon exemple est les signatures DSS, qui n'ont aucune preuve de sécurité.

$M$$M'$$M'$$w \iff M$$w$$M'$$w \iff M$$w$$M'$$M$$M'$$M$

Il existe de nombreuses sociétés commerciales qui proposent des solutions d'obscurcissement binaire, et il existe également plusieurs solutions open source. Bien entendu, les méthodes exactes d'obscurcissement sont gardées secrètes; le paradigme de l'obfuscation répandu dans l'industrie est heuristique, donc connaître les algorithmes utilisés pour obscurcir un binaire dans ce contexte garantira généralement un certain avantage dans la désobfuscation. L'obfuscation dans l'industrie est connue sous le nom de «sécurité par l'obscurité».

Il existe des approches théoriques au problème de l'obscurcissement qui formalisent les désirs de l'industrie mais reposent sur une notion de sécurité strictement plus forte basée sur l'intractabilité informatique (imaginez remplacer les tests d'équivalence d'entiers et de chaînes par des tests d'équivalence de fonction unidirectionnelle). En particulier, l'étude de l' obscurcissement ponctuel composable a été avancée pour tenter de résoudre le problème d'obscurcissement intéressant l'industrie. Malheureusement, le modèle théorique le plus répandu pour l'obscurcissement basé sur un modèle inspiré par du matériel inviolable a obtenu un résultat d'impossibilité en 2001 par Barak et al dans l'article " Sur la (im) possibilité d'obscurcir les programmes ". (Depuis, plusieurs autres modèles ont également obtenu des résultats d'impossibilité).

À l'heure actuelle, la théorie de l'obscurcissement du programme est en pleine évolution, nécessitant un nouveau modèle (probablement moins restrictif). En fait, le principal problème de la théorie est son absence d'un modèle convenu (et donc de bénévoles formels). L'avènement récent du cryptage entièrement homomorphe peut fournir une telle base (il s'agit purement de spéculations de la part de cet auteur).

Pour clarifier, l'obscurcissement correspond à votre troisième exemple: "Les exemples de quelque chose dans une utilisation pratique répandue ont peu de théorie derrière cela." L'obfuscation est largement utilisée aujourd'hui par l'industrie et par ceux qui ont des buts plus néfastes. L'obfuscation dans l'industrie n'est actuellement basée sur aucune théorie rigoureuse malgré les tentatives.

Il existe un écart important, même en ce qui concerne les primitives de base telles que les générateurs pseudo-aléatoires. Prenons par exemple les fonctions pseudo-aléatoires. Dans la pratique, les gens utilisent des choses comme AES , qui diffèrent des candidats théoriques (Goldreich, Goldwasser, Micali; Naor, Reingold; etc.) selon plusieurs dimensions: Premièrement, les paramètres sont complètement différents, par exemple AES peut avoir une longueur de clé égale à la longueur d'entrée , ce qui est inconnu dans les constructions théoriques. Peut-être plus important encore, AES (et de nombreux autres chiffrements par blocs) suivent le paradigme du réseau dit de substitution-permutation qui est assez différent de la façon dont les constructions théoriques se déroulent (par exemple celles mentionnées ci-dessus).

Le plus intéressant sera bien sûr des exemples qui suggèrent de nouvelles voies de recherche théorique basées sur l'expérience pratique :).

Je pense que ce qui précède est un tel exemple, voir par exemple cet article avec Eric Miles (dont essentiellement cette réponse est tirée).