Clés asymétriques et partage...

Erwan David

06/12/2006 à 08:12

"Dan" écrivait :

Je cherche autre chose :
Y a-t-il moyen de faire un message qui ne puisse être lu que par B et
C (les deux simultanément donc). Je n'aimerais pas une solution du
genre cB(cC(X)), car B doit alors accepter de décoder son bout de
message, sans être certain que C fera son bout de travail. C pourrait
prendre connaissance de X sans que B ne le puisse....

En prqtique les algorithmes asymétriques ne sont pas adaptés à
chiffrer directement un message, sans compter le problème du partage.

Donc quand A veut envoyer un message chiffré à B, il génére une clef
secrète K et envoie cB(K)K(X).

DOnc pour envoyer un message lisibe par B & C il envoie cB(K)cC(K)K(X).

--
Erwan

Thomas Pornin

06/12/2006 à 09:00

According to Dan :

Y a-t-il moyen de faire un message qui ne puisse être lu que par B et
C (les deux simultanément donc)

Quelle est _précisément_ la question ? Est-ce : "y a-t-il moyen de faire
un message que B et C peuvent tous deux lire ?" Ou encore : "y a-t-il
moyen de faire un message qui ne peut être lu que par B et C agissant
conjointement ?"

Les réponses sont différentes suivant les cas. Dans le premier, c'est
simple : il suffit de chiffrer le message deux fois, une fois pour B et
une fois pour C. Pragmatiquement, le message est chiffré symétriquement
avec une clé de session, et c'est cette clé de session qui est chiffrée
asymétriquement deux fois, pour B et pour C. C'est exactement ce qui se
passe quand on envoie un email chiffré (en S/MIME ou en OpenPGP, même
principe) à plusieurs destinataires.

Dans le deuxième cas, on peut chiffrer symétriquement le message avec
une clé de session K, puis envoyer à B une clé Kb (chiffrée avec la
clé publique de Kb) et à C une clé Kc (chiffrée avec la clé publique
de C) telles que Kb XOR Kc = K : comme cela, B et C doivent collaborer
pour lire le message (enfin, pour retrouver K). C'est un simple partage
de secret qui s'étend à plus de deux destinataires avec le système de
Shamir, qui permet d'établir un quorum et autres fioritures.

Notons que si ce système règle le problème de l'action conjointe, il ne
fait rien quant aux possibilités pour B de truander C : quand B et C
déchiffrent, respectivement, Kb et Kc, il faut bien qu'ils s'envoient
ces clés. Le premier à parler (mettons C) prend un risque : B pourrait
alors recevoir Kc, puis "omettre" d'envoyer Kb en réponse, et C se
fait avoir. Dans le cas général, sans tiers "de confiance" pour faire
l'assemblage final, il n'y a pas de bonne solution, mais on peut faire
des béquilles : genre, s'échanger les bits un par un, ce qui fait que
B ne peut gagner qu'un bit de connaissance de plus que C en trichant.
Là, on arrive à une évaluation des puissances de calcul respectives de
B et C : si l'un des deux arrête le protocole, alors il peut "terminer"
l'échange par une recherche exhaustive sur les bits qui lui manquent. Si
l'un des deux protagonistes a beaucoup plus de puissance de calcul que
l'autre, alors il peut s'arrêter "tôt" et réussir son arnaque. On peut
compenser ça par un handicap : par exemple, si B a trente fois plus de
puissance, on lui impose de commencer par envoyer cinq bits d'un coup à
C.

Ce mécanisme d'envois successifs a le gros défaut de ne présenter aucune
garantie de correction : C ne peut pas s'assurer que les bits envoyés
par B sont bien ceux de Kb, et pas un aléa bidon. On peut arranger ça
avec des preuves zero-knowledge de correction à chaque bit, mais :
1. c'est compliqué ;
2. ça devient très lourd sur les communications ;
3. ça ne marche que si le chiffrement asymétrique est conçu pour, ce qui
n'a rien d'évident. Notamment, pas la peine d'espérer faire ça avec un
RSA de base.

En bref, pas de solution simple dans le cas général.

--Thomas Pornin

According to Dan <environ314@gmail.com>:

Y a-t-il moyen de faire un message qui ne puisse être lu que par B et
C (les deux simultanément donc)

Quelle est _précisément_ la question ? Est-ce : "y a-t-il moyen de faire
un message que B et C peuvent tous deux lire ?" Ou encore : "y a-t-il
moyen de faire un message qui ne peut être lu que par B et C agissant
conjointement ?"

Les réponses sont différentes suivant les cas. Dans le premier, c'est
simple : il suffit de chiffrer le message deux fois, une fois pour B et
une fois pour C. Pragmatiquement, le message est chiffré symétriquement
avec une clé de session, et c'est cette clé de session qui est chiffrée
asymétriquement deux fois, pour B et pour C. C'est exactement ce qui se
passe quand on envoie un email chiffré (en S/MIME ou en OpenPGP, même
principe) à plusieurs destinataires.

Dans le deuxième cas, on peut chiffrer symétriquement le message avec
une clé de session K, puis envoyer à B une clé Kb (chiffrée avec la
clé publique de Kb) et à C une clé Kc (chiffrée avec la clé publique
de C) telles que Kb XOR Kc = K : comme cela, B et C doivent collaborer
pour lire le message (enfin, pour retrouver K). C'est un simple partage
de secret qui s'étend à plus de deux destinataires avec le système de
Shamir, qui permet d'établir un quorum et autres fioritures.

Notons que si ce système règle le problème de l'action conjointe, il ne
fait rien quant aux possibilités pour B de truander C : quand B et C
déchiffrent, respectivement, Kb et Kc, il faut bien qu'ils s'envoient
ces clés. Le premier à parler (mettons C) prend un risque : B pourrait
alors recevoir Kc, puis "omettre" d'envoyer Kb en réponse, et C se
fait avoir. Dans le cas général, sans tiers "de confiance" pour faire
l'assemblage final, il n'y a pas de bonne solution, mais on peut faire
des béquilles : genre, s'échanger les bits un par un, ce qui fait que
B ne peut gagner qu'un bit de connaissance de plus que C en trichant.
Là, on arrive à une évaluation des puissances de calcul respectives de
B et C : si l'un des deux arrête le protocole, alors il peut "terminer"
l'échange par une recherche exhaustive sur les bits qui lui manquent. Si
l'un des deux protagonistes a beaucoup plus de puissance de calcul que
l'autre, alors il peut s'arrêter "tôt" et réussir son arnaque. On peut
compenser ça par un handicap : par exemple, si B a trente fois plus de
puissance, on lui impose de commencer par envoyer cinq bits d'un coup à
C.

Ce mécanisme d'envois successifs a le gros défaut de ne présenter aucune
garantie de correction : C ne peut pas s'assurer que les bits envoyés
par B sont bien ceux de Kb, et pas un aléa bidon. On peut arranger ça
avec des preuves zero-knowledge de correction à chaque bit, mais :
1. c'est compliqué ;
2. ça devient très lourd sur les communications ;
3. ça ne marche que si le chiffrement asymétrique est conçu pour, ce qui
n'a rien d'évident. Notamment, pas la peine d'espérer faire ça avec un
RSA de base.

En bref, pas de solution simple dans le cas général.

--Thomas Pornin

Vous avez filtré cet utilisateur ! Consultez son message

According to Dan :

Y a-t-il moyen de faire un message qui ne puisse être lu que par B et
C (les deux simultanément donc)

Quelle est _précisément_ la question ? Est-ce : "y a-t-il moyen de faire
un message que B et C peuvent tous deux lire ?" Ou encore : "y a-t-il
moyen de faire un message qui ne peut être lu que par B et C agissant
conjointement ?"

Les réponses sont différentes suivant les cas. Dans le premier, c'est
simple : il suffit de chiffrer le message deux fois, une fois pour B et
une fois pour C. Pragmatiquement, le message est chiffré symétriquement
avec une clé de session, et c'est cette clé de session qui est chiffrée
asymétriquement deux fois, pour B et pour C. C'est exactement ce qui se
passe quand on envoie un email chiffré (en S/MIME ou en OpenPGP, même
principe) à plusieurs destinataires.

Dans le deuxième cas, on peut chiffrer symétriquement le message avec
une clé de session K, puis envoyer à B une clé Kb (chiffrée avec la
clé publique de Kb) et à C une clé Kc (chiffrée avec la clé publique
de C) telles que Kb XOR Kc = K : comme cela, B et C doivent collaborer
pour lire le message (enfin, pour retrouver K). C'est un simple partage
de secret qui s'étend à plus de deux destinataires avec le système de
Shamir, qui permet d'établir un quorum et autres fioritures.

Notons que si ce système règle le problème de l'action conjointe, il ne
fait rien quant aux possibilités pour B de truander C : quand B et C
déchiffrent, respectivement, Kb et Kc, il faut bien qu'ils s'envoient
ces clés. Le premier à parler (mettons C) prend un risque : B pourrait
alors recevoir Kc, puis "omettre" d'envoyer Kb en réponse, et C se
fait avoir. Dans le cas général, sans tiers "de confiance" pour faire
l'assemblage final, il n'y a pas de bonne solution, mais on peut faire
des béquilles : genre, s'échanger les bits un par un, ce qui fait que
B ne peut gagner qu'un bit de connaissance de plus que C en trichant.
Là, on arrive à une évaluation des puissances de calcul respectives de
B et C : si l'un des deux arrête le protocole, alors il peut "terminer"
l'échange par une recherche exhaustive sur les bits qui lui manquent. Si
l'un des deux protagonistes a beaucoup plus de puissance de calcul que
l'autre, alors il peut s'arrêter "tôt" et réussir son arnaque. On peut
compenser ça par un handicap : par exemple, si B a trente fois plus de
puissance, on lui impose de commencer par envoyer cinq bits d'un coup à
C.

Ce mécanisme d'envois successifs a le gros défaut de ne présenter aucune
garantie de correction : C ne peut pas s'assurer que les bits envoyés
par B sont bien ceux de Kb, et pas un aléa bidon. On peut arranger ça
avec des preuves zero-knowledge de correction à chaque bit, mais :
1. c'est compliqué ;
2. ça devient très lourd sur les communications ;
3. ça ne marche que si le chiffrement asymétrique est conçu pour, ce qui
n'a rien d'évident. Notamment, pas la peine d'espérer faire ça avec un
RSA de base.

En bref, pas de solution simple dans le cas général.

--Thomas Pornin

Francois Grieu

06/12/2006 à 09:26

Dans l'article ,
"Dan" écrit:

Supposons que trois personnes, A,B,C, ont chacune leur paire de clé
privée (dA, dB, et dC) et publique (cA,cB,cC).

Y a-t-il moyen de faire un message qui ne puisse être lu que par B et
C (les deux simultanément donc).

Une méthode consiste à ce que A
- choisisse deux nombres aléatoires rB et rC
- chiffre rB avec la clé publique cB, rC avec cC,
et chiffre selon un algorithme symétrique (AES-CBC..)
le message avec la clé rB XOR rC
- transmette le résultat de ces trois chiffrements
(tant que l'on y est, signé par dA).

B et C devront collaborer pour déchiffrer le message.
Aucun n'est avantagé par rapport à l'autre.

Par contre chaqun des deux peut "tricher" en refilant
un maucais rB/rC à l'autre; pour que ce soit au moins
détectable, on peut transmettre (toujours signé par dA)
une information caractéristique de rB et rC mais ne les
révélant pas, telle que les hashs de rB et rC (ou le
chiffrement symétrique de rB avec la clé rB, idem rC)

Par contre je ne vois pas immédiatement comment construire
un protocole entre B et C (ne nécessitant pas la collaboration
active de A après l'émission du message) qui rende impossible
que B déchiffre le message si C ne le peut pas.

François Grieu

Pascal Bourguignon

06/12/2006 à 10:49

"Dan" writes:

Bonjour,
Supposons que trois personnes, A,B,C, ont chacune leur paire de clé
privée (dA, dB, et dC) et publique (cA,cB,cC).

Les applications classiques sont :
Codage/décodage, authentification, codage+authentification :
* A écrit à B un message codé X en lui envoyant cB(X), et B décode
ce message en lui appliquant dB : dB(cB(X))=X
* A signe un message envoyé non codé. Il publie dA(X), et chacun, en
lui appliquant cA, peut à la fois lire X et s'assurer que c'est bien A
qui l'a codé.
* A crypte et signe un message pour B. Il lui envoie cB(dA(X))

Je cherche autre chose :
Y a-t-il moyen de faire un message qui ne puisse être lu que par B et
C (les deux simultanément donc). Je n'aimerais pas une solution du
genre cB(cC(X)), car B doit alors accepter de décoder son bout de
message, sans être certain que C fera son bout de travail. C pourrait
prendre connaissance de X sans que B ne le puisse....

C'est possible.

Il faut implémenter un protocole d'échange simultané de secrêts entre
B et C.

Voir par exemple:
http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id1221

ou une description d'un tel protocole dans:
http://www.amazon.com/Applied-Cryptography-Protocols-Algorithms-Source/dp/0471117099/sr=8-1/qid65398395/ref=pd_bbs_1/002-4176967-3674463?ie=UTF8&s=books
(il y a une édition française aussi).

--
__Pascal Bourguignon__ http://www.informatimago.com/

PLEASE NOTE: Some quantum physics theories suggest that when the
consumer is not directly observing this product, it may cease to
exist or will exist only in a vague and undetermined state.

Dan

06/12/2006 à 15:25

On 6 déc, 09:00, Thomas Pornin wrote:

According to Dan :

Y a-t-il moyen de faire un message qui ne puisse être lu que par B et
C (les deux simultanément donc)Quelle est _précisément_ la questi on ? Est-ce : "y a-t-il moyen de faire
un message que B et C peuvent tous deux lire ?" Ou encore : "y a-t-il

moyen de faire un message qui ne peut être lu que par B et C agissant
conjointement ?"

Il s'agit bien de la 2ème version.

Exemple fantaisiste : j'ai écris mes mémoires, où je révèle un tas
d'informations relevant de la vie privée de ma famille. Mes deux
enfants ont connaissance de l'existence du document, chiffré, mais je
ne souhaite qu'ils puissent le lire seulement si les deux sont
d'accord. Il n'est par ailleurs pas question que l'un des deux puisse
avoir connaissance du contenu sans que l'autre le puisse également.

Merci à tous pour vos réponses !

Dan

06/12/2006 à 15:28

On 6 déc, 08:12, Erwan David wrote:

"Dan" écrivait :

Je cherche autre chose :
Y a-t-il moyen de faire un message qui ne puisse être lu que par B et
C (les deux simultanément donc). Je n'aimerais pas une solution du
genre cB(cC(X)), car B doit alors accepter de décoder son bout de
message, sans être certain que C fera son bout de travail. C pourrait
prendre connaissance de X sans que B ne le puisse....En prqtique les al gorithmes asymétriques ne sont pas adaptés à
chiffrer directement un message, sans compter le problème du partage.

Donc quand A veut envoyer un message chiffré à B, il génére une c lef
secrète K et envoie cB(K)K(X).

DOnc pour envoyer un message lisibe par B & C il envoie cB(K)cC(K)K(X).

Ca c'est pour permettre à A OU B de lire X. Mon propos est pour qu'il

y ait accord préalable de A ET B pour que la lecture de X soit possible

Erwan David

06/12/2006 à 15:31

"Dan" écrivait :

On 6 déc, 08:12, Erwan David wrote:
"Dan" écrivait :

Je cherche autre chose :
Y a-t-il moyen de faire un message qui ne puisse être lu que par B et
C (les deux simultanément donc). Je n'aimerais pas une solution du
genre cB(cC(X)), car B doit alors accepter de décoder son bout de
message, sans être certain que C fera son bout de travail. C pourrait
prendre connaissance de X sans que B ne le puisse....En prqtique les algorithmes asymétriques ne sont pas adaptés à
chiffrer directement un message, sans compter le problème du partage.

Donc quand A veut envoyer un message chiffré à B, il génére une clef
secrète K et envoie cB(K)K(X).

DOnc pour envoyer un message lisibe par B & C il envoie cB(K)cC(K)K(X).

Ca c'est pour permettre à A OU B de lire X. Mon propos est pour qu'il

y ait accord préalable de A ET B pour que la lecture de X soit possible

D'accord, j'avais mal compris la question. Mais je crois qu'il y a eu
assez de réponses déjà à la bonne question.

--
Erwan

Dan

06/12/2006 à 15:33

On 6 déc, 09:26, Francois Grieu wrote:

Dans l'article ,
"Dan" écrit:

Supposons que trois personnes, A,B,C, ont chacune leur paire de clé
privée (dA, dB, et dC) et publique (cA,cB,cC).

Y a-t-il moyen de faire un message qui ne puisse être lu que par B et
C (les deux simultanément donc).Une méthode consiste à ce que A
- choisisse deux nombres aléatoires rB et rC

- chiffre rB avec la clé publique cB, rC avec cC,
et chiffre selon un algorithme symétrique (AES-CBC..)
le message avec la clé rB XOR rC

c'est-à-dire ? Si on connait rB et rB XOR rC, on ne peut pas en
déduire rC ?
Je vais essayer de comprendre ton idée...

Dan

06/12/2006 à 15:34

On 6 déc, 10:49, Pascal Bourguignon wrote:

Voir par exemple:http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUI DE&id1221

Merci pour la référence. N'étant pas spécialiste de ce genre de
question, est-il possible d'en donner les idées directrices ?

ou une description d'un tel protocole dans:http://www.amazon.com/Applied- Cryptography-Protocols-Algorithms-Sourc...
(il y a une édition française aussi).

--
__Pascal Bourguignon__ http://www.informatimago.com/

Francois Grieu

06/12/2006 à 17:04

Dans l'article ,
"Dan" a écrit:

On 6 déc, 09:26, Francois Grieu wrote:
Dans l'article ,
"Dan" écrit:

Supposons que trois personnes, A,B,C, ont chacune leur paire de clé
privée (dA, dB, et dC) et publique (cA,cB,cC).

Y a-t-il moyen de faire un message qui ne puisse être lu que par B et
C (les deux simultanément donc).
Une méthode consiste à ce que A

- choisisse deux nombres aléatoires rB et rC
- chiffre rB avec la clé publique cB, rC avec cC,
et chiffre selon un algorithme symétrique (AES-CBC..)
le message avec la clé rB XOR rC

c'est-à-dire ? Si on connait rB et rB XOR rC, on ne peut pas en
déduire rC ?

B connais rB (après l'avoir déchiffré avec cB) mais ni rC, ni rB XOR rC
C connais rC (après l'avoir déchiffré avec cC) mais ni rB, ni rB XOR rC

B et C peuvent échanger les rC et rB qui leur manquent, calculer
rB XOR rC, puis déchiffrer le message.

François Grieu

Clés asymétriques et partage...

10 réponses

Veuillez sélectionner un problème