td2 Corr [PDF]

Zitiervorschau

Initiation `a la cryptographie

Correction TD de cryptographie no 2 —T´el´ecom Nancy 2A TRS—

1

LFSR

x Exercice 1. LFSR

On consid`ere le LFSR dont le polynˆome de r´etroaction est z 6 + z 3 + 1 (c’est un polynˆ ome irr´eductible). (i)

(i)

1. Quelle est la matrice permettant de passer de l’´etat interne (x0 , . . . , x5 ) `a l’´etat interne (i+1) (i+1) suivant (x0 , . . . , x5 ). ´ 2. Faire le dessin du LFSR en indiquant les fils de la r´etroaction. Ecrire les ´equations de r´ecurrence. ` partir d’un ´etat interne non nul, calculer les ´etats internes suivants. Quelle est la p´eriode 3. A de ce LFSR ? Est-ce optimal ? 4. On suppose que lors de six it´erations successives num´erot´ees N `a N + 5, les bits produits par le LFSR sont, dans l’ordre : 0, 1, 0, 1, 0, 1. Quel est l’´etat interne avant l’´etape N ? Quels sont les bits suivants ? 5. Mˆemes questions avec z 5 + z 3 + z 2 + z + 1. Comment peut on s’assurer rapidement, dans le cas de ce polynˆ ome, que la p´eriode est n´ecessairement maximale ?

! Correction : 1. La matrice est :



0 0  1  0  0 1

1 0 0 0 0 0

0 1 0 0 0 0

0 0 1 0 0 0

0 0 0 1 0 0

 0 0  0  0  1 0

2. On a le dessin suivant : x0 x1 x2 x3 x4 x5 0 1 0 1 1 1

ki

L’´etat interne ` a l’´etape i + 1 d´ecoule de l’´etat interne `a l’´etape i : (i+1)

(i)

(i+1)

xk+1 = xk ,

x0

(i)

(i)

= x5 ⊕ x2 .

d´ecalage dont le bit d’entr´e est calcul´e `a partir de son ´etat pr´ec´edent. 3. Partons de 0010000. Les ´etats successifs sont : ´ Num´ero d’´etape Etat interne bit produit 0 001000 0 1 100100 0 2 010010 0 3 001001 1 4 000100 0 5 000010 0 6 000001 1 7 100000 0 8 010000 0 9 001000 0 (identique `a l’´etape 0)

1

La p´eriode est donc de 9. C’est un diviseur strict de 63 = 26 − 1, qui est le maximum possible pour un polynˆ ome de r´etroaction de degr´e 6. Donc ce polynˆome n’est pas optimal (il n’est pas primitif : l’ordre de x n’est pas 63 dans F2 [z]/(z 6 + z 3 + 1)). (N )

(N +1)

(N )

4. On a kN = x5 = 0, kN +1 = x5 = x4 = 1, etc. D’o` u l’´etat interne `a l’´etape N : 101010. 5. En degr´e 5, l’ordre de x est un diviseur de 25 − 1 = 31. Comme ce nombre est premier, et que x est diff´erent de 1 bien ´evidemment, l’ordre est n´ecessairement ´egal `a 31.

! 2

Arithm´ etique modulaire et g´ en´ eration al´ eatoire

x Exercice 2. Inversion du PRNG propos´ e dans POSIX

La norme UNIX appel´ee POSIX.1-2001 propose une impl´ementation simple et peu ambitieuse de la fonction standard rand(), qui doit ˆetre fournie par la biblioth`eque standard du langage C. Cette proposition n’est pas normative : elle constitue juste une suggestion, `a destination des impl´ementeurs : static unsigned long interne = 1; /* RAND_MAX assumed to be 32767 */ int rand(void) { interne = interne * 1103515245 + 12345; return((unsigned)(interne/65536) % 32768); } void srand(unsigned long graine) { interne = graine; } Nous proposons de montrer que ce type d’impl´ementation n’est pas convenable pour l’utilisation cryptographique, car il est possible de pr´edire les r´esultats produits. 1. Montrer que pour deux valeurs interne in interne0 qui diff`erent d’un multiple de 231 , les valeurs produites par rand sont identiques. Que dire des ´etats internes suivants ? Le fonctionnement de ce g´en´erateur al´eatoire est-il sensible au fait que unsigned long soit une valeur de 32 ou 64 bits ? 2. On consid`ere une valeur k0 produite par rand(). On appelle i1 la valeur de l’´etat interne apr`es cet appel. Quelle information partielle sur i1 peut-on ´ecrire `a l’aide de k0 ? 3. On appelle x0 la partie inconnue de l’´etat interne i1 . Combien y a-t-il de valeurs possibles pour x0 ? Est-il coˆ uteux de toutes les tester ? Comment confirme-t-on que cette valeur test´ee est la bonne ? Si on ´etend ce concept du PRNG lin´eaire congruentiel `a un ´etat interne de n bits, avec n tel que l’´enum´eration des ´etats internes possibles est impossible, alors d’autres attaques, de complexit´e polynomiale en n, peuvent ˆetre utilis´ees. Elles sont cependant plus complexes `a mettre en œuvre.

! Correction : 1. La valeur de l’´etat interne peut ˆetre consid´er´ee modulo 231 sans que c¸a fasse une diff´erence. 2. On peut ´ecrire i1 = 216 k0 + x0 . 3. Il y a 216 valeurs possibles. Les ´enum´erer n’est pas cher. En comparant `a uen poign´ee de valeurs retourn´ees par rand(), on peut confirmer qu’on a devin´e juste. Si on ´etend ` a n bits, le coˆ ut de l’´enum´eration est quand mˆeme en 2n/2 . En v´erit´e on peut faire beaucoup mieux en utilisant des outils de cryptanalyse tels les fractions continues ou la r´eduction de r´eseaux.

! 2

x Exercice 3. Calcul Mental

Calculer sans l’aide de la calculatrice les expressions suivantes : 2256 mod 128 ; 529436 mod 66 ; 10234096 mod 210 ; 47059 mod 1009 (Indication : 1009 est premier.) ; 96125 mod 127 ; 10146 mod 219.

! Correction : 1. 2256 mod 128 = 2249 · 128 mod 128 = 0 2. 529436 mod 66 = (529 mod 66)436 = 1436 = 1 3. 10234096 mod 210 = (−1)4096 mod 210 = 1 4. 7059 = 1008×7+3. Par le petit th´eor`eme de Fermat : 41008 mod 1009 = 1. Ainsi 47059 mod 1009 = 43 mod 1009 = 64. 5. 96125 mod 127 est l’inverse de 96 modulo 127 (petit th´eor`eme de Fermat). D’autre part on a 96 = 3×25 . On a 3 × 42 ≡ −1, et 2 × 26 ≡ 1. Donc (3 × 25 )−1 ≡ (−42) × (26 )5 ≡ (−42) × 230 . D”autre part 27 ≡ 1. Donc 230 ≡ 228 × 4 ≡ 4. On obtient 96−1 ≡ −4 × 42 ≡ −168 ≡ −41 = 86. 6. On a 219 = 3 × 73. D’apr`es le th´eor`eme des restes chinois, il y a un isomorphisme entre Z/pqZ et Z/pZ × Z/qZ. On calcule donc 10146 ≡ 1 mod 3, et 10146 ≡ 102×72+2 ≡ 100 mod 73. D`es lors, la solution x v´erifie x ≡ 1 mod 3, et x ≡ 100 mod 73. Donc x ≡ 100 mod 219 convient.

! 3

Cl´ e secr` ete



x Exercice 4. Authentification de type d´ efi–r´eponse

Il existe des protocoles permettant d’authentifier une entit´e A aupr`es d’une entit´e B. Cela pr´esuppose donc que A sache effectivement que l’entit´e v´erificatrice est bien B, et pas un attaquant C qui se fait passer pour B. Or lors de la plupart des connexions, rien ne l’en assure. Il faudrait alors que B s’authentifie ´egalement aupr`es de A. C’est ce qu’on appelle l’authentification mutuelle. L’id´ee g´en´erale est alors de reprendre les protocoles qui existent pour l’authentification d’une entit´e et de l’appliquer de mani`ere sym´etrique pour authentifier B aupr`es de A. Nous allons voir sur deux exemples qu’il est tout de mˆeme n´ecessaire de pr´evoir quelques ajustements. 1. Expliquer pourquoi il n’est pas possible de faire de l’authentification mutuelle par mot de passe. ´ 2. Sugg´erer alors une attaque qui permet de r´ecup´erer un mot de passe UNIX. Enum´ erez d’autres situations dans lesquelles une interception de mot de passe est possible en l’absence d’authentification du serveur. On cherche maintenant ` a utiliser une authentification de type d´efi–r´eponse utilisant un syst`eme `a cl´e secr`ete. Consid´erons le protocole suivant qui utilise un chiffrement `a cl´e secr`ete. A et B partagent au pr´ealable une cl´e secr`ete K. (i) A tire une valeur al´eatoire rA et l’envoie `a B ; (ii) B tire une valeur al´eatoire rB et calcule β = EK (rA , rB ). B envoie β `a A ; 3

(iii) A calcule DK (β). S’il n’y a pas eu d’attaque, il retrouve rA : B s’est authentifi´e. Il prend connaissance de rB . Il envoie rB `a B : A s’est authentifi´e. 3. Trouver une attaque de ce protocole par rejeu. On donne les ´el´ements de d´epart de l’approche. Le participant A est honnˆete, et l’attaquant C (malhonnˆete !) se fait passer pour B. C va, parall`element ` a la tentative d’authentification mutuelle ´emanant de A (vers B, pense-t-il) appel´ee  session 1 , initier une session d’authentification vers A (en faisant croire qu’elle ´emane de B), qu’on appellera  session 2 . Les messages de ces deux sessions s’entrelacent. Les premi`eres ´etapes sont (exactement dans cet ordre) : — (session 1) : A envoie rA ` a C. — (session 2) : C envoie rA ` a A. Compl´eter, et expliquer d’o` u provient le probl`eme. 4. Sugg´erer une am´elioration.

! Correction : 1. Il n’est pas possible de faire de l’authentification mutuelle par mot de passe tout simplement parce qu’on ne peut donner un mot de passe qu’`a une entit´e de confiance (on doit ˆetre sˆ ur de qui elle est) ce qui n’est ´evidemment pas le cas si on a besoin d’authentification mutuelle.2. Le faux ´ecran de login sous toutes ses formes. . . Il est possible si un serveur DNS est compromis qu’un nom renvoie `a une adresse IP diff´erente. Un utilisateur non averti peut donc penser communiquer avec le v´eritable serveur. 3. Il suffit que l’attaquant C lance en parall`ele une autre session d’authentification mutuelle vers A en rejouant imm´ediatement les al´eas envoy´es et en entrela¸cant correctement les envois de mani`ere `a faire calculer a` A les valeurs des r´eponses. Cela donne : 1

A tire une valeur al´eatoire rA et l’envoie `a C qui se fait passer pour B ;

1bis

C rejoue imm´ediatement la valeur rA en lan¸cant en parall`ele une autre session d’authentification ; 0 A tire une valeur al´eatoire rA et calcule α = 0 EK (rA , rA ). A envoie α `a C ;

2bis 2 3

C renvoie alors α (qu’il ne peut pas d´echiffrer) ` a A; A calcule DK (α). Il retrouve rA : C s’est 0 authentifi´e. Il prend connaissance de rA . Il 0 envoie rA ` a C;

3bis

0 `a A. C renvoie rA

4. Le probl`eme provient du fait que les messages ne sont pas personnalis´es et que les proc´ed´es sont sym´etriques. Afin d’introduire de la dissym´etrie dans un proc´ed´e `a cl´e secr`ete, il faut utiliser des MAC. On am´enage alors le protocole pr´ec´edent en concat´enant les identit´es aux valeurs al´eatoires tir´ees par chaque partie avant de calculer le MAC.

! 4