Cryptage inviolable : bientôt en France

"Thomas Pornin" <pornin@nerim.net> a écrit dans le message de news:
ddvdup$2lun$1@biggoron.nerim.net...

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.

Amusant, mais le problème est que cela demande un ratio débit / capacité de
stockage très supérieur à ceux constatés actuellement. Par exemple si on
prend 100 Mbps , ce qui est à l'heure actuelle déjà pas mal comme débit pour
des personnes distantes, ça ne génère que 1 To de données en 24h, ce qui se
stocke avec quelques centaines d'euros.

Et prendre une hypothèse de débit plus élevée ne résout rien, car les coûts
du débit augmentent plus que linéairement, alors que ceux de stockage sont
presque linéaires, surtout dans ce cas où l'indexation est très simple.

Or la tendance historique c'est plutôt un abaissement du ratio débit /
capacité de stockage. Je ne vois donc pas comment cette idée pourrait
trouver un jour une application concrète.

JL.

pornin@nerim.net (Thomas Pornin) wrote in
news:de4bjl$2rtq$1@biggoron.nerim.net:

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

Ce n'est pas betement passer de la probabilité d'une collision à deux vers
une probabilité de collision à trois? qui peut être nettement inférieure,
je ne discute pas, mais proche de N, intuitivement, je ne suis pas sûr...

--
Pierre Vandevenne - DataRescue sa/nv - www.datarescue.com
The IDA Pro Disassembler & Debugger - world leader in hostile code analysis
PhotoRescue - advanced data recovery for digital photographic media
latest review: http://www.pcmag.com/article2/0,1759,1590497,00.asp

Bonjour.

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

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" ?

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

Mais c'est déjà très bien, merci beaucoup !
Je ne sais pas encore comment, mais ça peut me donner des idées de mise en
pratique. Il faudra que je voie comment exactement se formule cette
démonstration de probabilité de collision, et surtout par quel artifice on
peut envisager de réduire le volume sans perte de cet avantage par rapport à
l'attaquant.

Sauriez-vous par hasard où trouver des documents traitant des liens
possibles entre les stratégies de partage de secret et celles de ZKP
(preuves à divulgation nulle) ?

Merci beaucoup.

Cordialement,

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

According to Pierre Vandevenne <pierre@datarescue.com>:

Ce n'est pas betement passer de la probabilité d'une collision à deux vers
une probabilité de collision à trois?

Ici, Alice et Bob ne jouent pas le jeu de l'attaquant, et n'enregistrent
pas plus que leurs sqrt(N) statutaires. Eux s'en tiennent au minimum
syndical pour avoir leur collision à deux. Du coup, Charlie doit forcer
la dose pour obtenir sa collision à trois.


--Thomas Pornin

pornin@nerim.net (Thomas Pornin) wrote in
news:de6mp8$18nh$1@biggoron.nerim.net:

According to Pierre Vandevenne <pierre@datarescue.com>:

Ce n'est pas betement passer de la probabilité d'une collision à deux
vers une probabilité de collision à trois?

Ici, Alice et Bob ne jouent pas le jeu de l'attaquant, et
n'enregistrent pas plus que leurs sqrt(N) statutaires. Eux s'en
tiennent au minimum syndical pour avoir leur collision à deux. Du
coup, Charlie doit forcer la dose pour obtenir sa collision à trois.

OK, compris. Merci.

Haaa,

--- SwissCrypt.com --- wrote:

Nous vous informons que notre logiciel de cryptage inviolable sera
bientôt disponible pour les entreprises et organisations françaises.
Jean-Claude Volet
www.swisscrypt.com

Mais je les connait ceux là! Ils m'avaient spammé sur ce sujet y'a de ca
quelques années...

Maintenant c'est les news.


Yannick


--
_/ Yannick Patois ___________________________________________________
| web: http://feelingsurfer.net/garp/ | Garp sur irc undernet |
| email: patois@calvix.org | |

Thomas Pornin wrote:

Numériquement : si la source émet environ 2^60 mots pendant la séance
(soit 16 milliards de giga-octets...)

Et que vois-tu comme source qui pourrait émettre un tel débit ?

JL.

According to JL <JL@Jlamy.com>:

Thomas Pornin wrote:

Numériquement : si la source émet environ 2^60 mots pendant la séance
(soit 16 milliards de giga-octets...)

Et que vois-tu comme source qui pourrait émettre un tel débit ?

Il y a des problèmes pratiques, c'est clair. Un premier problème est
que le schéma suppose que l'attaquant ne peut pas empêcher les deux
parties d'écouter la même source, ce qui est incompatible avec, par
exemple, des câbles en fibre optique (à moins qu'on puisse en assurer
la sécurité physique, mais si on peut faire ça, on peut se demander
pourquoi on s'embêterait avec un système d'échange de clés). On peut
quand même envisager un système à base de satellites. Un satellite émet
avec une porteuse à quelques GHz, ça devrait être suffisant pour cracher
1 giga-bit par seconde. En multiplexant sur une centaine de longueurs
d'onde, on peut transmettre 100 Gbps, ce qui nous donne une "séance" qui
dure environ... 40 ans. Hmpf.

Le deuxième problème est qu'il faut un bon aléa. Comme on cherche à
défaire un attaquant qui a une puissance de calcul infinie, cet aléa ne
peut pas être constitué d'un PRNG, à moins d'avoir une "graine" dont
la taille dépasse la quantité de mémoire disponible à l'attaquant, ce
qui est ennuyeux, parce que la source doit disposer de cette mémoire,
qui est alors technologiquement faisable -- ce qui rend un peu caduque
l'hypothèse que l'attaquant n'y a pas accès. Il faut donc taper dans des
processus "physiquement aléatoires" (i.e. ceux dont on ne sait même pas
établir une façon théorique de les prévoir, même avec une puissance de
calcul infinie), ce qui 1. est un pari sur l'avancée de la physique,
et 2. n'offre en l'état actuel des choses que des performances beaucoup
trop médiocres pour l'usage qu'on envisage ici. De fait, on a bien du mal
à faire du "vrai aléa" à 1 kilo-bit par seconde, ce qui est 100 millions
de fois trop lent pour la séance de 40 ans décrite ci-dessus.

En bref, tout cela est purement théorique, et clairement non
implémentable dans la pratique. C'est quand même un résultat intéressant
puisqu'il permet de mieux cerner les limites du théoriquement faisable.


--Thomas Pornin

Mais si Charlie dispose de plus de mémoire qu'Alice et Bob et qu'il est
capable de capter la communication spécifiant les numéros des clés dont
le cryptage doit se servir ... quand Alice et Bob tomberont d'accord sur
une ou plusieurs clés, il est assez probable que Charlie les possède
aussi, puisqu'il dispose de plus de mémoire.

La probabilité que Alice et Bob possèdent une clé que Charlie ne possède
pas devrait pouvoir se calculer par une simple fonction.

En supposant que :
- La quantité totale de données envoyées soit Q ;
- La mémoire dont dispose Alice soit A ;
- La mémoire dont dispose Bob soit B ;
- La mémoire dont dispose Charlie soit C ;
- Le temps nécessaire à l'envoi de Q soit T ;
- A, B, C < Q ;

La chance que Alice et Bob possèdent une clé commune est alors égale à :

(A/Q) * (B/Q) = AB/Q^2

Ou, en français, le produit des proportions de données que chacun a pu
enregistrer. Maintenant la probabilité que Charlie ne connaisse pas une
clé :

1 - (C/Q)

Donc recoupons tout ça pour obtenir la probabilité qu'Alice et Bob
possèdent une clé que Charlie ne possède pas :

(AB/Q^2) * (1 - (C/Q)) = (A*B) * (Q-C) / Q^3

Si on prend des valeurs Q astronomiques comme vous le proposez, le temps
nécessaire pour trouver une clé commune va suivre une courbe très
exponentielle comme nous l'indique si bien le Q^3 et se rapprocher
rapidement - enfin façon de parler - de l'infini puisque le temps
nécessaire à trouver une clé commune à Alice et à Bob est :

T * (Q^3 / (A*B) * (Q-C))

Tandis que si on choisit un Q moindre au profit de plus nombreuses
séances, les chances que Charlie possède la même paire :

(A/Q) * (B/Q) * (C/Q)

vont augmenter vers :

(A/Q) * (B/Q) * 1

où il sera impossible à Alice et à Bob de partager deux clés sans que
Charlie les possède également.

Donc le système ne peut marcher que si, inversons les rôles, Alice et
Bob possèdent une quantité de mémoire très largement supérieure à celle
de Charlie ou que la quantité de mémoire échangée est gigantesque, et
"gigantesque" exposant 3, ça fait vite "trop" !

Du moins c'est mon point de vue de petit crypto-rien amateur ^^ !

P.S. : Je m'excuse d'avance si j'ai posté d'une manière inadéquate,
c'est mon premier message Usenet ...

According to Pero <pero_news@hotmail.com>:

En supposant que :
- La quantité totale de données envoyées soit Q ;
- La mémoire dont dispose Alice soit A ;
- La mémoire dont dispose Bob soit B ;
- La mémoire dont dispose Charlie soit C ;
- Le temps nécessaire à l'envoi de Q soit T ;
- A, B, C < Q ;

La chance que Alice et Bob possèdent une clé commune est alors égale à :

(A/Q) * (B/Q) = AB/Q^2

En fait non. Ce résultat n'est pas correct. Pour le voir, supposons
qu'Alice et Bob enregistre chacun deux blocs sur trois (A = B = 2Q/3).
À eux deux, ils cumulent plus de blocs que Q, donc ils en ont fatalement
en commun. La probabilité de clé commune est 1. Mais votre calcul ne
donne que 0.44...

Si on suppose A = B (Alice et Bob ont la même quantité de mémoire -- ça
simplifie les calculs), alors la probabilité qu'Alice et Bob possèdent
au moins un bloc commun est d'environ 1-exp(-A²/2Q), ce qui dépasse 50%
dès que A dépasse 1.18*srqt(Q) (je note sqrt(x) la racine carrée de x).
Si A vaut, par exemple, 4*sqrt(Q), alors la probabilité de succès est
de l'ordre de 99.97%, ce qui est "raisonnable".


Donc l'ordre de grandeur de la quantité de mémoire pour Alice et Bob
pour que le système fonctionne (ils arrivent à trouver une clé
commune quasiment à coup sûr) est la racine carrée de Q.

Voyons Charlie maintenant : lui, il ne veut pas avoir seulement un bloc
commun avec Alice et un autre avec Bob ; il veut avoir, précisément,
l'intégralité des blocs communs à Alice et Bob. Pour simplifier,
supposons qu'Alice et Bob ont un unique bloc commun. Du point de vue de
Charlie, ce bloc commun est issu d'un tirage aléatoire équiprobable. Ses
chances d'avoir précisément ce bloc sont de C/Q. Si on veut que Charlie
n'ait que, mettons, une chance sur 10000 de réussir son attaque, alors
il faut que Q soit supérieur ou égal à 10000*C, ou encore que C soit
inférieur ou égal à 0.0001*Q.

Le protocole est alors applicable si 4*sqrt(Q) est une taille viable
pour Alice et Bob (ils peuvent chacun avoir une mémoire de cette taille)
mais que 0.0001*Q ne soit pas viable pour Charlie. On voit ici que
le désavantage de Charlie est en sqrt(Q) par rapport à Alice et Bob.


--Thomas Pornin