1 % Modèles discrets pour la sécurité inforamtique: des méthodes itératives à l'analyse vectorielle
3 Les informations traitées par un ordinateur ne sont, \textit{in fine},
4 que discrètes: les flottants (sur un nombre fini de bits) sont une
5 interprétation des réels, les \textit{longs} une interpréation finie
7 Les phénomènes physiques ou naturels peuvent aussi être modélisés par des
9 il n'est parfois pas nécessaire de suivre exactement tous les états par
10 lesquels peut passer l'élément d'étude. Pour peu que l'on sache
11 identifier les seuils de son domaine (c'est-à-dire les valeurs
12 critiques permettant au système global de changer),
13 il est parfois suffisant de réduire le domaine de l'état de l'élément
14 à un ensemble fini d'intervalles définis par ces seuils.
15 Un élément passe d'un état $i$ à un état $j$ si dans la version continue il
16 passe d'un état de l'intervalle numéro $i$ à un état de l'intervalle numéro $j$.
17 En abstrayant à l'extrême,
18 on peut considérer pour chaque élément seulement deux états:
19 1 pour le fait d'être présent et 0 pour le fait d'être absent, ou bien
20 1 pour le fait d'avoir une valeur supérieure à un seuil et 0 pour le fait qu'elle y soit inférieure.
21 Ces réseaux particuliers sont qualifiés de \emph{réseaux booléens}.
24 Soit ${\mathsf{N}}$ un entier naturel représentant le nombre
25 d'éléments étudiés (le nombre bits qu'un générateur veut engendrer,
26 le nombre de pixel que l'on veut modifier\ldots) un réseau booléen est
27 défini à partir d'une fonction booléenne $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$
28 et un mode de mise à jour.
29 A chaque étape, on peut intuitivement ne modifier qu'une partie des
30 $\mathsf{N}$ éléments.
31 En fonction des élements qui sont susceptibles d'être modifiés à chaque étape,
32 on peut se poser les questions de savoir si le réseau atteint un point fixe (ét qu'il peut donc converger) ou
33 s'il possède des attracteurs cycliques (et qu'il diverge donc).
35 Détecter la convergence ou son contraire peut se faire \textit{ a priori} dans
36 certain cas. En effet, de nombreux travaux ont énoncé des conditions
37 suffisantes sur les réseaux bouléens garantissant leur convergence
38 ou leur divergence . Lorsqu'aucune d'entre elle ne s'applique, on peut penser
39 à étendre ces résultats théoriques et compléter ceci par des simulations.
40 Lorsque la convergence est pratiquement observée, il reste à vérifier que
41 celle-ci est indépendante du choix des parties à modifier, par exemple.
42 Une vérification \textit{a posteriori} s'impose, sauf si la méthode de
43 simulation a été prouvée comme exhaustive.
45 Une fonction qui admet un attracteur cyclique égal à l'ensemble
46 des sommets diverge. Admet-il cependant un comportement chaotique?
47 Les théories mathématiques du chaos ont énoncé des critères permettant
48 de décider si une fonction est chaotique ou non, et plus récemment
49 si certains réseaux bouléens étaient l'étaient. Se pose légitimement
50 la question de savoir si cette caractérisation s'étend quelque soient
51 les parties modifiées à chaque étape. Naturellement, ceci n'a un sens
52 pratique que si le nombre de réseaux bouléens qui possèdent cette
53 caractéristique est suffisament grand et que l'on sache engendrer
54 algorithmiquement de tels réseaux.
56 Les liens entre chaos et aléas sont certes intuitifs, mais sont-ils suffisants
57 pour espérer construire un générateur de nombres pseudo-aléatoires (PRNG)
58 à partir de fonctions au comportement chaotique? La réponse est certes
59 positive, mais pas triviale. Il est nécessaire de définir les propriétés
60 attendues de la sortie d'un PRNG et
61 l'uniformité de sa distribution est sans doute la première
62 des propriétés à assurer.
63 Comment alors générer des fonctions chaotiques dont les itérations
64 peuvent converger vers une distribution uniforme?
65 Combien d'itérations suffit-il alors
66 d'effectuer pour s'approcher suffisament de celle-ci?
68 Les liens entre chaos et marquage d'information sont aussi faciles à établir:
69 de tout média marqué même attaqué, la marque doit pouvoir être extraite.
70 Cette propriété du marquage est proche en effet de celle de régularité des opérateurs chaotique. Il est alors naturel d'envisager exploiter les
71 fonctions chaotiques extraites dans ce contexte et donc de modifier
72 certains bits d'un média pour y insérer de l'information: la marque.
75 Les compétences acquise dans l'étude des algorithme d'insertion d'une marque
76 dans une image nous permettent aussi d'adresser le problème d'insérer un message dans une image, mais en priviligeant cette fois l'imperceptibilité et
77 non plus la robustesse.
