"porte dérobée" potentielle dans un PRNG publié par le NIST

Le
Francois Grieu
Bonjour,

pour les anglophones, à ne pas manquer:
http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115
http://rump2007.cr.yp.to/15-shumow.pdf

Résumé: la NSA a imposé, dans un standard sur les générateurs
pseudo-aléatoires publié par le National Institute of Standards
and Technology (USA), un algorithme taillé sur mesure pour permettre
de laisser une "porte dérobée" permettant de pénétrer le système,
sans courir le risque que l'examen du système permette de trouver
ladite porte dérobée. Si l'on suit les recommandations expresses
de ce standard il est concevable que la NSA puisse pénétrer le
système résultant.

Plus précidément, l'algorithme du générateur pseudo-aléatoire met
en jeu une constante publique qu'il est possible de préparer à partir
d'une constante secrète, et celui qui connais la constante secrète
peut "casser" le générateur à partir de 32 octets consécutifs
produits par le générateur.
L'algorithme vient avec une constante publique [A1] explicitement
recommandée [A2] dans une partie normative du standard. Il existe
nécessairement une constante secrète correspondante, dont on peut
soupçonner (sans preuve) qu'elle est connue de quelqu'un à la NSA,
puisque aucun détail ne semble disponible sur la manière dont cet
exemple de constante publique a été généré. Celui qui utiliserais
l'algorithme avec la constante recommandée s'exposerais donc à ce
que son système soit pénétrable par la NSA.

Note: je n'ai PAS vérifié en détail les allégations de ces articles,
émanant d'auteurs réputés.

François Grieu

[A1] annexe A, point 1
[A2] annexe A, point 2 dans le standard:
http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Francois Grieu
Le #594824
Toujours pour anglophones, plus de détails ici:
http://marc.info/?l=cryptography&m9516611229001

François Grieu
JL
Le #594823
"Francois Grieu"

Celui qui utiliserait
l'algorithme avec la constante recommandée s'exposerais donc à ce
que son système soit pénétrable par la NSA.


C'est un peu gros quand même, non ?

Existe-t-il des raisons d'utiliser une constante publique particulière ? Par
exemple, existe-t-il des constantes "faibles" qui permettraient de casser le
PRG, ce qui pourrait justifier qu'une constante "forte" soit fournie.

JL.

Francois Grieu
Le #594675
Dans l'article "JL"
"Francois Grieu"

Celui qui utiliserait l'algorithme avec la constante recommandée
s'exposerais donc à ce que son système soit pénétrable par la NSA.


C'est un peu gros quand même, non ?

Existe-t-il des raisons d'utiliser une constante publique particulière ?


Oui, faire comme il est recommandé explicitement dans une partie
normative du standard, et s'économiser beaucoup de travail:
"The security of Dual_EC_DRBG requires that the points P and Q be
properly generated. To avoid using potentially weak points,
the points specified in Appendix A.1 *should* be used.
However, an implementation may use different pairs of points,
provided that they are verifiably random, as evidenced by the use
of the procedure specified in Appendix A.2.1 below, and
the self-test procedure in Appendix A.2.2."

Le mot "should" est en gras dans le standard. Il est moins fort que
"shall", mais il serait difficile de blâmer celui qui fait comme
le standard recommande, et évite ainsi un développement complexe.

Par exemple, existe-t-il des constantes "faibles" qui permettraient
de casser le PRG, ce qui pourrait justifier qu'une constante "forte"
soit fournie.


Oui il y a de mauvaises constantes publiques P Q; le standard donne
une méthode qui les évite, et mieux, permet de convaincre un tiers que
P Q peut être utilisé en confiance.


Ce qui est remarquable, c'est que
- P Q peuvent être générés à partir d'une valeur secrète constituant
la clé d'une "porte dérobée", clé qui ne peut être déduite des valeurs
publiques P Q;
- le générateur est tel que cette "porte dérobée" est exploitable
dans de nombreux cas pratiques, pour qui en détient la clé;
- l'existence de cette "porte dérobée" sure et exploitable n'est ni
triviale, ni signalée explicitement dans le standard;
- l'algorithme est très lent, et on ne lui connais pas d'intérêt
pratique (sauf, maintenant, cette "porte dérobée");
- le standard donne toutes raisons et justifications à l'implémenteur
d'utiliser des valeurs spécifiées de P Q, sans pour autant fournir
la preuve qu'elles sont générés conformément à la méthode proposée
par le standard, ni par une méthode donnant des garanties
équivalentes contre la possibilité que quelqu'un détienne la clé de
la "porte dérobée" correspondant à ces P Q spécifiés;
- selon Bruce Schneier, la NSA a poudu l'algorithme et bataillé pour
qu'il soit intégré au standard.

On atteind il me semble la limite de l'adage, pourtant maintes fois
vérifié, qui recommande de ne pas voir la malice là ou les faits
s'expliquent par la paresse ou l'incompétence.


François Grieu


Al
Le #594674
On atteint il me semble la limite de l'adage, pourtant maintes fois
vérifié, qui recommande de ne pas voir la malice là ou les faits
s'expliquent par la paresse ou l'incompétence.


ne serais tu pas professionnel ? au minimum très expérimenté...
probablement les deux ? ;-)

l'expérience avec le DES montre plutôt que la NSA a tendance à protéger
les usagers à leur insu d'attaques qu'il gardent secrète (cryptanalyse
différentielle et linéaire dans ce cas) . ce qui est signe de compétence
et de travail... ils ont du laisser le travail à des scientifiques et
pas inclure de commerciaux ou de politiques dans ces décisions.

Francois Grieu
Le #594673
Le 17 nov, 19:18, Al a écrit:

On atteint il me semble la limite de l'adage, pourtant maintes fois
vérifié, qui recommande de ne pas voir la malice là où les faits
s'expliquent par la paresse ou l'incompétence.


Ne serais tu pas professionnel ? au minimum très expérimenté...
probablement les deux ? ;-)


Après une première exposition en 1979 par mon prof de math
de taupe qui a expliqué RSA un jour de grève, je suis
progressivement entré dans la crypto, la sécurité informatique
en général, et la carte à puce en particulier. C'est devenu ma
profession.

l'expérience avec le DES montre plutôt que la NSA a tendance
à protéger les usagers à leur insu d'attaques qu'il gardent
secrète (cryptanalyse différentielle et linéaire dans ce cas) .


Les faits établis concernant la genèse de DES:
- DES est covenablement protégé contre la cryptanalyse
différentielle.
- La NSA connaissait la cryptanalyse différentielle.
- La cryptanalyse différentielle n'a pas été révélée
publiquement par les auteurs de DES, qui l'ont
justifié ensuite par des considérations de sécurité
nationale:
http://www.research.ibm.com/journal/rd/383/coppersmith.pdf
- selon cette source, les concepteurs avaient dès
l'origine connaissance de la cryptanalyse
différentielle;
- selon une commission d'enquète officielle, l'apport
de la NSA à la sécurité de DES est indirect;
- la NSA n'a rien fait d'autre pour affaiblir le DES
que de faire réduire la taille de clé à 56 bits, ce
qui reste la meilleure attaque en pratique.

ce qui est signe de compétence et de travail...


Oui la NSA était en avance à l'époque, et tout donne
à penser qu'aujourd'hui ils sont *au moins* de très haut
niveau, compétents et bien organisés. C'est précisément
ce qui rend les omissions de ce standard de CSPRNG
pour le moins surprenantes.

François Grieu


Jean-Marc Desperrier
Le #594669
Francois Grieu wrote:
On atteind il me semble la limite de l'adage, pourtant maintes fois
vérifié, qui recommande de ne pas voir la malice là ou les faits
s'expliquent par la paresse ou l'incompétence.


"Never attribute to malice that which is adequately explained by
stupidity (Hanlon's razor)" que je traduirais plutôt "Ne jamais
attribuer à la malveillance ce que la stupidité suffit à expliquer".

JL
Le #594667
"Francois Grieu"

- le standard donne toutes raisons et justifications à l'implémenteur
d'utiliser des valeurs spécifiées de P Q, sans pour autant fournir
la preuve qu'elles sont générés conformément à la méthode proposée
par le standard, ni par une méthode donnant des garanties
équivalentes contre la possibilité que quelqu'un détienne la clé de
la "porte dérobée" correspondant à ces P Q spécifiés;


Dans ce cas qu'est-ce qui empêche un généreux serviteur de la Cause de
fournir d'autres constantes publiques, qui répondraient elles à ces
conditions, et de les proposer comme alternatives au standard ?

Ce serait un bon coup de pub, non ?

JL.

Francois Grieu
Le #594510
Dans l'article "JL"
Qu'est-ce qui empêche un généreux serviteur de la Cause de fournir
d'autres constantes publiques, qui répondraient elles à ces
conditions, et de les proposer comme alternatives au standard ?


Ce n'est pas impossible, mais le générateur résultant sera plus
gros en code (donc plus couteux à écrire et valider) et plus lent à
l'initialisation que celui utilisant les constantes de l'annexe A.1;
ou alors il ne sera pas conforme au standard, qui impose que si l'on
utilise des constantes autres que celles de l'annexe A.1, on fasse
à chaque initialisation des tests suplémentaires, définis en annexe
A.2.2 "Additional Self-testing Required for Alternative P, Q".

Bref, le standard organise une pénalité pour ceux qui voudraient
utiliser autre chose que les constantes de l'annexe A.1, pour
lesquelles manquent les éléments nécessaires à se convaincre que
personne n'a les clés de la "porte dérobée" correspondante.


François Grieu

Le générateur en question: Dual_EC_DRBG dans
http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf

Publicité
Poster une réponse
Anonyme