OVH Cloud OVH Cloud

Théorie de l'échange de secret : Est-ce prouvé possible, ou impossible ?

48 réponses
Avatar
Patrick 'Zener' Brunet
Bonjour.

A force d'étudier des algorithmes et des protocoles visant à le résoudre en
pratique, j'en viens à me poser la question de la séparation entre la
difficulté théorique et la difficulté technologique du problème :

Soient A et B deux stations disposant chacune d'une enceinte protégée, mais
ne pouvant communiquer qu'à travers un canal non sécurisé :
- le canal est écoutable, enregistrable, non synchronisé,
- des messages peuvent être insérés par un usurpateur par rapport à A et/ou
à B,
- mais on suppose que le canal n'est pas interruptible : un message peut
toujours tôt ou tard parvenir à passer.

On suppose que A et B ne possèdent au départ aucun référentiel sémantique,
même élémentaire, qui soit un secret partagé par eux seuls. Seuls sont
partagés des référentiels publics.

Alors le problème consiste pour A et B, uniquement à travers des échanges
ainsi possibles mais non secrets, à construire ensemble un secret partagé
(même un simple booléen).

Et la question est là :

En ignorant toute contrainte d'ordre pratique (technologique, calculatoire,
etc.), et donc d'un point de vue purement théorique,
Est-il possible de démontrer que c'est possible, ou au contraire que c'est
impossible ?

Je n'ai jamais trouvé une telle démonstration soit positive soit négative,
et malheureusement ça dépasse un peu mes compétences (en théorie de
l'information et/ou en logique épistémique).

Pouvez-vous m'indiquer des pistes dans ce sens, dont je me repaîtrai avec
délice et reconnaissance ?

Merci d'avance.

Cordialement,

--

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

10 réponses

1 2 3 4 5
Avatar
Raymond H.
Merci pour les précisions :-)
r.h.
Avatar
Bob qui Trolle
Patrick 'Zener' Brunet wrote:

Et donc en reprenant le problème purement théorique ?


La cryptographie moderne fait le choix de réduire toute communication à
l'emploi de l'algèbre dans N (ou Z/nZ selon les tendances
maniaco-dépressives de l'interlocuteur) assortie de l'assertion de
l'existence d'un canal de communication.

Donc, toute question cryptographique se résume à un problème d'algèbre
dans N.

En termes simples, l'algèbre dans N est une méthode de résolution de
tous les problèmes imaginables dans N.

Mais, bien qu'il soit démontré que l'algèbre résolve tous les problèmes
dans N, il n'est pas démontré qu'il n'existe pas de méthode résolvant
tout ou partie des problèmes qu'on puisse composer dans N (ou un
superset de N dans lequel il existe un problème entièrement contenu dans
N, mais dont les étapes de résolutions passent par l'emploi d'élements
du superset de N n'appartenant pas N) qui ne soit pas l'algèbre.

Donc, il n'est pas possible de démontrer qu'il n'existe un nombre donné
(0, 1, ou plus) de méthodes d'un problème dans N.

Avatar
Jean-Marc Desperrier
Christophe HENRY wrote:
La révélation d'une donnée qui n'est pas connue s'apparente
à la brisure de la chaîne des événements qui n'est plus inversible.
1- Je ne connais pas
2- Révélation de l'information
3- Je la connais

A l'envers :
1- Je la connais
2- Je rend l'info (et comment vais-je l'oublier ?)
3- Je ne la connais pas (plus)

Ce n'est pas réalisable. Tout comme on ne peut pas recoller les morceaux
d'un vase brisé sans traces.


On peut aussi considérer que l'oubli s'il ne peut être délibéré est
cependant inévitable au bout d'un temps suffisant.

Donc pour un individu donné :

- Je ne conais pas
- J'apprend
- Je connais
- J'oublie
- Je ne conais pas

Et ça c'est symétrique et réversible.

Avatar
Patrick 'Zener' Brunet
Bonjour.

"JL" a écrit dans le message de news:
42127132$0$1723$
Patrick 'Zener' Brunet wrote:

J'insiste sur le fait que je réclame une preuve ou une contre-preuve
qui soit ***théorique et pas fondée sur une difficulté
technologique***.


D'accord.

Tous les systèmes à clé publique reposent sur des problèmes
mathématiques réputés ***difficiles*** et donc qui le sont de moins
en moins avec l'avancée des technologies. D'où la fuite en avant dans
la longueur des clés.


Dans ce cas on connait aussi la réponse : non, on ne peut pas démontrer
que

les algorithmes actuels de chiffrement à clef publique sont incassables.
Ça

ne veut pas dire qu'ils sont cassable, on est même à peu près convaincu
qu'ils sont incassables en l'état actuel les connaissances humaines.



J'ai précisé ce point dans la seconde partie du fil, et c'est revenu dans la
discussion avec Christophe HENRY.
Le problème est de devoir s'engager maintenant sur une qualité de robustesse
face à des découvertes futures, pour des documents qui doivent
impérativement résister au décryptage (à la casse donc) pendant un délai qui
peut atteindre le demi-siècle.

C'est pourquoi mon but est de faire la différence entre les limitations
technologiques/pratiques et les impossibilités dûment prouvées.
Par exemple le chiffrement de Vernam est inconditionnellement prouvé
incassable, et présente donc l'avantage de permettre de tenter sans risque
la transmission de la clé avant celle du message.

Ca repose aussi sur l'utilisation de "tiers de confiance"




C'est plus ou moins imposé dans les architectures à clés publiques-privées
et les protocoles d'authentification actuels.

Non, pas avec les hypothèses que vous prenez, du moins tel que je les
comprends. Si on suppose l'existence de référentiels publics partagés,
ceux-ci peuvent inclure la connaissance réciproque de la signature du
destinataire (sa clef publique). Sauf à limiter arbitrairement le
périmètre

de ce référentiel public, mais c'est une restriction qui ne figure pas
dans

vos hypothèses.

Et c'est contre l'hypothèse de départ : deux stations isolées et sans
référentiel secret commun (même indirect).


Justement, le principe de la clef publique c'est qu'elle n'est pas
secrète.

Cette hypothèse est donc parfaitement respectée.



Ceci dans la mesure où il est possible de construire une véritable paire de
clés publique-privée dont la robustesse ne repose pas sur une difficulté
technologique (système à trappe secrète en général). Dans le cas contraire,
on introduit souvent un mécanisme de révocation, et là on passe par une
autorité de certification...

Par ailleurs, une telle diffusion symétrique de clés publiques est
typiquement attaquable par usurpation (attaque dite du milieu), c'et évident
avec Diffie-Hellmann par exemple, et donc la clé échangée doit
impérativement être authentifiée par un certificat, ce qui renvoie au tiers
de confiance préalable.


Votre analogie de cadenas passe sous silence un problème fondamental
: si un dispositif physique (même s'il s'agit d'un simple photon pour
la crypto quantique) peut être inviolable (ie: non clonable et donc
analysable seulement par une lecture destructive), ce n'est pas le
cas d'une donnée pure qui peut être clonée à volonté.


Ça n'affaiblit en rien un système à clef publique. On sait très bien que
des

données informatiques peuvent être clonées à volonté, mais ça n'est pas un
problème.



Le problème de la clonabilité, c'est quelle rend la lecture (et la
dissection) non destructive.
Votre cadenas n'est plus inviolable.
Par exemple, le concept de la "caverne d'Ali Baba", qui est à l'origine des
protocoles de preuves à divulgation nulle (ZKP), repose dans sa forme
inviolable sur l'existence d'un tel "mécanisme" matériel. La seule
alternative que j'ai pu trouver est un principe de divination (des tirages
pile ou face par exemple), où le temps introduit une irréversibilité de
l'annonce. Mais donc là il faut que le prouveur utilise une compétence
"médiumnique" qui relève seulement du cas d'école.
Si vous connaissez un exemple de ZKP qui n'utilise qu'un référentiel fait de
pure information, et qui ne nécessite pas de tiers de confiance pour le
détenir, il est possible d'en tirer une solution au problème d'échange. Mais
je n'en ai pas encore trouvé un seul qui marche (ie: l'immatérialité permet
le rejeu par C et donc évente le secret).

Reprenez le protocole de la crypto quantique en supposant que C
(l'intrus) peut faire une copie exacte du photon avant de le lire et
vous réduisez à néant l'inviolabilité du système.


Le principe de la crypto quantique c'est justement qu'une telle copie est
impossible. C'est pourquoi le protocole est beaucoup plus simple que celui
de la crypto à clef publique déterministe.



Mais en contrepartie il résussite le canal unique. L'attaque la plus
évidente est alors de couper ce canal (un point suffit) ou de l'écouter
ostensiblement pour forcer A et B à se replier sur un medium moins protégé !
Précisément, c'est ce scénario qui est à l'origine de la structure "toile"
d'Internet.

Et donc en reprenant le problème purement théorique ?


Dans ce cas, dans un cadre déterministe la réponse est non, on ne peut
pas,

comme expliqué au premier paragraphe. Il n'existe donc ni preuve ni
contre-preuve.



Précisément je me demande toujours comment on peut formuler une telle
démonstration :
- soit à partir des "quantités d'information" et des principes de Shannon,
- soit par approche épistémique, avec des quantificateurs Know( x) et
Believe( x).
C'est vers ce genre de théorie que j'aimerais bien trouver des liens, parce
que malheureusement j'ai un peu faibli en maths (enfin pour des trucs
pareils je suis autodidacte), et donc j'ai besoin d'un petit coup de pouce.
(Si vous connaissez une jolie chercheuse en mathématiques qui cherche une
âme-soeur qui la comprenne...)


Par contre, dans le cadre de la crypto quantique, vos hypothèses sont
respectées, et la réponse devient oui. Le seul problème c'est qu'elle
n'est

pas disponible en pratique...



C'est pour très bientôt, il y a un projet à base de satellites pour faire
mieux que la fibre optique. Mais bon, ça ne sera pas pour toutes les
bourses, du coup vont se monter des services prestataires auprès desquels on
s'abonnera pour leur passer des messages à sécuriser ... ceci à travers une
connexion Internet classique :-)

Merci pour l'intérêt de vos contributions.
Cordialement,

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


Avatar
Patrick 'Zener' Brunet
Bonjour.

"jpeps" a écrit dans le message de
news: 421271cb$0$5079$

[...]
Soient A et B deux stations disposant chacune d'une enceinte protégée,
mais


ne pouvant communiquer qu'à travers un canal non sécurisé :
- le canal est écoutable, enregistrable, non synchronisé,
- des messages peuvent être insérés par un usurpateur par rapport à A
et/ou


à B,
- mais on suppose que le canal n'est pas interruptible : un message peut
toujours tôt ou tard parvenir à passer.

On suppose que A et B ne possèdent au départ aucun référentiel
sémantique,


même élémentaire, qui soit un secret partagé par eux seuls. Seuls sont
partagés des référentiels publics.

Alors le problème consiste pour A et B, uniquement à travers des
échanges


ainsi possibles mais non secrets, à construire ensemble un secret
partagé


(même un simple booléen).
[...]




J'ai un peu précisé le problème entre-temps, voir le post en milieu de fil
(juste au-dessus du post entre parenthèses).



Bonjour

Échanger de façon sûre avec un parfait inconnu est inutile (de mon point
de

vue).



J'avais formulé ces cas de figure dans le premier échange avec Christophe
HENRY :

A et B peuvent très bien en fait s'être rencontrés préalablement, mais ne
plus être en mesure de le faire et avoir épuisé (prématurément, à la suite
d'un imprévu) leurs possibilités d'échange secret. Selon les principes de
Kerkhoff, une clé ne doit servir qu'une seule fois.

On peut également envisager que A et B ont dans le passé disposé d'un canal
sécurisé ou d'une clé secrète, mais qu'ils soupçonnent ce medium d'être
désormais compromis. Ils ne peuvent donc plus l'utiliser pour convenir d'un
remplacement.


Je reformule donc.

Soit un Univers habité par trois entité (Alice, Bob et Charlie, comme il
se

doit). Ces trois entités connaissent tout de leur Univers, a deux
exceptions

près, car chacune des 3 entités détient un secret qui lui est propre.

Ces entités communiquent par un réseau "de diffusion", donc tout le monde
connaît tous les messages.

Dans cet Univers, le but d'Alice est de fusionner avec Bob (Hum, le 14
février n'est pas loin ;-). Cette fusion se fait par le partage des
secrets

que possèdent Bob et Alice, sans que Charlie puisse en avoir connaissance.

Bob est en accord avec cette situation, et collabore avec les tentatives
d'Alice.

Charlie est en désaccord avec cette situation car il souhaite fusionner
avec

Alice. Son objectif est donc de se faire passer pour Bob, ou
accessoirement,

d'empêcher la fusion entre Bob et Alice (en attendant avec espoir qu'elle
change d'avis).

Il existe dans cet Univers :

- un mécanisme *sûr* permettant de dériver un secret d'un autre secret,
sans

qu'il ne soit possible de déduire quoi que ce soit du premier secret
(une

sorte de hash parfait),

- un mécanisme *sûr* permettant à deux entité s'échangeant deux élément
public de construire un secret partagé (genre DH) ; c'est à dire une
partie de ce que tu cherche.

- un mécanisme *sur* permettant de communiquer de façon secrète si l'on
partage un secret.

Démonstration (par l'absurde) :

A partir des mécanismes ci-dessus, Alice initialise une conversation
visant

à établir un secret partagé avec Bob.

Afin de faire échouer l'action, Charlie émet des messages type "man in the
middle".

A la fin du "round" :

- A et B ont un secret commun, inconnu de C,
- B et C ont un secret commun, inconnu de A,
- A et C ont un secret commun, inconnu de B.

Il existe donc 3 canaux de communication "presque secret" (l'entité 3 sait
que 1 et 2 parlent).

Dans la mesure où Charlie mime Bob, Alice ne peut pas déterminer qui est
son

correspondant.



Le même mécanisme permet d'arriver au même résultat avec B ou C qui
initialise la communication.



Dans cet Univers, Alice ne peut donc pas parvenir à ses fins (Snif . . . )
faute de pouvoir obtenir l'assurance de l'identité de son correspondant.

Sans secret partagé avant l'initialisation de la communication, il n'est
donc pas possible de créer une communication sûre.

Si mon Univers reflète ton problème, la réponse est "c'est pas possible".
Je me limite à la logique, mais cela doit s'écrire mathématiquement.



C'est un raisonnement purement logique(le premier dans ce sens que je
recueille !) et très intéressant .
Je vais prendre le temps de le passer au crible par rapport au problème et à
mes indices.
Merci et à bientôt.

Cordialement,

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


Avatar
remy
"Bob qui Trolle" a écrit dans le message de
news:4212f874$0$15729$
Patrick 'Zener' Brunet wrote:

Et donc en reprenant le problème purement théorique ?


La cryptographie moderne fait le choix de réduire toute communication à
l'emploi de l'algèbre dans N (ou Z/nZ selon les tendances
maniaco-dépressives de l'interlocuteur) assortie de l'assertion de
l'existence d'un canal de communication.

Donc, toute question cryptographique se résume à un problème d'algèbre
dans N.

En termes simples, l'algèbre dans N est une méthode de résolution de
tous les problèmes imaginables dans N.

Mais, bien qu'il soit démontré que l'algèbre résolve tous les problèmes
dans N, il n'est pas démontré qu'il n'existe pas de méthode résolvant
tout ou partie des problèmes qu'on puisse composer dans N (ou un
superset de N dans lequel il existe un problème entièrement contenu dans
N, mais dont les étapes de résolutions passent par l'emploi d'élements
du superset de N n'appartenant pas N) qui ne soit pas l'algèbre.

Donc, il n'est pas possible de démontrer qu'il n'existe un nombre donné
(0, 1, ou plus) de méthodes d'un problème dans N.



trivial bien que postulat de base soit induit par la construction de N
et de l'algebre


Avatar
remy
"Patrick 'Zener' Brunet" a écrit dans
le message de news:4213018b$0$18648$
Bonjour.

"jpeps" a écrit dans le message de
news: 421271cb$0$5079$

[...]
Soient A et B deux stations disposant chacune d'une enceinte protégée,
mais


ne pouvant communiquer qu'à travers un canal non sécurisé :
- le canal est écoutable, enregistrable, non synchronisé,
- des messages peuvent être insérés par un usurpateur par rapport à A
et/ou


à B,
- mais on suppose que le canal n'est pas interruptible : un message
peut



toujours tôt ou tard parvenir à passer.

On suppose que A et B ne possèdent au départ aucun référentiel
sémantique,


même élémentaire, qui soit un secret partagé par eux seuls. Seuls sont
partagés des référentiels publics.

Alors le problème consiste pour A et B, uniquement à travers des
échanges


ainsi possibles mais non secrets, à construire ensemble un secret
partagé


(même un simple booléen).
[...]




J'ai un peu précisé le problème entre-temps, voir le post en milieu de fil
(juste au-dessus du post entre parenthèses).



Bonjour

Échanger de façon sûre avec un parfait inconnu est inutile (de mon point
de

vue).



J'avais formulé ces cas de figure dans le premier échange avec Christophe
HENRY :

A et B peuvent très bien en fait s'être rencontrés préalablement, mais ne
plus être en mesure de le faire et avoir épuisé (prématurément, à la suite
d'un imprévu) leurs possibilités d'échange secret. Selon les principes de
Kerkhoff, une clé ne doit servir qu'une seule fois.

On peut également envisager que A et B ont dans le passé disposé d'un
canal

sécurisé ou d'une clé secrète, mais qu'ils soupçonnent ce medium d'être
désormais compromis. Ils ne peuvent donc plus l'utiliser pour convenir
d'un

remplacement.



donc maintenant il reste a construire un masque jetable
a partir de la cle qui tienne la route

par exemple etablir une relation d'ordre dans un ensemble infini
coucou les nbs premiers

mon cote bucolique me poisse a faire une methaphore

dans le grand champ des entiers je vais butiner de fleur en fleur (nombre
premier)
et c'est ce parcours qui va me permettre de creer une relation d'ordre
reproductible

algo

p=nb premier;
x=1;
n=;
tant que(p ! premier)
{
p=p+x*2^n;
x++;
}
return x;

la cle n et p l'on peut meme passer en mode tambouille avec le n

ps :l'idee ne doit pas etre tres nouvel



Avatar
Christophe HENRY

...
Si vous connaissez un exemple de ZKP qui n'utilise qu'un référentiel fait de
pure information, et qui ne nécessite pas de tiers de confiance pour le
détenir, il est possible d'en tirer une solution au problème d'échange. Mais
je n'en ai pas encore trouvé un seul qui marche (ie: l'immatérialité permet
le rejeu par C et donc évente le secret).


Supposons que A et B disposent d'une connaissance commune que personne
(donc C) ne possède. Par une assertion sur cette connaissance, ils
peuvent se transmettre un booléen. En poussant plus loin, ils pourraient
de la sorte constituer une clé s'ils ont pris la précaution au
préalable d'avoir prévu ce cas : si une impossibilité de communiquer se
présentait, ils s'enverraient des assertions dont eux seuls connaissent
la véracité.

A mon humble avis, ce que tu recherches se traduit en le calcul de
l'information résiduelle entre A et B. Avec un canal écouté par C,
l'information ne peut que diminuer au fil du temps. Seule cette
information résiduelle, connue de A et B exclusivement, peut permettre
l'authentification préalable. En y ajoutant du ZKP, ça doit passer.

Avec cette clé transmise, l'un deux peut ensuite transmettre un procédé
mathématique pour générer une clé jetable. Evidemment, elle n'est pas
aléatoire mais en compliquant généreusement on peut en faire une
relativement efficace.

Ensuite, chiffrement du clair avec un vernam et, tatam!, ajout d'une autre
séquence réellement aléatoire chiffrée avec la même clé. La clé du
Vernam est réutilisée, certes, mais étant appliquée sur une séquence
aléatoire de bits, il n'y a pas de "mots probables" pour sa cryptanalyse.

Une fois que le correspondant a reçu l'ensemble, il déchiffre les deux
parties (clair et clé) et répond en chiffrant son message avec la clé
déjà transmise et y ajoutant la clé qu'il a générée et chiffrée
avec la clé déjà transmise.
Le point faible du système est que la compromission d'un seul transfert
menace la totalité des transferts passés et futurs.


--
-- -
/**************************************************************


Encore raté ! Avec OEQuotefix ?

--
Christophe HENRY
(sans lkm)
GnuPG : 3922239E60036EC86BF7268A877C52AC 4883C02A

Avatar
Christophe HENRY

On peut aussi considérer que l'oubli s'il ne peut être délibéré est
cependant inévitable au bout d'un temps suffisant.

Donc pour un individu donné :

- Je ne conais pas
- J'apprend
- Je connais
- J'oublie
- Je ne conais pas

Et ça c'est symétrique et réversible.


Pour passer de "je ne connais pas" à "je connais" il passe par
"j'apprend". Je supposais que "j'apprend" puise dans une source externe.
Or, par construction, cette information n'est pas présente à
l'extérieur.

Ces considérations ne doivent pas tant viser l'individu que l'ensemble
des moyens dont ils dispose pour communiquer. On peut voir la mémoire de
l'individu comme une mémoire cache qu'il faut rafraîchir. Le
rafraîchissement provenant de l'intérieur du système, sa feuille de
papier par exemple. En revanche, le système a toujours disposé de
l'information et ne l'a donc jamais oublié.

--
Christophe HENRY
(sans lkm)
GnuPG : 3922239E60036EC86BF7268A877C52AC 4883C02A

Avatar
remy
oops
p=p+x*2^n;
p=p+2^n;


cela va plus vite

1 2 3 4 5