|
|
Home | Switchboard | Unix Administration | Red Hat | TCP/IP Networks | Neoliberalism | Toxic Managers |
| (slightly skeptical) Educational society promoting "Back to basics" movement against IT overcomplexity and bastardization of classic Unix | |||||||
Dual_Ec_Drbg backdoor: a proof of concept
31/12/13 - 01:51pm
Dual_EC_DRBG is an pseudo-random number generator promoted by NIST in NIST SP 800-90A and created by NSA. This algorithm is problematic because it has been made mandatory by the FIPS norm (and should be implemented in every FIPS approved software) and some vendors even promoted this algorithm as first source of randomness in their applications. edit: I’ve been told it’s not the case anymore in FIPS-140-2 but the cat is already out of the bag
If you still believe Dual_EC_DRBG was not backdoored on purpose, please keep
reading.
In 2007 already, Dan Shumow and Niels Ferguson from Microsoft
showed that Dual_EC_DRBG
algorithm could be backdoored. Twitter also uncovered recently that this
algorithm was even
patented in 2004 by Dan Brown (Not the Da Vinci guy, the Certicom one) as a
“key escrow mechanism” (government jargon/lingo for trapdoor/backdoor).
I will go a little bit further in explaining how it works and give a
proof-of-concept code, based on OpenSSL FIPS. This is in the best of my
knowledge the only public proof of concept published today. (correct me if I’m
wrong).
The PRNG works as following: it takes a seed that goes through a hashing algorithm. This data is then “fed” into two Elliptic Curve points, P and Q, before being slightly transformed and output.
In order to understand how the algorithm (and the backdoor) works, let’s see the relevant maths from Elliptic Curves:
Many types of elliptic curves exist. They are classified in function of their properties and equations. We’re going to see here the curve NIST-p256 which is one of the three curves being used by Dual_EC_DRBG. NIST-p384 and NIST-p521 have very similar characteristics. I’ll try to (poorly) give you the basic theoretics for EC, but I’m no mathematician. Please forgive me and correct me if I’m wrong.
A curve is a set of points that follow a group structure. The curve is defined over several parameters (for NIST GFp curves):
Curve members are points. A point is a pair of coordinates X and Y that satisfy the curve’s equation. They are written as capital letters such as G, P or Q. Points have some characteristics from groups:
The group of Elliptic Curves is very useful in cryptography, because an equation such as iQ = P is very easy to resolve for Q or P (if you know i) but very hard to resolve for i (if all you know is P and Q). This is the Discrete logarithm problem in the EC group. That’s why most of the time the points are used as public parameters/keys and scalars as private counterparts.
All NIST curves have different parameters p, r, a, b and points G. These parameters have been constructed from a sha1 hash of a public seed but nobody knows how the seed itself has been chosen.
Enough on the theory, let’s study the PRNG !
Dual_EC_DRBG is defined in NIST
SP800-90A page 60. It is an algorithm generating an infinite number of
pseudo-random sequences from a single seed, taken in the first step or after an
explicit reseed.
It is unfortunate that SP800-90A and the presentation from Microsoft use
conflicting terminology (variable names). So I will use these variables:
:
Internal seed value.
:
External (output) value.
You can also see in the document two functions:
and
.
is a function that does a mapping between a large integer and binary data. It
doesn’t do much, in fact we can happily ignore it.
simply gets the X coordinate of a point, as the X and Y coordinates are mostly
redundant (as we’re going to see later). If we unroll the inductive feedback
loop on the first two generated outputs, we get this:
output(30 least significant bytes of
)
output(30 least significant bytes of
)
Let’s begin working on
and look if we can guess
from its content. We can see that
is the X coordinate of a point, with 16 bits missing (we lost the 2 most
significant bytes in the output process). In a NIST GFp curve, There are for
every value of X, zero, one or two points on the curve. So we have at most 17
bits of bruteforce to do to recover the original point A. Let’s work on the
hypothesis that we know the point A and it is equal (by definition) to A =
.
Then the equation:
but if we have a (secret) relation between P and Q such as
with d = secret number (our backdoor !):
multiplicating each side by d
(replacing dQ with P)
If you look carefully at the unrolled algorithm, you will notice that if we
know
we can calculate
and we have all the required information to calculate subsequent
and
.
All we need to do is to guess a value of A (based on a bruteforce approach),
multiply it by the secret value d, then multiply the resulting scalar
with Q, strip two bytes and publish the output. It is also very interesting that
if we learn (in a practical attack) the first 32 bytes generated by this PRNG,
the 30 first bytes give us candidates for A and the remaining two bytes can be
used to validate our findings. If the X value had been output on 32 bytes, we
would have an one over two chance of success because of the two coexisting
points on same coordinate X. (Remember from high school, second degree equations
can have two solutions).
As you have seen before, for our backdoor to work we need to choose the P and Q points in order to have the secret key to the backdoor. We have chosen to define P = dQ, however, that can’t work, because P is a generator for the EC group and its value has already been fixed. So, we have to find a value e such as Q = eP. This value can be calculated :
(mult. by e)
We need to find a value e such as ed = 1 for the curve C. The
equation to resolve is
where r is the order of the EC.
The value of e is the inverse of d modulo
r. We can
then use that value to generate Q.
/* 256 bits value randomly generated */ unsigned char d[]= "\x75\x91\x67\x64\xbe\x30\xbe\x85\xd1\x50\x09\x19\x50\x8a\xf4\xb5" "\x7a\xc7\x09\x22\x07\x32\xae\x40\xac\x3e\xd5\xfe\x2e\x12\x25\x2a"; d_bn = BN_new(); assert(d_bn != NULL); BN_bin2bn(d, 32, d_bn); /* ensure d is well inside the group order */ EC_GROUP_get_order(curve, r, bn_ctx); BN_mod(d_bn, d_bn, r, bn_ctx); /* calculate Q = d * Generator + (NULL * NULL) */ ret = EC_POINT_mul(curve, my_Q, d_bn, NULL, NULL, bn_ctx); assert(ret == 1); /* calculate e = d^-1 (mod r) */ e_bn = BN_new(); assert(e_bn != NULL); /* invert d to get the value of e */ assert(NULL != BN_mod_inverse(e_bn, d_bn, r, bn_ctx));
(note: I know I mixed up e with d between the code and blog post but that doesn’t change anything at all.)
You can find the proof of concept code on my github. I’ll comment how it works:
Most of the work needed for this POC actually was fighting with OpenSSL FIPS mode (getting it to compile at first) and finding the good APIs to use. OpenSSL FIPS and OpenSSL are two different software that share some codebase. I had to fetch a specific commit of OpenSSL FIPS (one that would compile) and patch it a little to have a few functions from Bignums usable from inside my application. I haven’t been able to mix FIPS and regular libcrypto, because of header incompatibilities (or a bug in my code I though was caused by incompatibilities). The README explains the steps to take (please read it).
If you remember, we have the 30 least significant bytes of the X coordinate,
that means we need to bruteforce our way into A point candidates. This can be
easily done in a loop over the 2^16 possibilities. OpenSSL doesn’t provide any
way of recovering a point from a single coordinate (there exists a point
compression algorithm, but it is so badly patented that it’s not implemented
anywhere). We have to resolve the curve’s equation:
Resolving such an equation for
y is not so different from the equation
resolving you learned at high school:
for (prefix = 0; prefix <= 0x10000 ; ++prefix){ x_bin[0] = prefix >> 8; x_bin[1] = prefix & 0xff; BN_bin2bn(x_bin, 32, x_value); //bnprint("X value", x_value); /* try to find y such as */ /* y^2 = x^3 - 3x + b (mod p) */ /* tmp1 = x^2 */ ret = BN_mod_mul(tmp1, x_value, x_value, &curve->field, bn_ctx); assert(ret == 1); ret = BN_set_word(tmp2, 3); assert(ret == 1); /* tmp1 = x^2 - 3 */ ret = BN_mod_sub(tmp1, tmp1, tmp2, &curve->field, bn_ctx); assert(ret == 1); /* tmp1 = (x^2 -3) * x */ ret = BN_mod_mul(tmp1, x_value, tmp1, &curve->field, bn_ctx); assert(ret == 1); /* tmp1 = x^3 - 3x + b */ ret = BN_mod_add(tmp1, tmp1, b_bn, &curve->field, bn_ctx); assert(ret == 1); //bnprint("Y squared", tmp1); if (NULL != BN_mod_sqrt(y_value, tmp1, &curve->field, bn_ctx)) { //printf("value %x match !\n", prefix); if(verbose) bnprint("calculated Y", y_value); BN_mod_sub(y_value, zero_value, y_value, &curve->field, bn_ctx); if(verbose) bnprint("calculated Y opposite", y_value); test_candidate(buffer + 30, x_value, y_value, bn_ctx); valid_points += 2; } }
I mentioned that for every X, there were zero, one or two solutions: zero if
the square root fails (not all elements of Z/pZ are quadratic residues), one if
the result is 0 and two for all other answers. There are then two valid points
and
where
is the opposite of the first value modulo p. Explanation (thanks Rod):
This part is pretty straightforward. We import the estimated x and y values, verify that they are in the curve (they should !), then multiply that point with the secret value. We then multiply Q with the resulting scalar and we get 30 bytes of the next output. If the two first bytes match, we have successfully guessed the 28 remaining bytes. That attack can recover everything that’s output by that PRNG till a reseed.
/* create the point A based on calculated coordinates x and y */ ret = EC_POINT_set_affine_coordinates_GFp(curve, point, x, y, bn_ctx); assert(ret == 1); /* Normally the point should be on curve but we never know */ if (!EC_POINT_is_on_curve(curve, point, bn_ctx)) goto end; /* calculates i2 = phi(x(e.A)) */ ret = EC_POINT_mul(curve, point, NULL, point, e_bn, bn_ctx); assert(ret ==1); ret = EC_POINT_get_affine_coordinates_GFp(curve, point, i2x, NULL, bn_ctx); assert(ret ==1); if(verbose) bnprint ("i2_x", i2x); /* calculate o1 = phi(x(i2 * Q)) */ ret = EC_POINT_mul(curve, point, NULL, my_Q, i2x, bn_ctx); assert(ret == 1); ret = EC_POINT_get_affine_coordinates_GFp(curve, point, o1x, NULL, bn_ctx); if(verbose) bnprint ("o1_x", o1x); BN_bn2bin(o1x, o1x_bin); if (o1x_bin[2] == buffer[0] && o1x_bin[3] == buffer[1]){ printf("Found a match !\n"); bnprint("A_x", x); bnprint("A_y", y); print_hex("prediction", o1x_bin + 4, 28); }
aris@kalix86:~/dualec$ ./dual_ec_drbg_poc
s at start of generate:
E9B8FBCFCDC7BCB091D14A41A95AD68966AC18879ECC27519403B34231916485
[omitted: many output from openssl]
y coordinate at end of mul:
0663BC78276A258D2F422BE407F881AA51B8D2D82ECE31481DB69DFBC6C4D010
r in generate is:
96E8EBC0D507C39F3B5ED8C96E789CC3E6861E1DDFB9D4170D3D5FF68E242437
Random bits written:
000000000000000000000000000000000000000000000000000000000000
y coordinate at end of mul:
5F49D75753F59EA996774DD75E17D730051F93F6C4EB65951DED75A8FCD5D429
s in generate:
C64EAF10729061418EB280CCB288AD9D14707E005655FDD2277FC76EC173125E
[omitted: many output from openssl]
PRNG output: ebc0d507c39f3b5ed8c96e789cc3e6861e1ddfb9d4170d3d5ff68e242437449e
Found a match !
A_x: 96e8ebc0d507c39f3b5ed8c96e789cc3e6861e1ddfb9d4170d3d5ff68e242437
A_y: 0663bc78276a258d2f422be407f881aa51b8d2d82ece31481db69dfbc6c4d010
prediction: a3cbc223507c197ec2598e6cff61cab0d75f89a68ccffcb7097c09d3
Reviewed 65502 valid points (candidates for A)
PRNG output: a3cbc223507c197ec2598e6cff61cab0d75f89a68ccffcb7097c09d3
Yikes !
It is quite obvious in light of the recent revelations from Snowden that this weakness was introduced by purpose by the NSA. It is very elegant and leaks its complete internal state in only 32 bytes of output, which is very impressive knowing it takes 32 bytes of input as a seed. It is obviously complete madness to use the reference implementation from NIST and I’m not the only one to be angry about it. You could use it with custom P and Q values, but that’s very seldom possible. Nevertheless having a whole EC point parameter leaked in the output makes it too easy to distinguish from real random and should never have been made into any specs at all. Let’s all bury that PRNG and the “security” companies bribed by NSA to enable backdoors by default for thirty silver coins.
edits: fixed Dan Brown’s employer name, changed a variable name to avoid
confusion, fixed counting error 28 bytes to 30 bytes
note: I did
not break the official algorithm. I do not know
the secret value used to compute the Q constant, and thus cannot break the
default implementation. Only NSA (and people with access to the key) can exploit
the PRNG weakness.
Category: security | Tags:
← The war against autocomplete=off: let my browser remember passwords !
Dual_Ec_Drbg backdoor a proof of concept at Aris' Blog - Computers, ssh and rock'n roll
However, using your own Q and P parameters is patented, so you’re not allowed to do that..
Well Done, Aris. Happy New Year . Phi²
Do you know that the link to your blog is being blocked by Facebook? We found out today when trying to share it. Google+ is cool with it. Very strange.
Awesome work! A pleasure to read!
Victor: bad news
try http://www.badcode.be/ instead, it redirects here.
Victor. I can confirm this. They’re refusing to give a preview of it and so I haven’t yet submitted it. I suspect when I do I’m going to get an error message.
I got the error message
I wrote a little request in the feedback form but have little hope that
it works.
Also confirmed, had to type www badcode be to get it past facebook’s filter.
It appears to work through donotlink.com, but through tinyurl it is now being blocked (it was not at first…). The plot thickens.
Facebook even tell me now that my email address is invalid and I have to change it. it seems convinced that my domain name is malicious
Facebook blocks url shortners. I’ve made a 301 redirect with a subdomain to your site and posted it on Facebook. This works, but for how long?
After 5 minutes, my subdomain was also blocked by Facebook.
I think the best you can do is to post the link to the slashdot article http://it.slashdot.org/story/14/01/01/1830238/dualecdrbg-backdoor-a-proof-of-concept
