La sécurité informatique absolue n’existe pas !

Démonstration complète, rédigée de manière à être accessible par le plus grand nombre.

Partager sur:
Sauvegarder cet article
Aimer cet article 0
Anonymous Hacker - Credits Brian Klug (CC BY-NC 2.0)

Promouvoir la liberté n’est pas gratuit

Mais cela peut aider à réduire vos impôts de 66%

Faites un don dès maintenant

Faire un don

La sécurité informatique absolue n’existe pas !

Publié le 20 avril 2015
- A +

Par Thierry Berthier

Anonymous Hacker - Credits Brian Klug (CC BY-NC 2.0)
Anonymous Hacker – Credits : Brian Klug via Flickr (CC BY-NC 2.0)

 

On entend souvent dire que la sécurité absolue en matière d’informatique n’existe pas. Ceux qui prononcent cette phrase ne savent pas forcément justifier cette vérité qui s’appuie avant tout sur un résultat purement mathématique. Il peut être utile et agréable (car le côté esthétique de la preuve est bien présent) de reproduire sa démonstration mathématique. Il s’agit d’une preuve standard bien connue des étudiants des Masters en informatique – calcul formel – cryptographie. Elle est suffisamment courte et simple pour être lue et comprise par un lecteur non spécialiste doté d’un bac scientifique. Elle ne nécessite aucun pré-requis particulier et c’est là tout son charme ! Le cryptologue français David Naccache (ENS Paris) l’utilise régulièrement dans ses interventions sur la sécurité numérique et parvient à la présenter de manière « décontractée » sans pour autant perdre la rigueur mathématique en cours de route. C’est une performance assez rare pour être soulignée. Prouvons maintenant que la sécurité absolue en informatique n’existe pas.

Une belle preuve inspirée des conférences de David Naccache

Si cette sécurité absolue existait, on disposerait alors d’un analyseur magique M capable de dire sans jamais se tromper pour tout programme P si ce programme est sûr ou non. On aurait en terme fonctionnel pour tout programme P :

M(P) renvoie 1 si le programme est jugé sûr par M et M(P) renvoie 0 s’il est jugé non sûr par M.

Dire que la sécurité absolue existe c’est affirmer que l’analyseur magique existe. C’est aussi se dire qu’on ne l’a pas encore trouvé aujourd’hui mais que dans quelques temps (années ou siècles), après de laborieux efforts algorithmiques, on le découvrira.

Montrons que cet analyseur magique n’existe pas et n’existera jamais même dans un futur éloigné. Pour montrer que M n’existe pas, on va d’abord établir un résultat bien connu d’Alan Turing (qui a tout démontré ou presque) lié au problème de l’arrêt d’un programme.

1 – Le problème de l’arrêt (Turing)

Étant donné un programme arbitraire P (quelconque), il n’existe pas de moyen systématique de dire si ce programme va se terminer sur une entrée ou s’il va boucler et calculer indéfiniment sur cette entrée sans jamais s’arrêter ni donner un résultat. Ce résultat majeur de Turing peut sembler anodin pour celui qui le découvre pour la première fois, il est pourtant fondamental et constitue le fondement d’autres résultats d’une très grande profondeur. Là encore, il est possible de le démontrer à peu de frais.

On procède par l’absurde (comme on dit au lycée) et l’on suppose que l’on dispose d’un programme A capable d’analyser un programme P et une donnée d’entrée x de la façon suivante :

A( P,x ) = 1 si P se termine lorsqu’on lui donne x en entrée
et
A( P, x ) = 0 si P ne se termine pas lorsqu’on lui donne x en entrée

Notre programme A est donc capable de détecter pour tous les programmes P du monde existant et à venir s’ils s’arrêtent sur une entrée x ou non.

À partir de ce programme A, nous allons construire un super programme B qui fait quelque chose de très simple. Par définition de B :

Si A( x, x ) = 0 alors B( x ) = 1
Si A( x, x ) = 1 alors B( x ) tourne indéfiniment sans jamais s’arrêter et sans donner le moindre résultat.

Construire le programme B à partir de notre programme A initial est très simple, il suffit d’écrire par exemple :

int B( Program x)
{
if ( A(x,x) == 0 ) return (1)
else
{ while(true) {} }
}

Une fois ce programme B construit, nous nous interrogeons sur la valeur de B ( B ) (B appliqué à B).

Que vaut B(B) ?

Il n’y a que deux cas possibles :

Cas N°1 : B( B ) = 1

Si B( B ) = 1 alors en remontant à la définition de B, on voit que A( B , B ) = 0 ce qui signifie que B ne s’arrête pas (il boucle pour toujours) lorsqu’on lui donne B en entrée. Ceci est absurde puisque B(B) = 1.

Cas N°2 : B( B ) ne s’arrête pas

Si B( B ) ne s’arrête pas alors A( B,B ) = 1 et B( B ) se termine, ce qui est encore absurde.

Les deux cas possibles conduisent à une absurdité, c’est donc que notre hypothèse initiale n’est jamais vérifiée. Notre programme A n’existe pas ! (cqfd).

2 – Notre analyseur magique M n’existe pas

Le gros du travail a été réalisé dans la partie 1 sur le problème de l’arrêt. Nous allons encore procéder par l’absurde dans cette dernière partie. Supposons que la société de sécurité AbsoluteSecurity (je viens d’inventer le nom à l’instant, il n’y a pas de sens caché) dispose un jour d’un analyseur magique M capable de détecter si un programme quelconque P est sûr ou non et qu’il puisse le faire pour tout programme P.

Construisons spécialement pour cette société arrogante le petit programme suivant qui comporte trois lignes :

Dans l’ordre d’exécution du programme, la première ligne génère une clé très secrète notée « Verysecretkey ». La ligne suivante fait appel à un programme P’ quelconque et la troisième ligne imprime et affiche à l’écran la clé très secrète :

verysecretkey = newkey( );
P'( );
System.out.println( verysecretkey);

Observons maintenant le fonctionnement de ce petit programme de trois lignes :

Si le programme P'( ) ne boucle pas indéfiniment, cela signifie nécessairement que notre petit programme est totalement vulnérable (donc non sûr) puisqu’il va afficher au public notre clé très secrète dès que P’ aura terminé son exécution, c’est-à-dire au bout d’un temps fini.

Si au contraire le programme P'( ) ne s’arrête pas et boucle pour toujours, la troisième instruction du petit programme ne sera jamais exécutée et notre clé très secrète ne sera jamais dévoilée. Dans ce cas, notre petit programme est très sûr puisqu’il n’affiche pas la clé.

Utilisons maintenant l’analyseur magique de la société arrogante AbsoluteSecurity sur notre petit programme de trois lignes. L’analyseur magique fonctionne pour tous les programmes P donc en particulier pour notre petit programme. Il est donc capable de dire s’il est sûr ou non, c’est-à-dire de décider si le programme P'( ) de la seconde ligne s’arrête ou pas. Or, on a démontré dans la partie 1 que ce type de programme n’existe pas.

Conclusion 1 : la société AbsoluteSecurity est effectivement arrogante car elle ment sur son analyseur magique M qui n’est pas en mesure d’analyser tous les programmes !

Conclusion 2 : La sécurité absolue n’existe pas !

Conseil au lecteur : il ne faut pas hésiter à lire et relire cette démonstration plusieurs fois tant que la chose ne semble pas limpide. La relecture est un petit effort intellectuel au regard de la puissance du résultat…

Voir les commentaires (23)

Laisser un commentaire

Créer un compte Tous les commentaires (23)
  • La puissance du résultat ? Moi, il m’a toujours paru évident qu’il fallait être naïf ou fêlé pour croire à des généralités absolues du style « l’informatique peut garantir une sécurité absolue ». Il m’a aussi paru évident, mais là je suis peut-être original, que l’amélioration de la sécurité était bien plus facile par des actions individuelles reposant sur le bon sens et l’astuce, éventuellement aidées par l’informatique mais sans plus, que par l’abandon des systèmes au contrôle de logiciels.

    • Oui, oui, bien que formel, ce résultat est puissant au même titre que la forme faible du théorème de Gödel liée à l’arrêt elle aussi. Le truc nous dit seulement qu’il faut rester humble face au désir de globaliser un système de défense numérique. Le facteur humain, les vulnérabilités de celui qui clique un jour ou l’autre sur la mauvaise URL (vous, moi, absolument tout le monde) sont bien plus concrètes que ce résultat formel et ce sont bien ces vulnérabilités humaines qui rendent possible l’essentiel des cyber-agressions actuelles.

    • « que l’amélioration de la sécurité était bien plus facile par des actions individuelles reposant sur le bon sens »

      Discutable. La sécurité de l’ensemble est aussi forte que celle du plus faible de ces maillons. Les actions individuelles ne seront donc efficaces que si tout le monde les appliques. Mais à ce moment-là, peut-on encore parler d’actions individuelles?

  • Cette démonstration suppose qu’on a besoin de programmes ou de langages complets au sens de Turing. Il me semblait, d’après ce que j’entends venant de spécialistes de la théorie des langages de programmation, qu’un mouvement de fond déplaçait de plus en plus les usages vers l’utilisation de langages totaux (je ne connais pas le terme utilisé en français), pour lesquels le problème de l’arrêt ne se pose pas.

    Ce qui bien entendu n’invalide pas nécessairement la thèse de l’article, mais pour des arguments bien différents. La majorité des problèmes de sécurité ne provient-elle pas de la possibilité du social engineering?

    • On parle dans cette preuve d’analyse statique d’un programme qui est équivalente au problème de l’arrêt.
      C’est dans ce sens qu’il faut entendre ce résultat formel qui a le mérite de « calmer » certaines ambitions fonctionnelles. Ensuite, effectivement, vous avez parfaitement raison, l’ingénierie sociale et plus généralement le FACTEUR HUMAIN sont les principaux vecteurs des cyberattaques. Plus de 90 % des attaques actuelles s’appuient sur du social engineering… E fait nous cliquons tous un jour ou l’autre là où il ne faut pas cliquer !

      • J’ai bien compris l’objet de la démonstration, mais ma question est la suivante : a-t-on concrètement besoin d’hypothèses aussi fortes/générales ? Ne peut-on pas réduire les programmes que nous écrivons (ou du moins les programmes les plus critiques) à un sous-ensemble non-Turing complet dont la sécurité sera démontrable ?

        Il me semble qu’il ne faut pas perdre de vue que dans l’infinité de programme Turing complets à la sécurité indémontrable, il y en a beaucoup qui ne nous viendraient jamais à l’idée d’écrire, car ils n’ont aucun intérêt pratique.

        C’est de ce type d’ambitions fonctionnelles que vous parlez : http://en.wikipedia.org/wiki/Total_functional_programming ? Si oui, il me semble qu’elles reposent justement sur la connaissance du résultat énoncé dans l’article, et donc qu’elles représentent une évolution logique (c’est le cas de le dire).

        • Oui, parce que dans la réalité, tout est finalement implémenté sur un ordinateur, qui est une machine de Turing. (les systèmes formels ne pouvant engendrer que des systèmes formels)

          Les soi-disant programmes fonctionnels ne sont que des approximations asymptotiques.

          Il suffit de couper l’horloge du processeur pour que tout s’écroule … démonstration assez rudimentaire mais efficace pour expliquer ce que l’article démontre.

        • Le résultat en question est général et s’appuie sur une construction formelle. Il ne dit rien sur des sous-ensembles de programmes prouvables (dont la sécurité est affirmée par l’analyseur universel).
          Même si l’on réduit l’espace aux programmes critiques réalisant des sorties « utiles », le problème de décider de la sureté de P reste extrêmement complexe lorsque la taille de P augmente. On arrive à de la complexité exponentielle en la taille.

  • hum… très joli preuve, mais qui prouve seulement que la sécurité informatique absolue « générale » ET « prouvée » n’existe pas. Ça n’interdit pas l’existence d’une sécurité absolue particulière, limité à un sous ensemble fini de programme, dans des conditions limitativement défini, et ça n’itnerdit pas non plus une sécurité qu’on ne peut pas prouver (théorème de Gödel : on ne peut pas prouver toutes les propositions vraies ; il est ainsi possible qu’un système soit absolument sûr sans qu’on puisse le prouver) . dit autrement : le fait qu’il n’existe pas de programme P capable de conclure pour tout programme n’interdit pas l’existence d’un programme P qui ne fonctionne que pour certaines classes de programme, et l’existence d’un programme P n’est même pas nécessaire à la sécurité absolue.
    Par exemple, une paire couplée de machine enigma à usage unique dont la clef est stocké de manière physique est informatiquement incraquable pourvu que le message échangé soit plus court que la clef (et on peut faire des clefs très, très longue !) et l’accès physique à la boite soit efficacement interdit. Non ?

    • D’accord avec vous; lorsqu’on restreint l’ensemble des programmes (par exemple ceux de taille < N réalisant une classe de calculs bien définie; ils sont alors en nombre fini), le contexte de calcul et de preuve n'est effectivement plus le même. D'accord avec vous également sur la fin de votre commentaire qui concerne la cryptographie. En fait, il ne faut pas faire dire plus au résultat formel du billet que ce qu'il nous dit. C'est aussi une façon de fixer une borne lointaine certes mais qui existe bien.
      Dans la réalité des attaques, ce sont souvent des choses très triviales (loin de la cryptographie) qui sont mises en œuvre pour pénétrer un système. On est alors très loin des résultats du calcul formel…

    • « Par exemple, une paire couplée de machine enigma à usage unique dont la clef est stocké de manière physique est informatiquement incraquable pourvu que le message échangé soit plus court que la clef (et on peut faire des clefs très, très longue !) et l’accès physique à la boite soit efficacement interdit. Non ? »

      Mais même là. Vous ne pouvez pas trouver de failles, peut-être même que personne ne peut trouver de failles, mais ça ne veut pas dire qu’il n’y en a pas. Et quelqu’un de plus intelligent que vous pourrait trouver une de ces failles. Tant qu’on a pas de preuve formelle de la sécurité de cet algorithme en particulier, on doit (ou du moins on ferait mieux, si on souhaite l’utiliser) partir du principe qu’il n’est pas fiable à 100% (du point de vue de la sécurité).

      La question devient donc: si on détient un programme 100% sécurisé, est-on en mesure de le savoir avec certitude.

      • « est-on en mesure de le savoir avec certitude. » Évidemment non, on ne peut rien savoir avec certitude. exiger une certitude à cet égard relève de la folie pure. Les « preuves » mathématiques (et algorithmiques) ne sont pas des preuves empiriques, se sont des constructions formelles basées sur des hypothèses appelées « axiomes ». Vous êtes toujours obliger de faire l’hypothèse que ses axiomes représentent correctement la réalité, mais ce n’est jamais qu’une hypothèse improuvable.

  • Pour être plus terre à terre, que P’ finisse ou pas, vous collez un point d’arrêt juste avant et suffit de lire ce qu’il y a en mémoire (que ce soit avec un outil spécialisé Java si c’est dans une JVM ou avec un debugger / désassembleur hard ou soft si c’est du natif).

    question subsidiaire: est-ce qu’un programme qui sait mesurer de façon absolu le temps pris pour un autre programme peut exister ? Non, ça empêche pas l’utilisation de « time », de « callgrind » ou « perf » 😀

  • Pas besoin de faire si compliqué, prenez n’importe quelle méthodologie de « sécurité » informatique et vous « découvrirez » non pas une analyse sécurité mais l’inverse, une analyse de risque : les ressources disponibles sont limitées et il faut donc faire des choix…. La sécurité, ça commence par l’analyse des risque et continu par la définitions des priorités mises en regarde de l’effort et des ressources disponibles… cette expression de besoin du métier sert de point d’entrée à l’architecte sécurité qui a pour charge de démontrer comment on répond via l’organisation et les technologies aux besoin exprimés….

    https://en.wikipedia.org/wiki/EBIOS

  • La logique dit que le sécurité absolue en informatique n’existe pas, mais elle a tort.
    La psychologie dit qu’elle existe, parce que les attaques sont le fait d’humains qui ne suivent pas toujours la logique la plus stricte, voire l’ignorent avec dédain.
    Pour résumé, on ne force que ce qui a de la valeur. Donc ce qui n’a pas de valeur ne subira jamais aucune attaque informatique, donc la sécurité absolue en informatique existe.
    Je sais, cela n’a rien de scientifique, mais c’est très vrai.
    Je vous certifie que le site web qui abrite les photos de mon chat depuis 1996 n’a jamais été attaqué et je vous certifie qu’il ne sera jamais attaqué. Toute votre science n’y changera rien.

    • Votre site n’a aucun intérêt, mais le serveur qui l’héberge lui, en a, ne serait-ce que pour faire tourner des botnets. Donc si, il sera ou a déjà été attaqué. Désolé.

  • Dans la pratique, comme dans le monde informatique, on sait bien que rien n’est fiable à 100% et loin s’en faut et pour de multiples raisons. Alors on segmente et on surveille. Du moins on devrait !

    On multiplie les calculateurs ou les gens et on compare les résultats. On sépare les fonctions de travail et de surveillance, de calcul et de communication, on détecte les anomalies. On ne fournit pas les outils de développement ou d’analyse permettant d’explorer et changer le code dans un environnement de production. On crée des guichets d’accès au ressources critiques. On sépare les responsabilités et les pouvoirs. On organise les pouvoirs en couches successives …

    Et je dis on devrait non sans raisons. Que chacun se demande si cela est fait dans son propre ordinateur, dans son entreprise, dans ses outils, dans le gouvernement ou l’armée …

    • « On multiplie les calculateurs ou les gens et on compare les résultats. On sépare les fonctions de travail et de surveillance, de calcul et de communication, on détecte les anomalies. On ne fournit pas les outils de développement ou d’analyse permettant d’explorer et changer le code dans un environnement de production. On crée des guichets d’accès au ressources critiques. On sépare les responsabilités et les pouvoirs. On organise les pouvoirs en couches successives … »

      Ca c’est dans le monde merveilleux de Walt Disney, ou les animaux parlent et ou les entreprises ont un budget informatique infini.

      Dans la vrai vie, la DSI propose ce genre de chose et la finance dit niet, pas de budget. Au final, c’est un arbitrage plus ou moins bancal entre les deux, basé sur une estimation plus ou moins juste du niveau de sécurité qu’on veut atteindre. Et si on a des données vraiment critique on s’arrange pour qu’elles ne soient pas sur le réseau.

      Et quand par malheur on subit une attaque, on fait un audit.

      • J’ai bien dit « on devrait »

        Mais d’une part les pratiques ne sont pas les mêmes quand le calculateur sert à piloter un avion ou à traiter des données marketing, quand une entreprise travaille pour la défense nationale ou dans le commerce.

        Par ailleurs, cela s’applique aussi à la conception d’un système d’exploitation par exemple. Un programme applicatif n’est pas censé pouvoir stopper le processeur ou planter autre chose que lui même, car celui-ci le lui interdit. (Mais cela suppose que n’importe qui n’installe pas des drivers sur une machine, que la NSA de bricole pas le code avant sa diffusion, et que le code soit ouvert ou que le vendeur assume ses responsabilités)

  • Chacun sait que virer un mec d’une société le pousse à s’en prendre à cette société et à en révéler les secrets. Donc rien ne tient dans ce monde sans foi ni loi.

  • Très bel article.

    L’aspect sécurité physique existe aussi. Aucun automate même fermé ne sera fiable à 100% ni donc sur.
    D’autant plus qu’il sera peut-être possible d’accéder à sa mémoire un jour.

  • Bonjour,

    J’ai un petit souci avec la démonstration…

    On a A(x,x) => B(x)=1 (et non A(x,x) B(x)=1), le mot utilisé est « alors » et pas « équivaut à ».

    Donc comment peut-on utiliser dans le cas n°1 B(B)=1 => A(B,B)=0 ?

  • Les commentaires sont fermés.

Promouvoir la liberté n’est pas gratuit

Mais cela peut aider à réduire vos impôts de 66%

Faites un don dès maintenant

Faire un don

Lorsque les premiers jeunes réfugiés ukrainiens arrivèrent en France au début du mois d'avril, ce fut une véritable surprise pour leurs petits camarades français qui les accueillirent dans leurs écoles : leur niveau en mathématiques était notoirement meilleur que le leur et certains professeurs de notre Édulcolration Nationale s'en ouvrirent abondamment dans la presse.

Eh oui : apparemment, en Ukraine, les élèves ne lambinaient pas trop sur les exercices simples de mathématiques. Les opérations de base en arithmétique, y compris sur le... Poursuivre la lecture

Par Armand Lépiers, lycéen.

Il s'agit d'un secret de polichinelle, le niveau des élèves français est désormais faible. Selon les derniers classements PISA nous nous hissons péniblement au-dessus de la moyenne des résultats des pays de l'OCDE et à peu près au même niveau que le Portugal...

Cependant, les gouvernements successifs ne cessent de nous seriner que tout va bien, que le constat de la chute du niveau est une esbroufe tantôt réactionnaire tantôt élitiste (souvent les deux) et que nous devrions dormir tranquilles, la relèv... Poursuivre la lecture

On remarquera que le ministre de l’Éducation nationale, Jean-Michel Blanquer, dans ce bref entretien, où il n’est question que d’ajouter 1 h 30 d’enseignement scientifique aux élèves dont ce n’est pas un «  enseignement de spécialité », doit à la fois se référer aux paroles du président de la République et au Conseil supérieur des programmes qui a élaboré un « projet pour un nouveau programme de mathématiques » à la rentrée 2022 :

🎙️ @jmblanquer : "Nous allons mettre plus de mathématiques dans le tronc commun. 3h30... Poursuivre la lecture

Voir plus d'articles