Nouvelle "famille" de fonctions de hachage basée sur RC4
7 réponses
cgonzale
Bonjour à tous
Je vous invite à lire le lien suivant qui présente un nouveau modèle
de fonction de hachage:
http://perso.numericable.fr/~cgonzale/hur/hurricane.html
En résumé: mon idée maîtresse est de me baser sur le stream cipher RC4
et en particulier sur le KSA ("Key Setup Algorithm" ou algo de
préparation de la clé). Au moins je suis assuré que ma fonction va se
baser sur un algorithme connu, et analysé en profondeur. De plus, je
peux ma baser également sur une taille de variable de chaînage
colossale : 256! ce qui doit dissuader une attaque de type
"man-in-the-middle" ou même l'attaque des anniversaires.
En gros: au lieu de ne traiter qu'une clé de taille limitée (<= 256
octets), on va faire en sorte que la clé soit le message qu'on veut
hacher. La clé est donc de taille variable. La fonction de compression
va traiter chaque octet du message, en séquence, et lorsqu'on a traité
le dernier octet on obtient un état interne qui dépend donc
logiquement de tout le message. Ensuite, il y a une phase de sécurité
avec "padding" (on fait tourner l'algo "à vide" pour bien mélanger
l'état interne), et enfin on génère le hash qui est tout simplement
une séquence limitée du flux de clé (keystream) de RC4.
Ca c'est dans les grandes lignes.
Dans les détails, il faut déterminer une bonne fonction de
compression, qui se base sur les permutations "pseudo-aléatoires" de
RC4, et qui doit empêcher TOUTE COLLISION (pour ce qui est de la
difficulté d'inverser, ça c'est gagné).
Voici donc ma nouvelle proposition (TAZ) qui fait suite à une
discussion avec M. François Grieu, qui semble très efficace (+ rapide
que SHA-1):
(le message M est divisé en k octets M0 M1 .. Mk-1)
j = 0
For i = 0 to k 1:
(début de la compression)
j = ( j + S[i mod 256] + Mi ) mod 256
Swap S[i] and S[j]
j = ( j + S[(i+128) mod 256] ) mod 256
Swap S[i+128] and S[j]
(fin de la compression)
End-for.
L'idée (simple) c'est que si on peut trouver deux messages qui
diffèrent mettons sur 2 octets consécutifs , et qui rattrappent la
différence de permutations côté i, on ne peut pas trouver deux
messages différents qui vont rattraper SIMULTANEMENT la différence de
permutations côté i, et côté i+128.
Voilà, j'attends vos avis sur la question, et ou sur la manière de
renforcer encore la fonction.
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Mathieu Arnold
Claudio écrivait:
Voilà, j'attends vos avis sur la question, et ou sur la manière de renforcer encore la fonction.
Je pense qu'avec un hash de 256 octets, il va être facile d'y faire rentrer tout les fichiers qui ont comme taille 256 octets, pour les autres fichiers, de taille inférieure ou supérieure, ils auront forcément des copains (aka des fichiers qui ont le même hash) dans les fichiers qui font 256 octets.
-- Mathieu Arnold
Claudio écrivait:
Voilà, j'attends vos avis sur la question, et ou sur la manière de
renforcer encore la fonction.
Je pense qu'avec un hash de 256 octets, il va être facile d'y faire
rentrer tout les fichiers qui ont comme taille 256 octets, pour les
autres fichiers, de taille inférieure ou supérieure, ils auront
forcément des copains (aka des fichiers qui ont le même hash) dans les
fichiers qui font 256 octets.
Voilà, j'attends vos avis sur la question, et ou sur la manière de renforcer encore la fonction.
Je pense qu'avec un hash de 256 octets, il va être facile d'y faire rentrer tout les fichiers qui ont comme taille 256 octets, pour les autres fichiers, de taille inférieure ou supérieure, ils auront forcément des copains (aka des fichiers qui ont le même hash) dans les fichiers qui font 256 octets.
La version 0.3 de Hurricane diffère beaucoup d'une précédente version dont j'avais relevé la non-résistance aux collisions; en particulier il n'y a plus qu'une permutation S, au lieu de deux (incidemment il reste un S2 dans la description, il faut lire S).
Claudio propose aussi TAZ, une version simplifiée de Hurricane. Partant de S[x]=x pour 0<=x<256, la compression de TAZ est:
For i = 0 to longueur_du_message-1: j = ( j + S[i mod 256] + Mi ) mod 256 Swap S[i] and S[j] j = ( j + S[(i+128) mod 256] ) mod 256 Swap S[i+128] and S[j]
De tête, sauf erreur de ma part, changer M0=0 en M08 dans le premier octet d'un message suffit à provoquer une collision !
Même si je me trompe, je reste pessimiste sur la résistance aux collisions délibérément provoquées, tant pour Hurricane que pour TAZ. Le problème, c'est que dans une fonction de hashage, l'adversaire "voit" tout, alors que dans RC4, il y a une clé.
François Grieu
Dans l'article <5be1a970.0503280718.3aff3aad@posting.google.com>,
cgonzale@numericable.fr (Claudio) propose:
La version 0.3 de Hurricane diffère beaucoup d'une précédente
version dont j'avais relevé la non-résistance aux collisions;
en particulier il n'y a plus qu'une permutation S, au lieu de
deux (incidemment il reste un S2 dans la description, il faut
lire S).
Claudio propose aussi TAZ, une version simplifiée de Hurricane.
Partant de S[x]=x pour 0<=x<256, la compression de TAZ est:
For i = 0 to longueur_du_message-1:
j = ( j + S[i mod 256] + Mi ) mod 256
Swap S[i] and S[j]
j = ( j + S[(i+128) mod 256] ) mod 256
Swap S[i+128] and S[j]
De tête, sauf erreur de ma part, changer M0=0 en M08 dans le
premier octet d'un message suffit à provoquer une collision !
Même si je me trompe, je reste pessimiste sur la résistance
aux collisions délibérément provoquées, tant pour Hurricane que
pour TAZ. Le problème, c'est que dans une fonction de hashage,
l'adversaire "voit" tout, alors que dans RC4, il y a une clé.
La version 0.3 de Hurricane diffère beaucoup d'une précédente version dont j'avais relevé la non-résistance aux collisions; en particulier il n'y a plus qu'une permutation S, au lieu de deux (incidemment il reste un S2 dans la description, il faut lire S).
Claudio propose aussi TAZ, une version simplifiée de Hurricane. Partant de S[x]=x pour 0<=x<256, la compression de TAZ est:
For i = 0 to longueur_du_message-1: j = ( j + S[i mod 256] + Mi ) mod 256 Swap S[i] and S[j] j = ( j + S[(i+128) mod 256] ) mod 256 Swap S[i+128] and S[j]
De tête, sauf erreur de ma part, changer M0=0 en M08 dans le premier octet d'un message suffit à provoquer une collision !
Même si je me trompe, je reste pessimiste sur la résistance aux collisions délibérément provoquées, tant pour Hurricane que pour TAZ. Le problème, c'est que dans une fonction de hashage, l'adversaire "voit" tout, alors que dans RC4, il y a une clé.
La version 0.3 de Hurricane diffère beaucoup d'une précédente version dont j'avais relevé la non-résistance aux collisions; en particulier il n'y a plus qu'une permutation S, au lieu de deux (incidemment il reste un S2 dans la description, il faut lire S).
Claudio propose aussi TAZ, une version simplifiée de Hurricane. Partant de S[x]=x pour 0<=x<256, et j=0, TAZ comprime un message M de k octets par:
For i = 0 to k-1: j = ( j + S[i mod 256] + Mi ) mod 256 Swap S[i] and S[j] j = ( j + S[(i+128) mod 256] ) mod 256 Swap S[i+128] and S[j]
De tête, sauf erreur de ma part, changer M0=0 en M08 suffit à provoquer une collision !
Avec Hurricane (0.3), il me semble impossible de trouver des collisions avec une différence de seulement 1 octet dans les messages; mais je reste pessimiste sur la résistance aux collisions délibérément provoquées. Un problème, c'est que dans une fonction de hashage, l'adversaire "voit" tout, alors que dans RC4, il y a une clé. L'autre problème, c'est que des changements localisés dans le message ont une chance de se compenser; alors puisque c'est possible et que l'on sais tout, on parvient à forcer la chance et à trouver des collisions.
AMHA, pour parvenir à quelque chose de (peut-être) sur dans cette voie "RC4" (intéressante sur un microprocesseur 8 bits), sans pour autant utiliser une clé secrète (auquel cas il y a des solutions a sécurité provable, genre poly1305), une piste serait une structure où l'on puisse démonter que tout changement sur une petite portion du message ne peut en aucun cas provoquer une collision dans la phase de compression; ET où ce changement a le temps "d'exploser" et de devenir irratrapable avant qu'un changement ultérieur puisse le compenser.
François Grieu [reposté avec révision]
Dans l'article <5be1a970.0503280718.3aff3aad@posting.google.com>,
cgonzale@numericable.fr (Claudio) propose:
La version 0.3 de Hurricane diffère beaucoup d'une précédente
version dont j'avais relevé la non-résistance aux collisions;
en particulier il n'y a plus qu'une permutation S, au lieu de
deux (incidemment il reste un S2 dans la description, il faut
lire S).
Claudio propose aussi TAZ, une version simplifiée de Hurricane.
Partant de S[x]=x pour 0<=x<256, et j=0, TAZ comprime un
message M de k octets par:
For i = 0 to k-1:
j = ( j + S[i mod 256] + Mi ) mod 256
Swap S[i] and S[j]
j = ( j + S[(i+128) mod 256] ) mod 256
Swap S[i+128] and S[j]
De tête, sauf erreur de ma part, changer M0=0 en M08 suffit
à provoquer une collision !
Avec Hurricane (0.3), il me semble impossible de trouver des
collisions avec une différence de seulement 1 octet dans les
messages; mais je reste pessimiste sur la résistance aux
collisions délibérément provoquées. Un problème, c'est que
dans une fonction de hashage, l'adversaire "voit" tout, alors
que dans RC4, il y a une clé. L'autre problème, c'est que des
changements localisés dans le message ont une chance de se
compenser; alors puisque c'est possible et que l'on sais tout,
on parvient à forcer la chance et à trouver des collisions.
AMHA, pour parvenir à quelque chose de (peut-être) sur dans
cette voie "RC4" (intéressante sur un microprocesseur 8 bits),
sans pour autant utiliser une clé secrète (auquel cas il y a
des solutions a sécurité provable, genre poly1305), une piste
serait une structure où l'on puisse démonter que tout changement
sur une petite portion du message ne peut en aucun cas provoquer
une collision dans la phase de compression; ET où ce changement
a le temps "d'exploser" et de devenir irratrapable avant qu'un
changement ultérieur puisse le compenser.
La version 0.3 de Hurricane diffère beaucoup d'une précédente version dont j'avais relevé la non-résistance aux collisions; en particulier il n'y a plus qu'une permutation S, au lieu de deux (incidemment il reste un S2 dans la description, il faut lire S).
Claudio propose aussi TAZ, une version simplifiée de Hurricane. Partant de S[x]=x pour 0<=x<256, et j=0, TAZ comprime un message M de k octets par:
For i = 0 to k-1: j = ( j + S[i mod 256] + Mi ) mod 256 Swap S[i] and S[j] j = ( j + S[(i+128) mod 256] ) mod 256 Swap S[i+128] and S[j]
De tête, sauf erreur de ma part, changer M0=0 en M08 suffit à provoquer une collision !
Avec Hurricane (0.3), il me semble impossible de trouver des collisions avec une différence de seulement 1 octet dans les messages; mais je reste pessimiste sur la résistance aux collisions délibérément provoquées. Un problème, c'est que dans une fonction de hashage, l'adversaire "voit" tout, alors que dans RC4, il y a une clé. L'autre problème, c'est que des changements localisés dans le message ont une chance de se compenser; alors puisque c'est possible et que l'on sais tout, on parvient à forcer la chance et à trouver des collisions.
AMHA, pour parvenir à quelque chose de (peut-être) sur dans cette voie "RC4" (intéressante sur un microprocesseur 8 bits), sans pour autant utiliser une clé secrète (auquel cas il y a des solutions a sécurité provable, genre poly1305), une piste serait une structure où l'on puisse démonter que tout changement sur une petite portion du message ne peut en aucun cas provoquer une collision dans la phase de compression; ET où ce changement a le temps "d'exploser" et de devenir irratrapable avant qu'un changement ultérieur puisse le compenser.
François Grieu [reposté avec révision]
Kevin Drapel
En gros: au lieu de ne traiter qu'une clé de taille limitée (<= 256 octets), on va faire en sorte que la clé soit le message qu'on veut hacher. La clé est donc de taille variable. La fonction de compression va traiter chaque octet du message, en séquence, et lorsqu'on a traité le dernier octet on obtient un état interne qui dépend donc logiquement de tout le message. Ensuite, il y a une phase de sécurité avec "padding" (on fait tourner l'algo "à vide" pour bien mélanger l'état interne), et enfin on génère le hash qui est tout simplement une séquence limitée du flux de clé (keystream) de RC4.
L'idée est séduisante. Je me demande si la présence de clés faibles dans RC4 et d'autres attaques sur des clés apparentées peut compromettre votre hachage (inversibilité partielle). En particulier dans le papier de Shamir, on peut lire une attaque portant sur la même clé concaténée avec un vecteur d'initialisation variable de taille constante (placé au début de la clé ou à la fin, les deux attaques sont présentées). Par exemple les messages suivants sont des candidats pour cette attaque "key recovery" :
192.168.1.60 Hello world 192.168.1.40 Hello world 128.178.12.4 Hello world
Peut-être que RC4 n'est pas la meilleure solution en terme de résistance (mais intéressante pour les performances) ?
En gros: au lieu de ne traiter qu'une clé de taille limitée (<= 256
octets), on va faire en sorte que la clé soit le message qu'on veut
hacher. La clé est donc de taille variable. La fonction de
compression va traiter chaque octet du message, en séquence, et
lorsqu'on a traité le dernier octet on obtient un état interne qui
dépend donc logiquement de tout le message. Ensuite, il y a une phase
de sécurité avec "padding" (on fait tourner l'algo "à vide" pour bien
mélanger l'état interne), et enfin on génère le hash qui est tout
simplement une séquence limitée du flux de clé (keystream) de RC4.
L'idée est séduisante. Je me demande si la présence de clés faibles dans
RC4 et d'autres attaques sur des clés apparentées peut compromettre
votre hachage (inversibilité partielle). En particulier dans le papier
de Shamir, on peut lire une attaque portant sur la même clé concaténée
avec un vecteur d'initialisation variable de taille constante (placé au
début de la clé ou à la fin, les deux attaques sont présentées). Par
exemple les messages suivants sont des candidats pour cette attaque "key
recovery" :
192.168.1.60 Hello world
192.168.1.40 Hello world
128.178.12.4 Hello world
Peut-être que RC4 n'est pas la meilleure solution en terme de résistance
(mais intéressante pour les performances) ?
En gros: au lieu de ne traiter qu'une clé de taille limitée (<= 256 octets), on va faire en sorte que la clé soit le message qu'on veut hacher. La clé est donc de taille variable. La fonction de compression va traiter chaque octet du message, en séquence, et lorsqu'on a traité le dernier octet on obtient un état interne qui dépend donc logiquement de tout le message. Ensuite, il y a une phase de sécurité avec "padding" (on fait tourner l'algo "à vide" pour bien mélanger l'état interne), et enfin on génère le hash qui est tout simplement une séquence limitée du flux de clé (keystream) de RC4.
L'idée est séduisante. Je me demande si la présence de clés faibles dans RC4 et d'autres attaques sur des clés apparentées peut compromettre votre hachage (inversibilité partielle). En particulier dans le papier de Shamir, on peut lire une attaque portant sur la même clé concaténée avec un vecteur d'initialisation variable de taille constante (placé au début de la clé ou à la fin, les deux attaques sont présentées). Par exemple les messages suivants sont des candidats pour cette attaque "key recovery" :
192.168.1.60 Hello world 192.168.1.40 Hello world 128.178.12.4 Hello world
Peut-être que RC4 n'est pas la meilleure solution en terme de résistance (mais intéressante pour les performances) ?
En gros: au lieu de ne traiter qu'une clé de taille limitée (<= 256
octets), on va faire en sorte que la clé soit le message qu'on veut
hacher. La clé est donc de taille variable. La fonction de compression va traiter chaque octet du message, en séquence, et lorsqu'on a traité le dernier octet on obtient un état interne qui
dépend donc logiquement de tout le message. Ensuite, il y a une phase
de sécurité avec "padding" (on fait tourner l'algo "à vide" pour bien
mélanger l'état interne), et enfin on génère le hash qui est tout
simplement une séquence limitée du flux de clé (keystream) de RC4.
L'idée est séduisante. Je me demande si la présence de clés faibles dans
RC4 et d'autres attaques sur des clés apparentées peut compromettre votre hachage (inversibilité partielle). En particulier dans le papier
de Shamir, on peut lire une attaque portant sur la même clé concaténée
avec un vecteur d'initialisation variable de taille constante (placé au
début de la clé ou à la fin, les deux attaques sont présentées). Par
exemple les messages suivants sont des candidats pour cette attaque "key
recovery" :
192.168.1.60 Hello world 192.168.1.40 Hello world 128.178.12.4 Hello world
Peut-être que RC4 n'est pas la meilleure solution en terme de résistance
Il s'agit d'une faiblesse statistique sur les premiers octets générés, en particulier le deuxième octet. Je ne suis pas inquiet de ce type d'attaque: dans mon système j'effectue un tour à vide de 256 étapes après avoir comprimé le message. Il s'agit bien de "défausser" 256 octets du keystream avant de sortir le hash. On est donc dans une situation où on ne peut pas (a priori) exploiter cette faiblesse.
Cdt, Claudio
Kevin Drapel wrote:
En gros: au lieu de ne traiter qu'une clé de taille limitée (<=
256
octets), on va faire en sorte que la clé soit le message qu'on
veut
hacher. La clé est donc de taille variable. La fonction de
compression va traiter chaque octet du message, en séquence, et
lorsqu'on a traité le dernier octet on obtient un état interne
qui
dépend donc logiquement de tout le message. Ensuite, il y a une
phase
de sécurité avec "padding" (on fait tourner l'algo "à vide" pour
bien
mélanger l'état interne), et enfin on génère le hash qui est
tout
simplement une séquence limitée du flux de clé (keystream) de
RC4.
L'idée est séduisante. Je me demande si la présence de clés
faibles dans
RC4 et d'autres attaques sur des clés apparentées peut compromettre
votre hachage (inversibilité partielle). En particulier dans le
papier
de Shamir, on peut lire une attaque portant sur la même clé
concaténée
avec un vecteur d'initialisation variable de taille constante (placé
au
début de la clé ou à la fin, les deux attaques sont présentées).
Par
exemple les messages suivants sont des candidats pour cette attaque
"key
recovery" :
192.168.1.60 Hello world
192.168.1.40 Hello world
128.178.12.4 Hello world
Peut-être que RC4 n'est pas la meilleure solution en terme de
résistance
Il s'agit d'une faiblesse statistique sur les premiers octets
générés, en particulier le deuxième octet. Je ne suis pas inquiet
de ce type d'attaque: dans mon système j'effectue un tour à vide de
256 étapes après avoir comprimé le message. Il s'agit bien de
"défausser" 256 octets du keystream avant de sortir le hash.
On est donc dans une situation où on ne peut pas (a priori) exploiter
cette faiblesse.
En gros: au lieu de ne traiter qu'une clé de taille limitée (<= 256
octets), on va faire en sorte que la clé soit le message qu'on veut
hacher. La clé est donc de taille variable. La fonction de compression va traiter chaque octet du message, en séquence, et lorsqu'on a traité le dernier octet on obtient un état interne qui
dépend donc logiquement de tout le message. Ensuite, il y a une phase
de sécurité avec "padding" (on fait tourner l'algo "à vide" pour bien
mélanger l'état interne), et enfin on génère le hash qui est tout
simplement une séquence limitée du flux de clé (keystream) de RC4.
L'idée est séduisante. Je me demande si la présence de clés faibles dans
RC4 et d'autres attaques sur des clés apparentées peut compromettre votre hachage (inversibilité partielle). En particulier dans le papier
de Shamir, on peut lire une attaque portant sur la même clé concaténée
avec un vecteur d'initialisation variable de taille constante (placé au
début de la clé ou à la fin, les deux attaques sont présentées). Par
exemple les messages suivants sont des candidats pour cette attaque "key
recovery" :
192.168.1.60 Hello world 192.168.1.40 Hello world 128.178.12.4 Hello world
Peut-être que RC4 n'est pas la meilleure solution en terme de résistance
Il s'agit d'une faiblesse statistique sur les premiers octets générés, en particulier le deuxième octet. Je ne suis pas inquiet de ce type d'attaque: dans mon système j'effectue un tour à vide de 256 étapes après avoir comprimé le message. Il s'agit bien de "défausser" 256 octets du keystream avant de sortir le hash. On est donc dans une situation où on ne peut pas (a priori) exploiter cette faiblesse.
Cdt, Claudio
cgonzale
Bien joué !
TAZ est touché ... mais pas encore complètement coulé. Voici la version 0.2 qui déjoue ce "court-circuit" astucieux (et qui peut d'ailleurs se produire à n'importe quelle position du tableau avec un peu de chance).
J'étends le modèle de TAZ:
j = ( j + S[i mod 256] + Mi ) mod 256 Swap S[i] and S[j] j = ( j + S[(i+K) mod 256] ) mod 256 Swap S[i+K] and S[j] K est une constante, comprise entre 0 et 255.
Le but est d'éviter la configuration suivante: - L'octet du message 1 provoque: Auto-Permutation (AP) + Permutation "vraie" (PV). - L'octet du message 2 provoque: Permutation "vraie" (PV) + Auto-Permutation (AP). - les deux permutations vraies (ie permutant des éléments différents) concernent deux mêmes positions. Cette configuration amène un cas de collision qu'on peut qualifier de trivial.
Mathématiquement cela s'exprime par (en supposant qu'on a même "j" et même tableau avant de traiter l'octet "malicieux"): Message 1: j1 = j0 + S[i] + Mi = i (AP) Puis j2 = i + S[i+K] (PV) Message 2: j0 + S[i] + M'i = j'1 (PV) j'1 + S[i+K] = i + K (AP)
Avec la condition supplémentaire : j2 = j'1 . Ce qui implique: (E1) j0 + S[i] + Mi = i (E2) j0 + S[i] + M'i + S[i+K] = i + K (E3) i + S[i+K] = j0 + S[i] + M'i
(E2) et (E3) implique: i + S[i+K] + S[i+K] = i + K on a donc 2.S[i+K] = K modulo 256.
Si K est impair cette configuration ne peut jamais arriver.
Je propose donc par exemple K7.
Claudio
Bien joué !
TAZ est touché ... mais pas encore complètement coulé. Voici la
version 0.2 qui déjoue ce "court-circuit" astucieux (et qui peut
d'ailleurs se produire à n'importe quelle position du tableau avec un
peu de chance).
J'étends le modèle de TAZ:
j = ( j + S[i mod 256] + Mi ) mod 256
Swap S[i] and S[j]
j = ( j + S[(i+K) mod 256] ) mod 256
Swap S[i+K] and S[j]
K est une constante, comprise entre 0 et 255.
Le but est d'éviter la configuration suivante:
- L'octet du message 1 provoque: Auto-Permutation (AP) + Permutation
"vraie" (PV).
- L'octet du message 2 provoque: Permutation "vraie" (PV) +
Auto-Permutation (AP).
- les deux permutations vraies (ie permutant des éléments
différents) concernent deux mêmes positions.
Cette configuration amène un cas de collision qu'on peut qualifier de
trivial.
Mathématiquement cela s'exprime par (en supposant qu'on a même "j" et
même tableau avant de traiter l'octet "malicieux"):
Message 1:
j1 = j0 + S[i] + Mi = i (AP)
Puis j2 = i + S[i+K] (PV)
Message 2:
j0 + S[i] + M'i = j'1 (PV)
j'1 + S[i+K] = i + K (AP)
Avec la condition supplémentaire :
j2 = j'1
.
Ce qui implique:
(E1) j0 + S[i] + Mi = i
(E2) j0 + S[i] + M'i + S[i+K] = i + K
(E3) i + S[i+K] = j0 + S[i] + M'i
(E2) et (E3) implique:
i + S[i+K] + S[i+K] = i + K
on a donc 2.S[i+K] = K modulo 256.
Si K est impair cette configuration ne peut jamais arriver.
TAZ est touché ... mais pas encore complètement coulé. Voici la version 0.2 qui déjoue ce "court-circuit" astucieux (et qui peut d'ailleurs se produire à n'importe quelle position du tableau avec un peu de chance).
J'étends le modèle de TAZ:
j = ( j + S[i mod 256] + Mi ) mod 256 Swap S[i] and S[j] j = ( j + S[(i+K) mod 256] ) mod 256 Swap S[i+K] and S[j] K est une constante, comprise entre 0 et 255.
Le but est d'éviter la configuration suivante: - L'octet du message 1 provoque: Auto-Permutation (AP) + Permutation "vraie" (PV). - L'octet du message 2 provoque: Permutation "vraie" (PV) + Auto-Permutation (AP). - les deux permutations vraies (ie permutant des éléments différents) concernent deux mêmes positions. Cette configuration amène un cas de collision qu'on peut qualifier de trivial.
Mathématiquement cela s'exprime par (en supposant qu'on a même "j" et même tableau avant de traiter l'octet "malicieux"): Message 1: j1 = j0 + S[i] + Mi = i (AP) Puis j2 = i + S[i+K] (PV) Message 2: j0 + S[i] + M'i = j'1 (PV) j'1 + S[i+K] = i + K (AP)
Avec la condition supplémentaire : j2 = j'1 . Ce qui implique: (E1) j0 + S[i] + Mi = i (E2) j0 + S[i] + M'i + S[i+K] = i + K (E3) i + S[i+K] = j0 + S[i] + M'i
(E2) et (E3) implique: i + S[i+K] + S[i+K] = i + K on a donc 2.S[i+K] = K modulo 256.
Si K est impair cette configuration ne peut jamais arriver.
Je propose donc par exemple K7.
Claudio
cgonzale
En fait, je me pose la question suivante plus générale. Puisqu'il est possible de faire une construction qui évite les cas de collisions "courtes" (rattrapage des erreurs de permutations sur un ou 2 octets différents au maximum sur des mêmes positions ), le but pour l'attaquant serait d'essayer de trouver un algo qui MINIMISE le nombre d' erreurs de permutations, tout en les changeant. Au fur et à mesure des changements le taux d'erreur s'amenuiserait jusqu'à tomber à zéro.
Déjà un tel algo existe-t-il ?
J'en doute et j'aurais même tendance à croire que l'erreur ne peut que se propager (mais ceci reste à prouver formellement).
Dans TAZ (version K7), quand on créée une pseudo-collision côt é i, c'est à dire qu'on a créé en i les actions: - (message 1) S[i] échangé avec S[i+1] puis S[i+1] échangé avec S[i] - (message 2) S[i] échangé avec lui-même et S[i+1] échangé avec lui-même
On obtient entre 4 et 6 positions où les tableaux ont des valeurs différentes. Cela peut se voir facilement grâce au schéma que j'ai fait sur la page de présentation. Dans le meilleur des cas: 6 positions différentes, dans le pire (ou le meilleur si on est l'attaquant) 4 positions lorsque S[i+127] = 126 et S[i+128] = 128.
Ensuite les messages restent identiques après k > i + 1, et on choisit les valeurs d'octet pour ne pas permuter un octet en erreur.
Le pb c'est que comme i défile, il va bien tomber sur une position en erreur. On peut ensuite choisir les valeurs d'octet des messages pour tomber sur un même j. On permute une 1ère fois: l'octet en erreur se déplace. On permute une deuxième fois: pas de différences.
Globalement le nombre d'erreurs reste identique. Si on ne fait rien d'autre que compenser l'erreur en cours, on ne diminue pas le nombre global d'erreur.
En fait, je me pose la question suivante plus générale. Puisqu'il
est possible de faire une construction qui évite les cas de collisions
"courtes" (rattrapage des erreurs de permutations sur un ou 2 octets
différents au maximum sur des mêmes positions ), le but pour
l'attaquant serait d'essayer de trouver un algo qui MINIMISE le nombre
d' erreurs de permutations, tout en les changeant. Au fur et à mesure
des changements le taux d'erreur s'amenuiserait jusqu'à tomber à
zéro.
Déjà un tel algo existe-t-il ?
J'en doute et j'aurais même tendance à croire que l'erreur ne peut
que se propager (mais ceci reste à prouver formellement).
Dans TAZ (version K=127), quand on créée une pseudo-collision côt é
i, c'est à dire qu'on a créé en i les actions:
- (message 1) S[i] échangé avec S[i+1] puis S[i+1] échangé avec
S[i]
- (message 2) S[i] échangé avec lui-même et S[i+1] échangé avec
lui-même
On obtient entre 4 et 6 positions où les tableaux ont des valeurs
différentes. Cela peut se voir facilement grâce au schéma que j'ai
fait sur la page de présentation. Dans le meilleur des cas: 6
positions différentes, dans le pire (ou le meilleur si on est
l'attaquant) 4 positions lorsque S[i+127] = 126 et S[i+128] = 128.
Ensuite les messages restent identiques après k > i + 1, et on choisit
les valeurs d'octet pour ne pas permuter un octet en erreur.
Le pb c'est que comme i défile, il va bien tomber sur une position en
erreur. On peut ensuite choisir les valeurs d'octet des messages pour
tomber sur un même j. On permute une 1ère fois: l'octet en erreur
se déplace. On permute une deuxième fois: pas de différences.
Globalement le nombre d'erreurs reste identique. Si on ne fait rien
d'autre que compenser l'erreur en cours, on ne diminue pas le nombre
global d'erreur.
En fait, je me pose la question suivante plus générale. Puisqu'il est possible de faire une construction qui évite les cas de collisions "courtes" (rattrapage des erreurs de permutations sur un ou 2 octets différents au maximum sur des mêmes positions ), le but pour l'attaquant serait d'essayer de trouver un algo qui MINIMISE le nombre d' erreurs de permutations, tout en les changeant. Au fur et à mesure des changements le taux d'erreur s'amenuiserait jusqu'à tomber à zéro.
Déjà un tel algo existe-t-il ?
J'en doute et j'aurais même tendance à croire que l'erreur ne peut que se propager (mais ceci reste à prouver formellement).
Dans TAZ (version K7), quand on créée une pseudo-collision côt é i, c'est à dire qu'on a créé en i les actions: - (message 1) S[i] échangé avec S[i+1] puis S[i+1] échangé avec S[i] - (message 2) S[i] échangé avec lui-même et S[i+1] échangé avec lui-même
On obtient entre 4 et 6 positions où les tableaux ont des valeurs différentes. Cela peut se voir facilement grâce au schéma que j'ai fait sur la page de présentation. Dans le meilleur des cas: 6 positions différentes, dans le pire (ou le meilleur si on est l'attaquant) 4 positions lorsque S[i+127] = 126 et S[i+128] = 128.
Ensuite les messages restent identiques après k > i + 1, et on choisit les valeurs d'octet pour ne pas permuter un octet en erreur.
Le pb c'est que comme i défile, il va bien tomber sur une position en erreur. On peut ensuite choisir les valeurs d'octet des messages pour tomber sur un même j. On permute une 1ère fois: l'octet en erreur se déplace. On permute une deuxième fois: pas de différences.
Globalement le nombre d'erreurs reste identique. Si on ne fait rien d'autre que compenser l'erreur en cours, on ne diminue pas le nombre global d'erreur.
