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.

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…