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
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?
> 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.
Why would you need proof that it has been backdoored? The fact that it can be backdoored should be enough to disregard it for all uses right from the start.
There are some algorithms where there's no obvious way to back door it, but it's always conceivable -- the person designing it may know some clever mathematics that you don't.
With Dual_EC_DRBG, everyone knew that it could be back doored. It's not some guess, or "maybe it could have". It was obviously designed to be back doored. It should have been called "NSA_BACKDOOR_RNG", because that's literally what it is.
And yes, all organisations that are not under the thumb of the US Government laughed at the transparent attempt to introduce a back door and rejected Dual_EC_DRBG. Only US-based companies use it, which ought to give you a hint.
No, not really. If the data you hold is precious enough that you may have an actor with near infinite resources after you then you don't wait for proof to arrive, you assume the holes are there and act accordingly. Paranoia is fine if you have actual enemies, banking on the theory that evidence that a backdoor exists in a tool that you are using today will never surface is entirely the wrong approach.
Knowledge that this environment exists is also strong evidence that it was a backdoor.
If you propose a clearly questionable security practice in some arbitrary bureaucracy, the assumption is it's incompetence because that happens all the time and no one detects it until it's already in production.
If you propose a clearly questionable security practice to a cryptography standards body, the expectation is that you get laughed out of the room. Even the possibility of a backdoor would make everyone skeptical, which would be useless in a standard because no one would trust it.
And yet it made it through the standards process for some reason, but there is only one plausible reason.
> In this way, entire sections of industry will auto-assume the backdoor was both deliberate, and used both both friendlies & hostiles.
That’s fine. But they should be equally paranoid of all substitute products/services that use other recommendations from NIST, right? Are there greater than zero products on the (US) market with no encryption in the system recommended by NIST?
Also, I don’t think I was limiting my thinking to a customer of the weak encryption product. I was also thinking through the lens of legal implications.
If, for example, SHA2 had a backdoor or a weakness known only to the NSA, then random contractors (like Snowden) could use that to extract money from the Bitcoin network, which uses SHA256 as its core cryptographic primitive.
That's easily a billion dollar motivation right there, and I can't imagine a bunch of low-paid government drones resisting that cash prize. Everyone has a price.
Hence, there's a level of trust that can be gained through observation of failures to abuse backdoors. If they don't exist, they can't be abused. If they exist, then they must be used/abused, otherwise what's the point? Such usage will be eventually discovered. E.g.: The use of the Dual_EC_DRBG back-door to tap into Juniper VPN connections by the Chinese government was discovered and made public.
I'm not advocating in either direction here, but let's assume backdoors like this do exist: Just because they haven't been abused doesn't mean that they wont in the future.
Of the people I know that work with highly privileged materials, none would take advantage or abuse something like this, even with such a high payout. Even if they did, how would they continue to live comfortably? That said, it just takes one person under the right circumstances to act maliciously, which is why screening and compartmentalization is critically important for these organizations.
We use computers because it is pretty much impossible to live in modern society without using computers.
But by the time Dual_EC_DRBG was published, we already had alternatives that were better in just about every way, including being much less likely to contain a backdoor.
Interestingly, Trusting Trust style attacks on compilers was later (theoretically, idk to what degree it's been put into practice) solved by "diverse double compiling": https://dwheeler.com/trusting-trust/
I like the link and the explanations about the weaknesses.
I detest the only evidence being circumstantial and the _argument from ignorance_ being the one that you lean on. Make the simple observations and don’t try to oversell it.
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.
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.
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.
> 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...
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/...
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.
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.
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)
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?
> 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.
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?
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-modu...