Si j'ai bien compris l'astuce des réseaux de Feitsel, je peux intégrer une
fonction de hachage à sens unique et mon algorithme de chiffrement (basé sur
les réseaux de ...) est parfaitement réversible ?
Si j'ai bien compris l'astuce des réseaux de Feitsel, je peux intégrer une
fonction de hachage à sens unique et mon algorithme de chiffrement (basé sur
les réseaux de ...) est parfaitement réversible ?
Oui, les réseaux de Feitsel permettent de construire une bijection à partir d'une fonction à sens unique.
C'est bien ce que j'avais cru comprendre, merci !
pornin
According to Erwan David :
Oui, les réseaux de Feitsel permettent de construire une bijection à partir d'une fonction à sens unique.
Je me permets d'ajouter que Luby et Rackoff ont théorisé la chose dans leur article de 1988 "How to construct pseudorandom permutations and pseudorandom functions". Leur résultat est que la permutation construite est "sûre" si on met au moins quatre tours, avec quatre fonctions à sens unique, elles-mêmes "sûres" et "indépendantes".
Du coup on peut être tenté de faire un système de chiffrement avec quatre tours et des variations sur SHA-1 à chaque tour (en faisant entrer une clé) mais il s'avère que les performances atteintes sont assez décevantes (un bon AES bien optimisé va dix à vingt fois plus vite).
--Thomas Pornin
According to Erwan David <erwan@rail.eu.org>:
Oui, les réseaux de Feitsel permettent de construire une bijection à
partir d'une fonction à sens unique.
Je me permets d'ajouter que Luby et Rackoff ont théorisé la chose dans
leur article de 1988 "How to construct pseudorandom permutations and
pseudorandom functions". Leur résultat est que la permutation construite
est "sûre" si on met au moins quatre tours, avec quatre fonctions à sens
unique, elles-mêmes "sûres" et "indépendantes".
Du coup on peut être tenté de faire un système de chiffrement avec
quatre tours et des variations sur SHA-1 à chaque tour (en faisant
entrer une clé) mais il s'avère que les performances atteintes sont
assez décevantes (un bon AES bien optimisé va dix à vingt fois plus
vite).
Oui, les réseaux de Feitsel permettent de construire une bijection à partir d'une fonction à sens unique.
Je me permets d'ajouter que Luby et Rackoff ont théorisé la chose dans leur article de 1988 "How to construct pseudorandom permutations and pseudorandom functions". Leur résultat est que la permutation construite est "sûre" si on met au moins quatre tours, avec quatre fonctions à sens unique, elles-mêmes "sûres" et "indépendantes".
Du coup on peut être tenté de faire un système de chiffrement avec quatre tours et des variations sur SHA-1 à chaque tour (en faisant entrer une clé) mais il s'avère que les performances atteintes sont assez décevantes (un bon AES bien optimisé va dix à vingt fois plus vite).
--Thomas Pornin
Pascal Junod
Par exemple la construction de Luby et Rackoff appliquée à un mot de 2x2 bits produit un chiffrement sur [0..15], mais - toute contruction de Luby et Rackoff est une permutation paire; donc connaissant le chiffré pour [0..13] on peut déduire le chiffré pour [14..15]
En pratique, il est extremement difficile de decrire un algorithme qui genere des permutations impaires.
- parmis les 16!/2 permutations paires, certaines sont plus probables que d'autres; en particulier, connaissant le chiffré pour [0..12] on peut déduire le chiffré pour 13 avec une proabilité meilleure que 1/3
Il faut remettre ces "attaques" dans leur contexte en les comparant aux attaques génériques sur un cipher qui chiffre 2 bit !
A+
Pascal
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ * Pascal Junod http://crypto.junod.info * * Security and Cryptography Laboratory (LASEC) * * Swiss Federal Institute of Technology (EPFL), CH-1015 Lausanne * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Par exemple la construction de Luby et Rackoff appliquée à un mot
de 2x2 bits produit un chiffrement sur [0..15], mais
- toute contruction de Luby et Rackoff est une permutation paire;
donc connaissant le chiffré pour [0..13] on peut déduire le chiffré
pour [14..15]
En pratique, il est extremement difficile de decrire un algorithme qui
genere des permutations impaires.
- parmis les 16!/2 permutations paires, certaines sont plus probables
que d'autres; en particulier, connaissant le chiffré pour [0..12] on
peut déduire le chiffré pour 13 avec une proabilité meilleure que 1/3
Il faut remettre ces "attaques" dans leur contexte en les comparant aux
attaques génériques sur un cipher qui chiffre 2 bit !
A+
Pascal
--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Pascal Junod <pascal.junod@epfl.ch> http://crypto.junod.info *
* Security and Cryptography Laboratory (LASEC) *
* Swiss Federal Institute of Technology (EPFL), CH-1015 Lausanne *
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Par exemple la construction de Luby et Rackoff appliquée à un mot de 2x2 bits produit un chiffrement sur [0..15], mais - toute contruction de Luby et Rackoff est une permutation paire; donc connaissant le chiffré pour [0..13] on peut déduire le chiffré pour [14..15]
En pratique, il est extremement difficile de decrire un algorithme qui genere des permutations impaires.
- parmis les 16!/2 permutations paires, certaines sont plus probables que d'autres; en particulier, connaissant le chiffré pour [0..12] on peut déduire le chiffré pour 13 avec une proabilité meilleure que 1/3
Il faut remettre ces "attaques" dans leur contexte en les comparant aux attaques génériques sur un cipher qui chiffre 2 bit !
A+
Pascal
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ * Pascal Junod http://crypto.junod.info * * Security and Cryptography Laboratory (LASEC) * * Swiss Federal Institute of Technology (EPFL), CH-1015 Lausanne * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Francois Grieu
In article , Pascal Junod wrote:
Par exemple la construction de Luby et Rackoff appliquée à un mot de 2x2 bits produit un chiffrement sur [0..15], mais - toute contruction de Luby et Rackoff est une permutation paire; donc connaissant le chiffré pour [0..13] on peut déduire le chiffré pour [14..15]
En pratique, il est extremement difficile de decrire un algorithme qui genere des permutations impaires.
Rarement utile en pratique, mais pas très difficile en théorie. Partant disons de triple DES noté 3DES(K,P) avec K a 168 bits utiles parmis 192. La fonction suivante est un algorithme de chiffrement à clé de 193 bits où l'adversaire ne peux pas trouver les 2 dernières paires de clair-chiffré à partir des 2^64-2 autres (autrement qu'en cassant 3DES) 0 -> 3DES(K,0) si K pair 0 -> 3DES(K,1) si K impair 1 -> 3DES(K,1) si K pair 1 -> 3DES(K,0) si K impair P -> 3DES(K,P) si P>1
- parmis les 16!/2 permutations paires, certaines sont plus probables que d'autres; en particulier, connaissant le chiffré pour [0..12] on peut déduire le chiffré pour 13 avec une proabilité meilleure que 1/3
Il faut remettre ces "attaques" dans leur contexte en les comparant aux attaques génériques sur un cipher qui chiffre 2 bit !
[Note: je considérais un chiffrement sur 4 bits]
Un exemple concret où le phénomène que je décris est significatif: on veux choisir un ordre pseudo-aléatoire pour n éléments en fonction d'une clé, avec un algorithme qui n'utilise pas une taille mémoire proportionelle à n. Une technique attrayante et théoriquement parfaite: on trouve l'image par la permutation de l'élément j (0<=j<n) en chiffrant j avec un algorithme de chiffrement opérant sur au moins ceil(log2(n)) bits, et ce itérativement jusqu'à ce que le résultat soit inférieur à n. Eh bien, si on fait cela sans tenir compte des défauts de la contruction de Luby et Rackoff quand on défini l'algorithme de chiffrement, la répartition des permutations est loin d'être équiprobable pour les petits n, et carrément désastreuse quand l'agorithe de chiffrement opère sur exactement log2(n) bits.
François Grieu
In article <Pine.LNX.4.44.0307030912280.1787-100000@lasecpc10.epfl.ch>,
Pascal Junod <pascal.junod@epfl.ch> wrote:
Par exemple la construction de Luby et Rackoff appliquée à un mot
de 2x2 bits produit un chiffrement sur [0..15], mais
- toute contruction de Luby et Rackoff est une permutation paire;
donc connaissant le chiffré pour [0..13] on peut déduire le chiffré
pour [14..15]
En pratique, il est extremement difficile de decrire un algorithme qui
genere des permutations impaires.
Rarement utile en pratique, mais pas très difficile en théorie.
Partant disons de triple DES noté 3DES(K,P) avec K a 168 bits
utiles parmis 192. La fonction suivante est un algorithme de
chiffrement à clé de 193 bits où l'adversaire ne peux pas trouver
les 2 dernières paires de clair-chiffré à partir des 2^64-2
autres (autrement qu'en cassant 3DES)
0 -> 3DES(K,0) si K pair 0 -> 3DES(K,1) si K impair
1 -> 3DES(K,1) si K pair 1 -> 3DES(K,0) si K impair
P -> 3DES(K,P) si P>1
- parmis les 16!/2 permutations paires, certaines sont plus probables
que d'autres; en particulier, connaissant le chiffré pour [0..12] on
peut déduire le chiffré pour 13 avec une proabilité meilleure que 1/3
Il faut remettre ces "attaques" dans leur contexte en les comparant aux
attaques génériques sur un cipher qui chiffre 2 bit !
[Note: je considérais un chiffrement sur 4 bits]
Un exemple concret où le phénomène que je décris est significatif:
on veux choisir un ordre pseudo-aléatoire pour n éléments en fonction
d'une clé, avec un algorithme qui n'utilise pas une taille mémoire
proportionelle à n. Une technique attrayante et théoriquement
parfaite: on trouve l'image par la permutation de l'élément j (0<=j<n)
en chiffrant j avec un algorithme de chiffrement opérant sur au
moins ceil(log2(n)) bits, et ce itérativement jusqu'à ce que le
résultat soit inférieur à n.
Eh bien, si on fait cela sans tenir compte des défauts de la
contruction de Luby et Rackoff quand on défini l'algorithme de
chiffrement, la répartition des permutations est loin d'être
équiprobable pour les petits n, et carrément désastreuse
quand l'agorithe de chiffrement opère sur exactement log2(n) bits.
Par exemple la construction de Luby et Rackoff appliquée à un mot de 2x2 bits produit un chiffrement sur [0..15], mais - toute contruction de Luby et Rackoff est une permutation paire; donc connaissant le chiffré pour [0..13] on peut déduire le chiffré pour [14..15]
En pratique, il est extremement difficile de decrire un algorithme qui genere des permutations impaires.
Rarement utile en pratique, mais pas très difficile en théorie. Partant disons de triple DES noté 3DES(K,P) avec K a 168 bits utiles parmis 192. La fonction suivante est un algorithme de chiffrement à clé de 193 bits où l'adversaire ne peux pas trouver les 2 dernières paires de clair-chiffré à partir des 2^64-2 autres (autrement qu'en cassant 3DES) 0 -> 3DES(K,0) si K pair 0 -> 3DES(K,1) si K impair 1 -> 3DES(K,1) si K pair 1 -> 3DES(K,0) si K impair P -> 3DES(K,P) si P>1
- parmis les 16!/2 permutations paires, certaines sont plus probables que d'autres; en particulier, connaissant le chiffré pour [0..12] on peut déduire le chiffré pour 13 avec une proabilité meilleure que 1/3
Il faut remettre ces "attaques" dans leur contexte en les comparant aux attaques génériques sur un cipher qui chiffre 2 bit !
[Note: je considérais un chiffrement sur 4 bits]
Un exemple concret où le phénomène que je décris est significatif: on veux choisir un ordre pseudo-aléatoire pour n éléments en fonction d'une clé, avec un algorithme qui n'utilise pas une taille mémoire proportionelle à n. Une technique attrayante et théoriquement parfaite: on trouve l'image par la permutation de l'élément j (0<=j<n) en chiffrant j avec un algorithme de chiffrement opérant sur au moins ceil(log2(n)) bits, et ce itérativement jusqu'à ce que le résultat soit inférieur à n. Eh bien, si on fait cela sans tenir compte des défauts de la contruction de Luby et Rackoff quand on défini l'algorithme de chiffrement, la répartition des permutations est loin d'être équiprobable pour les petits n, et carrément désastreuse quand l'agorithe de chiffrement opère sur exactement log2(n) bits.
François Grieu
Pascal Junod
En pratique, il est extremement difficile de decrire un algorithme qui genere des permutations impaires.
Rarement utile en pratique, mais pas très difficile en théorie.
Pour preciser ma pensee: par "en pratique", j'entendais travailler sur des blocs etant d'une taille puissance de deux avec une clef de taille puissance de deux et des operations sur des elements de taille puissance de deux.
A+
Pascal
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ * Pascal Junod http://crypto.junod.info * * Security and Cryptography Laboratory (LASEC) * * Swiss Federal Institute of Technology (EPFL), CH-1015 Lausanne * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
En pratique, il est extremement difficile de decrire un algorithme qui
genere des permutations impaires.
Rarement utile en pratique, mais pas très difficile en théorie.
Pour preciser ma pensee: par "en pratique", j'entendais travailler sur
des blocs etant d'une taille puissance de deux avec une clef de
taille puissance de deux et des operations sur des elements de
taille puissance de deux.
A+
Pascal
--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Pascal Junod <pascal.junod@epfl.ch> http://crypto.junod.info *
* Security and Cryptography Laboratory (LASEC) *
* Swiss Federal Institute of Technology (EPFL), CH-1015 Lausanne *
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
En pratique, il est extremement difficile de decrire un algorithme qui genere des permutations impaires.
Rarement utile en pratique, mais pas très difficile en théorie.
Pour preciser ma pensee: par "en pratique", j'entendais travailler sur des blocs etant d'une taille puissance de deux avec une clef de taille puissance de deux et des operations sur des elements de taille puissance de deux.
A+
Pascal
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ * Pascal Junod http://crypto.junod.info * * Security and Cryptography Laboratory (LASEC) * * Swiss Federal Institute of Technology (EPFL), CH-1015 Lausanne * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
