"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/secur...tters_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/n...ch2007.pdf
pour les anglophones, à ne pas manquer:
http://www.wired.com/politics/secur...tters_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/n...ch2007.pdf
Poser une question
http://marc.info/?l=cryptography&m9516611229001
François Grieu
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.
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.
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
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.
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.
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...rsmith.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.
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