Sponsorship

>You are assuming that the PRNG has near-perfect entropy and that the search space is thus as large as you think it is.
I think that for most practical PRNGs it's not feasible to find their bias. And it's also ultimately futile because you'd have to re-do the analysis for each new version of PRNG.

Now, if we're talking about keys derived from users' input then it's a whole different story. It's very much feasible to brute-force most of passwords that are easily memorable.

>This might be a reasonably safe assumption, but it's less than provable. Also note that the search space for quantum computers would be the square root of the search space size for von Neuman ones.
So just use 256-bit keys. Building a quantum computer capable of iterating through the 128-bit keyspace is very faaaar in the future if even practically possible, and it'll have the same issue with the boiling oceans.

>We can only use NSA's actions to forcast their capabilities. Right now there is an effort to make encryption mandatory for every HTTP connection in the next version of the HTTP standard.
NSA is not omnipotent. Also, it's far easier for them to force most of cloud providers to provide direct taps to their internal networks.