Vernam logistique

Le
jeffvidal
Bonjour,

voila je me pose une question, peut-être l'idée est-elle idiote.

Comment peux faire un cryptanaliste pour tenter de décoder le chiffre
à clef privé suivant:

Soit le mot de passe de longueur finie, qui par une certaine bijection
sert a générer la clef composée de:
P(0) entre 0 et 1
MU entre 3.57 et 4

P(0) et MU sont codés sur "pas mal" de bits, assez pour rendre
impossible une attaque bruteforce sur l'ensemble des valeurs
possibles.

Pour chaque M(n) du message a crypter on calcul le mot crypté C(n) =
M(n) XOR ( mu*P(n-1)*(1-P(n-1)) )
(et reciproquement pour decrypter)

Sachant que la suite logistique est totalement chaotique pour MU entre
3.57 et 4, il est en théorie impossible de prédire son comportement si
on ne connais pas la valeur initiale et MU.

Comment attaquer M ?
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 2
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
jeffvidal
Le #579101
Pardon, ca sera plus clair si j'écris:
P(n) = ( mu*P(n-1)*(1-P(n-1)) )
C(n) = M(n) XOR P(n)
Francois Grieu
Le #579100
On 16 avr, 20:50, wrote:
Pardon, ca sera plus clair si j'écris:
P(n) = ( mu*P(n-1)*(1-P(n-1)) )
C(n) = M(n) XOR P(n)


Dans la première expression, P est un réel, n'est-ce pas ?
Dans la seconde, que doit-on comprendre ? Sur combien de bits est le
XOR pour une valeur de n donnée ?

Quand à la cryptanalyse, dans le vague en l'absence de ces précisions:
il semble assez facile de trouver par tâtonnement des valeurs de P(0)
et mu qui donnent un clair dont le début est connu (voire: un clair
vraissembable si le clair a assez de redondance); ensuite, quand on a
tous les bits définissant P(0) et mu, on a toute la suite du clair
sans effort.

François Grieu

jeffvidal
Le #579099
On 17 avr, 15:36, Francois Grieu
On 16 avr, 20:50, wrote:

Pardon, ca sera plus clair si j'écris:
P(n) = ( mu*P(n-1)*(1-P(n-1)) )
C(n) = M(n) XOR P(n)


Dans la première expression, P est un réel, n'est-ce pas ?
Dans la seconde, que doit-on comprendre ? Sur combien de bits est le
XOR pour une valeur de n donnée ?


Absolument, P est un réel compris entre 0 et 1.On ne code que la
partie décimale.
P est codé sur autant de bits que P(0), c'est à dire "pas mal
d'octets", a vrai dire on s'en fiche, mais assez pour que la clef soit
"assez grande"
pour ne pas etre attaqué exhaustivement. Si P est codé sur N bits, on
XOR P avec N bits du message a coder.


Quand à la cryptanalyse, dans le vague en l'absence de ces précisions:
il semble assez facile de trouver par tâtonnement des valeurs de P(0)
et mu qui donnent un clair dont le début est connu (voire: un clair
vraissembable si le clair a assez de redondance); ensuite, quand on a
tous les bits définissant P(0) et mu, on a toute la suite du clair
sans effort.



Justement ce "tâtonnement" me semble assez difficile car a cet endroit
la suite logistique se comporte de facon totalement anarchique.
Elle illustre bien "l'effet papillon", une modification d'un seul bit
de MU ou de P(0) change radicalement l'ensemble des valeurs prises par
P.
Tout l'interet est la..

Je vous invite a visualiser ce graphique: http://www.gvidal.fr/misc/diff.jpg
que matlab viens de me sortir.
Il represente la différence entre deux suites P et R, qui ne diffèrent
que par une variation de MU de 0.0001, en abscisse c'est n.
On voit que si l'on commence le cryptage pour n0 = 40, le tatonnement
pour trouver un début de clair connu est difficile.








François Grieu



Alain
Le #578882
le principe du chaos déterministe est qu'il reste du déterminisme,
entre des valeurs proches dans le temps.

ainsi si en supposant certaine choses sur le clair, on obtient des
valeurs possibles pour certains points (si tu connais des contraintes
sur P(k), P(k+1),... genre P(8)~0.7+/- 0.01 P(9)~0.9+/-0.02, ou des
trucs plus binaires... genre bit 12 de P(0)=1 )
alors tu peut remonter sur des contraintes sur mu et p(k-1)

si tu as des tas de contraintes, tu peux créer un système et le résoudre
par une système de programmation sous contrainte, ou une methode plus
général pour les problèmes NP-Complet (recuit simulé, algo génétiques,
programmation dynamique)...

bref je parrirais pas là dessus...

ds'ailleur ca me fait penser aux chiffres liés à des polynomes
binaires... trivial à casser...



Bonjour,
Sachant que la suite logistique est totalement chaotique pour MU entre
3.57 et 4, il est en théorie impossible de prédire son comportement si
on ne connais pas la valeur initiale et MU.
Comment attaquer M ?


Francois Grieu
Le #578880
On 17 avr, 19:07, wrote:
On 17 avr, 15:36, Francois Grieu
On 16 avr, 20:50, wrote:

Pardon, ca sera plus clair si j'écris:
P(n) = ( mu*P(n-1)*(1-P(n-1)) )
C(n) = M(n) XOR P(n)


Dans la première expression, P est un réel, n'est-ce pas ?
Dans la seconde, que doit-on comprendre ? Sur combien de bits
est le XOR pour une valeur de n donnée ?


Absolument, P est un réel compris entre 0 et 1.On ne code que la
partie décimale.
P est codé sur autant de bits que P(0), c'est à dire "pas mal
d'octets", a vrai dire on s'en fiche, mais assez pour que la clef soit
"assez grande" pour ne pas etre attaqué exhaustivement.
Si P est codé sur N bits, on XOR P avec N bits du message
a coder.


Si on utilise tous les bits significatifs de P, cela signifie que la
connaissance du clair sur disons 3*N-1 bits donne la connaissance
complète de 2 valeurs de P consécutives, ce qui permet de retrouver
tous les bits de ces P, puis de mu (à quelques bits près trouvables
par tâtonnement, en supposant mu et P sur le même nombre de bits),
donc tous les P ultérieurs. On peut aussi revenir en arrière, pourvu
qu'il y ait un minimum de redondance dans le clair. Et donc le système
est totalement vulnérable à une attaque où une petite fraction du
clair est connu.

Bref c'est l'archétype du cryptosystème désastreusement faible. Il est
également très vulnérable à une attaque où l'on sait seulement qu e le
clair a certaines caractéristiques.

Le système serait nettement moins trivial à casser si l'on utilisait
un seul bit de chaque P, quelque part au milieu des bits
significatifs. Mais ça resterais mauvais, sur de nombreux critères,
dont le risque de tomber dans un cycle court dépendant essentiellement
de mu.

François Grieu



jeffvidal
Le #578879
Désasteusement faible...

Et si je vous donnais trois valeurs de P(n), P(n+1), P(n+2),
concrètement, comment allez vous calculer n, P(0) et mu ?

Parceque je vois mal un algo génétique y parvenir .. mais si quelqu'un
peut me le prouver soit.
Et quel serait a complexité de l'algo et sur quel type de machine
faudrait t-il le faire tourner, et combien de temps ?
jeffvidal
Le #578878
Non j'ai rien dit, en effet c'est plutot simple
michael.spath
Le #578877
On Apr 16, 8:46 pm, wrote:

Sachant que la suite logistique est totalement chaotique pour MU entre
3.57 et 4, il est en théorie impossible de prédire son comportement si
on ne connais pas la valeur initiale et MU.


Pas toujours, esayez par exemple MU = 1+sqrt(8)

Comment attaquer M ?


Chosen plaintext attack avec quelques bytes nuls ?

Francois Grieu
Le #578874
On 17 avr, 23:47, wrote:

Et si je vous donnais trois valeurs de P(n), P(n+1), P(n+2),
concrètement, comment allez vous calculer n, P(0) et mu ?


Non j'ai rien dit, en effet c'est plutot simple


Oui. On obtient mu à peut-être 1 ou 2 bits près (à cause des erreurs
d'arrondi) par
mu = P(n+1)/P(n)/(1-P(n))
La valeur de n est connue si on a obtenu les P à partir du chiffré et
d'un clair connu, mon hypothèse.
On a les 1 ou 2 bits manquants de mu par tâtonnement à partir du
chiffré qui suit, si le clair à un minimum de redondance.
Pour revenir en arrière, il faut à chaque étape choisir la bonne des 2
solutions d'une équation du second degré, et avec un minimum de
redondance dans le clair c'est facile de choisir la bonne. Reste à
retrouver peut-être 1 ou 2 bits de P, mais si la redondance du clair
laisse un doute, on peut souvent lever ce doute car si l'on choisi
mal, il est probable qu'en revenant en arrière de quelques pas on
trouvera une impossibilité.

Bref si un portion du clair est connue, et l'ensemble du clair
nettement redondant, on connais toute la suite du clair, et
l'essentiel de ce qui précède, avec une puissance de calcul
négligeable. La plus grosse faiblesse (mais pas la seule) est que la
valeur de P est complètement connue dès qu'une portion du clair est
connue.

François Grieu


jeffvidal
Le #578682
Bon OK et maintenant si je fais ca:

P(n) = ( mu*P(n-1)*(1-P(n-1)) )
C(n) = M(n) XOR HASH( P(n) )

HASH = MD5, SHA1 ou bien n'importe quelle fonction de hash plus
performante.
La connaissance de valeurs M(n) permet de remonter a HASH(P(n)) mais
comme les fonctions
de hash ne sont pas bijectives... on ne peut pas forcément remonter a
la bonne valeur de P(n) facilement, et donc remonter a MU et P(0) ??

Haha, cette fois j'attend votre solution avec impatience
Publicité
Poster une réponse
Anonyme