[prev in list] [next in list] [prev in thread] [next in thread]
List: openssl-announce
Subject: Flaw in Dual EC DRBG (no, not that one)
From: Steve Marquess <marquess () opensslfoundation ! com>
Date: 2013-12-19 14:08:20
Message-ID: 52B2FDD4.5080701 () opensslfoundation ! com
[Download message RAW]
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
This is an unusual bug report for an unusual situation. I'm using it
as an opportunity to point out some considerations that have not been
widely reported.
Summary:
- -------
Stephen Checkoway and Matt Green of the Johns Hopkins University
Information Security Institute discovered a fatal bug in the Dual EC
DRBG implemention in the OpenSSL FIPS Object Module v2.0. This bug is
fatal in the sense that it prevents all use of the Dual EC DRBG
algorithm.
Note the bug is present in the Dual EC DRBG only, no other DRBG
types are affected.
The nature of the bug shows that no one has been using the OpenSSL
Dual EC DRBG.
Given the current status of Dual EC DRBG (now disowned[1] by the NIST
CMVP[2] and pretty much toxic for any purpose) we do not plan to
correct the bug. A FIPS 140-2 validated module cannot be changed
without considerable expense and effort, and we have recently
commenced that process of entirely removing the Dual EC DRBG code
from the formally validated module.
What is the bug?
- ---------------
When a PRNG is in free running mode it has to continuously check that
each block of output doesn't match the previous one (the so called
"continuous PRNG test").
If there is no previous block (as is the case on the very first call)
then a block has to be generated, stored as the "previous block" and
discarded. The output of the PRNG that the application sees is the
**next* *block which is now compared with the previous block.
It's this discarding part where the bug occurs: when the discard is
done the code places the output into a buffer and updates the Dual
EC DRBG state. When the discard occurs the data must not be output
and the Dual EC DRBG state must be updated, but that state update
isn't done. In the case of no additional input this has no effect,
but additional input is used by the "FIPS capable" OpenSSL. Note
that additional input does *not* effectively defeat the backdoor
vulnerability[3].
Will it be fixed?
- ----------------
We have no plans to fix this bug, as NIST has disowned Dual EC
DRBG in an official NIST Recommendation
(http://csrc.nist.gov/publications/nistbul/itlbul2013_09_supplemental.pdf)
and use of Dual EC DRBG is already disabled in upcoming OpenSSL
releases.
Even if we wanted to fix it our options are severely constrained by
the fact that the CMVP process forbids modifications of any
kind (even to address severe vulnerabilities) without the substantial
time and expense of formal retesting and review.
Is there a patch?
- ----------------
Of course:
diff --git a/fips/rand/fips_drbg_ec.c b/fips/rand/fips_drbg_ec.c
index 6be6534..270cfbb 100644
- --- a/fips/rand/fips_drbg_ec.c
+++ b/fips/rand/fips_drbg_ec.c
@@ -328,6 +328,7 @@ static int drbg_ec_generate(DRBG_CTX *dctx,
if (!bn2binpad(dctx->lb, dctx->blocklength, r))
goto err;
dctx->lb_valid = 1;
+ t = s;
continue;
}
if (outlen < dctx->blocklength)
This patch is of academic interest only as *any* modification to the
official FIPS module source code distribution means that the result
isn't validated and is not suitable for any context requiring a FIPS
140-2 validated module.
The OpenSSL FIPS module is commonly used as the basis for rebranded
proprietary validations (we call these "private label" validations).
Any such private label validations will have this same bug, and thus
an assurance that Dual EC DRBG is not being used, *unless* the vendor
detected and corrected the bug beforehand without notifying us. Or
removed the additional input supplied by the "FIPS capable" OpenSSL,
which would eliminate fork protection (we have also determined that
a workaround in the "FIPS capable" OpenSSL that retains fork
protection is possible, but we don't plan to implement it).
How can I reproduce the bug?
- ---------------------------
First enable the Dual EC DRBG as default in the "FIPS capable" OpenSSL
1.0.1:
./config fips -DOPENSSL_DRBG_DEFAULT_TYPE=0x19f02a0 \
-DOPENSSL_DRBG_DEFAULT_FLAGS=0 -DOPENSSL_ALLOW_DUAL_EC_DRBG
Note this rather complex incantation[4] demonstrates that one cannot
accidentally enable the Dual EC DRBG as the default.
The bug is then manifested by:
OPENSSL_FIPS=1 apps/openssl sha1 README
which will exhibit Dual EC DRBG stuck errors. Apply the above patch
to the FIPS module, rebuild and reinstall the module, recompile the
FIPS capable OpenSSL and the bug will no longer be present.
Why did we implement Dual EC DRBG in the first place?
- ----------------------------------------------------
It was requested by a sponsor as one of several deliverables. The
reasoning at the time (my reasoning and call as the project manager)
was that we would implement any algorithm based on official published
standards. SP800-90A is a more or less mandatory part of FIPS 140-2,
for any module of non-trivial complexity. FIPS 140-2 validations are
expensive and difficult, taking on average a year to complete and we
have to wait years between validations. So, there is an incentive to
pack as much as possible into each validation and our sponsors (dozens
of them) had a long list of requirements they were willing to fund.
We knew at the time (this was the pre-Snowden era) that Dual EC DRBG
had a dubious reputation, but it was part of an official standard (one
of the four DRBGs in SP800-90A) and OpenSSL is after all a comprehensive
cryptographic library and toolkit. As such it implements many algorithms
of varying strength and utility, from worthless to robust. We of course
did not enable Dual EC DRBG by default, and the discovery of this bug
demonstrates that no one has even attempted to use it.
Where did our implementation come from?
- --------------------------------------
The client requirement was simply "Implement all of SP800-90A". Our code
was implemented solely from that standard.
Did we have any discretion in how Dual EC DRBG was implemented?
- --------------------------------------------------------------
No. We did specifically ask the accredited test lab if we had any
discretion at all in the choice of points (the written standard isn't
entirely clear), and were told that we were required to use the
compromised points.
SP800-90A allows implementers to either use a set of compromised points
or to generate their own. What almost all commentators have missed is
that hidden away in the small print (and subsequently confirmed by our
specific query) is that if you want to be FIPS 140-2 compliant you MUST
use the compromised points. Several official statements including the
NIST recommendation don't mention this at all and give the impression
that alternative uncompromised points can be generated and used.
Why wasn't this bug caught in the FIPS 140-2 validation testing?
- ---------------------------------------------------------------
Not only the original validation (#1747) but many subsequent validations
and platforms have successfully passed the CAVP[5] algorithm tests ...
several hundred times now. That's a lot of fail.
In test mode the implementation works fine both with and without
additional data. In free running mode the bug is triggered by additional
data on the first call, which is done automatically by the "FIPS capable"
OpenSSL.
Frankly the FIPS 140-2 validation testing isn't very useful for catching
"real world" problems.
Could we have coded the test better?
- -----------------------------------
Outside of test mode the first PRNG block generated is discarded and so
the output would not agree with the algorithm tests. So in the artificial
environment of the FIPS algorithm tests we did have to use the test mode.
There are several ways to implement the continuous PRNG test. These were
discussed with test labs quite extensively as we had prior unfortunate
experiences with a continuous PRNG implementation in an earlier
validation that resulted in effective revocation of that validation. In
principle we could have tried a new and better approach, but the CMVP
process abhors novelty of any kind so we were strongly motivated to stick
with what has been accepted in the past.
[1] NIST "SUPPLEMENTAL ITL BULLETIN FOR SEPTEMBER 2013"
(http://csrc.nist.gov/publications/nistbul/itlbul2013_09_supplemental.pdf)
[2] The Cryptographic Module Validation Program, one of the two
bureaucracies responsible for FIPS 140-2 validations.
[3] Matt Green, private communication.
[4] The 0x19f02a0 comes from the type parameter documented in
Section 6.1 of the OpenSSL FIPS Object Module User Guide
(http://www.openssl.org/docs/fips/UserGuide-2.0.pdf), which for P-256
using SHA256 translates to 0x19f02a0.
[5] The Cryptographic Algorithm Validation Program, one of the two
bureaucracies responsible for FIPS 140-2 validations.
- --
Steve Marquess
OpenSSL Software Foundation, Inc.
1829 Mount Ephraim Road
Adamstown, MD 21710
USA
+1 877 673 6775 s/b
+1 301 874 2571 direct
marquess@opensslfoundation.com
marquess@openssl.com
gpg/pgp key: http://openssl.com/docs/0xCE69424E.asc
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/
iEYEARECAAYFAlKy/dMACgkQJBALAc5pQk7gpgCgzY51VkO8MMxOccRMlm24MJW3
8hIAn2ciEcUR30TwTEcAlbDUUxCk7Uq+
=6INf
-----END PGP SIGNATURE-----
[Attachment #3 (text/html)]
<html>
<head>
<meta http-equiv="content-type" content="text/html;
charset=ISO-8859-1">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<br>
-----BEGIN PGP SIGNED MESSAGE-----<br>
Hash: SHA1<br>
<br>
This is an unusual bug report for an unusual situation. I'm using it<br>
as an opportunity to point out some considerations that have not
been<br>
widely reported.<br>
<br>
Summary:<br>
- -------<br>
<br>
Stephen Checkoway and Matt Green of the Johns Hopkins University<br>
Information Security Institute discovered a fatal bug in the Dual EC<br>
DRBG implemention in the OpenSSL FIPS Object Module v2.0. This bug
is<br>
fatal in the sense that it prevents all use of the Dual EC DRBG<br>
algorithm.<br>
<br>
Note the bug is present in the Dual EC DRBG only, no other DRBG<br>
types are affected.<br>
<br>
The nature of the bug shows that no one has been using the OpenSSL<br>
Dual EC DRBG.<br>
<br>
Given the current status of Dual EC DRBG (now disowned[1] by the
NIST<br>
CMVP[2] and pretty much toxic for any purpose) we do not plan to<br>
correct the bug. A FIPS 140-2 validated module cannot be changed<br>
without considerable expense and effort, and we have recently<br>
commenced that process of entirely removing the Dual EC DRBG code<br>
from the formally validated module.<br>
<br>
What is the bug?<br>
- ---------------<br>
<br>
When a PRNG is in free running mode it has to continuously check
that<br>
each block of output doesn't match the previous one (the so called<br>
"continuous PRNG test").<br>
<br>
If there is no previous block (as is the case on the very first
call)<br>
then a block has to be generated, stored as the "previous block" and<br>
discarded. The output of the PRNG that the application sees is the<br>
**next* *block which is now compared with the previous block.<br>
<br>
It's this discarding part where the bug occurs: when the discard is<br>
done the code places the output into a buffer and updates the Dual<br>
EC DRBG state. When the discard occurs the data must not be output<br>
and the Dual EC DRBG state must be updated, but that state update<br>
isn't done. In the case of no additional input this has no effect,<br>
but additional input is used by the "FIPS capable" OpenSSL. Note<br>
that additional input does *not* effectively defeat the backdoor<br>
vulnerability[3].<br>
<br>
Will it be fixed?<br>
- ----------------<br>
<br>
We have no plans to fix this bug, as NIST has disowned Dual EC<br>
DRBG in an official NIST Recommendation<br>
(<a class="moz-txt-link-freetext" \
href="http://csrc.nist.gov/publications/nistbul/itlbul2013_09_supplemental.pdf">http:/ \
/csrc.nist.gov/publications/nistbul/itlbul2013_09_supplemental.pdf</a>)<br> and use \
of Dual EC DRBG is already disabled in upcoming OpenSSL<br> releases.<br>
<br>
Even if we wanted to fix it our options are severely constrained by<br>
the fact that the CMVP process forbids modifications of any<br>
kind (even to address severe vulnerabilities) without the
substantial<br>
time and expense of formal retesting and review.<br>
<br>
Is there a patch?<br>
- ----------------<br>
<br>
Of course:<br>
<br>
diff --git a/fips/rand/fips_drbg_ec.c b/fips/rand/fips_drbg_ec.c<br>
index 6be6534..270cfbb 100644<br>
- --- a/fips/rand/fips_drbg_ec.c<br>
+++ b/fips/rand/fips_drbg_ec.c<br>
@@ -328,6 +328,7 @@ static int drbg_ec_generate(DRBG_CTX *dctx,<br>
if \
(!bn2binpad(dctx->lb, dctx->blocklength, r))<br> \
&n \
bsp; goto err;<br> \
\
dctx->lb_valid = 1;<br> \
+ t = s;<br> \
\
continue;<br>   \
; }<br> if (outlen < \
dctx->blocklength)<br> <br>
This patch is of academic interest only as *any* modification to the<br>
official FIPS module source code distribution means that the result<br>
isn't validated and is not suitable for any context requiring a FIPS<br>
140-2 validated module.<br>
<br>
The OpenSSL FIPS module is commonly used as the basis for rebranded<br>
proprietary validations (we call these "private label" validations).<br>
Any such private label validations will have this same bug, and thus<br>
an assurance that Dual EC DRBG is not being used, *unless* the
vendor<br>
detected and corrected the bug beforehand without notifying us. Or<br>
removed the additional input supplied by the "FIPS capable" OpenSSL,<br>
which would eliminate fork protection (we have also determined that<br>
a workaround in the "FIPS capable" OpenSSL that retains fork<br>
protection is possible, but we don't plan to implement it).<br>
<br>
How can I reproduce the bug?<br>
- ---------------------------<br>
<br>
First enable the Dual EC DRBG as default in the "FIPS capable"
OpenSSL<br>
1.0.1:<br>
<br>
./config fips -DOPENSSL_DRBG_DEFAULT_TYPE=0x19f02a0 \<br>
-DOPENSSL_DRBG_DEFAULT_FLAGS=0 \
-DOPENSSL_ALLOW_DUAL_EC_DRBG<br> <br>
Note this rather complex incantation[4] demonstrates that one cannot<br>
accidentally enable the Dual EC DRBG as the default.<br>
<br>
The bug is then manifested by:<br>
<br>
OPENSSL_FIPS=1 apps/openssl sha1 README<br>
<br>
which will exhibit Dual EC DRBG stuck errors. Apply the above patch<br>
to the FIPS module, rebuild and reinstall the module, recompile the<br>
FIPS capable OpenSSL and the bug will no longer be present.<br>
<br>
Why did we implement Dual EC DRBG in the first place?<br>
- ----------------------------------------------------<br>
<br>
It was requested by a sponsor as one of several deliverables. The<br>
reasoning at the time (my reasoning and call as the project manager)<br>
was that we would implement any algorithm based on official
published<br>
standards. SP800-90A is a more or less mandatory part of FIPS 140-2,<br>
for any module of non-trivial complexity. FIPS 140-2 validations are<br>
expensive and difficult, taking on average a year to complete and we<br>
have to wait years between validations. So, there is an incentive to<br>
pack as much as possible into each validation and our sponsors
(dozens<br>
of them) had a long list of requirements they were willing to fund.<br>
<br>
We knew at the time (this was the pre-Snowden era) that Dual EC DRBG<br>
had a dubious reputation, but it was part of an official standard
(one<br>
of the four DRBGs in SP800-90A) and OpenSSL is after all a
comprehensive<br>
cryptographic library and toolkit. As such it implements many
algorithms<br>
of varying strength and utility, from worthless to robust. We of
course<br>
did not enable Dual EC DRBG by default, and the discovery of this
bug<br>
demonstrates that no one has even attempted to use it.<br>
<br>
Where did our implementation come from?<br>
- --------------------------------------<br>
<br>
The client requirement was simply "Implement all of SP800-90A". Our
code<br>
was implemented solely from that standard.<br>
<br>
Did we have any discretion in how Dual EC DRBG was implemented?<br>
- --------------------------------------------------------------<br>
<br>
No. We did specifically ask the accredited test lab if we had any<br>
discretion at all in the choice of points (the written standard
isn't<br>
entirely clear), and were told that we were required to use the<br>
compromised points.<br>
<br>
SP800-90A allows implementers to either use a set of compromised
points<br>
or to generate their own. What almost all commentators have missed
is<br>
that hidden away in the small print (and subsequently confirmed by
our<br>
specific query) is that if you want to be FIPS 140-2 compliant you
MUST<br>
use the compromised points. Several official statements including
the<br>
NIST recommendation don't mention this at all and give the
impression<br>
that alternative uncompromised points can be generated and used.<br>
<br>
Why wasn't this bug caught in the FIPS 140-2 validation testing?<br>
- ---------------------------------------------------------------<br>
<br>
Not only the original validation (#1747) but many subsequent
validations<br>
and platforms have successfully passed the CAVP[5] algorithm tests
...<br>
several hundred times now. That's a lot of fail.<br>
<br>
In test mode the implementation works fine both with and without<br>
additional data. In free running mode the bug is triggered by
additional<br>
data on the first call, which is done automatically by the "FIPS
capable"<br>
OpenSSL.<br>
<br>
Frankly the FIPS 140-2 validation testing isn't very useful for
catching<br>
"real world" problems.<br>
<br>
Could we have coded the test better?<br>
- -----------------------------------<br>
<br>
Outside of test mode the first PRNG block generated is discarded and
so<br>
the output would not agree with the algorithm tests. So in the
artificial<br>
environment of the FIPS algorithm tests we did have to use the test
mode.<br>
<br>
There are several ways to implement the continuous PRNG test. These
were<br>
discussed with test labs quite extensively as we had prior
unfortunate<br>
experiences with a continuous PRNG implementation in an earlier<br>
validation that resulted in effective revocation of that validation.
In<br>
principle we could have tried a new and better approach, but the
CMVP<br>
process abhors novelty of any kind so we were strongly motivated to
stick<br>
with what has been accepted in the past.<br>
<br>
<br>
[1] NIST "SUPPLEMENTAL ITL BULLETIN FOR SEPTEMBER 2013"<br>
(<a class="moz-txt-link-freetext" \
href="http://csrc.nist.gov/publications/nistbul/itlbul2013_09_supplemental.pdf">http:/ \
/csrc.nist.gov/publications/nistbul/itlbul2013_09_supplemental.pdf</a>)<br> <br>
[2] The Cryptographic Module Validation Program, one of the two<br>
bureaucracies responsible for FIPS 140-2 validations.<br>
<br>
[3] Matt Green, private communication.<br>
<br>
[4] The 0x19f02a0 comes from the type parameter documented in<br>
Section 6.1 of the OpenSSL FIPS Object Module User Guide<br>
(<a class="moz-txt-link-freetext" \
href="http://www.openssl.org/docs/fips/UserGuide-2.0.pdf">http://www.openssl.org/docs/ \
fips/UserGuide-2.0.pdf</a>), which for P-256<br>
using SHA256 translates to 0x19f02a0.<br>
<br>
[5] The Cryptographic Algorithm Validation Program, one of the two<br>
bureaucracies responsible for FIPS 140-2 validations.<br>
<br>
<br>
- -- <br>
Steve Marquess<br>
OpenSSL Software Foundation, Inc.<br>
1829 Mount Ephraim Road<br>
Adamstown, MD 21710<br>
USA<br>
+1 877 673 6775 s/b<br>
+1 301 874 2571 direct<br>
<a class="moz-txt-link-abbreviated" \
href="mailto:marquess@opensslfoundation.com">marquess@opensslfoundation.com</a><br> \
<a class="moz-txt-link-abbreviated" \
href="mailto:marquess@openssl.com">marquess@openssl.com</a><br> gpg/pgp key: <a \
class="moz-txt-link-freetext" \
href="http://openssl.com/docs/0xCE69424E.asc">http://openssl.com/docs/0xCE69424E.asc</ \
a><br> <br>
-----BEGIN PGP SIGNATURE-----<br>
Version: GnuPG v1.4.11 (GNU/Linux)<br>
Comment: Using GnuPG with Thunderbird - <a class="moz-txt-link-freetext" \
href="http://www.enigmail.net/">http://www.enigmail.net/</a><br> <br>
iEYEARECAAYFAlKy/dMACgkQJBALAc5pQk7gpgCgzY51VkO8MMxOccRMlm24MJW3<br>
8hIAn2ciEcUR30TwTEcAlbDUUxCk7Uq+<br>
=6INf<br>
-----END PGP SIGNATURE-----<br>
<br>
</body>
</html>
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Announcement Mailing List openssl-announce@openssl.org
Automated List Manager majordomo@openssl.org
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic