"porte dérobée" potentielle dans un PRNG publié par le NIST
8 réponses
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
Toujours pour anglophones, plus de détails ici: http://marc.info/?l=cryptography&m9516611229001
François Grieu
JL
"Francois Grieu" a écrit dans le message de news:
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" <fgrieu@gmail.com> a écrit dans le message de news:
fgrieu-B3E3B6.08581216112007@news-2.proxad.net...
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.
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
Dans l'article <473e096a$0$29351$, "JL" a écrit:
"Francois Grieu" a écrit dans le message de news:
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
Dans l'article <473e096a$0$29351$426a74cc@news.free.fr>,
"JL" <JL@jlamy.com> a écrit:
"Francois Grieu" <fgrieu@gmail.com> a écrit dans le message de news:
fgrieu-B3E3B6.08581216112007@news-2.proxad.net...
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.
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
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.
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.
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 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
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.
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
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".
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".
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
"Francois Grieu" a écrit dans le message de news:
- 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" <fgrieu@gmail.com> a écrit dans le message de news:
fgrieu-8D39FD.19000817112007@news-4.proxad.net...
- 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 ?
- 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
Dans l'article <4742011c$0$24937$, "JL" écrit:
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
Dans l'article <4742011c$0$24937$426a74cc@news.free.fr>,
"JL" <JL@jlamy.com> écrit:
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
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
