Random numbers are too important to be left to chance

Random numbers are too important to be left to chance

There’s no program that can generate truly random numbers.  That’s why people talk about pseudorandom numbers.   But now ‘pseudo’ takes on a whole new meaning: the NSA has been getting companies to make their random number generators less random!  Bruce Schneier of The Guardian writes:

As was revealed today, the NSA also works with security product vendors to ensure that commercial encryption products are broken in secret ways that only it knows about. We know this has happened historically: CryptoAG and Lotus Notes are the most public examples, and there is evidence of a back door in Windows. A few people have told me some recent stories about their experiences, and I plan to write about them soon. Basically, the NSA asks companies to subtly change their products in undetectable ways: making the random number generator less random, leaking the key somehow, adding a common exponent to a public-key exchange protocol, and so on. If the back door is discovered, it’s explained away as a mistake. And as we now know, the NSA has enjoyed enormous success from this program.

In the article I’m linking to, he says what he’s been doing to protect himself since he got ahold of some documents from Snowden.  He adds: “Trust the math. Encryption is your friend. That’s how you can remain secure even in the face of the NSA.”

But the math is subtle.  Any really good code, or pseudorandom number generator, relies on a computational hardness assumption.  This is, roughly, the assumption that some particular math problem can’t be quickly solved by any program.   You can see a list of these assumptions here:

http://en.wikipedia.org/wiki/Computational_hardness_assumption

But here’s the kicker: none of these assumptions have been proved to be true!   Very smart people have tried and failed. 

That doesn’t mean these assumptions are false.  Some things are true but hard to prove.  And some things may be true but impossible to prove – at least, starting from the axioms of math most of us agree on.  So it’s possible that some widely used computational hardness assumptions are true but we’ll never know it for sure!

Here’s my favorite computational hardness assumption: the existence of a one-way function. 

Very roughly speaking, this is a function that’s easy to compute but hard to invert.  In other words, it’s a function f such that for any number n, the number f(n) is easy to compute… but given a number m that equals f(n) for some n, it’s hard to find such an n.  (There could be more than one.)

My explanation here is rough because I haven’t said what ‘easy’ and ‘hard’ mean.  If you’re interested – and it’s very interesting! – read this:

http://en.wikipedia.org/wiki/One-way_function

The existence of one-way functions is crucial for getting really good pseudorandom number generators. But nobody knows if one-way functions exist – though most mathematicians believe they do, and there are some candidates. 

And here’s where things get really gnarly.  The existence of one-way functions is equivalent to the famous unproved conjecture “P ≠ NP”.  However, their existence would also imply there’s no ‘natural proof’ that P ≠ NP!   A ‘natural proof’ is a specific kind of proof you’d be likely to try, if you tried to prove this conjecture… again, I’ll skip the details, which can be found starting here:

http://en.wikipedia.org/wiki/Natural_proof

But oversimplifying quite a bit, the upshot is roughly this: to get really good pseudorandom number generators, we need one-way functions, but if they exist, it is hard to prove they exist!

So you see, pseudorandom number generators would be tricky things even if the NSA were not trying to fool us into thinking numbers are more random than they are.

And I would not be surprised if they work hard to co-opt mathematicians and computer scientists that get interested in these issues.  Forget true but unprovable facts for a minute: how many important theorems are classified?

#logic  

http://www.theguardian.com/world/2013/sep/05/nsa-how-to-remain-secure-surveillance//cdn.embedly.com/widgets/platform.js