1

As I understand, key exchange for secure communications like TLS has a client take a server's public key, generate a random AES key and send that as a shared key for further communication. The key is generated using a cryptographically secure random number generator where the seed is obtained via system entropy.

I assume a random generator is used to create the key rather than purely from system entropy because it's faster/easier, but why does the generator have to be cryptographically secure? The benefits of being so are that given any state of the generator, it's infeasible to predict the next bit, or any of the previously generated ones. However, if an attacker can see the output of the number generator, don't they already have the AES key anyway? In what scenario would they only ever have part of the key, which they could then exploit the number generator to recover the rest?

I assume I'm misunderstanding it's purpose.

muke
  • 135
  • 2

2 Answers2

2

  1. As AndrolGenhald wrote in comment, modern protocols use Diffie Hellman (usually an Elliptic Curve Diffie Hellman) and don't use asymmetric encryption for key exchange.

  2. The protocol often requires both sides to generate and send in the clear some random bytes. These can be "server random" and "client random" in the TLS handshake (and equivalent in SSH and IKEv2 for IPSec) but also nonces or IVs (CBC is not allowed in TLS 1.3 but bear with me). Basically, it is assumed that either side has used the same CSPRNG to generate data that was sent in the clear, before or after generating secret key material. If seeing the data that was sent in the clear allows a passive attacker to completely determine the inner state of the CSPRNG and then to "step" the CSPRNG forwards or backwards, the attacker gets the keys.

An illustrative example is the Juniper NSA backdoor. They had to exfiltrate some consecutive number of bytes from the CSPRNG to enable the passive attacker to compute the CSPRNG state to compute the secret keys. This necessitated multiple changes to the software in addition to the use of the backdoored PRNG. A non-cryptographic PRNG (like a Mersenne Twister) instead of a backdoored PRNG would be exploited in similar ways. Changes to how some of its output is sent in the clear will make exploitation easier or harder.

Community
  • 1
Z.T.
  • 7,768
  • 1
  • 20
  • 35
  • To the best of my knowledge, there is no public evidence that the Juniper ScreenOS back door was connected to the NSA. It used a _design_ that came out of the NSA, which was standardized by NIST along with standard base points that one can reasonably presume are the NSA's back door (unless the NSA is astonishingly incompetent at their own tasks)—but the base points used in the malicious change to Juniper's code were _not_ the standard base points. – Squeamish Ossifrage Nov 10 '19 at 14:56
  • @SqueamishOssifrage the Juniper code was changed twice. In ~2008 the NSA backdoor was inserted, using a key generated by Juniper, together with other changes required to make it easy to exploit. In ~2012, someone else replaced the Q parameter (key) with a new one, and thus gained the ability to decrypt the traffic themselves and locked NSA out of the traffic (!). This was discovered in 2015. So I'm willing to bet the original party to insert the backdoor were the NSA, and the people who replace the key were not the NSA. (https://blog.cryptographyengineering.com/2015/12/22/on-juniper-backdoor/) – Z.T. Nov 10 '19 at 15:51
  • From the evidence I have seen, Juniper used Dual_EC_DRBG _but generated their own Q_, rather than using the standard one (NSA's back door); then in 2012 _Q_ was replaced. It's possible that Juniper's original _Q_ was _also_ chosen by NSA, but why would they do that instead of using the standard _Q_? Another hypothesis is that Juniper wanted _their own_ back door, along the lines of the Brown & Vanstone ‘key escrow’ patent on bespoke Dual_EC_DRBG base points; still another is sabotage on the payroll _another_ government's intelligence agency. Do you have evidence that either back door is NSA's? – Squeamish Ossifrage Nov 10 '19 at 16:32
  • @SqueamishOssifrage I concede I don't have any more evidence. I can call it "the NSA designed backdoor in Juniper", since we don't know it was used by NSA. But I don't understand the motivation for Juniper to insert the backdoor themselves. And if China/Russia/Israel/Etc inserted it, what an amazing failure of US counterintelligence. – Z.T. Nov 10 '19 at 16:44
  • It's weird, I agree! It's the use of a nonstandard _Q_ that makes me doubt it was the NSA's doing. I don't have _evidence_ that it's another government's, but it would be foolish _not_ to try to have people working at companies like Juniper (and [Twitter](https://www.nytimes.com/2019/11/06/technology/twitter-saudi-arabia-spies.html)!) which have a substantial influence on widely used networking and communications infrastructure. I usually just say the Dual_EC_DRBG back door, since that's a specific keyword that you can easily search for to find, _e.g._, https://projectbullrun.org/dual-ec. – Squeamish Ossifrage Nov 10 '19 at 18:01
0

Predicting future output from existing output is only one of many problems a PRNG can have. I'm not an expert in this area, but just looking at PRNG on Wikipedia, I see it links to RANDU, which, among other serious issues, only generates odd numbers...which loses you a bit of security right there (actually 4 bits if you use it to generate 4 32 bit integers to be used as a 128 bit key). But it's worse than that, when generating an 8 bit number (by taking the lowest 8 bits of the 32 bit output), it only generated 1/4th of the possible values.

If you use a bad PRNG to generate a key, you could be drastically reducing the keyspace without being aware of it.

AndrolGenhald
  • 15,436
  • 5
  • 45
  • 50
  • with a PRNG this bad, very few ECDSA signatures need to be observed until a passive attacker can compute your private key. – Z.T. Sep 23 '19 at 02:12
  • 1
    @Z.T. Oh I'm sure, I expect someone with more knowledge on CSPRNGs and cryptography could point out countless other issues, I just wanted to make the point that predicting future output from previous output (commonly known to be an issue with Mersenne Twister) is far from the only issue a PRNG can have. – AndrolGenhald Sep 23 '19 at 02:15