Weekly edition Kernel Security Distributions Contact Us Search Archives Calendar Subscribe Write for LWN LWN.net FAQ Sponsors

# Good piece

## Good piece

Posted Nov 20, 2012 21:42 UTC (Tue) by dlang (✭ supporter ✭, #313)
In reply to: Good piece by man_ls
Parent article: LCE: Don't play dice with random numbers

the issue isn't repeating numbers, it's repeating the exact same sequence of numbers.

If you flip a (fair) coin and it lands head 8 times in a row (a 1 in 256 chance), what are the odds of it landing heads the next time.

if it's really a fair coin, the chance is 1 in 2

If you are getting a 8 bit value, the chances of getting the exact same number the next time you get a value are 1 in 256.

If you change your system so that you guarantee that you don't get that same number twice within 128 tries, you will have seriously hurt the randomness of your results

*Secure* randomness

Posted Nov 21, 2012 12:39 UTC (Wed) by kirkengaard (subscriber, #15022) [Link]

The question isn't really whether we have an ideal rng that produces non-patterned outputâ€”the question is whether our rng produces random output suited to operational demands. So we do in fact "restrict" randomness in order to get non-patterned output that is also not value-repetitive.

If all we want is pure randomness, and we don't rely on it for anything, any non-patterned output, however often it may reproduce specific values in its output, is sufficient. A d6, for example, or a coin.

But if what we want is *secure* randomness over long cycles, then repeating entries is bad. Collisions are breaches waiting to happen. Even if the sequence doesn't repeat, if I know enough of the output, I can wait.

Strings of 1s may happen with a two-state generator, for example, but the point of running them through much more complicated chains, to generate "more" randomness, is really also to generate more *usefully secure sequences* (that is, non-repetitive) of random numbers. Which is why also the filtering and throttling and whatnot.

Good piece

Posted Nov 28, 2012 16:49 UTC (Wed) by akeane (subscriber, #85436) [Link]

>If you flip a (fair) coin and it lands head 8 times in a row (a 1 in 256 chance), what are the odds of it landing heads the next time.

>if it's really a fair coin, the chance is 1 in 2

Yep, and it's amazing how many well educated numerate people don't get this (I once had a friend who was an astrophysicist who thought tails was more likely)

The way I explain it is this, the coin doesn't have a memory or a conscience, it just reacts to a bunch of forces which are hard to predict, and have been around since that Newton fellow invited gravity in 1964.

111111111 is just as likely as 100110100 etc, it's just that people recognize or interpret the 111111111 as a pattern and think, wow what are the chances of that...

111111111 is just as random a number as anything else because you can't predict the tenth flip.

Now if the coin landed on it's side 10 times in a row...

If you really want to wind somebody up (and I generally do) try telling someone who works in the financial industry to plot a histogram of the daily percentage movements for the last 25 years of the SP500, of the FTSE all share and ask what curve they get :-)

Good piece

Posted Nov 28, 2012 20:05 UTC (Wed) by mathstuf (subscriber, #69389) [Link]

> Newton fellow invited gravity in 1964.

Huh, I didn't know you could invite gravity anywhen.

Good piece

Posted Dec 1, 2012 21:55 UTC (Sat) by akeane (subscriber, #85436) [Link]

>Huh, I didn't know you could invite gravity anywhen.

That's OK, my simple colonial friend, don't be ashamed of your ignorance, back in the old country we used to invent stuff all the time, behold: friction co-efficients, the lingua franca, owls and even the concept of pitying fools. Although the last one was purloined ("nicked" as we say in the modern parlance) by a mo-hawked maniac who had an unhealthy obsession with his "van"...

Note that I am not including calculus in this analysis as even the most bereft of brain molecules can clearly see it's naught more than filthy hack, the universe should be modeled with integers, or at least BCD.

Divide h plus a bit by h, tut!

Good piece

Posted Dec 5, 2012 19:38 UTC (Wed) by jrigg (subscriber, #30848) [Link]

>> Newton fellow invited gravity in 1964.

> Huh, I didn't know you could invite gravity anywhen.

You can if the invitation is posthumous by 237 years ;-)

Good piece

Posted Nov 29, 2012 1:40 UTC (Thu) by cb064 (guest, #88059) [Link]

I would suppose it to be bell shaped, though not very certain about the amount of "mass" in the tails (not even sure if the only reason it's measureable being that markets do not run "forever" and are limited by the life-expectancy of human civilisation)

PS: for anybody interested:
https://www.student.gsu.edu/~gconnaughton1/Project2.htm

Good piece

Posted Dec 2, 2012 11:35 UTC (Sun) by akeane (subscriber, #85436) [Link]

>I would suppose

Rather than suppose why not try, the data is all there, it takes a few lines of a bash script to download the data (stuff that actually exists rather than supposition), do the counting and produce a csv file you can put into whatever graphing tool you like and see what you get?

And if you can't be bothered to do that, don't start whining when your pension or 401k plan, doesn't "perform" like you were told...

:-)