Cryptage inviolable : bientôt en France

Laurent Fousse wrote:

Quel joli sens de l'humour !

En fait j'ai cru à une blague quand j'ai vu le site. Mais non, ça semble
réel.

A moins que. J'ai un doute d'un coup. Me serais-je fait avoir ?

Très honetement... j'ai un couteau suisse avec une clef usb et ça marche
très bien ;-)

Patrick 'Zener' Brunet wrote:

Le premier paragraphe donne les dates, le deuxième et la fin du quatrième
rappellent les points gênants.

Je pense qu'ils devraient rappeler un autre point génant.
C'est que dans de nombreux cas d'utilisation concrets de cette méthode
de chiffrement, la communication a fini par être déchiffrée.

Car dès qu'on s'intéresse au monde réel, on ne peut en rester à la
théorie, il faut prendre en compte tout ce qui peut arriver.
Et très régulièrement quand ce chiffrement est utilisé au delà d'une
échelle réduite, un utilisateur se retrouve à devoir transmettre un
message alors qu'il ne lui reste plus de nouvelle clé secréte.

A tous les coups il commence à réutiliser des clés.
Et en faisant cela, on passe sans transition d'un système totalement sûr
à un système dans lequel on casse vraiment facilement à la fois le
message qu'il va envoyer et le précédent message envoyé avec la même clé.

Humm ... le code produit ressemble comme deux gouttes d'eau à celui de CDP
:-)

C'est bizarre qu'a lui on ne lui demande pas l'algo :-)


--
Lheureux Philippe
http://www.superlutin.net/crypto.html

Bonjour.

Je réponds à Jean-Marc Desperrier <jmdesp@alussinan.org>

Patrick 'Zener' Brunet wrote:

Le premier paragraphe donne les dates, le deuxième et la fin du
quatrième rappellent les points gênants.

Je pense qu'ils devraient rappeler un autre point génant.
C'est que dans de nombreux cas d'utilisation concrets de cette méthode
de chiffrement, la communication a fini par être déchiffrée.

Oui, mais ça n'est pas une faille du protocole, c'est ce qu'en informatique
on nomme les bugs de l'interface fauteuil-clavier.
Le chiffre de Vernam n'est inconditionnellement sûr que tant qu'il reste
bien un chiffre de Vernam, mis en oeuvre selon les critères nominaux.

Car dès qu'on s'intéresse au monde réel, on ne peut en rester à la
théorie, il faut prendre en compte tout ce qui peut arriver.
Et très régulièrement quand ce chiffrement est utilisé au delà d'une
échelle réduite, un utilisateur se retrouve à devoir transmettre un
message alors qu'il ne lui reste plus de nouvelle clé secréte.

Effectivement, c'est pourquoi le chiffre de Vernam n'apporte rien à part une
petite facilité : risquer la clé en premier, plutôt que le message lui-même.

Tout le problème réside entièrement dans la génération, la transmission et
la gestion a posteriori de la clé.

Idéalement, le troisième point se règle facilement par une destruction
définitive, si les deux autres le permettent.

Le premier et le second sont liés dans un compromis pratique :
- vrai hasard non reproductible et transmission sécurisée d'une "grosse"
clé,
- "hasard reproductible" permettant de transmettre plus facilement une "clé
génération de clé" plus petite.

A tous les coups il commence à réutiliser des clés.
Et en faisant cela, on passe sans transition d'un système totalement
sûr à un système dans lequel on casse vraiment facilement à la fois le
message qu'il va envoyer et le précédent message envoyé avec la même
clé.

Alors ce n'est plus du Vernam, dans la mesure où globalement tout ou partie
de la clé est réutilisé, même si c'est d'une message à un autre, ou via la
génération d'une clé à partir d'une autre : il n'y a plus absence totale de
corrélation.

Effectivement, j'aimerais bien trouver quelque part une démonstration
formelle de la faisabilité ou au contraire de l'impossibilité des deux
points suivants, dans l monde réel (c'est à dire selon moi, sans faire appel
à des compétences "médiumniques" (divination, télépathie) ou toute autre
solution théorique genre hyper-espace) :

1) générer une séquence S pseudo-aléatoire de longueur Ls à partir d'une clé
K de longueur Lk, telle que
- Ls >> Lk et que
- S semble réellement aléatoire si K est inconnue (c'est à dire que la
cryptanalyse du chiffré ne puisse se faire que sur l'espace des S possibles,
générés exhaustivement à partir de tous les K possibles). C'est à dire donc
que l'algorithme générateur soit irréversible et n'ait pas d'impact
caractéristique permettant de réduire l'espace de recherche de Ls à Lk,

2) élaborer un secret partagé (même un simple booléen) entre deux stations,
sans référentiel secret préalable, et au moyen d'échanges tous écoutés et
éventuellement enregistrés (ce qui disqualifie toute stratégie fondée sur le
temps) par l'environnement hostile. Sans tiers de confiance ni canal
sécurisé bien entendu : juste deux châteaux-forts dans une plaine hostile,
avec des mégaphones.
En contrepartie, pas de problème de rendement du code (ratio [taille
secret]/[taille échanges]) ni de traitement en temps-réel pour une première
approche.

Je lis tout ce que je peux trouver sur ces deux points, et pour le second
notamment, je n'ai pas encore pu trouver de démonstration formelle, ni de
possibilité, ni d'impossibilité.
Donc ça m'intéresse terriblement...

Cordialement,

--
/***************************************
* Patrick BRUNET
* E-mail: lien sur http://zener131.free.fr/ContactMe
***************************************/

According to Patrick 'Zener' Brunet <use.link.in.signature@ddress.invalid>:

2) élaborer un secret partagé (même un simple booléen) entre deux stations,
sans référentiel secret préalable, et au moyen d'échanges tous écoutés et
éventuellement enregistrés (ce qui disqualifie toute stratégie fondée sur le
temps) par l'environnement hostile. Sans tiers de confiance ni canal
sécurisé bien entendu : juste deux châteaux-forts dans une plaine hostile,
avec des mégaphones.
En contrepartie, pas de problème de rendement du code (ratio [taille
secret]/[taille échanges]) ni de traitement en temps-réel pour une première
approche.

On est donc dans le cas d'un attaquant purement passif (le méchant n'a
pas son propre mégaphone). Ceci évite de se poser les problèmes
d'authentification donc de définition de ce que c'est que "l'autre" :
par définition, on cherche à échanger des messages avec celui avec qui
on échange effectivement des messages.

Face à un attaquant limité en pouvoir de calcul (i.e., il ne possède
que quelques millions de PC), ça se fait sans problème : Diffie-Hellman
est l'exemple canonique. À ma connaissance, on ne sait pas prouver
formellement la réductibilité de ce problème à un objet plus bas niveau
comme une fonction à sens unique ou une permutation pseudo-aléatoire
(deux autres objets dont, par ailleurs, on ne sait pas prouver
formellement l'existence). On est un peu dans la même situation que pour
les fonctions de hachage : on ne sait pas si ça existe vraiment, mais on
a des candidats qui semblent tenir la route (enfin, pour le hachage ce
n'est pas très clair ces derniers temps).

Face à un attaquant au pouvoir de calcul illimité, la question n'a pas
vraiment de sens : l'attaquant peut faire une recherche exhaustive sur
les données secrètes connues de chacune des deux parties. À la rigueur,
on se demande pourquoi il prend la peine d'écouter...

Ce qui est amusant, c'est qu'on peut faire un système sûr face à un
attaquant qui est limité seulement en mémoire (par exemple, il ne peut,
à tout moment, stocker que 500 téra-octets de données ; mais il est
capable d'overclocker ses processeurs à 354328954907325 GHz, voire
plus). Ça a été présenté à Crypto'97 : "Unconditional Security Against
Memory-Bounded Adversaries", par Christian Cachin et Ueli Maurer. L'idée
est que l'une des deux parties, ou alors un tiers quelconque mais sans
connaissance d'un quelconque secret, hurle des données aléatoires à
haut débit. Les deux parties écoutent pendant la journée en en notant
quelques bribes, puis utilisent les quelques rares morceaux qu'ils ont
en commun comme clé. On peut montrer que les deux gentils auront des
morceaux communs avec relativement peu de stockage chacun, mais que
l'attaquant devra avoir un stockage pharaonique pour avoir des chances
raisonnables d'avoir lui aussi ces morceaux communs.


--Thomas Pornin

On 2005-08-17, lheureuxph <lheureuxph@666wanadoo.fr> wrote:

Humm ... le code produit ressemble comme deux gouttes d'eau à celui de CDP
:-)

À peu près autant que ce qui sort de mon générateur d'octets aléatoires.

C'est bizarre qu'a lui on ne lui demande pas l'algo :-)

Il le donne, et il n'y a rien d'intéressant à voir.

Si j'ai bien retenu la leçon , un ordi ( qui n'utilise pas le principe lent
de CDP ) ne peut pas générer de suites aléatoires autrement que
mathématiquement.
Est ce qu'ils disent comment ils génerent leur masque aléatoire ????

lheureuxph wrote:

Si j'ai bien retenu la leçon , un ordi ( qui n'utilise pas le principe lent
de CDP ) ne peut pas générer de suites aléatoires autrement que
mathématiquement.
Est ce qu'ils disent comment ils génerent leur masque aléatoire ????



à coup de hache.

Bonjour.

Je réponds à Thomas Pornin <pornin@nerim.net>

According to Patrick 'Zener' Brunet
<use.link.in.signature@ddress.invalid>:

2) élaborer un secret partagé (même un simple booléen) entre deux
stations, sans référentiel secret préalable, et au moyen d'échanges
tous écoutés et éventuellement enregistrés (ce qui disqualifie toute
stratégie fondée sur le temps) par l'environnement hostile. Sans
tiers de confiance ni canal sécurisé bien entendu : juste deux
châteaux-forts dans une plaine hostile, avec des mégaphones.
En contrepartie, pas de problème de rendement du code (ratio [taille
secret]/[taille échanges]) ni de traitement en temps-réel pour une
première approche.

On est donc dans le cas d'un attaquant purement passif (le méchant n'a
pas son propre mégaphone). Ceci évite de se poser les problèmes
d'authentification donc de définition de ce que c'est que "l'autre" :
par définition, on cherche à échanger des messages avec celui avec qui
on échange effectivement des messages.

En fait j'ai des idées à développer pour assurer l'authentification, pour
autant que le premier problème ait une solution. Donc ça se règle
séparément.
Mais évidemment, ces idées perdent tout intérêt si on peut prouver qu'il n'y
a pas de solution. Donc je commence par le début.

Face à un attaquant limité en pouvoir de calcul (i.e., il ne possède
que quelques millions de PC), ça se fait sans problème :
Diffie-Hellman est l'exemple canonique. À ma connaissance, on ne sait
pas prouver formellement la réductibilité de ce problème à un objet
plus bas niveau comme une fonction à sens unique ou une permutation
pseudo-aléatoire (deux autres objets dont, par ailleurs, on ne sait
pas prouver formellement l'existence). On est un peu dans la même
situation que pour les fonctions de hachage : on ne sait pas si ça
existe vraiment, mais on
a des candidats qui semblent tenir la route (enfin, pour le hachage ce
n'est pas très clair ces derniers temps).

J'ai répondu sur ce point à Erwan David, juste au-dessus.
Effectivement, je vois bien qu'on essaie toujours de dépasser en volume de
calculs nécessaire un majorant de la capacité de calcul estimée de
l'attaquant. La validité de la solution est donc nécessairement limitée dans
le temps, ce qui implique que la donnée à chiffrer sera nécessairement
éventée au bout d'un délai ... finalement peu prévisible.
L'autre aspect de la chose est que, vu la taille de la clé nécessaire, on ne
peut pas faire du Vernam pour une raison "économique" : on pourrait prendre
la parité de la clé et donc en faire un bit de l'OTP, mais le coût serait
dispendieux. Donc on accepte le principe de structures de message chiffré
dans lesquelles il y a une corrélation théoriquement exploitable.

Face à un attaquant au pouvoir de calcul illimité, la question n'a pas
vraiment de sens : l'attaquant peut faire une recherche exhaustive sur
les données secrètes connues de chacune des deux parties. À la
rigueur, on se demande pourquoi il prend la peine d'écouter...

Oui, s'il écoute, c'est forcément pour arriver à capter le secret partagé en
cours de construction. Quand je mets ça dans mon énoncé, ça veut clairement
dire qu'il n'y a pas de canal protégé, même à faible débit, pour y faire
passer "la clé de la clé", Oulahup Barbatruc et voilà mon super algo
inviolable :-)

Par rapport à ce que je dis ci-dessus, il est clair que ce que je cherche,
plutôt que d'outrepasser les possibilités de calcul de l'attaquant (on sait
ce qu'en pense E.A. Poe), c'est de trouver un protocole qui le laisse sur un
problème définitivement indéterminé. Finalement c'est l'esprit-même du
chiffre de Vernam : pour chaque bit de message chiffré intercepté, vous
pouvez choisir au hasard le bit de clé et ça vous donne un clair possible.

Ce qui est amusant, c'est qu'on peut faire un système sûr face à un
attaquant qui est limité seulement en mémoire (par exemple, il ne
peut,
à tout moment, stocker que 500 téra-octets de données ; mais il est
capable d'overclocker ses processeurs à 354328954907325 GHz, voire
plus). Ça a été présenté à Crypto'97 : "Unconditional Security Against
Memory-Bounded Adversaries", par Christian Cachin et Ueli Maurer.
L'idée est que l'une des deux parties, ou alors un tiers quelconque
mais sans connaissance d'un quelconque secret, hurle des données
aléatoires à
haut débit. Les deux parties écoutent pendant la journée en en notant
quelques bribes, puis utilisent les quelques rares morceaux qu'ils ont
en commun comme clé. On peut montrer que les deux gentils auront des
morceaux communs avec relativement peu de stockage chacun, mais que
l'attaquant devra avoir un stockage pharaonique pour avoir des chances
raisonnables d'avoir lui aussi ces morceaux communs.

Ca c'est une piste intéressante à première vue : en supposant que les bribes
à comparer sont en fait engendrées par des échanges plus petits, on peut
peut-être en tirer quelque chose dans mon sens ... Est-ce qu'il y a un lien
avec le "paradoxe des anniversaires" ?

La question est de savoir comment les deux gentils arrivent à identifier les
bribes qu'ils ont en commun (sans les montrer bien sûr). C'est en rapport
avec la sémantique du mot "quelques" (bribes à noter) : tirages aléatoires
non correllés ? Car s'ils se sont entendus (forcément en public) sur une
stratégie de choix, c'est déjà fichu.

Cette dernière question est typiquement le genre de chose qui me prend la
tête depuis 3 ans. C'est elle qui justifie ma question initiale : prouver
que c'est possible ou prouver que c'est impossible. Actuellement je n'ai
réussi ni l'un ni l'autre et je ne vois pas comment mettre en place une
telle démonstration (je ne suis pas assez costaud en logique épistémique, ni
en théorie de l'information).

Merci de vos conseils.
Cordialement,

--
/***************************************
* Patrick BRUNET
* E-mail: lien sur http://zener131.free.fr/ContactMe
***************************************/

According to Patrick 'Zener' Brunet <use.link.in.signature@ddress.invalid>:

Ca c'est une piste intéressante à première vue : en supposant que
les bribes à comparer sont en fait engendrées par des échanges plus
petits, on peut peut-être en tirer quelque chose dans mon sens ...
Est-ce qu'il y a un lien avec le "paradoxe des anniversaires" ?

Il y a un lien, oui. Pour simplifier, supposons que les données soient
des mots de 128 bits, émis à fort débit. Alice et Bob écoutent ça et
enregistrent, chacun de leur côté, divers mots de 128 bits choisis
aléatoirement, en enregistrant aussi le "rang" de chaque mot choisi
(i.e., si Alice enregistre le 1673ème mot émis par la source à haut
débit, elle note aussi à côté le numéro "1673").

Après la séance d'écoute, Alice et Bob s'envoient les rangs des mots
qu'ils ont enregistré. Ensuite, ils regardent s'ils en ont un en commun.
S'ils en ont un, bingo, c'est leur clé. Sinon, ils n'ont plus qu'à
recommencer (s'ils en ont plusieurs, ils peuvent prendre le XOR bit à
bit de tous les mots communs). On peut montrer que, statistiquement,
s'il y a N mots émis, Alice et Bob ont de bonnes chances d'avoir au
moins un mot commun s'ils en notent chacun de l'ordre de sqrt(N)
(c'est le même effet que dans le "paradoxe des anniversaires", et
c'est là qu'est le lien). En revanche, pour que Charlie (le méchant)
ait des chances raisonnable d'avoir lui aussi le mot qui est, in fine,
utilisé comme clé par Alice et Bob, alors il doit enregistrer une bonne
proportion des mots émis, donc de l'ordre de N plutôt que sqrt(N).

Numériquement : si la source émet environ 2^60 mots pendant la séance
(soit 16 milliards de giga-octets...), Alice et Bob peuvent se contenter
d'enregistrer 16 Go chacun (ce qui n'est pas cher, maintenant que le
giga-octet de disque dur est en-dessous de 1 euro), mais si Charlie ne
consacre "que" 1000 téra-octets (soit un million de giga-octets, ce qui
est tout de suite un peu plus onéreux), alors il n'a qu'une chance sur
16 millions d'avoir lui aussi la clé (autrement dit, il ferait mieux de
jouer au Loto, où il a une chance sur 13 millions d'avoir les six bons
numéros).


Bien évidemment, la réalisation pratique n'est pas complètement
évidente, et la sécurité effective repose pas mal sur la façon de
sélectionner "aléatoirement" les mots par Alice et Bob. Il faudrait
théoriquement que le tirage aléatoire d'Alice soit uniforme sur toutes
les combinaisons possible (i.e. un milliard de choix distincts sur un
milliard de milliards de mots). Une méthode plus rustique (Alice fait un
tirage pour chaque mot, et décide de le conserver avec une probabilité
de un sur un milliard, indépendamment des autres mots) ne fournit pas
la même distribution de probabilité. De plus, techniquement, Alice
pourrait avoir du mal à enregistrer des "bursts" (beaucoup de mots
consécutifs) (ça dépend du buffer d'entrée, qui est devant le disque dur
et qui doit travailler au rythme de la source), ce qui modifie encore la
distribution de probabilité. Tout ça peut se quantifier et s'arranger,
mais la démonstration mathématique dans le cadre formel de la théorie
de l'information dépasse largement ce que j'ai le courage d'expliquer
dans un message sur Usenet.


--Thomas Pornin