[PDF] Chiffrement par Bloc: Cryptanalyse Linéaire/Différentielle

View - Download Chiffrement par Bloc: Cryptanalyse Linéaire/Différentielle

Previous PDF

Next PDF

Chiffrement par Bloc:

Cryptanalyse Linéaire/Différentielle

Cours 5: 14/03/2016

Plan du cours

1) Principes généraux:

Rappel : block ciphers

Attaques génériques

2) Cryptanalyse contre le DES

Cryptanalyse différentielle

Cryptanalyse linéaire

3 FULPqUHV GH UpVLVPMQŃH SRXU O·$(6

4) Autres techniques de cryptanalyse

Rappel : Block Cipher

Définition : Un algorithme de chiffrement symétrique transforme un message en clair M avec une clé secrète K. Le résultat est un chiffré C 3

Notation:

E: ΂0,1΃௡×΂0,1΃௞՜΂0,1΃௡

Cryptanalyse linéaire

F·HVP XQH MPPMTXH j texte clair connucontre les protocoles de cryptographie dont la confusion est faible. Texte clair connu. I·MPPMTXMQP GLVSRVH GH XQ RX SOXVLHXUV PHVVMJHV clair(s) avec le(s) message(s) crypté(s) correspondant, tous cryptés avec la PrPH ŃOpB I·MPPMTXMQP ŃOHUŃOH j UHPURXYHU GH O·LQIRUPMPLRQ VXU OM ŃOpB Une idée. Trouver des relations linéaires de dépendance de probabilités H[ŃHSPLRQQHOOHV HQPUH OHV NLPV G·HQPUpH HP GH VRUPLHB En effet, une relation linéaire ne peut pas être vraie pour tous les messages sinon le protocole a une faiblesse.

Sécurité

Idéalement, Cne doit laisser fuir aucune information sur M ou sur K

0MLV OM VpŃXULPp Q·HVP ÓMPMLV ©SMUIMLPHªB

Un attaquant connaissant Cet Mpeut " tester toutes les clés »

‡ Modèle de la boîte noire

la recherche exhaustive

Fonction à sens unique:

f: E ՜ܨ x ՜f(x): Facile

Etant y=f(x), trouver x: Difficile

la recherche exhaustive:consiste à calculer les images par f de tous les éléments x deEjusqu'à en trouver un qui donne y.

Cette technique est très coûteuse en temps de calcul et doit être répétée pour chaque nouvelle valeur dey;

Utiliser un pré calcul ?

Larecherche par dictionnaire

Phase de précalcul(une fois pour toutes fait indépendamment de y )

1.Calculer à l'avance les f(x)

2.Stocker en mémoire tous les couples (x, f(x)) en les triant suivant la valeur de f(x)

Phase du calcul:

Trouver x à partir de y est extrêmement rapide (avantageux par rapport à la méthode précédente).

I·LQŃRQYpQLHQP la taille de la mémoire utilisée, puisqu'il faut stocker tous les couples (x, f(x)) ÎCompromis temps/mémoire de Hellman

Compromis temps/mémoire de Hellman

Points de

départ3RLQPV G·MUULYpH

Pour inverser f(x) :

mémoire nécessaire = #lignes temps nécessaire = #colonnes (#lignes)x(# colonnes)= espace des clés

Recherche exhaustive (ou attaque par

Force Brute)

2^{31}Cycles / seconde (2GHz)

2^{56}Recherche exhaustive DES (RC5 -1997 -

distributed.net)

2^{64} " Record » de recherche exhaustive (RC5 -2002-

distributed.net)

2^{72}Tentative en cours (RC5 -distributed.net)

2^{128}Sécurité de AES

Complexité théorique de l'attaque

Compromis temps/mémoire de Hellman

Clé de k bits

Temps 2^2k/3

Mémoire 2^2k/3 Précalcul2^k

Exemple DES : 56 bits

‡ Précalcul2^56

‡ 7HPSV 2A3E

‡ 0pPRLUH 2A3E

Introduction: Cryptanalyse

Les deux principales méthodes connues de cryptanalyse des chiffrements par blocs symétriques sont la cryptanalyse différentielle et la cryptanalyse linéaire. Elles exploitent toutes deux des comportements statistiques non uniformes dans le processus de chiffrement. La cryptanalyse différentielle date de 1990 et est due à Biham et Shamir. La cryptanalyse linéaire date de 1992 et est due à

Matsui.

Appelons ݔle texte clair, ݕson chiffré.

Fonctions linéaires/non linéaires

Soit L une fonction linéaire

S01`௡ĺS01`௡

L(x ْy) = L(x) ْ

Alors la différentielle de L est très simple, en tout point x :

L*(ȟ) = L(x ْȟ) ْ

Soit L une fonction affine

$ÓRXP G·XQH VRXV-clé K: ܮ௞(x) = x ْ

La différentielle ܮ

Fonctions non-linéaires

La différentielle F*dépend du point x concerné

F(x,y) = (x.y, x)

Fonctions non-linéaires

Différentielle en (0,0)

F*(0,0) = (0,0)

F*(0,1) = (0,0)

F*(1,0) = (0,1)

F*(1,1) = (1,1)

Différentielle en (1,1)

F*(0,0) = (0,0)

F*(0,1) = (1,0)

F*(1,0) = (1,1)

F*(1,1) = (1,1)

Cas des block ciphers

Fonction F

X F(X)

K ْ.· ْ

Pour résumer

Fonctions linéaires :

²Différentielle prévisible de façon exacte

‡ )RQŃPLRQV MIILQHV ;25 GH VRXV-clé)

²Différentielle indépendante de la clé

‡ )RQŃPLRQV QRQ-linéaires

²On ne peut rien dire de façon générale ²Donc on ne peut pas calculer directement la différentielle pour tout le block cipher

‡ 2Q MGRSPH XQH MSSURŃOH statistique

Cryptanalyse différentielle

HO V·MJLP G·XQH MPPMTXH j ŃOMLUV ŃORLVLVB IM ŃU\SPMQMO\VH GLIIpUHQPLHOOH V·LQPpUHVVH j O·pYROXPLRQ OHV différences ݔ௜+ݔԢ௜pour deux clairs ݔǡݔǯ. On détermine que,

si ݔ௜+ ݔԢ௜ ǂ MORUV ݔ௥ିଵ+ ݔԢ௥ିଵ ǃ MYHŃ une probabilité non

négligeable. On utilise cela pour déterminer la clé inconnue ݇௥à partir de plusieurs messages ݔet de leurs chiffrés ݔ௥obtenus par ܧ

Cryptanalyse différentielle

Le principe général de cette attaque consiste à considérer des couples de ŃOMLUV ; HP ;Ļ SUpVHQPMQP XQH GLIIpUHQŃH ¨; IL[pH HP j pPXGLHU OM propagation de cette différence initiale à travers le chiffrement.

2Q PUMLPH OHV ŃRXSOHV G·HQPUpH HP GH VRUPLH ŃRPPH GHV YMULMNOHV MOpMPRLUHV TXH O·RQ QRPH ; K ¨; ¨KB

Les différences sont définies par une loi de groupe, en général le xorbit à bit.

Cette attaque utilise la faiblesse potentielle de la fonction itérée f dans une dérivation à l'ordre 1.

Exemple: cryptanalyse différentielle

La cryptanalyse différentielle utilise la comparaison du XOR de deux entrée avec le XOR des deux sorties

2Q QRPH ¨[ [· ْ

Exemple: cryptanalyse différentielle

Si le système cryptographique était parfaitalors la SURNMNLOLPp SRXU TX·XQ ¨\SURYLHQQH G·XQ ¨[devrait être de

1/2^n où n est le nombre de bits de X.

IM ŃU\SPMQMO\VH GLIIpUHQPLHOOH H[SORLPH OH IMLP TX·LO SHXP MUULYHU TX·XQ ¨\ SMUPLŃXOLHU MUULYH MYHŃ XQH PUqV JUMQGH SURNMNLOLPp

S !! 1C2AQ G·XQ ¨[ SMUPLŃXOLHUB

IH ŃRXSOH ¨[ ¨\ HVP MSSHOpH XQH GLIIpUHQPLHOOHB

Méthodologie

On suppose que le cryptanalysteGLVSRVH G·XQ JUMQG QRPNUH GH TXMGUXSOHPV [· [µ \· \µ RZ OM YMOHXU GH ¨[ HVP IL[pH HP TXH PRXV OHV PH[PHV VRQP ŃOLIIUpV avec la même clef inconnue K.

3RXU ŃOMŃXQ GHV TXMGUXSOHPV RQ ŃRPPHQŃH SMU GpŃOLIIUHU \· HP \·· HQ XPLOLVMQP

toutes les sous clefs candidates pour le dernier étage. On commence par regarder les caractéristiques différentielles des S-boites. On UHPMUTXH TXH GMQV ŃH ŃMV ¨\ 6[· ْ

Approche statistique

Caractéristiquedifférentielle

²Probabilité p associée (moyennée sur tous les x possibles)

Cryptanalyse linéaire

Idée générale proche de la cryptanalyse différentielle (attaque à clairs choisis) ‡ 2Q XPLOLVH des approximations linéaires des algorithmes de chiffrement par bloc La cryptanalyse linéaire consiste j VLPSOLILHU O·MOJRULPOPH GH ŃOLIIUHPHQP HQ IMLVMQP XQH approximation linéaire. En augmentant le nombre de couples disponibles, on améliore la précision de O·MSSUR[LPMPLRQ HP RQ SHXP HQ H[PUMLUH OM ŃOpB IM ŃU\SPMQMO\VH OLQpMLUH V·LQPpUHVVH MX[ UHOMPLRQV OLQpMLUHV HQPUH OHV NLPV MX ŃRXUV GH

O·MOJRULPOPHB

Forme linéaire

Soit F : S01`௡ĺS01`௡

Une forme linéaire z S01`௡ĺS01`௡est définie par un

masquea = (ܽଵ" ܽ௡ ‡ z(ݔଵ" ݔ௡) = ܽଵ.ݔଵْ" ْܽ

Caractéristique linéaire

Une caractéristique linéaire de F est un couple de formes que ‡ MYHŃ SURNMNLOLPp S SULVH VXU PRXV OHV [ SRVVLNOHV

Méthodologie

sortie qui ait lieu avec une probabilité nettement supérieure ou nettement

considérés comme des variables aléatoires définies sur {0, 1} et ݕଵ" ݕ௡sont

les bits de la sortie (du message chiffré) considérés comme des variables

aléatoires définies sur {0, 1} on ait Pr { ܺ௜భْܺ௜మْ···ْܺ௜೙ْܻ௜భْ

Table des app. linéaires

En général, deux formes linéaires aléatoires sont égales avec probabilité 0,5 ‡ 2Q V·LQPpUHVVH GRQŃ j O·pŃMUP MYHŃ S 0D MXVVL MSSHOp NLMLV dž

M1 ń M2 Lproba= 0.5 כ

M1 ń M2 LNLMLV dž@

Méthodologie

Par analogie avec la cryptanalyse différentielle, on note ‡ 2Q XPLOLVH XQH PMNOH GHV ŃMUMŃPpULVPLTXHV OLQpMLUHV ņ PMNOH des différences)

Exemple: (1,0) ĺ(0,1) [proba= 1]

quotesdbs_dbs30.pdfusesText_36

[PDF] on a reçu le message suivant : jwpnwmrcfwmy

[PDF] cryptage affine spé maths

[PDF] déchiffrement affine

[PDF] vigenere python code

[PDF] chiffre de vigenère langage c

[PDF] vigenere python decode

[PDF] decoder vigenere sans clef

[PDF] chiffre de vigenere algorithme

[PDF] algorithme rsa exemple

[PDF] algorithme rsa pdf

[PDF] algorithme rsa exercice corrigé

[PDF] cryptage rsa exemple

[PDF] cryptographie asymétrique algorithme

[PDF] chiffrement asymétrique et symétrique

[PDF] chiffrement asymétrique exemple