4

How can we trust our encryption methods if our random number generators are to be [assumed] compromised? Does encryption also depend on the random number generators of our hardware?

I forgot to also say, if any of this is true, then how are we able to trust the companies that hold our data "securely". If the NSA has all of these backdoors into systems by the companies being forced to comply with the requests or them handing them over, is there no way to fix these vulnerabilities?

Allow me to quote Edward Snowden, Thomas Drake, and Bruce Schneier regarding the assumption:

We should [assume] that everything [that all encryption] is compromised by the NSA

That is a pretty powerful statement coming from three Security Experts, which I strongly believe that we can trust their opinion.

Traven
  • 866
  • 1
  • 9
  • 19
  • Can you include the source link for that statement? – Nathan Arthur May 06 '14 at 14:13
  • 2
    It is posted on [Schneier's blog](https://www.schneier.com/blog/archives/2013/09/the_nsa_is_brea.html) plus TekSynidcate interviewed Drake and Schneier also with their [YouTube Video](https://www.youtube.com/watch?v=Az-jXeCswCg) at the Stop Watching Us Rally. – Traven May 06 '14 at 14:18

1 Answers1

1

Can we trust encryption when the random number generator is compromised?

No. For example, if you are doing AES-128 and your flawed pseudo random number generator creates a 128-bit key, where the key due to flawed random number generation can only be one of 2^40 (10^12 ) options (that are well distributed and appear random), it would be possible for a governmental attacker to simply try all 2^40 options to try brute-forcing your AES-128 key. Many more attacks of this sort are described on wikipedia.

I don't think its fair to assume that the NSA has compromised encryption by simply compromising all random number generators. It's probably a multi-faceted approach that ranges from compromising hardware, software (both open source software by submitting new features with subtle flaws) and closed-source software (either develop it yourself, or pay someone off to alter the source code right before it ships), certificate authorities, standards, infiltrating and paying off organizations (like paying RSA Security $10 million to default to Dual EC DRBG with its "rather-obvious" ability to be backdoored). Possibly even involves number theoretic advances like the ability to break easily factor prime numbers or solve discrete logs which would undermine RSA and ElGamal encryption.

Speculation

My guess is no on this number-theoretic front -- if the government could very easily break RSA moduli easily, then why did they have to shutdown lavabit when the founder refused to give away his private SSL key (versus let him continue to operate and decrypt the traffic anyway). My personal guess is a lot of it tends to be nonsensical designs that allow programming "mistakes" that undermine security through side-channel attacks like Heartbleed, or software with deliberately introduced flaws (open-source with mistakes like heartbleed or closed-source through modifications secretly made), or hardware with major vulnerabilities in the design. Yes, it sounds like a conspiracy theory, but to quote the NY Times reporting on leaked Snowden documents:

The N.S.A.'s SIGINT Enabling Project is a $250 million-a-year program that works with Internet companies to weaken privacy by inserting back doors into encryption products.

Community
  • 1
dr jimbob
  • 38,768
  • 8
  • 92
  • 161
  • 1
    Re: your last paragraph, the reason why they asked for Lavabit's private SSL cert is for 'parallel construction'. They want a plausible (and legal) way to say how they obtained the key which does not reveal their actual methods or capabilities publicly. If they really wanted the SSL cert they would have just used Heartbleed, some other undiscovered weakness or the TAO team. If they wanted to intercept traffic from users to the Lavabit server they don't even need exploits, they just perform a MITM using one of the govt or compromised CA root certs trusted by every browser... – NDF1 May 07 '14 at 02:45
  • It is much cheaper and faster for an intelligence agency to subvert encryption and render it useless by inserting backdoors, creating weaknesses in the RNGs, or exploiting broken implementations/designs than it is to crack the encryption outright on a global scale. They use what is fastest as their primary method. It is highly likely they can break crypto with secret quantum computers or knowledge of algorithmic weaknesses, however it makes sense to only use that for high value messages because they might not have capability to crack the whole planet's daily codes in a reasonable time frame. – NDF1 May 07 '14 at 03:00