6 ms·

Dual_EC_DRBG backdoor: a proof of concept

175 points by infinity 13y ago

nwh 13y ago
Site seems sluggish, here's a mirror — http://archive.is/On8jE http://archive.is/On8jE
- atmosx 13y ago
  Thanks
KwanEsq 13y ago
I'm confused how this is valid, since he seems to be using the OpenSSL code without the patch[1] that actually makes Dual EC work and his patch doesn't (to my C-ignorant eyes) include the fix either. Does it fix it in another way? [1] http://marc.info/?l=openssl-announce&m=138747119822324&w=2&x=1 http://marc.info/?l=openssl-announce&m=138747119822324&w=2&x... [2] Discussion: https://news.ycombinator.com/item?id=6949652 https://news.ycombinator.com/item?id=6949652
- timtadh 13y ago
  perhaps it is related to this point, since that bug causes the algorithm to get "stuck". 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.
  - aris_ada 13y ago
    Honestly I don't know why. I generate 60 bytes of pseudorandom and that worked on first try.
    - rsync 13y ago
      My understanding thus far has been that openssl has gotten a pass because their implementation was always broken ... so nobody was at risk. Has that changed ?
      - aris_ada 13y ago
        No, they plan on removing the PRNG from their release. I understand better why my POC worked without triggering the bug. From the mail archive: ". 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]." I do not use the reseed functionality either, because I only generate two or three output blocs and never call an explicit reseed.
StavrosK 13y ago
"An hashing algorithm"? That struck me as odd, is this valid in any accent other than Cockney? EDIT: Oh, he's a fellow Greek. That explains that.
- X-Istence 13y ago
  "an hashing algorithm" is also valid as a way to say "one hashing algorithm". I find myself adding a "n" to "a" quite a bit since a lot of times it seems to flow better than using "a".
  - StavrosK 13y ago
    Only if you don't pronounce the "h", which is pretty nonstandard.
    - DougBTX 13y ago
      "An" can also be used if the first letter is an h and the first syllable is unstressed (an historical event is the example on the Wikipedia page), but, I'm pretty sure the h in hashing is in a stressed syllable, so that doesn't count either.
- badman_ting 13y ago
  Thanks for posting!
- asveikau 13y ago
  Reminds me of some native English speakers who say "an historic ..." Pretty common even in accents that won't drop the H. Seems like that word is an outlier though.
  - StavrosK 13y ago
    That's true, but the "h" there is followed by an "i", which sounds more natural. Omitting it in "ha" sounds odder, but it looks like it's just a typo.
- 13y ago
flyryan 13y ago
"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." I found this note interesting. How big is the secret value used to compute the Q constant? Is it a single static value or does it vary? Would it be possible to brute force this? I'm not a crypto expert and want to understand this a bit better. One of the big arguments about the NSA introducing weaknesses into these algorithms is "this makes them insecure for everyone and flaws exploited by the government could be exploited by anyone", but this makes it sound like ONLY the NSA could exploit this. I'm not saying this is better. I just think, if true, it's an interesting discussion point in the debate. [Cross-posted and answered at /r/netsec]: http://www.reddit.com/r/netsec/comments/1u5jvw/dual_ec_drbg_backdoor_proof_of_concept/ceevcet http://www.reddit.com/r/netsec/comments/1u5jvw/dual_ec_drbg_...
- dangero 13y ago
  Right. I think the big issue is that we are one NSA key leak away from breaking every product that uses this type of encryption. It introduces a single point of failure.
  - andreyf 13y ago
    Can't you say the same thing about SSL keys? One leak away and every gmail account can be MITM'd.
    - klausa 13y ago
      SSL certificates can be revoked.
      - csandreasen 13y ago
        and the Dual_EC_DRBG specs allow for the user to supply their own values for P and Q (much like the author did). NSA only provides the default.
pbsd 13y ago
Here's an example in Sage, if the verbosity of OpenSSL code annoys you as much as it does me: n = 115792089210356248762697446949407573529996955224135760342422259061068512044369 p = 2^256 - 2^224 + 2^192 + 2^96 - 1 a = -3 b = 41058363725152142129326129780047268409114441015993725554835256314039467401291 E = EllipticCurve(GF(p), [a,b]) P = E(48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109) """ Q = E(91120319633256209954638481795610364441930342474826146651283703640232629993874, 80764272623998874743522585409326200078679332703816718187804498579075161456710) """ e = 0x12345678 ei = inverse_mod(e, n) Q = e*P def to_bin(x): return ("%060x" % x).decode('hex') def from_bin(x): return int(x.encode('hex'), 16) def dual_ec_drbg(s, len): out = '' for i in range(0, len, 30): x, y = (s*P).xy() s = Integer(x) x, y = (s*Q).xy() r = Integer(x) % 2**240 out += to_bin(r) return out[0:len] def recover_s(s0, s1): for i in range(2**16): # For all possible 256-bit x r = i*2**240 + s0 # if E.is_x_coord(r): # is valid x? R = E.lift_x(r) # Lift it to a point x, y = (R*ei).xy() # Undo s*Q s = Integer(x) x, y = (s*Q).xy() # Check if it matches next observed block if (Integer(x) % 2**240) == s1: return s # done return None import os # Get 3 blocks: 2 are for the break, the other to confirm prediction s = dual_ec_drbg(from_bin(os.urandom(16)), 30*3) s0 = from_bin(s[ 0:30]) s1 = from_bin(s[30:60]) s2 = from_bin(s[60:90]) # Recover internal state s = recover_s(s0, s1) # Now try predicting something t = dual_ec_drbg(s, 30) assert( from_bin(t) == s2 ) print "Done"

175 points by infinity 13y ago

nwh 13y ago

Site seems sluggish, here's a mirror — http://archive.is/On8jE http://archive.is/On8jE

atmosx 13y ago
Thanks

KwanEsq 13y ago

I'm confused how this is valid, since he seems to be using the OpenSSL code without the patch[1] that actually makes Dual EC work and his patch doesn't (to my C-ignorant eyes) include the fix either. Does it fix it in another way? [1] http://marc.info/?l=openssl-announce&m=138747119822324&w=2&x=1 http://marc.info/?l=openssl-announce&m=138747119822324&w=2&x... [2] Discussion: https://news.ycombinator.com/item?id=6949652 https://news.ycombinator.com/item?id=6949652

timtadh 13y ago
perhaps it is related to this point, since that bug causes the algorithm to get "stuck". 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.
- aris_ada 13y ago
  Honestly I don't know why. I generate 60 bytes of pseudorandom and that worked on first try.
  - rsync 13y ago
    My understanding thus far has been that openssl has gotten a pass because their implementation was always broken ... so nobody was at risk. Has that changed ?
    - aris_ada 13y ago
      No, they plan on removing the PRNG from their release. I understand better why my POC worked without triggering the bug. From the mail archive: ". 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]." I do not use the reseed functionality either, because I only generate two or three output blocs and never call an explicit reseed.

StavrosK 13y ago

"An hashing algorithm"? That struck me as odd, is this valid in any accent other than Cockney? EDIT: Oh, he's a fellow Greek. That explains that.

X-Istence 13y ago
"an hashing algorithm" is also valid as a way to say "one hashing algorithm". I find myself adding a "n" to "a" quite a bit since a lot of times it seems to flow better than using "a".
- StavrosK 13y ago
  Only if you don't pronounce the "h", which is pretty nonstandard.
  - DougBTX 13y ago
    "An" can also be used if the first letter is an h and the first syllable is unstressed (an historical event is the example on the Wikipedia page), but, I'm pretty sure the h in hashing is in a stressed syllable, so that doesn't count either.
badman_ting 13y ago
Thanks for posting!
asveikau 13y ago
Reminds me of some native English speakers who say "an historic ..." Pretty common even in accents that won't drop the H. Seems like that word is an outlier though.
- StavrosK 13y ago
  That's true, but the "h" there is followed by an "i", which sounds more natural. Omitting it in "ha" sounds odder, but it looks like it's just a typo.
13y ago

flyryan 13y ago

"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." I found this note interesting. How big is the secret value used to compute the Q constant? Is it a single static value or does it vary? Would it be possible to brute force this? I'm not a crypto expert and want to understand this a bit better. One of the big arguments about the NSA introducing weaknesses into these algorithms is "this makes them insecure for everyone and flaws exploited by the government could be exploited by anyone", but this makes it sound like ONLY the NSA could exploit this. I'm not saying this is better. I just think, if true, it's an interesting discussion point in the debate. [Cross-posted and answered at /r/netsec]: http://www.reddit.com/r/netsec/comments/1u5jvw/dual_ec_drbg_backdoor_proof_of_concept/ceevcet http://www.reddit.com/r/netsec/comments/1u5jvw/dual_ec_drbg_...

dangero 13y ago
Right. I think the big issue is that we are one NSA key leak away from breaking every product that uses this type of encryption. It introduces a single point of failure.
- andreyf 13y ago
  Can't you say the same thing about SSL keys? One leak away and every gmail account can be MITM'd.
  - klausa 13y ago
    SSL certificates can be revoked.
    - csandreasen 13y ago
      and the Dual_EC_DRBG specs allow for the user to supply their own values for P and Q (much like the author did). NSA only provides the default.

pbsd 13y ago

Here's an example in Sage, if the verbosity of OpenSSL code annoys you as much as it does me: n = 115792089210356248762697446949407573529996955224135760342422259061068512044369 p = 2^256 - 2^224 + 2^192 + 2^96 - 1 a = -3 b = 41058363725152142129326129780047268409114441015993725554835256314039467401291 E = EllipticCurve(GF(p), [a,b]) P = E(48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109) """ Q = E(91120319633256209954638481795610364441930342474826146651283703640232629993874, 80764272623998874743522585409326200078679332703816718187804498579075161456710) """ e = 0x12345678 ei = inverse_mod(e, n) Q = e*P def to_bin(x): return ("%060x" % x).decode('hex') def from_bin(x): return int(x.encode('hex'), 16) def dual_ec_drbg(s, len): out = '' for i in range(0, len, 30): x, y = (s*P).xy() s = Integer(x) x, y = (s*Q).xy() r = Integer(x) % 2**240 out += to_bin(r) return out[0:len] def recover_s(s0, s1): for i in range(2**16): # For all possible 256-bit x r = i*2**240 + s0 # if E.is_x_coord(r): # is valid x? R = E.lift_x(r) # Lift it to a point x, y = (R*ei).xy() # Undo s*Q s = Integer(x) x, y = (s*Q).xy() # Check if it matches next observed block if (Integer(x) % 2**240) == s1: return s # done return None import os # Get 3 blocks: 2 are for the break, the other to confirm prediction s = dual_ec_drbg(from_bin(os.urandom(16)), 30*3) s0 = from_bin(s[ 0:30]) s1 = from_bin(s[30:60]) s2 = from_bin(s[60:90]) # Recover internal state s = recover_s(s0, s1) # Now try predicting something t = dual_ec_drbg(s, 30) assert( from_bin(t) == s2 ) print "Done"