Cryptanalyse chiffrement par flot

Pierre-Alain Fouque

Description

Niveau: Supérieur

• mémoire

Cryptanalyse : chiffrement par flot Pierre-Alain Fouque Département d'Informatique Ecole normale supérieure

• tq ?


• attaques spécifiques de streams


• technique générale


• solution x1


• piling-up lemma


• existence de solution

Sujets

• Mémoire
• Fouqué
• Piling-up lemma

Informations

• Publié par: profil-nechor-2012
• Nombre de lectures: 97
• Langue: Français

Extrait

Cryptanalyse : chiffrement par flot
Pierre-Alain Fouque
Département d’Informatique
Ecole normale supérieurePlan
• Technique générale:
– Piling up lemma
– birthday paradox (et généralisation)
– distingueur
• Attaques générales de streams:
– recherche exhaustive et compromis temps/mem
– attaque par corrélation (rapide)
• Attaques spécifiques de streams: A5, RC4,..Piling-Up Lemma
• Th: Soit n VA binaires indépendantes
X ,...,X de biais ε , ie tq Pr(X =1)=1/2(1+ε ). 1 n i i i
n n nAlors le biais ε de X est (-1) ∏ ε .i=1 i i=1 i
• Preuve: Récurrence sur n.
n-1 n-1 • Pr(X=1)=Pr( X =1)Pr(X =0)+Pr(i=1 i n i=1
n-1 n-1X =0)Pr(X =1)=1/4(1+(-1) ∏ ε )×(1-ε ) + i n i=1 i n
n-1 n-1 n-1 n1/4(1-(-1) ∏ ε )×(1+ε )=1/2-2 ∏ ε .i=1 i n i=1 i
<~<~<~Paradoxe des anniversaires
• Si on choisit indépendamment et au
hasards N éléments dans D, alors Pr
(collision)>1/2 si N>√D.
• Etant donné 2 listes L , L , d’éléments 1 2
choisis uniformément et indépendamment
ndans {0,1} , trouver x L et x L tq 1 1 2 2
n nx x =0 . Pr(solution x1 et x2)=|L |×|L |/21 2 1 2
<h<h<~Paradoxe des anniversaires
• Version généralisée: étant donné k listes L , trouver i, i
n nx L tq x =0 .i i i=1 i
n n• Existence d’une solution si ∏ |L |=2 .i=1 i
n/4• Cas n=4. Existence solution si |Li|≈2 . Trouver une
n/3telle solution peut se faire en temps et mémoire 2 .
n/3• Construire 4 listes de 2 élé. chacune et un arbre de
collision: apparier les n/3 bits de L et L dans L’ et 1 2 1
n/3ceux de L et L dans L’ . |L’ |≈2 . Donc, collision 3 4 2 i
entre ces deux listes sur 2n/3 bits avec proba. 1/2.
<|<h<~Distingueur
• Test d’hypothèse: H={1,2}
• Observation X dans ensemble E
• Deux distributions: e E, D (e)=P(X=x|H=i)i
• ∑ D (e)=1, E’ E, D (E’)= ∑ D (e)e E i i e E’ i
• Règle de décision: A distingueur défini par E = 1
domaine d’acceptation où A retourne 1
• p (A)=p ∑ P(X=x|H=1)+p ∑ P(X=x|H=2)succ 1 x E1 2 x E2
• p (A)=p D (E )+p D (E )succ 1 1 1 2 2 2
<h<l<h<h<h<hDistingueur optimal
• Lemme de Neyman Pearson:
• S={x E|p D (x)>p D (x)}1 1 2 2
• Distingueur optimal (A ): E =Sopt 1
• A, p (A)≤p (A )succ succ opt
• Rapport de vraisemblance: D (x)/D (x)>?λ où 1 2
λ=p /p .2 1
• Si λ=1, A retourne 1 si D (x)>D (x)opt 1 2
• Si p =0.9, A retourne toujours 1, p (A)=0.91 succ
<|<hExpériences multiples
• M-uplet au lieu d’une valeur
M M• D et D les deux distributions1 2
• On peut montrer que si elles sont proches:
2si on fait M=d/∑ (D (x)-D (x)) /D (x) x E 1 2 1
tirages, alors la proba de distinguer est
√d/2 2p =1-1/√2π∫ exp(-u /2) du.succ -∞
• Si E={0,1}, et D dist. uniforme, D (1)=0.5(1+ε), 2 1
-2ε est le biais et on va mq M≈ε pour distinguer
<hApproximation gaussienne
M M M M• Si D uniforme sur {0,1} , D (e)=1/2 .2 2
• T VA nombre d’indices i de e tq e =1. Si T=t, i
M M t M-tD (e)=1/2 (1+ε) (1-ε) 1
• E l’ensemble des M-uplet tq T=t,t
M M t M t M-t • D (T=t)=D (E )=C ×1/2 (1+ε) (1-ε)1 1 t M
M t M• D (T=t)=C ×1/22 M
M• Pour M grand, D se comporte comme 1
gaussienne, Esp=M/2(1+ε), σ≈√M/2. Gaussienne (suite)
M• De même pour D (T) centrée en M/2.2
• Elles sont approchées par
t 2P(T≤t)=1/(σ√2π)∫ exp(-1/2(x-Esp) /σ)dx-∞
n 2• P(T≤Esp+nσ)=1/(√2π)∫ exp(-1/2u )du-∞
• Distingueur optimal: si p =p =0.5, alors 1 2
n=ε√M/2, p =1-1/2erfc(n/√2), où p (n)succ succ
=0.5 (n=0), 0.84134 (n=1), 0.97723(n=2),
-20.99999 (n=5), donc il faut prendre M≈ε .