TAZ v1.0 fonction de hachage améliorée basée sur RC4

Dans l'article <1112564681.316984.213890@o13g2000cwo.googlegroups.com>,
Claudio <cgonzale@numericable.fr> dit:

J'ai fini de rédiger les spécifications (complètes je l'espère)
de TAZ version 1.0.

http://perso.numericable.fr/~cgonzale/taz/taz-fr.html


Je ne vois plus pour l'instant d'attaque meilleure que 2^128
hash pour provoquer une collision dans la phase de compression.
Alors je regarde le reste.


La finalisation produit 32 octets Hi par

Pour i = 0 à 31:
j = (j + S[i]) mod 256
Echanger S[i] et S[j]
Hi = (S[i] + S[j]) mod 256
Fin-pour.

Problème le plus visible: le bit de poids faible des Hi n'est
pas équidistribué; il est 0 avec une probabilité de l'ordre de
257/512. Un gros biais.

Je ne suis pas d'accord avec la proposition selon laquelle on
peut augmenter sans risque la taille du condensé. En effet on va
finir par trop révéler sur S[] et j avant la finalisation, et
ce serait grave [possibilité de prévoir la suite du condensé à
partir du début, et même de "revenir en arrière" car TAZ est
d'un certain point de vue "réversible": connaissant l'état
final de S[] et j, et la fin du message, on peut trivialement
remonter à un état précédent, et donc déduire le hash de
messages différant dans la partie connue].

Les deux remarques ci-dessus tomberaient pour l'essentiel si
pendant la finalisation l'on utilisait l'algorithme RC4 (et
non le KSA de RC4).
En effet, sauf à casser RC4, l'obervation du résultat de RC4
ne permet pas de remonter à l'état interne; et la sortie
de RC4 est "bien aléatoire", sauf pour des tailles immenses.


Plus généralement, le remplissage/finalisation n'est pas très
satisfaisant. Il n'est pas défini pour des tailles de message non
multiple de 8 bits; ça rend TAZ non substituable à SHA-256.
Il y a une irrégularité pour le message vide [en général le
premier octet du "bloc de sécurité" est la taille du message en
octet, plus 127, modulo 128; mais est 0 (au lieu de 127) pour
le message vide].

Je m'inquète aussi sur les relations que l'on pourrait espérer
trouver entre les hash de messages de même début. Exemple: pour
un M de 129 octets, les 128 hash obtenus en ajoutant 0 à 127
zeros sont produits de manière très similaire et je crains que
cela reste détectable dans les 128 hash; on peut même craindre
qu'un adversaire obtenant le hash de M suivi de 1 à 127 zero
puisse déduire le hash de M, sans connaitre M; proriété que n'a
pas une fonction de hash idéale, qui vise à être indistiguable
d'un oracle aléatoire.


François Grieu

Toujours à propos de TAZ 1.x
http://perso.numericable.fr/~cgonzale/taz/taz-fr.html

Je refais des essais de recherche de collision dans
la phase de compression.
Les octets du message sont traités dans l'ordre (hex)
00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F
10 11 12 13 14 15* 16* 17* 18 19 1A 1B 1C 1D 1E 1F
20 21 22 23 24 25 26 27 28 29 2A 2B 2C 2D 2E 2F
30 31 32 33 34 35 36 37 38* 39* 3A 3B 3C 3D 3E 3F
40 41 42 43 44 45 46 47 48 49 4A 4B 4C 4D 4E 4F
50 51 52 53 54 55 56 57 58 59 5A 5B 5C 5D 5E 5F
60 61 62 63 64 65 66 67 68 69 6A 6B 6C 6D 6E 6F
70 71 72 73* 74* 75 76 77 78 79 7A 7B 7C 7D 7E 7F
00 23 46 69 0C 2F 52 75 18 3B 5E 01 24 47 6A 0D
30 53 76 19 3C 5F 02 25 48 6B 0E 31 54 77 1A 3D
60 03 26 49 6C 0F 32 55 78 1B 3E 61 04 27 4A 6D
10 33 56 79 1C 3F 62 05 28 4B 6E 11 34 57 7A 1D
40 63 06 29 4C 6F 12 35 58 7B 1E 41 64 07 2A 4D
70 13 36 59 7C 1F 42 65 08 2B 4E 71 14 37 5A 7D
20 43 66 09 2C 4F 72 15* 38* 5B 7E 21 44 67 0A 2D
50 73* 16* 39* 5C 7F 22 45 68 0B 2E 51 74* 17* 3A 5D

Si l'on construit des blocs de 128 octets de message différents
dans les 7 octets aux indices (hex) 15 16 17 38 39 73 74
que j'ai repéré par 14 étoiles, ces octets forment 6 "segments"
de 2 ou 3 octets dans les deux moitiés.
On peut donc au moins espérer que la variable j ne propage pas
de changement de segment en segment; et par exemple on peut
choisir les octets en (hex) 17 39 et 74 pour forcer cela dans
les 3 premiers segments. Pour les 3 autres, il faut être plus
habile, ou compter sur la force brute (2^24 essais en moyenne).
On a beaucoup de liberté pour le reste, ce qui permet de
manipuler pas mal les S[] avant les 6 segments; il faut
cette liberté, pour faire en sorte que les octets permutés ne
se propagent pas via les autres octets du message, et que les
permutations causées par les 7 octets modifiés dans les 6
segments se compensent d'une manière ou d'une autre.

Je ne dis pas que c'est facile, mais c'est loin d'être désespéré,
comme mission.

A nouveau: la différence fondemmentale entre TAZ et RC4, c'est
que dans RC4 la permutation est présumée secrète, alors que
dans TAZ elle est connue de l'attaquant, ce qui constitue pour
lui un avantage décisif.


François Grieu

Toujours à propos de TAZ 1.x
http://perso.numericable.fr/~cgonzale/taz/taz-fr.html

Je refais des essais de recherche de collision dans
la phase de compression.
Les octets du message sont traités dans l'ordre (hex)
00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F
10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F
20 21 22 23 24 25 26 27 28 29 2A 2B 2C 2D 2E 2F
30 31 32 33 34 35 36 37 38 39 3A 3B 3C 3D 3E 3F
40 41 42 43 44 45 46 47 48 49 4A 4B 4C 4D 4E 4F
50 51 52 53 54 55 56 57 58 59 5A 5B 5C 5D 5E 5F
60 61 62 63 64 65 66 67* 68* 69 6A 6B 6C 6D 6E 6F
70 71* 72* 73* 74 75 76 77 78 79 7A 7B 7C* 7D* 7E 7F
00 0B 16 21 2C 37 42 4D 58 63 6E 79 04 0F 1A 25
30 3B 46 51 5C 67* 72* 7D* 08 13 1E 29 34 3F 4A 55
60 6B 76 01 0C 17 22 2D 38 43 4E 59 64 6F 7A 05
10 1B 26 31 3C 47 52 5D 68* 73* 7E 09 14 1F 2A 35
40 4B 56 61 6C 77 02 0D 18 23 2E 39 44 4F 5A 65
70 7B 06 11 1C 27 32 3D 48 53 5E 69 74 7F 0A 15
20 2B 36 41 4C 57 62 6D 78 03 0E 19 24 2F 3A 45
50 5B 66 71* 7C* 07 12 1D 28 33 3E 49 54 5F 6A 75

Si l'on construit des blocs de 128 octets de message différents
dans les 7 octets aux indices (hex) 67 68 71 72 73 7C 7D
que j'ai repéré par 14 étoiles, ces octets forment 6 "segments"
de 2 ou 3 octets dans les deux moitiés.
On peut donc au moins espérer que la variable j ne propage pas
de changement de segment en segment; et par exemple on peut
choisir les octets en (hex) 68 73 et 7D pour forcer cela dans
les 3 premiers segments. Pour les 3 autres, il faut être plus
habile, ou compter sur la force brute (2^24 essais en moyenne).
On a beaucoup de liberté pour le reste, ce qui permet de
manipuler pas mal les S[] avant les 6 segments; il faut
cette liberté, pour faire en sorte que les octets permutés ne
se propagent pas via les autres octets du message, et que les
permutations causées par les 7 octets modifiés dans les 6
segments se compensent d'une manière ou d'une autre.

Je ne dis pas que c'est facile, mais c'est loin d'être désespéré,
comme mission.

A nouveau: la différence fondemmentale entre TAZ et RC4, c'est
que dans RC4 la permutation est présumée secrète, alors que
dans TAZ elle est connue de l'attaquant, ce qui constitue pour
lui un avantage décisif.


François Grieu
[reposté avec correction de la table]

J'ai écrit:

Si l'on construit des blocs de 128 octets de message différents
dans les 7 octets aux indices (hex) 67 68 71 72 73 7C 7D,
ces octets forment 6 "segments" de 2 ou 3 octets dans les
deux moitiés.

J'ai un peu mieux: je considère les changements aux 6 indices
(hex) 00 01 0A 0B 0C 7F, qui forment seulement 5 segments.

00* 01* 02 03 04 05 06 07 08 09 0A* 0B* 0C* 0D 0E 0F
10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F
20 21 22 23 24 25 26 27 28 29 2A 2B 2C 2D 2E 2F
30 31 32 33 34 35 36 37 38 39 3A 3B 3C 3D 3E 3F
40 41 42 43 44 45 46 47 48 49 4A 4B 4C 4D 4E 4F
50 51 52 53 54 55 56 57 58 59 5A 5B 5C 5D 5E 5F
60 61 62 63 64 65 66 67 68 69 6A 6B 6C 6D 6E 6F
70 71 72 73 74 75 76 77 78 79 7A 7B 7C 7D 7E 7F*
00* 0B* 16 21 2C 37 42 4D 58 63 6E 79 04 0F 1A 25
30 3B 46 51 5C 67 72 7D 08 13 1E 29 34 3F 4A 55
60 6B 76 01* 0C* 17 22 2D 38 43 4E 59 64 6F 7A 05
10 1B 26 31 3C 47 52 5D 68 73 7E 09 14 1F 2A 35
40 4B 56 61 6C 77 02 0D 18 23 2E 39 44 4F 5A 65
70 7B 06 11 1C 27 32 3D 48 53 5E 69 74 7F* 0A* 15
20 2B 36 41 4C 57 62 6D 78 03 0E 19 24 2F 3A 45
50 5B 66 71 7C 07 12 1D 28 33 3E 49 54 5F 6A 75


François Grieu

Francois Grieu wrote:

Toujours à propos de TAZ 1.x
http://perso.numericable.fr/~cgonzale/taz/taz-fr.html

Je refais des essais de recherche de collision dans
la phase de compression.
Les octets du message sont traités dans l'ordre (hex)
00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F
10 11 12 13 14 15* 16* 17* 18 19 1A 1B 1C 1D 1E 1F
20 21 22 23 24 25 26 27 28 29 2A 2B 2C 2D 2E 2F
30 31 32 33 34 35 36 37 38* 39* 3A 3B 3C 3D 3E 3F
40 41 42 43 44 45 46 47 48 49 4A 4B 4C 4D 4E 4F
50 51 52 53 54 55 56 57 58 59 5A 5B 5C 5D 5E 5F
60 61 62 63 64 65 66 67 68 69 6A 6B 6C 6D 6E 6F
70 71 72 73* 74* 75 76 77 78 79 7A 7B 7C 7D 7E 7F
00 23 46 69 0C 2F 52 75 18 3B 5E 01 24 47 6A 0D
30 53 76 19 3C 5F 02 25 48 6B 0E 31 54 77 1A 3D
60 03 26 49 6C 0F 32 55 78 1B 3E 61 04 27 4A 6D
10 33 56 79 1C 3F 62 05 28 4B 6E 11 34 57 7A 1D
40 63 06 29 4C 6F 12 35 58 7B 1E 41 64 07 2A 4D
70 13 36 59 7C 1F 42 65 08 2B 4E 71 14 37 5A 7D
20 43 66 09 2C 4F 72 15* 38* 5B 7E 21 44 67 0A 2D
50 73* 16* 39* 5C 7F 22 45 68 0B 2E 51 74* 17* 3A 5D

Si l'on construit des blocs de 128 octets de message différents
dans les 7 octets aux indices (hex) 15 16 17 38 39 73 74
que j'ai repéré par 14 étoiles, ces octets forment 6 "segments"
de 2 ou 3 octets dans les deux moitiés.
On peut donc au moins espérer que la variable j ne propage pas
de changement de segment en segment; et par exemple on peut
choisir les octets en (hex) 17 39 et 74 pour forcer cela dans
les 3 premiers segments. Pour les 3 autres, il faut être plus
habile, ou compter sur la force brute (2^24 essais en moyenne).
On a beaucoup de liberté pour le reste, ce qui permet de
manipuler pas mal les S[] avant les 6 segments; il faut
cette liberté, pour faire en sorte que les octets permutés ne
se propagent pas via les autres octets du message, et que les
permutations causées par les 7 octets modifiés dans les 6
segments se compensent d'une manière ou d'une autre.

Il y a peut-être une raison toute bête pour que ça ne marche pas. Il
me semble qu'il faut au minimum un segment de 3 octets pour corriger
les permutations faites via les octets de ce segment. Avec des segments
de seulement 2 octets on peut créer une collision sur j, donc on ne
propage pas d'erreurs dans les permutations à venir, MAIS on ne peut
pas compenser les erreurs sur les 2 permutations déjà faites à
travers ce segment.

Comme entre les segments les octets des 2 messages ne bougent pas, un
rapide coup d'oeil sur la fonction de compression indique que dès
qu'on tombe sur un S[i] en différence on créé à partir de cette
position une divergence sur j qui ne semble pas contrôlable.

Je ne dis pas que c'est facile, mais c'est loin d'être désespéré,
comme mission.

A nouveau: la différence fondemmentale entre TAZ et RC4, c'est
que dans RC4 la permutation est présumée secrète, alors que
dans TAZ elle est connue de l'attaquant, ce qui constitue pour
lui un avantage décisif.


François Grieu

Dans l'article <1112822237.231564.239250@f14g2000cwb.googlegroups.com>,
cgonzale@numericable.fr a écrit:

Il y a peut-être une raison toute bête pour que ça ne marche pas.
Il me semble qu'il faut au minimum un segment de 3 octets pour
corriger les permutations faites via les octets de ce segment.

D'accord, si il faut corriger tout S[] et aussi j. Mais deux
objections indépendantes:


1) Si on préfére des segments de 3, j'ai

00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F
10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F
20 21 22 23 24 25 26 27 28 29 2A 2B 2C 2D 2E 2F
30 31 32 33 34 35 36 37 38 39 3A 3B 3C 3D 3E 3F
40 41 42 43 44 45 46 47 48 49 4A 4B 4C 4D 4E 4F
50 51 52 53 54 55 56 57 58 59 5A 5B 5C 5D 5E 5F
60 61 62 63 64 65 66* 67* 68* 69 6A 6B 6C 6D 6E 6F
70 71* 72* 73* 74 75 76 77 78 79 7A 7B 7C* 7D* 7E* 7F
00 0B 16 21 2C 37 42 4D 58 63 6E 79 04 0F 1A 25
30 3B 46 51 5C 67* 72* 7D* 08 13 1E 29 34 3F 4A 55
60 6B 76 01 0C 17 22 2D 38 43 4E 59 64 6F 7A 05
10 1B 26 31 3C 47 52 5D 68* 73* 7E* 09 14 1F 2A 35
40 4B 56 61 6C 77 02 0D 18 23 2E 39 44 4F 5A 65
70 7B 06 11 1C 27 32 3D 48 53 5E 69 74 7F 0A 15
20 2B 36 41 4C 57 62 6D 78 03 0E 19 24 2F 3A 45
50 5B 66* 71* 7C* 07 12 1D 28 33 3E 49 54 5F 6A 75


2) si on considère 2 segments de 2 octets pas trop éloignés,
il est assez probable sans rien faire de spécial que ce qu'il
y a entre les deux n'agrave pas la différence causée par le
premier; et je ne vois rien qui empêche les 2 segments de
se compenser, comme pourrait (je crois) le faire un segment
de 4 octets.


Note: un autre multiplicateur que 11 pourrait améliorer un peu
les choses SUR CE CRITERE; de mémoire, je crois qu'on démontre
que pour de grands n, si on prend k = l'entier premier avec n
le plus proche de n/phi avec phi = (racine(5)+1)/2, la
progression arithmétique par k, modulo n, est une permutation
qui sépare bien les points d'arrivée les uns des autres;
ça donnerais 79, au lieu de 11.

Au risque qu'on remarque que je me répète: le fait que l'adversaire
conaisse S[] et j lui est TRES favorable (par rapport à RC4), et
il n'est pas sur que rentrer chaque octet 2 fois dans le hash soit
suffisant pour compenser cela.


Bon, j'arrête d'en parler tant que j'ai pas quelque chose de
plus abouti, comme attaque.


François Grieu

Francois Grieu wrote:

Dans l'article
<1112822237.231564.239250@f14g2000cwb.googlegroups.com>,

cgonzale@numericable.fr a écrit:

Il y a peut-être une raison toute bête pour que ça ne marche
pas.

Il me semble qu'il faut au minimum un segment de 3 octets pour
corriger les permutations faites via les octets de ce segment.

D'accord, si il faut corriger tout S[] et aussi j. Mais deux
objections indépendantes:


1) Si on préfére des segments de 3, j'ai

00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F
10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F
20 21 22 23 24 25 26 27 28 29 2A 2B 2C 2D 2E 2F
30 31 32 33 34 35 36 37 38 39 3A 3B 3C 3D 3E 3F
40 41 42 43 44 45 46 47 48 49 4A 4B 4C 4D 4E 4F
50 51 52 53 54 55 56 57 58 59 5A 5B 5C 5D 5E 5F
60 61 62 63 64 65 66* 67* 68* 69 6A 6B 6C 6D 6E 6F
70 71* 72* 73* 74 75 76 77 78 79 7A 7B 7C* 7D* 7E* 7F
00 0B 16 21 2C 37 42 4D 58 63 6E 79 04 0F 1A 25
30 3B 46 51 5C 67* 72* 7D* 08 13 1E 29 34 3F 4A 55
60 6B 76 01 0C 17 22 2D 38 43 4E 59 64 6F 7A 05
10 1B 26 31 3C 47 52 5D 68* 73* 7E* 09 14 1F 2A 35
40 4B 56 61 6C 77 02 0D 18 23 2E 39 44 4F 5A 65
70 7B 06 11 1C 27 32 3D 48 53 5E 69 74 7F 0A 15
20 2B 36 41 4C 57 62 6D 78 03 0E 19 24 2F 3A 45
50 5B 66* 71* 7C* 07 12 1D 28 33 3E 49 54 5F 6A 75


2) si on considère 2 segments de 2 octets pas trop éloignés,
il est assez probable sans rien faire de spécial que ce qu'il
y a entre les deux n'agrave pas la différence causée par le
premier; et je ne vois rien qui empêche les 2 segments de
se compenser, comme pourrait (je crois) le faire un segment
de 4 octets.


Note: un autre multiplicateur que 11 pourrait améliorer un peu
les choses SUR CE CRITERE; de mémoire, je crois qu'on démontre
que pour de grands n, si on prend k = l'entier premier avec n
le plus proche de n/phi avec phi = (racine(5)+1)/2, la
progression arithmétique par k, modulo n, est une permutation
qui sépare bien les points d'arrivée les uns des autres;
ça donnerais 79, au lieu de 11.

Au risque qu'on remarque que je me répète: le fait que l'adversaire
conaisse S[] et j lui est TRES favorable (par rapport à RC4), et
il n'est pas sur que rentrer chaque octet 2 fois dans le hash soit
suffisant pour compenser cela.

Après réflexion je dirais que ce n'est pas forcément un avantage
décisif, mais ça aide beaucoup à se placer dans des conditions
favorables pour une collision.

Pour rendre le problème plus difficile pour l'attaquant j'essaye de
modéliser une construction par blocs de 256 octets où la permutation
d'indices est dépendante du bloc, et j'ai par exemple trouvé une
fonction simple: on prend une autre table de permutation S' de 256
éléments où on "comprime" un bloc suivant le KSA de RC4, puis on se
sert de cette table comme permutation d'indices des octets du même
bloc mais pour la table S.

Chaque position ou indice d'octet du message, lors du 2ème round,
dépend de tous les octets du bloc et ce de façon hautement
"non-linéaire". La meilleure attaque reste bien de provoquer des
collisions "délibérées".

J'ai réussi à estimer la complexité d'un certain type d'attaque de
collision par "triplets". Voici mon raisonnement:
On cherche un bloc M où aucun octet n'est imposé et qui:
- (E1) provoque une séquence de 3 indices consécutifs dans S'[]
(quelle que soit la position, quels que soient les indices. Cela peut
se noter: S'[i0] = k, S'[i0+1] = k+1, S'[i0+2] = k+2),
- (E2) fasse que dans S il y ait une collision sur j et qu'il n'y ait
pas d'erreur de permutations, ce qui veut dire que si on note S[k]=V0,
S[k+1]=V1 et S[k+2]=V2 alors le triplet va provoquer deux collisions:
- V0 permute avec V1, puis au coup d'après idem (puisque V0 s'est
retrouvé en position k+1), et V2 permute avec lui-même
- ou alors: V0, V1 et V2 sont permutés avec eux-mêmes.

Chacune de ces 2 collisions sur la table S[] impose une valeur unique
pour le triplet.

L'événement E1 a une probabilité P1 = 254/(255.256)
L'événement E2 a une probabilité P2 = 2/(256.256.256)

Ensuite on cherche un autre bloc M' tel que:
- (E'1) il provoque la même séquence d'indices consécutifs dans S'
(même position, mêmes indices)
- (E'2) fasse que dans S il y ait une collision sur j et qu'il n'y ait
pas d'erreur de permutations.
- "idéalement" les octets de M' qui sont à une position ne se
trouvant pas dans le triplet d'indices sont identiques à M (sinon,
cela vient "perturber" le problème puisqu'on provoque d'autres
permutations incontrolées au sens où on n'arrive pas estimer la
probabilité qu'elles puissent provoquer une collision)

On a : P'1 = 1/(254.255.256)
P'2 = P2.

J'estime la probabilité d'une collision , en cherchant au hasard:
P = P1.P2.P'1.P'2 ~ 2^-31.2^-47 ce qui donne 2^-78.

Cela donne une attaque en o(2^77) paire de blocs. Dans cette
construction, avec un hash de 160 bits, la meilleure attaque serait à
peine 8 fois plus rapide que l'attaque des anniversaires ...

Bon, j'arrête d'en parler tant que j'ai pas quelque chose de
plus abouti, comme attaque.


François Grieu

Dans l'article <1113059040.950467.241980@l41g2000cwc.googlegroups.com>,
cgonzale@numericable.fr a écrit:

J'estime la probabilité d'une collision , en cherchant au hasard:
P = P1.P2.P'1.P'2 ~ 2^-31.2^-47 ce qui donne 2^-78.

Cela donne une attaque en o(2^77) paire de blocs. Dans cette
construction, avec un hash de 160 bits, la meilleure attaque serait à
peine 8 fois plus rapide que l'attaque des anniversaires ...

Problèmes

- la sécurité conjecturée pour TAZ était 2^128 (voire 2^800),
et 2^77 c'est trop faible pour un hash qui produit 256 bits.

- rien n'oblige l'adversaire à "chercher au hasard", puisqu'il
connais chaque donnée manipulée; on ne peut valablement
parler de probabilité que si l'adversaire essaye au hasard,
ou si une inconnue de l'attaquant est choisie au hasard,
et aucune des deux hypothèses n'est garantie.

Dans les constructions "modernes" de hash, on essaye de pouvoir
montrer que si l'adversaire parvient à trouver une collision,
alors ils sait aussi faire quelque chose d'autre qui semble
improbable. Avec TAZ, il me semble sans espoir de démontrer que
trouver une collision implique une faiblesse de RC4 qui ne soit
déjà bien connue.


François Grieu

Francois Grieu <fgrieu@francenet.fr> wrote in message news:<fgrieu-0865D2.09385211042005@news5-e.proxad.net>...

Dans l'article <1113059040.950467.241980@l41g2000cwc.googlegroups.com>,
cgonzale@numericable.fr a ?crit:

J'estime la probabilit? d'une collision , en cherchant au hasard:
P = P1.P2.P'1.P'2 ~ 2^-31.2^-47 ce qui donne 2^-78.

Cela donne une attaque en o(2^77) paire de blocs. Dans cette
construction, avec un hash de 160 bits, la meilleure attaque serait ?
peine 8 fois plus rapide que l'attaque des anniversaires ...

Probl?mes

- la s?curit? conjectur?e pour TAZ ?tait 2^128 (voire 2^800),
et 2^77 c'est trop faible pour un hash qui produit 256 bits.

- rien n'oblige l'adversaire ? "chercher au hasard", puisqu'il
connais chaque donn?e manipul?e; on ne peut valablement
parler de probabilit? que si l'adversaire essaye au hasard,
ou si une inconnue de l'attaquant est choisie au hasard,
et aucune des deux hypoth?ses n'est garantie.

Dans les constructions "modernes" de hash, on essaye de pouvoir
montrer que si l'adversaire parvient ? trouver une collision,
alors ils sait aussi faire quelque chose d'autre qui semble
improbable. Avec TAZ, il me semble sans espoir de d?montrer que
trouver une collision implique une faiblesse de RC4 qui ne soit
d?j? bien connue.


Fran?ois Grieu

Si ?a ne marche pas aussi bien c'est que je ne cherche pas dans la
bonne direction.

Je laisse donc de c?t? les permutations en cascade (que ce soit avec
la toute premi?re version de TAZ, o? on faisait une permutation
suppl?mentaire en i+127, ou avec cette proposition plus r?cente ou la
permutation d?pend du bloc), et je reviens aux fondamentaux de la
cryptologie.

Il me semble que la 1?re ?tape devrait ?tre de diffuser les
diff?rences que l'on peut avoir sur certains octets du bloc, pour
qu'on ne puisse pas les recr?er au milieu de la fonction. j'imagine
bien une fonction interm?diaire, m?me lin?aire, qui va m?langer tous
les octets du bloc pour qu'? l'arriv?e on ait un bloc o?:
- chaque octet d?pend de tous les octets du bloc initial (au moins)
- chaque bit d?pend de tous les bits du bloc initial (au mieux)
et la condition la plus d?licate:
- on ne puisse pas cr?er deux blocs qui produisent des diff?rences
d'octets localis?es (par exemple sur des s?quences de 3 octets ? une
m?me position, les autres octets ?tant identiques).

je ne d?sesp?re pas de trouver une telle fonction.
Ensuite je fais confiance ? la primitive RC4 sur le c?t? non lin?aire
de la transformation de la table de permutation.