|
Vulnerability of the RNG ecosystem
Many organizations are involved in
designing, evaluating, standardizing, selecting, implementing, and deploying RNGs.
This ecosystem,
the entire design-through-deployment process
that eventually gives random numbers to users,
is a broader attack target than any particular RNG.
Papers analyzing the security of particular RNGs
do not answer the question of whether this ecosystem is secure.
This web page considers
an attack strategy against this ecosystem,
including several synergistic stages,
some of which do not appear to have been publicly considered before:
- Design: Construct a
PRNG that secretly contains a back door.
- Evaluation: Publish statements that the PRNG is secure;
if possible, publish statements that it is more secure than the alternatives.
This is important because public evaluation increases the probability of
standardization, selection, implementation, and deployment.
- Standardization:
Edit standards to include the PRNG.
This is important because standardization increases the probability of
selection, implementation, and deployment.
- Standardization maintenance:
Monitor changes to the PRNG standard,
and counteract changes that make the PRNG more difficult to exploit.
- Auxiliary standardization:
If necessary modify other standards, such as networking standards,
to make the PRNG easier to exploit.
- Selection, implementation, and deployment:
Modify cryptographic libraries to implement this PRNG,
at least as an option but preferably as default,
preferably with as many of the modifications as possible.
- Attack optimization:
Reduce the cost of computation required to exploit the back door,
through algorithmic improvements and
through influencing the way the PRNG is used in practice.
It is possible that
Dual EC
was part of a deliberate attack of this type.
Specifically,
each of the following events can be explained by such an attack:
- Design:
Shumow and Ferguson raised an alarm in 2007
regarding the ability of the Dual EC creators
to insert a back door into Dual EC.
News reports in 2013 appeared to confirm that
Dual EC had been
created by NSA with a back door.
- Evaluation:
Slides presented at a 2004
NIST workshop
claim that number-theoretic RNGs provide "increased assurance".
NIST SP800-90 contains
several positive statements regarding the security of Dual EC,
such as "The Dual_EC_DRBG is the only DRBG mechanism
in this Recommendation whose security is related to a hard problem in number theory."
- Standardization:
Dual EC has been
standardized
by ANSI, ISO, and NIST.
The standards were not withdrawn in response to
public objections to the security of Dual EC from the cryptographic community in 2006 and 2007.
- Standardization maintenance:
There was a change from the June 2006 NIST Dual EC standard
to the March 2007 NIST Dual EC standard.
This site reports new
security analysis from
Bernstein, Checkoway, Green, and Lange
with the following conclusions:
the claimed security benefit of this change
would also have been achieved by a simpler, faster change;
from an attacker's perspective,
the June 2006 standard contained
an obstacle to Dual EC exploitation in some circumstances;
the March 2007 standard removed this obstacle;
the simpler change would not have removed this obstacle.
- Auxiliary standardization:
New analysis from Checkoway, Fredrikson, Niederhagen, Everspaugh,
Green, Lange, Ristenpart, Bernstein, Maskiewicz, and Shacham
shows that the exploitability of Dual EC in TLS
depends on many TLS details.
A proposed "Extended Random" TLS extension coauthored by NSA
removes another obstacle
to exploiting Dual EC in TLS,
to the extent that the extension is used.
This site reports new security analysis from Bernstein and Lange
that does not support the claimed security benefit of this TLS extension.
- Selection, implementation, and deployment:
News reports in December 2013 indicated that NSA had paid RSA
to implement Dual EC in their security library and to make it the default.
- Attack optimization:
New analysis from Checkoway, Fredrikson, Niederhagen, Everspaugh,
Green, Lange, Ristenpart, Bernstein, Maskiewicz, and Shacham
shows that the computations required to exploit Dual EC are
considerably less expensive
than indicated by previous analyses.
These researchers demonstrate feasibility
of exploiting Dual EC in several TLS libraries.
This case study is intended to help support
followup analyses of ways to protect the ecosystem against attacks of this type.
For these analyses,
what matters is not determining whether any particular attacks have been carried out,
but rather understanding the attacks that can be carried out.
This site does not attempt to resolve questions such as
whether Dual EC was in fact created with a back door,
whether the March 2007 modification was in fact
intended to remove an obstacle to exploiting this back door,
or whether Extended Random was in fact
intended to remove another obstacle.
What matters is that the Dual EC designers
did have the option of secretly including a back door,
that the March 2007 modification removes an obstacle,
and that Extended Random removes another obstacle.
Of course,
security issues also arise for other cryptographic ecosystems,
and for the broader security ecosystem.
Authors of this "Vulnerability of the RNG ecosystem" page (alphabetical order)
Last modified: 2014.07.07
|