permutations & polémiques

arm7 a ecrit:

Le bruit blanc a statistiquement autant de zero que de un,
n'est-ce pas ? C'est la base même du bruit blanc.

Oui. Je n'ai pas employe' cette expression au pif.

Alors en quoi le XOR en question changera les probabilités ?

On parle bien de la proportion de 1 et de 0 dans le message
en clair, n'est-ce pas ?

Alors revenons a la base, puisque ca semble necessaire :

XOR|0|1
-------
0 |0|1
-------
1 |1|0

p(bruit=0) = 0.5
p(bruit=1) = 0.5

p(clair=0) = m
p(clair=1) = 1-m

p(bruit) et p(clair) sont independant.

p(chiffre'=0)= p((clair = 0 cap bruit = 0) cup (clair = 1 cap bruit =
1))
= p(clair=0)*p(bruit=0) + p(clair=1)*p(bruit=1)
= m*0.5 + (1-m)*05
= 0.5 (forall m)

Tadaaa !!!

Par contre l'attaque avec des paires de messages
clairs / cryptés est rendu impossible. C'est ca l'utilité de
la chose.

Impossible. Ben voyons.

Enfin je dis ca, mais tous ceux qui connaissent même
presque rien à la cryptographie le savent déjà.

Tous ceux qui connaissent meme presque rien en crypto
ont des notions de base sur les operations logiques,
en tout cas.

Oui, enfin, comme la variation par rapport à des vrais valeurs
aléatoire sera de 0.00000[..]000001%, on n'est que 0.00000[...]
00001% plus avancé...

L'avantage des demonstrations mathematiques, c'est que ca evite
de sortir des valeurs completement au pif comme ca.

En gros la faiblesse de la permutation de bit c'est que le bit
peut changer comme ne pas changer... wouaw !

Relisez calmement ce que j'ai ecrit, le petit exemple devrait
vous aider. La faiblesse des permutations c'est justement que
seul un nombre reduit de permutations est succeptible de correspondre
a une paire clair<->crypte' donnee. Quand c'est associe' a un
chiffrement par bloc, ca devient un vrai probleme.

sur des blocs de 8192 bits (rien que ça !!)

Mazette ! Rien que ca !

[...] avec une clé 100% random

Tuuuuuut. 100% pseudo-random.

tiré de timer évolant à la vitesse de 1.193.180
fois la seconde

Ca fait beaucoup. Ca doit forcement etre tres sur. Le seul
inconvenient etant qu'il faut que deux graines identiques donnent
deux series pseudo-aleatoires identiques, n'est-ce pas ? Donc
la graine determine une fonction du numero du tirage effectue'.
Pour une graine donnee, cette fonction est unique. La graine
fait 16 bits, 65536 valeurs possibles, pas une de plus. Donc
fut-ce 1.193.180 increments par micro-seconde que concretement,
on s'en cognerait un peu, n'est-ce pas ?

Ben pour ma part (j'ai craqué pas mal de truc dans ma jeunesse),

Dites, vous voyez la difference entre breaker sur un appel a
MessageBoxA et demontrer les faiblesses d'un algorithme de
chiffrement ?

quand je vois ça je me calme tout de suite.

Pourtant, la, vous commencez a vous exciter. La preuve, vous en
etes deja a la phase "je sors des gros nombres pour impressionner
l'assistance".

--
Tweakie


--
Posté via http://www.webatou.net/
Usenet dans votre navigateur !
Complaints-To: abuse@webatou.net

Encore un roman, merde j'ai du taf moi !

p(bruit=0) = 0.5
p(bruit=1) = 0.5

p(clair=0) = m
p(clair=1) = 1-m

p(bruit) et p(clair) sont independant.

p(chiffre'=0)= p((clair = 0 cap bruit = 0) cup (clair = 1 cap bruit > 1))
= p(clair=0)*p(bruit=0) + p(clair=1)*p(bruit=1)
= m*0.5 + (1-m)*05
= 0.5 (forall m)

Tadaaa !!!

Je comprends rien a la demonstration (c'est pas clairs les variables cap et
cup) mais
ca fonctionne ce truc !
Un XOR avec un bruit blanc donne une valeur moyenne (j'ai fait un code pour
le vérifier).
Ben l'algo du mec est vraiment tres fort alors, super !

Par contre l'attaque avec des paires de messages
clairs / cryptés est rendu impossible. C'est ca l'utilité de
la chose.

Impossible. Ben voyons.

Tu essayes ?

L'avantage des demonstrations mathematiques, c'est que ca evite
de sortir des valeurs completement au pif comme ca

Tu donnes les tiennes qu'on rigole ?

Relisez calmement ce que j'ai ecrit, le petit exemple devrait
vous aider. La faiblesse des permutations c'est justement que
seul un nombre reduit de permutations est succeptible de correspondre
a une paire clair<->crypte' donnee. Quand c'est associe' a un
chiffrement par bloc, ca devient un vrai probleme.

"réduit" ? ca serait sympa de quantifier non ? Sur des blocs de 8192 bits ca
fait combien alors ?
Surtout qu'une fois "descramblé" le résultat est un bruit blanc... ca doit
vachement aider a trouver la bonne substitution !

[...] avec une clé 100% random
Tuuuuuut. 100% pseudo-random.

Désolé prof, mais la clef est 100% random, elle. Enfin, quand on lance un
dé, le résultat est random ou pseudo random ? Là c'est pareil, aucune idée
de la valeur du timer au moment d'appuyer sur ENTER.

ts, 65536 valeurs possibles, pas une de plus. Donc
fut-ce 1.193.180 increments par micro-seconde que concretement,
on s'en cognerait un peu, n'est-ce pas ?

Oui-oui, évidement. Mais le mec prendrait la date du jour pour la même chose
ca ne marcherait pas. Parceque la date, on l'a dans le fichier. Tu comprends
un peu ou tu polémiques seulement ?

Ben pour ma part (j'ai craqué pas mal de truc dans ma jeunesse),

Dites, vous voyez la difference entre breaker sur un appel a
MessageBoxA et demontrer les faiblesses d'un algorithme de
chiffrement ?

troll

Pourtant, la, vous commencez a vous exciter. La preuve, vous en
etes deja a la phase "je sors des gros nombres pour impressionner
l'assistance".

retroll

Tu as raison sur le coup du bruit blanc, je n'y avais pas pensé et merci
beaucoup !

Par contre la question importante, tu l'as oubliées alors la voila :

Mais concretement on fait quoi avec ses permutations aléatoires effectuées
sur des blocs de 8192 bits (rien que ça !!) ayant déjà subit un brouillage
avec une clé 100% random (tiré de timer évolant à la vitesse de 1.193.180
fois la seconde et stocké a la fin) générant une suite de nombre aléatoire
lui même perturbé par le message en clair ?

on fait comment donc M.Prof ?

arm7 wrote:

Encore un roman, merde j'ai du taf moi !

C'est pas fini ;-)

Je comprends rien a la demonstration (c'est pas clairs
les variables cap et cup)

Lexique:

cap = intersection
cup = union
p(...) = probabilite' que...
forall : "quel que soit"

Ben l'algo du mec est vraiment tres fort alors, super !

Ne nous emballons pas.

L'avantage des demonstrations mathematiques, c'est que ca evite
de sortir des valeurs completement au pif comme ca

Tu donnes les tiennes qu'on rigole ?

Deja fait : je t'ai prouve' qu'en XORant des donnees quelconques
avec un bruit blanc, on obtenait un equilibre des bits a 1 et a
0. Malheureusement, tu n'as pas pige'.

"réduit" ? ca serait sympa de quantifier non ? Sur des blocs
de 8192 bits ca fait combien alors ?

(4096!)^2, ce qui est reduit par rapport a 8192!

Ca fait quand meme beaucoup. C'est vrai. Mais l'important,
c'est que si on considere B blocs successifs, la probabilite'
pour qu'une permutation donnee soit admissible pour tous ces
B blocs est de p=((4096!)^2/8192!)^{B-1}. Ca, c'est tres
reduit.

La probabilite' pour qu'il subsiste k permutations
admissibles apres que B blocs aient etes pris en compte
suit (me semble-t-il) une loi binomiale de parametres :
n = 8192!, p=((4096!)^2/8192!)^{B-1} (hum, ce nombre etant
compris entre 1 et (4096!)^2, j'ai du me vautrer quelque
part).
Ce qui peut etre approxime' par une loi de poisson de
parametre np. J'ai pas de quoi faire le calcul, la, mais
une 15aine de blocs doit suffire a avoir une probabilite'
de 0.99 pour (k<=1).

Surtout qu'une fois "descramblé" le résultat est un bruit
blanc... ca doit vachement aider a trouver la bonne
substitution !

Ca n'est pas franchement un obstacle, cf. plus bas.

Désolé prof, mais la clef est 100% random, elle. Enfin,
quand on lance un dé, le résultat est random ou pseudo
random ? Là c'est pareil, aucune idée de la valeur du timer
au moment d'appuyer sur ENTER.

OK. Je veux bien admettre qu'elle est random. Elle ne sert
pas forcement a grand chose, mais elle est random.

Oui-oui, évidement. Mais le mec prendrait la date du jour pour
la même chose ca ne marcherait pas. Parceque la date, on l'a
dans le fichier. Tu comprends un peu ou tu polémiques seulement ?

Il n'en reste pas moins qu'il y a seulement 2^16 valeurs
possibles pour la graine, ce qui est tres tres peu.

Il est donc possible de brute-forcer cette partie la de l'algo
(la qualite' du PRNG n'intervient donc pas) et d'etablir
une attaque a clair connu en seulement 16^2 tentatives (ce qui
cryptographiquement parlant est tres peu).

Mais concretement on fait quoi avec ses permutations aléatoires effectuées
sur des blocs de 8192 bits (rien que ça !!) ayant déjà subit un brouillage
avec une clé 100% random (tiré de timer évolant à la vitesse de 1.193.180
fois la seconde et stocké a la fin) générant une suite de nombre aléatoire
lui même perturbé par le message en clair ?

on fait comment donc M.Prof ?

Imagines qu'on ait un message clair M (connu) et un message
chiffre' C decoupes en blocs de N bits. X et C sont des
bitstrings. K est le tableau contenant les permutations et
T un bitarray representant de taille NxN. On cherche a
obtenir K a partir de M et C.

L'algo est le suivant (c'est pas sense' compiler, hein):

1 Pour tous les seeds possibles [0..2^16], generer
X = M xor rand(s) et ajouter le seed a la fin.

2 Pour tous les X ainsi generes, faire :

//Initialisation de la matrice des
//permutations
for(i = 0; i<N; i++){
for(j = 0; j< N; j++){
T[i][j] = 1;
}
}
count = N^2;
num_bloc = 0;

//Recuperation de la seule permutation
//admissible
while((float)count/N > 1.){
for(i = 0; i < N; i++){
for(j = 0; j<N; j++){
tmp = t[i][j];
T[i][j] &= !(C[i+b]^X[i+b]);
if(!T[i][j]&tmp) count--
}
}
b+=N;
}

//Recuperation de la clef:
for(i=0; i<N; i++){
for(i=0; i<N; i++){
if(T[i][j]){
k[i] = j;
break;
}
}
}

Qu'en penses tu ?

--
Tweakie

--
Posté via http://www.webatou.net/
Usenet dans votre navigateur !
Complaints-To: abuse@webatou.net

Bonjour Messieurs,

Pardonnez-moi de m'immiscer, mais je vous lisais avec intérêt et là il y a
un truc qui me gêne.

"arm7" <arm7@free.fr> a écrit dans le message de news:
41b98a59$0$3424$8fcfb975@news.wanadoo.fr...

Encore que statistiquement, la quantité de 1 et de 0 restera
inchangée...

En XORant avec un bruit blanc ? Z'etes sur ?

Le bruit blanc a statistiquement autant de zero que de un, n'est-ce pas ?
C'est la base même du bruit blanc.
[...]

Quel est l'intérêt pratique de vouloir introduire du bruit blanc dans un
système de chiffrement ?

- Soit vous disposez d'un générateur de bruit blanc, que l'on peut assimiler
à du hasard parfait, mais dont le résultat serait reproductible à partir
d'une graine de taille limitée,
- Soit vous disposez d'une séquence unique de bruit blanc, et le message
chiffré peut être rendu public, dixit M. Vernam, mais le problème se reporte
dans le transfert d'une clé non réductible et de taille au moins égale.

La première option semble bien être le nirvana des spécialistes du "hasard
algorithmique", mais que je sache elle n'a jamais été obtenue réellement, et
d'ailleurs on peut se demander si cela ne constituerait pas une
contradiction du concept même de hasard (théoriciens, venez à mon aide).

Quant à la seconde, elle présente l'unique avantage de permettre de changer
la clé en cas de compromission constatée lors de son transfert, avant que le
message ait été lui-même mis en jeu.

Donc quel est l'intérêt du bruit blanc ? Valider la résistance de principe à
la cryptanalyse ?
Pour ***chaque bit*** et à clair inconnu, avec un simple Xor, pour un bit de
chiffré on a alors une équation ***indépendante de toute autre*** et avec
deux indéterminées, donc deux hypothèses contradictoires entre lesquelles on
ne peut que choisir au hasard. Il me semble bien que c'est connu depuis
longtemps...

Donc d'après tous les documents que j'ai lu sur ce thème depuis longtemps,
le Xor est un opérateur équilibré (par rapport au Et (qui favorise les 0) et
au Ou (qui favorise les 1) par exemple, c'est "mieux" pour le brouillage se
surtout c'est inversible, mais l'opérateur en lui-même n'est pas la plus
grande partie du problème : si par sa faute on pouvait déduire un bit de la
clé dans les conditions du chiffrement de Vernam, on ne pourrait rien en
tirer du tout.

Donc selon moi (au moins) c'est bien le "bon hasard reproductible" qui a le
statut de problème majeur, pour autant que l'expression "bon hasard
reproductible" ne soit pas un non-sens.

Donc je ne saisis pas le but même de ce débat... Navré.

Cordialement,

--

/**************************************************************
* Patrick BRUNET @ ZenerTopia
* E-mail: lien sur http://zener131.free.fr/ContactMe
**************************************************************/
<8#--X--< filtré par Avast! 4 Home

Patrick 'Zener' Brunet wrote:

La première option semble bien être le nirvana des spécialistes
du "hasard algorithmique", mais que je sache elle n'a jamais été
obtenue réellement, et d'ailleurs on peut se demander si cela ne
constituerait pas une contradiction du concept même de hasard
(théoriciens, venez à mon aide).

Effectivement. Cependant pour en revenir au systeme de chiffrement
presente' par arm7, la faiblesse due a la petite taille de la
graine est telle que l'algorithme peut etre attaque' par force
brute, sans s'interesser a la qualite' du bruit genere' (si je
puis dire).

Dans ce systeme, l'interet de l'utilisation d'un XOR et d'un
pseudo-bruit-blanc (reproductible avec une graine donnee et
issu d'un generateur de nombre pseudo-aleatoires) est
d'equilibrer le nombre de 0 et de 1 dans ce qui sera ensuite
utilise' pour l'etape de permutations bit-a-bit.

Pourquoi equilibrer les 0 et les 1 ? Tout simplement (du
moins je le suppose) parce que sinon certains messages ne
seraient pas chiffres par les permutations (les messages
000...000 et 111...111 restent invariants), et que d'autres
seraient dechiffrable en tres peu d'essais (00001 et 10000).
Or idealement, le nombre d'essais necessaires au dechiffrage
ne devrait pas dependre du contenu du message.

Ce qui est dommage, c'est qu'en l'occurence cette operation
minimise le nombre de permutations admissibles en cas d'attaque
a clair connu : (N/2)!^2 permutations dans le cas ou elles sont
precedees par un XOR contre (p)!*(N-p)! (avec p = nombre
de bits a 0) dans le cas ou le message en clair est utilise'
directement.

Maintenant, au dela du cas particulier de l'algo presente'
par arm7, je ne sais pas trop quel est ou meme s'il existe,
en regle generale, un interet a inclure du (pseudo)bruit blanc
dans un systeme de chiffrement.

--
Tweakie


--
Posté via http://www.webatou.net/
Usenet dans votre navigateur !
Complaints-To: abuse@webatou.net

Pourquoi equilibrer les 0 et les 1 ? Tout simplement (du
moins je le suppose) parce que sinon certains messages ne
seraient pas chiffres par les permutations (les messages
000...000 et 111...111 restent invariants), et que d'autres
seraient dechiffrable en tres peu d'essais (00001 et 10000).
Or idealement, le nombre d'essais necessaires au dechiffrage
ne devrait pas dependre du contenu du message.

Dans le décriptage, l'étape du XOR est en seconde position.
Donc un seul postulat faux dans la première étape (où il s'agit de retrouver
l'ordre exacte de 8192 bits), empechera de retrouver la clef secrete de 16
bits a la fin du buffer. Du coup, pas un seul octet du buffer, en avant
comme en arrière de l'erreur ne sera décodé correctement. L'effet
d'avalanche est obtenu, avant comme arrière.

Ca évite d'avoir des buffers a moitier décodé et donc de voir une
progression dans le décodage.

En plus, deux fichiers identiques cryptés avec la même clef donne un
résultat différent. Génant pour les attaques en clair.

On peut brut-forcé la clé ? oui-oui... en théorie, sauf que tester 65536
clés sur des buffer de 1ko, ca prend pas mal de temps et le faire pour
chaque prédiction du "stage one" est inimaginable...

evidement, il ne s'agiut en rien d'un programme commercial ! Rien n'empeche
d'avoir comme clef 64 bits par exemple...

cap = intersection
cup = union
p(...) = probabilite' que...
forall : "quel que soit"

Haaaaaa ouuiiii !

(4096!)^2, ce qui est reduit par rapport a 8192!

Je vois qu'on s'approche !

Ca fait quand meme beaucoup. C'est vrai. Mais l'important,
c'est que si on considere B blocs successifs, la probabilite'
pour qu'une permutation donnee soit admissible pour tous ces
B blocs est de p=((4096!)^2/8192!)^{B-1}. Ca, c'est tres
reduit.

Ne te fatigue pas, pour chaque bloc, la permutation est recalculée. Le
message original en clair perturbe le random aussi...

Il n'en reste pas moins qu'il y a seulement 2^16 valeurs
possibles pour la graine, ce qui est tres tres peu.

Tout dépend du calcul qui est derrière. 2^16 xor c'est naze.
2^16 xor de 1024 bytes avec la routine de random a faire tourner pour chauqe
byte, c'est déja autre chose.

et 2^16 xor de 1024 bytes avec la routine de random a faire tourner pour
chauqe byte POUR CHAQUE postulat sur l'ordre des 8192 bits, juste pour voir
si ca veut dire quelquchose, c'est démentiel.

En plus, c'est a refaire pour le bloc suivant si t'a pas la clé, c'est
rassurant hein !

Evidement, rien ne prouve que l'on a pas crypté 2x le fichier, juste pour
rire... :-) et donc le buffer même bien décrypté n'a AUCUN sens
visuellement...

//Recuperation de la seule permutation
//admissible
Heu, franchement, comment tu sais si c'est la seule permutation admissible

???
il me faudrait un truc plus clair pour moi, hein, je ne suis pas théoricen,
j'ai une culture plus terre a terre...