7 ms·

Looking more closely at this, the backdoor is almost certainly based on the back-doored random number generator, Dual_EC_DRBG, which is implemented as NIST SP 8

Looking more closely at this, the backdoor is almost certainly based on the back-doored random number generator, Dual_EC_DRBG, which is implemented as NIST SP 800-90A. From Wiki: >>> NIST SP 800-90A ("SP" stands for "special publication") is a publication by the National Institute of Standards and Technology with the title Recommendation for Random Number Generation Using Deterministic Random Bit Generators. The publication contains the specification for three allegedly cryptographically secure pseudorandom number generators for use in cryptography: Hash DRBG (based on hash functions), HMAC DRBG (based on HMAC), and CTR DRBG (based on block ciphers in counter mode). Earlier versions included a fourth generator, Dual_EC_DRBG (based on elliptic curve cryptography). Dual_EC_DRBG was later reported to probably contain a kleptographic backdoor inserted by the United States National Security Agency (NSA). From Cavium's NIST FIPS-140-2, Section 3.3 [1] Approved and Allowed Algorithms: The cryptographic module supports the following FIPS Approved algorithms. *SP800-90 CTR DRBG Deterministic random number generation 32 1: https://csrc.nist.gov/csrc/media/projects/cryptographic-module-validation-program/documents/security-policies/140sp1369.pdf https://csrc.nist.gov/csrc/media/projects/cryptographic-modu...

stephen_g 3y ago
That's a very specific module - one of Cavium's dozens and dozens of products. Hard to tell what it is, more information is needed.
- convivialdingo 3y ago
  Well, there's several Cavium devices that support the deprecated/back-doored Hash_DRBG. For example, these devices were validated for the completely appropriately named "SonicOS 6.2.5 for TZ, SM and NSA". Gotta appreciate the irony. Cavium CN7020 Hash DRBG Cavium CN7130 Hash DRBG Cavium Octeon Plus CN66XX Family Hash DRBG Cavium Octeon Plus CN68XX Family Hash DRBG I don't know if that's hardware support or just a software validation - but it's still interesting that they validated it. https://csrc.nist.gov/Projects/Cryptographic-Algorithm-Validation-Program/details?validation=3445 https://csrc.nist.gov/Projects/Cryptographic-Algorithm-Valid...
  - dfox 3y ago
    Except Hash_DRBG is neither deprecated nor backdoored. See NIST SP 800-90A Rev. 1 section 10.1.1.1 for description of the algorithm.
    - convivialdingo 3y ago
      Well, true.. the Hash_DRBG hashing algorithm remains. But it's rather likely that previous FIPS validations occurred utilizing the actual backdoored and deprecated algorithm as an input to the Hash_DRBG, rendering it's security properties suspect. In NIST SP 800-90A Rev. 1, the HASH_DRBG section has been significantly updated to that effect. For instance, Appendix E: (Informative) Revisions. Section 10: Section 10 now includes a link to the DRBG test vectors on the NIST website. Sections 10.1, 10.1.1 and 10.1.2 now include short discussions about selecting hash functions to support the DRBG's intended security strength. The Dual_EC_DRBG has been removed, and section numbers adjusted accordingly.
      - dfox 3y ago
        The backdoor in DualEC_DRBG only works if there is some way for the attacker to directly observe its outputs (eg. using that for IVs). If you use it as an inner CSPRNG that seeds other faster algorithms the backdoor is irrelevant, but well, such a construction is total nonsense that only ever makes sense in the FIPS certification framework (DualEC_DRBG is ridiculously slow and not meaningfully more secure than the other FIPS CSPRNGs). On the other hand, I have the feeling that if you instantiate Hash_DRBG with certain classes of insecure hash functions (think MD2) the mechanism that protects the construction from effects of birthday paradox makes it simpler to break the underlying hash function, but for this attack to work the underlying hash function have to be really bad and this attack is probably impractical even for instantiations with MD4, much less the SHA variants in the specification.
GuB-42 3y ago
Is there any proof that Dual_EC_DRBG is backdoored? All I know is that Dual_EC_DRBG can be backdoored. And there are indeed suspicions, it was known from the start that not only Dual_EC_DRBG could be backdoored, but that it was rather weak to begin with. So, how could it be adopted as a standard? Now it seems that everyone takes the backdoor as a given. Is there any proof? Ideally the keys themselves (that would make it undeniable), but more credibly, leaks that show usage or potential usage of the backdoor. But what seems surprising to me about that story is that the potential for a backdoor was known even before the adoption of Dual_EC_DRBG as a standard. Any credible enemy of the state would know that and use something else, and be very suspicious of imported products using it. The ones following NIST recommendations would be allies, but why would you want allies to use weak ciphers?
- carbotaniuman 3y ago
  If you believe you are the only one who can break the cipher, then it doesn't really matter if your allies are using them - after all, spying happens even among ostensibly allied or friendly countries. I think most people's source of proof is the Snowden leaks, but I haven't actually read it or corroborated, and most backdoors should be deniable anyway - it'd be real dumb if they weren't. I think strong circumstantial evidence is really the only thing one can go on.
- lazide 3y ago
  It has constants chosen with NSA input which weaken it - and which were called out a long time ago as doing so. It isn’t a back door in the sense of ‘poke the code in a certain way and voila’, rather ‘if you know the counterpart to this constant, you can guess what values the RNG spits out at statistically improbable rates’. You’d never know if someone was doing so unless they admitted it or someone got arrested in a way that was only possible if they’d used it. Which good luck.
- jiggawatts 3y ago
  > Is there any proof that Dual_EC_DRBG is backdoored? The algorithm is bad: it's complicated and slow. The competing algorithms were much simpler, much more secure by construction, and much faster. Most importantly, there was no obvious way to backdoor the competing algorithms, but there's a hilariously trivial way to backdoor Dual_EC_DRBG. Ergo: the only reason you would ever devise or use Dual_EC_DRBG is to introduce a backdoor capability. There is no other believable benefit or reason. But rest assured, the NSA promised that they destroyed all copies of the private key they used to generate the public key for Dual_EC_DRBG. Oh wait, you thought you could generate your own pair and throw away the private key? Ha-ha... haaa. No. That's not compliant with the "standard", which the NSA forced upon the industry, and/or literally bribed companies with millions of dollars to accept willingly. It's as obvious a backdoor as you could possibly have. Even if the NSA didn't use it as a backdoor -- I'm crying with laughter now -- the Chinese hacking group APT5 definitely did: https://blog.cryptographyengineering.com/2015/12/22/on-juniper-backdoor/ https://blog.cryptographyengineering.com/2015/12/22/on-junip...
kurikuri 3y ago
You are wildly incorrect here. The cryptographic module uses the CTR_DRBG, not the withdrawn Dual_EC_DRBG. The Dual_EC_DRBG was withdrawn in 2014, but this Security Policy for this module was submitted well past that for FIPS 140-2 revalidation, and the CMVP would not have let a testing lab submit it at all. This isn’t the back door.
- mike_d 3y ago
  Irrelevant. This "revelation" is from pre-2013 information. Dual_EC may have been the capability before it was withdrawn.
  - kurikuri 3y ago
    > Irrelevant Except it was relevant as a response to the OP in that: I was pointing out their conflation of two different DRBGs. Having an SP 800-90A DRBG does not mean you support all of them, nor does it imply the user could change between the 3 (or, in that hypothetical, 4). Outside of that, it is unlikely that this module had Dual_EC_DRBG at any point in time for three reasons: 1) Submitting a hardware module that has an entirely new DRBG would require a lot of low level work from Cavium, and the modifications made to the physical module would likely constitute more than an updated certificate (i.e., a new certificate). 2) Even though the DRBG was withdrawn, the CAVP lists algorithm certificates, and this includes historic certificates. Cavium doesn’t have a Dual_EC_DRBG certificate for any operating environment. A list of Dual_EC_DRBG certificates can be seen here: https://csrc.nist.gov/projects/cryptographic-algorithm-valid https://csrc.nist.gov/projects/cryptographic-algorithm-valid... 3) the earliest security policy for the module that I could find dates back to 07/22/2014, and it still uses the CTR_DRBG. Security policy here: https://csrc.nist.rip/groups/STM/cmvp/documents/140-1/140sp/ https://csrc.nist.rip/groups/STM/cmvp/documents/140-1/140sp/...
_kbh_ 3y ago
> Looking more closely at this, the backdoor is almost certainly based on the back-doored random number generator, Dual_EC_DRBG, which is implemented as NIST SP 800-90A. This doesn't have to be backdoored. It could simply be a bug in their hardware RNG that uses something that isn't public to break it. Or something that Cavium did not realise was vulnerable.
0xDEFACED 3y ago
Computerphile has a video about this algorithm and its potential backdoor, it’s a great watch. https://youtube.com/watch?v=nybVFJVXbww https://youtube.com/watch?v=nybVFJVXbww
araes 3y ago
Since Calvium got rewarded for being "Completely Enabling for _______ encryption chips used in VPN and Web encryption" and then lists these on its Nitrox III and Nitrox V (https://pbs.twimg.com/media/F6Y_zDQWgAAj96s?format=jpg https://pbs.twimg.com/media/F6Y_zDQWgAAj96s?format=jpg) AES (128/192/256 CBC, GCM) Triple-DES (CBC, 3-key) SHS (SHA-1/256/384/512) HMAC (SHA-1/256/384/512) RSA (KeyGen, SigGen and SigVer; PKCS1 V1 5; 2048bits) ECDSA (PKG, SigGen and SigVer; P-256, P-384, P-521) CTR DRBG (AES-256) HASH DRBG (SHA-512) CVL Component (IKEv2, TLS, SSH) CKG (vendor affirmed) Does that imply that the NSA may have kleptographic (algorithm substition, or secondary key) attacks or something different for all of these?
distract8901 3y ago
Sorry, what does it even mean for a random number generator to have a backdoor? Is it leaking your generated keys to the NSA? Does it have some arbitrary code execution vulnerability?

stephen_g 3y ago

That's a very specific module - one of Cavium's dozens and dozens of products. Hard to tell what it is, more information is needed.

convivialdingo 3y ago
Well, there's several Cavium devices that support the deprecated/back-doored Hash_DRBG. For example, these devices were validated for the completely appropriately named "SonicOS 6.2.5 for TZ, SM and NSA". Gotta appreciate the irony. Cavium CN7020 Hash DRBG Cavium CN7130 Hash DRBG Cavium Octeon Plus CN66XX Family Hash DRBG Cavium Octeon Plus CN68XX Family Hash DRBG I don't know if that's hardware support or just a software validation - but it's still interesting that they validated it. https://csrc.nist.gov/Projects/Cryptographic-Algorithm-Validation-Program/details?validation=3445 https://csrc.nist.gov/Projects/Cryptographic-Algorithm-Valid...
- dfox 3y ago
  Except Hash_DRBG is neither deprecated nor backdoored. See NIST SP 800-90A Rev. 1 section 10.1.1.1 for description of the algorithm.
  - convivialdingo 3y ago
    Well, true.. the Hash_DRBG hashing algorithm remains. But it's rather likely that previous FIPS validations occurred utilizing the actual backdoored and deprecated algorithm as an input to the Hash_DRBG, rendering it's security properties suspect. In NIST SP 800-90A Rev. 1, the HASH_DRBG section has been significantly updated to that effect. For instance, Appendix E: (Informative) Revisions. Section 10: Section 10 now includes a link to the DRBG test vectors on the NIST website. Sections 10.1, 10.1.1 and 10.1.2 now include short discussions about selecting hash functions to support the DRBG's intended security strength. The Dual_EC_DRBG has been removed, and section numbers adjusted accordingly.
    - dfox 3y ago
      The backdoor in DualEC_DRBG only works if there is some way for the attacker to directly observe its outputs (eg. using that for IVs). If you use it as an inner CSPRNG that seeds other faster algorithms the backdoor is irrelevant, but well, such a construction is total nonsense that only ever makes sense in the FIPS certification framework (DualEC_DRBG is ridiculously slow and not meaningfully more secure than the other FIPS CSPRNGs). On the other hand, I have the feeling that if you instantiate Hash_DRBG with certain classes of insecure hash functions (think MD2) the mechanism that protects the construction from effects of birthday paradox makes it simpler to break the underlying hash function, but for this attack to work the underlying hash function have to be really bad and this attack is probably impractical even for instantiations with MD4, much less the SHA variants in the specification.

GuB-42 3y ago

Is there any proof that Dual_EC_DRBG is backdoored? All I know is that Dual_EC_DRBG can be backdoored. And there are indeed suspicions, it was known from the start that not only Dual_EC_DRBG could be backdoored, but that it was rather weak to begin with. So, how could it be adopted as a standard? Now it seems that everyone takes the backdoor as a given. Is there any proof? Ideally the keys themselves (that would make it undeniable), but more credibly, leaks that show usage or potential usage of the backdoor. But what seems surprising to me about that story is that the potential for a backdoor was known even before the adoption of Dual_EC_DRBG as a standard. Any credible enemy of the state would know that and use something else, and be very suspicious of imported products using it. The ones following NIST recommendations would be allies, but why would you want allies to use weak ciphers?

carbotaniuman 3y ago
If you believe you are the only one who can break the cipher, then it doesn't really matter if your allies are using them - after all, spying happens even among ostensibly allied or friendly countries. I think most people's source of proof is the Snowden leaks, but I haven't actually read it or corroborated, and most backdoors should be deniable anyway - it'd be real dumb if they weren't. I think strong circumstantial evidence is really the only thing one can go on.
lazide 3y ago
It has constants chosen with NSA input which weaken it - and which were called out a long time ago as doing so. It isn’t a back door in the sense of ‘poke the code in a certain way and voila’, rather ‘if you know the counterpart to this constant, you can guess what values the RNG spits out at statistically improbable rates’. You’d never know if someone was doing so unless they admitted it or someone got arrested in a way that was only possible if they’d used it. Which good luck.
jiggawatts 3y ago
> Is there any proof that Dual_EC_DRBG is backdoored? The algorithm is bad: it's complicated and slow. The competing algorithms were much simpler, much more secure by construction, and much faster. Most importantly, there was no obvious way to backdoor the competing algorithms, but there's a hilariously trivial way to backdoor Dual_EC_DRBG. Ergo: the only reason you would ever devise or use Dual_EC_DRBG is to introduce a backdoor capability. There is no other believable benefit or reason. But rest assured, the NSA promised that they destroyed all copies of the private key they used to generate the public key for Dual_EC_DRBG. Oh wait, you thought you could generate your own pair and throw away the private key? Ha-ha... haaa. No. That's not compliant with the "standard", which the NSA forced upon the industry, and/or literally bribed companies with millions of dollars to accept willingly. It's as obvious a backdoor as you could possibly have. Even if the NSA didn't use it as a backdoor -- I'm crying with laughter now -- the Chinese hacking group APT5 definitely did: https://blog.cryptographyengineering.com/2015/12/22/on-juniper-backdoor/ https://blog.cryptographyengineering.com/2015/12/22/on-junip...

kurikuri 3y ago

You are wildly incorrect here. The cryptographic module uses the CTR_DRBG, not the withdrawn Dual_EC_DRBG. The Dual_EC_DRBG was withdrawn in 2014, but this Security Policy for this module was submitted well past that for FIPS 140-2 revalidation, and the CMVP would not have let a testing lab submit it at all. This isn’t the back door.

mike_d 3y ago
Irrelevant. This "revelation" is from pre-2013 information. Dual_EC may have been the capability before it was withdrawn.
- kurikuri 3y ago
  > Irrelevant Except it was relevant as a response to the OP in that: I was pointing out their conflation of two different DRBGs. Having an SP 800-90A DRBG does not mean you support all of them, nor does it imply the user could change between the 3 (or, in that hypothetical, 4). Outside of that, it is unlikely that this module had Dual_EC_DRBG at any point in time for three reasons: 1) Submitting a hardware module that has an entirely new DRBG would require a lot of low level work from Cavium, and the modifications made to the physical module would likely constitute more than an updated certificate (i.e., a new certificate). 2) Even though the DRBG was withdrawn, the CAVP lists algorithm certificates, and this includes historic certificates. Cavium doesn’t have a Dual_EC_DRBG certificate for any operating environment. A list of Dual_EC_DRBG certificates can be seen here: https://csrc.nist.gov/projects/cryptographic-algorithm-valid https://csrc.nist.gov/projects/cryptographic-algorithm-valid... 3) the earliest security policy for the module that I could find dates back to 07/22/2014, and it still uses the CTR_DRBG. Security policy here: https://csrc.nist.rip/groups/STM/cmvp/documents/140-1/140sp/ https://csrc.nist.rip/groups/STM/cmvp/documents/140-1/140sp/...

_kbh_ 3y ago

> Looking more closely at this, the backdoor is almost certainly based on the back-doored random number generator, Dual_EC_DRBG, which is implemented as NIST SP 800-90A. This doesn't have to be backdoored. It could simply be a bug in their hardware RNG that uses something that isn't public to break it. Or something that Cavium did not realise was vulnerable.

0xDEFACED 3y ago

Computerphile has a video about this algorithm and its potential backdoor, it’s a great watch. https://youtube.com/watch?v=nybVFJVXbww https://youtube.com/watch?v=nybVFJVXbww

araes 3y ago

Since Calvium got rewarded for being "Completely Enabling for _______ encryption chips used in VPN and Web encryption" and then lists these on its Nitrox III and Nitrox V (https://pbs.twimg.com/media/F6Y_zDQWgAAj96s?format=jpg https://pbs.twimg.com/media/F6Y_zDQWgAAj96s?format=jpg) AES (128/192/256 CBC, GCM) Triple-DES (CBC, 3-key) SHS (SHA-1/256/384/512) HMAC (SHA-1/256/384/512) RSA (KeyGen, SigGen and SigVer; PKCS1 V1 5; 2048bits) ECDSA (PKG, SigGen and SigVer; P-256, P-384, P-521) CTR DRBG (AES-256) HASH DRBG (SHA-512) CVL Component (IKEv2, TLS, SSH) CKG (vendor affirmed) Does that imply that the NSA may have kleptographic (algorithm substition, or secondary key) attacks or something different for all of these?

distract8901 3y ago

Sorry, what does it even mean for a random number generator to have a backdoor? Is it leaking your generated keys to the NSA? Does it have some arbitrary code execution vulnerability?