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
Christophe HENRY

*********Et seulement là SVP :-)

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).



A mon avis à ce stade on doit flirter avec l'épistémologie, la
théorie de l'information, l'incomplétude de Gödel voire même
l'inspiration divine :-)


Supposons que _A_lice et _B_ob veulent se parler. Ils pensent, et donc,
ils sont. A sait que "A" existe. B sait que "B" existe.
Si A et B 'veulent' se parler, c'est qu'il y a une raison à cette
'communication'. La communication consistant en l'acquisition d'une
information dont on ne dipose pas encore, A et B ont dû se mettre
d'accord sur l'identification de cette information à communiquer.

Pour se mettre d'accord, il faut déjà avoir communiqué ou compris la
'problématique'. De plus, A et B se connaissent déjà. Donc il y a
déjà eu communication soit directe, soit indirecte. Fatalement, la toute
première forme de transmission de connaissance peut avoir été manipulée.
Même avec l'utilisation de la mécanique quantique, ça ne marcherait
pas. Ca marche une fois le canal établi et avec la confiance de A et B.
Mais avant ? Avant que le canal chiffré quantique soit établi ?

Je *pense* donc qu'il n'y a pas de solution absolue.

La difficulté est quasiment d'ordre cosmologique du fait de la flèche
du temps. En forçant bien, on doit même pouvoir y caser les lois de la
thermodynamique.


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



Bon'ap !


<8#--X--< filtré par Avast! 4 Home


<désolé>SPAM !</désolé>

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


Avatar
Patrick 'Zener' Brunet
Bonjour.

"Christophe HENRY" a écrit dans le
message de news: cuss5v$54u$

*********Et seulement là SVP :-)

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).



A mon avis à ce stade on doit flirter avec l'épistémologie, la
théorie de l'information, l'incomplétude de Gödel voire même
l'inspiration divine :-)



Oui, j'aimerais bien éviter la dernière voie. Par contre je n'ai rien contre
les précédentes pourvu que cela aboutisse à une réponse à la question qui me
travaille :-)


Supposons que _A_lice et _B_ob veulent se parler. Ils pensent, et donc,
ils sont. A sait que "A" existe. B sait que "B" existe.
Si A et B 'veulent' se parler, c'est qu'il y a une raison à cette
'communication'. La communication consistant en l'acquisition d'une
information dont on ne dipose pas encore, A et B ont dû se mettre
d'accord sur l'identification de cette information à communiquer.



Ca ils peuvent le faire publiquement, tant qu'il ne s'agit que de la
désignation de cette information et pas de sa valeur.


Pour se mettre d'accord, il faut déjà avoir communiqué ou compris la
'problématique'. De plus, A et B se connaissent déjà. Donc il y a
déjà eu communication soit directe, soit indirecte. Fatalement, la toute
première forme de transmission de connaissance peut avoir été manipulée.
Même avec l'utilisation de la mécanique quantique, ça ne marcherait
pas. Ca marche une fois le canal établi et avec la confiance de A et B.
Mais avant ? Avant que le canal chiffré quantique soit établi ?



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 *pense* donc qu'il n'y a pas de solution absolue.



Moi j'ai des indices pour et des indices contre, c'est pourquoi je m'efforce
de refuser mes intuitions et de rechercher une preuve, positive ou négative.
J'ai déjà passé beaucoup de temps à plancher sur le problème et je suis prêt
à continuer dans le premier cas, mais j'aurai la sagesse d'arrêter dans le
second.
C'est le doute qui tue !

La difficulté est quasiment d'ordre cosmologique du fait de la flèche
du temps.


L'irréversibilité du temps peut a priori être utilisée comme un composant
essentiel d'un protocole, mais seulement en rendant un choix irréversible.
C'est pouquoi je suppose que les messages peuvent être enregistrés (et donc
réécoutés) par _C_asse-burnes.
En conséquence, toute information qui est diffusée (et donc captée par
_C_hiant-comme-tout) ne peut pas être oubliée, et donc il n'est jamais "trop
tard" pour l'utiliser.
Ce principe pose d'ailleurs un gros problème théorique dans le cadre de
documents qui doivent être diffusés sous une forme chiffrée, puisqu'il ne
sera pas possible de retrouver et faire disparaître ces copies pour
renforcer le chiffrement par la suite, ce qui impose de s'engager sur la
robustesse d'un chiffre en anticipant des technologies qui restent à venir !
(Par exemple, certains documents militaires et assimilés ne sont déclassés
qu'après plus d'un demi-siècle).

En forçant bien, on doit même pouvoir y caser les lois de la
thermodynamique.



Le principe d'entropie portant sur des données pures, sans élément physique
? Vous spéculez là ...


Pouvez-vous m'indiquer des pistes dans ce sens, dont je me repaîtrai
avec



délice et reconnaissance ?



Bon'ap !



Question de goûts ;-)

Cordialement,

--

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



Avatar
remy
bonjour

La question semble intéresser du monde, mais pour l'instant je n'ai vu
passer que des rappels des systèmes connus dont aucun ne répond au
problème

fondamental.

Je vais donc préciser ci-dessous :


l'on a bien compris et tu n'es pas le seul a t'etre deja pose la question

j'avais propose un debut de piste pour essayer de repondre
l'idee de base etait de prendre un morceau d'un nb premier en base 2
pour faire un Xor et de changer de nb premier en fct du morceau

comme il y a une infinite de nb premier si l'on ne connait pas la graine
tu es de la baise
le pb c'est la fct de repartition des nbs premiers dans les entiers
il ne faudrait pas que le pas soit cyclique pour l'instant cela semble
acquis

et la graine tu la fais passer en lui payant un coup a boire


a+ remy

Avatar
remy
"Patrick 'Zener' Brunet" a écrit dans
le message de news:4211d29c$0$5075$

"Patrick 'Zener' Brunet" a écrit
dans

le message de news: 4211d1ae$0$3837$
<...>

de nouvelles technologies peuvent apparaître et changer la donne (par
exemple, ma mise au point réputée imminente d'un ordinateur quantique


Simple faute de frappe, c'est LA mise au point... (moi je travaille sur
autre chose).



l'on a bien compris et tu n'es pas le seul a t'etre deja pose la question

j'avais propose un debut de piste pour essayer de repondre
l'idee de base etait de prendre un morceau d'un nb premier en base 2
pour faire un Xor et de changer de nb premier en fct du morceau

comme il y a une infinite de nb premier si l'on ne connait pas la graine
tu es de la baise
le pb c'est la fct de repartition des nbs premiers dans les entiers
il ne faudrait pas que le pas soit cyclique pour l'instant cela semble
acquis

et la graine tu la fais passer en lui payant un coup a boire


a+ remy


Avatar
Patrick 'Zener' Brunet
Bonjour.

"remy" a écrit dans le message de news:
421217c1$0$17275$
<...>
j'avais propose un debut de piste pour essayer de repondre
l'idee de base etait de prendre un morceau d'un nb premier en base 2
pour faire un Xor et de changer de nb premier en fct du morceau

comme il y a une infinite de nb premier si l'on ne connait pas la graine
tu es de la baise
le pb c'est la fct de repartition des nbs premiers dans les entiers
il ne faudrait pas que le pas soit cyclique pour l'instant cela semble
acquis

et la graine tu la fais passer en lui payant un coup a boire



Mmmmmmh... Après maintes relectures et en ignorant le vocabulaire
"branché"...

Apparemment vous partez sur une stratégie permettant de construire une sorte
de séquence pseudo-aléatoire, c'est à dire dont la logique ne puisse pas
être devinée par l'intrus du milieu.

Fort bien, mais le but reste de construire un secret partagé entre les
stations A et B, sans secret préalable et à travers un canal notoirement
écouté par C.
Donc en toute logique :
- soit on suppose que B doit être capable de deviner cette logique de
construction pour construire la même séquence que A, alors que C lui en
serait incapable (au nom de quoi ?),
- soit on suppose que la logique de la construction peut être divulguée
publiquement et que la séquence ne dépend que du choix du nombre premier
initial, et alors comment B peut-il deviner celui que A a choisi ?
- soit on suppose que A va devoir aider B dans sa construction, et dans ce
cas C qui entend les mêmes conseils sera évidemment capable d'en profiter de
la même manière.

Donc sans même se préoccuper de la qualité de la construction, ce type de
collaboration directe la compromet à l'avance.
La solution ne se trouve pas dans la complexité de la construction, elle se
trouve nécessairement dans le protocole d'échange qui doit apporter la
certitude à A et B tout en laissant C sur un dilemme insoluble. C'est
pourquoi la construction d'un secret élémentaire (un booléen) suffirait à
valider un tel protocole.

Cordialement,

--

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

Avatar
remy
"Patrick 'Zener' Brunet" a écrit dans
le message de news:421223e3$0$3816$
Bonjour.

"remy" a écrit dans le message de news:
421217c1$0$17275$
<...>
j'avais propose un debut de piste pour essayer de repondre
l'idee de base etait de prendre un morceau d'un nb premier en base 2
pour faire un Xor et de changer de nb premier en fct du morceau

comme il y a une infinite de nb premier si l'on ne connait pas la graine
tu es de la baise
le pb c'est la fct de repartition des nbs premiers dans les entiers
il ne faudrait pas que le pas soit cyclique pour l'instant cela semble
acquis

et la graine tu la fais passer en lui payant un coup a boire



Mmmmmmh... Après maintes relectures et en ignorant le vocabulaire
"branché"...

Apparemment vous partez sur une stratégie permettant de construire une
sorte

de séquence pseudo-aléatoire, c'est à dire dont la logique ne puisse pas
être devinée par l'intrus du milieu.

Fort bien, mais le but reste de construire un secret partagé entre les
stations A et B, sans secret préalable et à travers un canal notoirement
écouté par C.
Donc en toute logique :
- soit on suppose que B doit être capable de deviner cette logique de
construction pour construire la même séquence que A, alors que C lui en
serait incapable (au nom de quoi ?),
- soit on suppose que la logique de la construction peut être divulguée
publiquement et que la séquence ne dépend que du choix du nombre premier
initial, et alors comment B peut-il deviner celui que A a choisi ?
- soit on suppose que A va devoir aider B dans sa construction, et dans ce
cas C qui entend les mêmes conseils sera évidemment capable d'en profiter
de

la même manière.

Donc sans même se préoccuper de la qualité de la construction, ce type de
collaboration directe la compromet à l'avance.
La solution ne se trouve pas dans la complexité de la construction, elle
se

trouve nécessairement dans le protocole d'échange qui doit apporter la
certitude à A et B tout en laissant C sur un dilemme insoluble. C'est
pourquoi la construction d'un secret élémentaire (un booléen) suffirait à
valider un tel protocole.


ok

ce que je propose est que vous avez parfaitement apprehende
peut etre simplifie par une approche mathematique
cela se resume a une mise en facteur des cles pour chaque msg
ou cela peut etre vu comme un enorme masque dans lequel
je prends des petits bouts

pour l'implementation cela a deja ete publie ici

pour ce qui vous pose pb ce modele ne repond pas completement a la
problematique
le partage initial "la graine"

l'on peut imaginer sans trop de difficulte que pour vouloir
partager un secret cela implique une collaboration etroite anterieure
le tout est de ne pas a avoir a renouveller l'echange de cles a chaque Msg

remy


Cordialement,

--

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





Avatar
Christophe HENRY

En forçant bien, on doit même pouvoir y caser les lois de la
thermodynamique.


Le principe d'entropie portant sur des données pures, sans élément physique
? Vous spéculez là ...


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.


--
<8#--X--< filtré par Avast! 4 Home


Tu vas dire que je râle mais :
- la signature c'est "tiret tiret espace". Ca permetttrait à mon logiciel
de retirer ta signature lors des réponses
- je suis très content que tu utilises un anti-virus.

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


Avatar
Patrick 'Zener' Brunet
Bonsoir.

"Christophe HENRY" a écrit dans le
message de news: cuti85$iib$

En forçant bien, on doit même pouvoir y caser les lois de la
thermodynamique.


Le principe d'entropie portant sur des données pures, sans élément
physique


? Vous spéculez là ...


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.



Je n'avais pas pensé à cet aspect.
Quoique je l'aie utilisé plus naïvement en disant que toute information qui
est diffusée (et donc captée par _C_hiant-comme-tout) ne peut pas être
oubliée, et donc il n'est jamais "trop tard" pour l'utiliser.



--
<8#--X--< filtré par Avast! 4 Home


Tu vas dire que je râle mais :
- la signature c'est "tiret tiret espace". Ca permetttrait à mon logiciel
de retirer ta signature lors des réponses


C'est un nouveau bug du mien alors, c'est lui qui rajoute les tirets sans
espace.
J'ai fait une correction dans ce que je maîtrise, on va voir ce que ça
donne...

- je suis très content que tu utilises un anti-virus.



Oui, moi aussi !

ben là-dessous il y est l'espace, 2 fois, avant l'envoi, attention je
touche...
--
--
/**************************************************************
* Patrick BRUNET
* E-mail: lien sur http://zener131.free.fr/ContactMe
**************************************************************/
<8#--X--< filtré par Avast! 4 Home



Avatar
jpeps

[...]
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).
[...]


Bonjour

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

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.

Salutations

JPP

*sur* = démontré mathématiquement.

--
Enlevez le NO du spam et .invalid pour me répondre

"Dans les champs de l'observation, le hasard ne favorise que les esprits
préparés." Louis Pasteur

Avatar
JL
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.

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


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.

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.

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.

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.

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...

JL.

1 2 3 4 5