voila je me pose une question, peut-=EAtre l'id=E9e est-elle idiote.
Comment peux faire un cryptanaliste pour tenter de d=E9coder le chiffre
=E0 clef priv=E9 suivant:
Soit le mot de passe de longueur finie, qui par une certaine bijection
sert a g=E9n=E9rer la clef compos=E9e de:
P(0) entre 0 et 1
MU entre 3.57 et 4
P(0) et MU sont cod=E9s 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=E9 C(n) =3D
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=2E57 et 4, il est en th=E9orie impossible de pr=E9dire son comportement si
on ne connais pas la valeur initiale et MU.
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
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
On 16 avr, 20:50, jeffvi...@gmail.com 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.
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
On 17 avr, 15:36, Francois Grieu wrote:
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
On 17 avr, 15:36, Francois Grieu <fgr...@gmail.com> wrote:
On 16 avr, 20:50, jeffvi...@gmail.com 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.
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 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 ?
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 ?
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
On 17 avr, 19:07, wrote:
On 17 avr, 15:36, Francois Grieu wrote:
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
On 17 avr, 19:07, jeffvi...@gmail.com wrote:
On 17 avr, 15:36, Francois Grieu <fgr...@gmail.com> wrote:
On 16 avr, 20:50, jeffvi...@gmail.com 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.
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
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 ?
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 ?
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 ?
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 ?
On Apr 16, 8:46 pm, jeffvi...@gmail.com 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 ?
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
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
On 17 avr, 23:47, jeffvi...@gmail.com 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.
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.
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
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
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
