Ansicht umschalten
Avatar von Akurei
  • Akurei

838 Beiträge seit 02.07.2006

Schneier / Bernstein: Elliptische Kurven des NIST nicht vertrauenswürdig

NIST secp256r1 secp384r1 secp521r1 Kurven sind NICHT
VERTRAUENSWÜRDIG!

Ich beginne mit einem Zitat von Bruce Schneier:

"I no longer trust the [NIST Elliptic Curves] constants. I believe
the NSA has manipulated them through their relationships with
industry."
> https://www.schneier.com/blog/archives/2013/09/the_nsa_is_brea.html#c1675929

Die vom NIST zertifizierten und von OpenSSH, Firefox, OpenSSL,
RedPhone, TextSecure, und vielen weiteren Firmen und Organisationen
benutzten Elliptischen Kurven der Form secp{256,384,521}r1 (wichtig
ist das 'r' für "random". Die Kurven mit 'k', Koblitz-Curves,
scheinen in Ordnung zu sein. Bitcoin benutzt beispielsweise die
secp256k1:
http://bitcoinmagazine.com/7781/satoshis-genius-unexpected-ways-in-wh
ich-bitcoin-dodged-some-cryptographic-bullet/ ) sind verdächtig, da
es nicht ersichtlich wird, wie die Zufälligen Parameter gewählt
wurden. Ein "Seed" wird angegeben, der durch SHA-1 gejagt wird, und
der zu der Wahl der Domainparameter führt, aber es wird nirgendwo
erklärt, woher der Seed kommt, und wieso dieser Seed benutzt wurde.

Nehmen wir den Seed von secp256r1. Der Seed lautet:
c49d360886e704936a6678e1139d26b7819f7e90
Bevor ich weiter ausführe, wieso dieser "Seed" verdächtig ist, rate
ich jedem Leser, diesen "Seed" in Google einzugeben und die ersten
paar Resultate der Suche zu lesen... Fertig? Gut.

Nirgends wird erklärt, wie dieser Seed zustande kommt. Dabei hätte
ein Seed wie beispielsweise "HalloDiesIstDerSEEDzuSECP256R1", oder
"1" oder "DIES IST SEED 1" exakt die selbe Sicherheit geboten wie
0xc49d360886e704936a6678e1139d26b7819f7e90, da wir das Ganze ja durch
SHA1 jagen.

Nun wird vermutet, dass es bei den "Random"-Curves, also den Curves
bei denen nach dem secp{256,384,521} ein r und eine 1 steht, auf
Grund des verdächtigen Seeds eine Backdoor gibt. Nehmen wir an, eine
in 10e9 Curve Domainparameter weißt eine nur der NSA bekannte
Schwachstelle auf. Dann musste die NSA nur 10e9/2 = 10e8 verschiedene
Seeds für den SHA1 testen, bevor sie eine schwache Kurve gefunden
hat. Uns wird das ganze als zusätzliche Sicherheit verkauft. 

Nachfolgend ein Text von Daniel J. Bernstein, der das viel besser als
ich zusammenfassen kann:

"The possibility of attackers manipulating standard curve choices was
raised in the late 1990s, when NSA volunteered to "contribute"
elliptic curves to the committee producing ANSI X9.62. NSA did in
fact end up producing various elliptic curves later standardized by
ANSI X9.62, SEC 2, and NIST FIPS 186-2; these curves were
subsequently deployed in many applications.

In response to NSA's contributions, ANSI X9.62 developed "a method
for selecting an elliptic curve verifiably at random", and a
procedure to "verify that a given elliptic curve was indeed generated
at random"; it even claims that this procedure "serves as proof
(under the assumption that SHA-1 cannot be inverted) that the
parameters were indeed generated at random". However, this procedure
does not verify randomness; it verifies only that the curve
coefficients were produced as SHA-1 output. The claimed "proof" is
nonexistent. The ANSI X9.62 curve-generation method is not trivially
manipulatable but it is manipulatable.

IEEE P1363 copied the same curve-generation method and stated that it
allows "others to verify that the curve was indeed chosen
pseudo-randomly". However, "pseudo-random" is not the same as
"random", and does nothing to stop a malicious curve generator from
searching through many choices of seeds. NIST correctly characterized
the verification procedure for these curves as merely checking "that
the coefficient b was obtained from s via the cryptographic hash
function SHA-1".

SEC 2 version 1.0 copied the curves that NSA had produced for NIST,
and copied the incorrect ANSI X9.62 claim that the curves were
"chosen verifiably at random". SEC 2 further claimed that the curves
were chosen "by repeatedly selecting a random seed and counting the
number of points on the corresponding curve until appropriate
parameters were found". This claim might be correct but is certainly
not verifiable."
> http://safecurves.cr.yp.to/rigid.html


Bewerten
- +
Ansicht umschalten