Quantcast

Flaw in Dual EC DRBG (no, not that one)

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Flaw in Dual EC DRBG (no, not that one)

Steve Marquess-3

-----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
[hidden email]
[hidden email]
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-----

Loading...