Random ideas sought to improve cryptography

Re: Reliable way to check the output

Yes, some sort... it's in the mail already.

Anyway, obligatory xkcd

Re: Reliable way to check the output

You joke, and I may get sternly corrected for this...

But some mathematical analyses is possible.

Say I try to zip a text document. I then try to zip some random data generated at the same bit length.

I would need to check the text document against quite a few random strings, but the text document should show its self to be more compressible than a random string <on average>.

This is of cause not true for other things, like video, as it may be compressed in a lossy method.

Data with redundancy in it, is different from true random data, however data with little redundancy is very similar, or arguably indistinguishable from random data.

Our language has a lot of redundant data in it, so we can use that to find patterns, and match it to other exiting patters (that is, unencrypted it). Random data, by it's definition, is suppose to have no real pattern. (For example, if your rng gives out four 1s, four zeros then repeats, on every result, it's not random and giving out a possible signal. See XKCD link above! :P ).

Things like stenography can be detected when comparing to original source (if available else where) etc.

I read one paper, where random strings were used to test against scientific theories. If the random string did a better prediction, your theory would officially be "worse than an absolute guess!". :D

Re: Silicon solution

This sounds right to me --- the sort of device that you can plug into a USB port to read, but made from simple components (capacitors, resistors, transistors) that you can verify (or assemble yourself). I've seen some circuit diagrams but we really need something very simple indeed. People add complexity to circuits by adding clever stuff to ensure random weighting* but this seems unnecessary and adds the kind of circuitry that could disguise randomness-subverting badness.

Maybe what we need is something physical that we can verify by eye -- like a lotto ball machine. We just need something that can generate numbers much faster. Perhaps a shaker full of tiny particles, read by a CCD?

* if you have a random bit stream which is suitable in every respect other than weighting (ratio of 1s and 0s) you can create a perfectly weighted stream from it by sampling non-overlapping pairs. I think it was Von Neumann who invented this - you read bits pairwise, discarding all pairs where the bits are equal. You convert the remaining pairs into 1s and 0s using the code 01->0; 10->1 (or vice versa) and bingo, you have a bit stream balanced perfectly 50:50 into 1s and 0s. This is because if the bits are independent then the probabilities of 01 and 10 are equal, whatever the probabilities of 0 and 1 (and hence 00 and 11, which have unknown probabilities, are discarded).

Re: Willing to sell

AC: "...simply get some decently sized particle detector and start counting."

Oh great. Then the spooks start firing fast neutrons at your house, to adjust the bias in your random noise generator.

Re: Willing to sell

"Six! Is six taken...? Does it have to be between one and 10?"

And...?

Do you have any results?

That tells you that they are distributed rather than random though.

"For the past year, I've been running tests on a couple random number generators. I grab a random 32-bit integer form it, each number is plotted on a 65,536 x 65,536 bitmap. Each time a number comes up, its pixel's color is bumped up by one. Every so often, the bitmap gets saved to an external storage array so that the image can be viewed from another machine, any number that is favored by the RNG will show up as a different color in the resulting image." -- Crazy Operations Guy

It's a good first attempt at RNG visualization but I'm afraid it is rather flawed: a quick example will show why: what if you replaced your RNG with a counter? It is lack of correlation between one bit and the next (more exactly that any given bit in no way depends on any of the previous history) that is the crucial thing rather than a completely even coverage (as explained in my earlier post you can extract a smaller number of perfectly distributed random bits from an imperfectly distributed random source as long as each bit is independent.

"...any number that is favored by the RNG will show up as a different color in the resulting image."

Great, but you may still have a crappy random number generator. an extreme example:

rand = rand +1;

return rand;

will have an extremely nice distribution, won't favor any numbers at all.

Can you guarantee your mirrors are 100% non-bias?

As the antimatter-matter imbalance exists by some unknown method, we could still find bias. But it'll be close enough. :)

Re: Way back when

The word "random" has many different meanings and people tend to confuse them. In this particular case, cryptography, the meaning we care about is "cannot be predicted by an attacker". So digits of pi are no good. And data derived from a quantum mechanical process are no good, either, if there's any possibility that an attacker might be able to observe the same process or intercept the data. So you're better off with crap generated inside the server box (such as a microphone picking up noise from the fan) than with any high-quality evenly distributed quantum-mechanical stuff that comes in over the (insecure) network.

Re: Verification not generation

2nd line of article, my emphasis:

"The recommendation NIST's put up for discussion covers the design principles and requirements for random bit generators, and tests to validate entropy sources."

Gideon 1, my emphasis

""Verification not generation ... It's interesting how many Commentards didn't understand the article."

Errm, yes?

On a more serious note, given the difficulties in verifiability (not just doing it, but doing it in a way that is widely understood), I think verifiable generation (quantum & other physical methods proposed above by commentards including myself "who didn't understand the article") would be a better approach than new methods for verification. Given that there are any number of deterministic sequences (e.g. digits of pi, mentioned above) that satisfy all existing tests for randomness and (as far as my limited mathematical understanding goes) are likely to continue to do so, verifiable generation seems to me a much more promising area than verification of deterministic generators.

Einstein's dice

>Going out on an existential limb, it could be that true randomness is impossible because there's an >innate order to the universe that can't be broken....

You're in good company. For Albert Einstein's famous statement: "God does not play dice with the universe" to be true, randomness where we think we've found this, would be an emergent as opposed to an intrinsic property of the universe.