real random

[BGB / cr88192]

Only in the USA and its dependent territories. In other countries,
people are not obliged to cover their eyes in an attempt to avoid
failing to see the emperor's new clothes.

(satire...) "but, how can anyone think the US is not the entire world?..."

 

[Beej Jorgensen]

Not that I disagree, but Keith wrote that, for the record.

-Beej

 

[Keith Thompson]

Can anyone show me a skeleton code for *real* random numbers? Not just
using srand and rand that sometimes depends on the clock.

Bill, if you're still reading this thread, you should know by now that
your use of the phrase "*real* random numbers" has sparked a long
discussion among people trying to guess what you actually meant.

So, what did you actually mean?

 

[Bill Cunningham]

Can anyone show me a skeleton code for *real* random numbers? Not just
using srand and rand that sometimes depends on the clock.

Bill

 

[Keith Thompson]

But the subject of this thread is most definitely not PRNGs such as
rand(). The OP asked for "real" random numbers, by which we may
reasonably presume that he means a non-pseudo RNG.

I frankly don't think we can reasonably presume *anything* about what
the OP meant until and unless he explains it (which is why I asked for
clarification in another post).

 

[BGB / cr88192]

In <[email protected]>,
websnarf wrote:



You can mean that if you like, but it's a very humpty-dumpty way of
looking at randomness.

"indeterministic" is the opposite of "deterministic" as I see it.

as I see it, a deterministic system is a system in which the results can be
generated from a finite (and typically known) set of rules.

hence, if you could know the complete state of the system at a given moment,
you could also know all possible future states as well (whether or not this
"can" be done in practice is another issue).

however, a deterministic system can be "chaotic", as is typically the case
with PRNGs.


granted, then there is the philosophical issue of "global" or "universal"
determinism or indeterminism, however, in this case this is not my focus of
concern. we can just assume that chaotic patterns in physical reality are
non-deterministic. (or, even if not, that they reprsent a MUCH larger state
than is typically available to a computer...).

But you can't, reasonably speaking, see /all/ an algorithm's possible
inputs, because (for any non-trivial algorithm) there are so many of
them.

agreed.



That sentence that no grammar with. But if you mean that randomness
depends on how much information the user has or can gain about the
sequence that assists in predicting future numbers, you are correct.

nevermind that none of this makes it "random" in a strict sense.

determinism vs non-determinism is not a matter of observervation (how much
the observer knows or does not know).

The problem with a /seeder/ is that it is used as a start point for a
PRNG. PRNGs are, practically by definition, not random. Given
knowledge of the start state and the algorithm, you have 100%
predictive power.

<snip>

yep, this is a flaw of PRNGs...

TRNG's, however, do not generally have the problem, but as noted, a TRNG is
not purely an algorithm (since, invariably, there is dependence on some sort
of external entropy source).


however, as I see it, the issue is not "as" difficult as people are making
it out to be, since there are plenty of useful sources which already exist
in a modern PC, and there are ways to both accumulate and "amplify" this
entropy (such that, the more often and longer the program runs, the more
entropy it has accumulated, and thus the better its RNG state).

so, my approach is to use a hybrid approach, with a TRNG component to
continuously mine entropy, and a PRNG-like part to essentially "hold" the
RNG state, and to work as an "amplifier" (basically, to get usable random
numbers).


the reason is that most natural sources tend to resemble a weak noise
pattern, which in a pure form is not very usable as random numbers (where
usually we want pure chaos, not a noise pattern).

however, having done some amount of statistical modeling on these noise
patterns, I have reason to suspect that they are, infact, random...


now, what are such sources?...
one I have used is a partially "filtered" version of the 'rdtsc' opcode,
which basically measures the current CPU time (in clock cycles). most of the
chaos I think is all of the internal goings-on in a computer (bus activity,
interrupts, activity in different apps and threads, ...), all of which will
disrupt the uniformity of this value (granted, on a modern system, on a DOS
box it would be somewhat less impressive).

I can then use a thread which mostly just sleeps, periodically reads and
filters the value (subtract last value), and adds it into the RNG state.
this thread will also occasionally write this state to a file (this file is
read-in when the RNG is first initialized).


other sources are possible, but this is just the one I mostly use at
present.

the exact sources, ... depend a lot on OS/... for example, for DOS there are
a few other sources I would likely attempt to use (specific common hardware
devices), and others which are specific to Windows or Linux (both of which
provide their own TRNGs, AFAIK based on entropy sources available to the OS
kernel).


'rdtsc' is just something available via the CPU, and so is essentially
"free"...

(and, yes, I didn't trust it at first, but it seems to hold up on what
statistical analysis tests I have used).

note: my analysis was based mostly on signal filtering and entropy
measurement (such as FIR / LPC based filtering, or DCT based analysis),
rather than bitwise tests (as usually used for PRNGs), given the specific
"signal" I was getting (a particularly weak source could be filtered into
being "silence").

No no no no no. One of the most important uses of "truly" random
processes for generating numbers is that of producing crypto keys.
You really, really don't want to offer any part of that process to a
remote machine.

yep...

granted, it does depend some on what he meant by this.

granted, a "random number server" would be a bad idea, but an app working as
a server would likely have enough "unique stuff" comming and going which it
could essentially "mine" as an entropy source, and this would be essentially
non-predictable from the outside (what all information has been seen, and
just how it has been all combined within the innards of the server).

 

[Default User]

I frankly don't think we can reasonably presume anything about what
the OP meant until and unless he explains it (which is why I asked for
clarification in another post).

I can't figure out why anyone is wasting time with this at all. The
idea of Bill writing a crypto program for his hard drive is laughable,
considering that he can't reliably write code the even opens files. Or
does anything else for that matter.




Brian

 

[Bill Cunningham]

Bill, if you're still reading this thread, you should know by now that
your use of the phrase "*real* random numbers" has sparked a long
discussion among people trying to guess what you actually meant.

So, what did you actually mean?

I think I'm looking for encryption algorithm. There has been a lot of
good advice here. Maybe the gpg as mentioned in an earlier post is what I'm
looking for I will have to chek into that. It seems to sound like the answer
I might be looking for.

Hope that helps.

Bill

 

[websnarf]

You seem determined to prove that claim by example.

How many people said the word "Fortuna" in their responses to Bill?
Quoting you was just a useful way to give an example of a totally
useless and wrong answer. But it appears I could literally have
quoted *anyone* else in this thread. That's just your penalty for
being first.

Feel free to post such an algorithm, then.

I described one ... do you not read or something? If you are looking
for something specific I cited "Fortuna".

Numbers aren't random. Number generation processes can be random.
?


You can mean that if you like, but it's a very humpty-dumpty way of
looking at randomness.

No. I am defining it *correctly*. You just don't realize the you are
*NOT*; and that that is your primary problem. If you can't generate
random numbers then no online poker website could possibly be in
operation without being hacked to death.

Look. People crack DVDs, HDMI, etc, even when there is little
monetary incentive. The reason is because there is no way to keep the
debugger out of a mainstream system -- i.e., they can't hide the
details, as much as they would want to. Its the nature of the problem
that makes it crackable. Yet poker sites; where there is a *LOT* of
monetary incentive remain relative unhacked (I won't claim totally,
but certainly many have been in long term operation, and are
profitable and "fair".) How could that be possible if you can't
generate random numbers? You think black hat hackers are less
incentivised by money than they are by mere copyright infringement?

But you can't, reasonably speaking, see /all/ an algorithm's possible
inputs, because (for any non-trivial algorithm) there are so many of
them.

Determinism is not about the size of the input; its about the fact
that you can *see* it.

The problem with a /seeder/ is that it is used as a start point for a
PRNG. PRNGs are, practically by definition, not random. Given
knowledge of the start state and the algorithm, you have 100%
predictive power.

Bill asked for *RANDOM*. He did not ask for an *UNBIASED
DISTRIBUTION* (which he might want -- I have a whole web page about
that; but he didn't ask for that). PRNGs are, at best, methods of
trying to achieve the latter, not the former.

The letter of what he's asking for is an entropy source, not a PRNG.
Good entropy sources are unpredictable, but not necessarily bias free.

No no no no no.

Yes yes yes yes yes.

[...] One of the most important uses of "truly" random
processes for generating numbers is that of producing crypto keys.

Correct. And how that is done is an interesting problem. Certainly
anyone who has used PGP knows about the whole "type a phrase" or
"wiggle your mouse" start up operation that it requests when you start
up the program (I'm not sure if it still does that or if GPG does, but
they have to do something comparable). Given your stance, perhaps you
think that PGP is not secure?

In any event, many secure protocols require that both sides produce
random numbers and use a bunch of encryption/decryption processes
going back and forth. The point is that to a third party observer
trying to read the information over the wire or from one side or the
other, what they see must be random. Its precisely because of the
multiple entities that makes this possible. The idea is that even if
you have a debugger or write your own man-in-the-middle or fake peer/
client, its of no use, because the other side is also producing
randomness (i.e., you are reduced to attacking the keys or the source
information).

You really, really don't want to offer any part of that process to a
remote machine.

Why not?

The logical conclusion of all your posturing, if they were realized as
actual objections, is that you should be able to hack any poker site
and just pour as much money as you like into your bank account. Is
that a reasonable position to be taking?

 

[Default User]

Because the abstract discussion is interesting on its own merits,
regardless of how much or how little credibility one feels able to
ascribe to the OP.

Then what the OP wants or doesn't want is immaterial.




Brian

 

[osmium]

Then what the OP wants or doesn't want is immaterial.

So what else is new?

 

[Seebs]

No. I am defining it *correctly*. You just don't realize the you are
*NOT*; and that that is your primary problem. If you can't generate
random numbers then no online poker website could possibly be in
operation without being hacked to death.

I have a keyfob that shows six digits. In thirty seconds, it will display
a different six digits.

Obviously, these numbers aren't random -- if they were, it wouldn't work
as a security token.

Just as obviously, you can't predict them by knowing what numbers it's shown
so far over a period of days, weeks, or months, or they would be trivial to
crack and would not offer effective security.

Conclusion: The value you're describing ("unpredictability") is not the same
as randomness.

-s

 

[Keith Thompson]

Look. People crack DVDs, HDMI, etc, even when there is little
monetary incentive. The reason is because there is no way to keep the
debugger out of a mainstream system -- i.e., they can't hide the
details, as much as they would want to. Its the nature of the problem
that makes it crackable. Yet poker sites; where there is a *LOT* of
monetary incentive remain relative unhacked (I won't claim totally,
but certainly many have been in long term operation, and are
profitable and "fair".) How could that be possible if you can't
generate random numbers? You think black hat hackers are less
incentivised by money than they are by mere copyright infringement?

[...]

It's possible either because the sites do use truly random numbers
(generated by something other than just an algorithm), or because
they use pseudo-random numbers that are sufficiently unpredictable
for their purposes.

Nobody said you "can't generate random numbers". You just can't
generate truly random numbers by a deterministic process. But for
some purposes you might not need to.

The OP asked for "*real* random numbers". A reasonable
interpretation of that phrase, though the OP apparently didn't
realize it, excludes pseudo-random numbers.

 

[BGB / cr88192]

"indeterministic" is the opposite of "deterministic" as I see it.

as I see it, a deterministic system is a system in which the results
can be generated from a finite (and typically known) set of rules.

And *therefore*, whether a system is deterministic depends on how much
knowledge you have about that system. For example, here is a set of
numbers, the last of which I have concealed from you. But *I* know
it.

40041 87595 86455 20463 74627 56958

To you, the rule for generating these numbers is unknown. To me, it is
known. So, for you, this system is non-deterministic. But for me, it
is highly deterministic. One might say that the randomness of the
sequence can be measured by one's inability to predict the next
number in that sequence. Thus, for me, what I might call the
"coefficient of randomness" [1] of the above sequence is 0.0, but for
you it is (probably) 0.99999 (i.e. you have one chance in 100,000 of
guessing it correctly). Of course, you might step outside the system
by guessing the rule. If your guess is correct, the randomness drops
to 0.0 for you, too.

[1] I am not sufficiently up on information theory to know whether
this "coefficient of randomness" is an exact analogue of the concept
of "entropy", but it is surely very close.

I disagree here, namely, I believe that whether or not a system is
deteministic is a part of the system, rather than a part of the observers.

just because a system is deterministic does not mean all observers will know
the state, or be able to draw predictions, but it will effect how the system
will behave in the long run...

Typical PRNGs are in fact not chaotic in the mathematical sense of the
word. A chaotic process is unpredictable in the long run, no matter
how much (finite) knowledge you have of the starting state. A typical
PRNG gives you 100% predictability if you know the algorithm and the
start state.

AFAIK, this statement is incorrect.

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

would seem to be in agreement with my understanding of the issue.

it would be a non-deterministic process which would be unpredictable, and
not a chaotic process, where a chaotic process remains deterministic, and
thus may be predicted given sufficient information (in much the same way as
a PRNG).


as I see it, a PRNG is a choatic deterministic process.

Um, no. Chaos is not randomness. Chaotic processes /are/
deterministic. They're unpredictable (in the long run), but not
random. (That doesn't mean you can't have a process that is partly
chaotic and partly random. As Ian Stewart rightly said, "chaos and
randomness are two sides of the same coin, except that it isn't a
coin and it doesn't have only two sides.")

as I say, we can "assume" this, regardless of the actual "universal" state
of things...

personally though, I believe that the universe is itself non-deterministic,
however, I also believe that the past/present/future distinction is
ultimately meaningless, as all exist essentially at the same time, but the
process is essentially a sort of asymmetric "cone" WRT entropy, which
essentially forces us to "move" along in a single direction WRT time (AKA:
the past has not "gone away", and the future is not "being made", rather it
just seems like this is the case...).

not that I believe in fatalism though, since, as I see this, this would be a
rather incorrect interpretation of the process (AKA: even if all of the
future and all of the past exist at the same time, there may exist far more
futures than there exist pasts, or it could be that the universe has already
"collapsed" onto a single outcome, and as such the eventual "fate" of
everything is already been decided, but even as such, free-will and freedom
of outcome will at least "appear" to exist...).

or, stated in another way:
there is no "guiding hand of fate" to force any particular output, and
infact people have full free will, only that the entire future state (every
decision to ever be made, everything to ever exist, ...) may already exist,
only that they are invisible from the present state.

(or something like this...).

Right.

either way, this was not the point of distinction, as I was saying, either
way, we can "assume" that the process is essentially random (or, at least,
it is very unlikely that this exact chain of events will be happening at
several different locations as to allow the RNGs to accidentially end up
with the same state).

Well, I think it does, actually.

(I think an important piece of context has been lost here...).


but, as I see it, randomness is not purely observer specific, and hence, as
I see it, a PRNG is not "random" even if it appears to be.

even though the sequences from a PRNG and TRNG may "look" exactly the same
(from a statistics POV), I have often observed that computationally, there
are many more subtle differences.

similarly, many specific algos may demand one but prohibit the other in
order to work correctly.

consider, for example:
GUID generation (kind of sucks with a PRNG);
permutative hashing/caches (totally breaks with anything other than a PRNG,
as a TRNG would essentially make it impossible to retrieve the information
again, since the ability to locate the information again depends purely on
the particular pseudo-random sequence...).


similarly, I use limited PRNGs in things like the code-generator for my
compiler (related to optimization and register allocation), however, any
variation from the strict deterministic sequence would essentially break the
compiler (by throwing passes out of sync, essentially throwing the whole
process into chaos...).

(granted, this sort of dependency between compiler passes is not exactly a
good thing, but to do things better at present would require essentially
re-engineering this whole section of the compiler...).

But how much the observer knows - even if it's only in a meta-sense -
will affect whether he considers a process to be deterministic.

potentially, however this may not matter, since he may guess one way or
another, and still be incorrect.

 

[websnarf]

I have a keyfob that shows six digits.  In thirty seconds, it will display
a different six digits.

Obviously, these numbers aren't random -- if they were, it wouldn't work
as a security token.

They are random to *YOU* (and to hackers, and to any outsider).

You are making a serious false dichotomy here. Its not random to the
inside of the secure system, regardless of how it works, but by its
very nature the whole system was built to make that as unobservable as
possible. I am willing to bet that the decryptor for that is just
some other dongle at the gatekeeper end of the secure system (with the
paired key) that is feed directly as a stream to that server. But the
more important point is that nobody knows what the state of the system
is, the other dongle's value, nor is there any straightforward way to
derive it. If that is the case and it is truly secure, then from your
point, or any outsider's point of view, those numbers *ARE* random.

Randomness is about point of view. If you can accurately model all
the atoms in a lava lamp (as someone else suggested) then you might
attempt to argue that that is not a random number generator either --
except the whole point is that you *CAN'T* do that. So its merely a
lack of ability for the observer to model the entropy exactly which
makes it random. So too it applies to your keyfob and its stream of
numbers. It *IS* random. That's the whole *POINT* of it. Its only
not random from the point of view of the inside of the security system
-- which nobody is supposed to be able to gain access to.

Just as obviously, you can't predict them by knowing what numbers it's shown
so far over a period of days, weeks, or months, or they would be trivial to
crack and would not offer effective security.

Conclusion:  The value you're describing ("unpredictability") is not the same
as randomness.

Ok, so let us say that you have to scenarios. In one you use your
keyfob as the seed for a PRNG and use its output as your random
stream. In the second you use something like a cosmic background
radiation detector or whatever you imagine is going to give you a
truly random seed.

Now give me an algorithm for determining the difference between those
two outputs. I.e., if I hand you one of the two streams (which I will
choose by a secret coin flip), you have to tell me which one I gave
you (assuming I could keep you from observing your own keyfob). You
may use any resource you like including the NSA, and the manufacturer
of your keyfob.

If you can't do it, then you can't say one is random and the other is
not. That's the whole point. If you can't *DETERMINE* the
difference, then they are equally random.

 

[Bill Cunningham]

I can't figure out why anyone is wasting time with this at all. The
idea of Bill writing a crypto program for his hard drive is laughable,
considering that he can't reliably write code the even opens files. Or
does anything else for that matter.

Not that anyone really cares what you or I think here atleast make
truthfull statements.

I'm outaa here.
Bill

 

[websnarf]

[...]> Look.  People crack DVDs, HDMI, etc, even when there is little

monetary incentive. The reason is because there is no way to keep the
debugger out of a mainstream system -- i.e., they can't hide the
details, as much as they would want to.  Its the nature of the problem
that makes it crackable.  Yet poker sites; where there is a *LOT* of
monetary incentive remain relative unhacked (I won't claim totally,
but certainly many have been in long term operation, and are
profitable and "fair".)  How could that be possible if you can't
generate random numbers?  You think black hat hackers are less
incentivised by money than they are by mere copyright infringement?

[...]

It's possible either because the sites do use truly random numbers
(generated by something other than just an algorithm), or because
they use pseudo-random numbers that are sufficiently unpredictable
for their purposes.

They use peer based PRNG seeding. At least the very public paper for
one online site that I read that explained it. I even tried to find a
flaw in their system, but they had actually thought of my objections
and covered them perfectly. There's no other method that's anywhere
near as practical or even as secure that I can think of. I have a
hard time believing that any site uses any different strategy.

I could just imagine these sites trying to rig up some cosmic ray
detector or lava lamps or whatever. Barely enough entropy for a
hundred rolls of the dice -- meanwhile, they are trying to deal maybe
a thousand hands per second. And what happens if the device fails?
That's just so truly not worth it. peer + server based accumulative
entropy is the only sensible way to go: the amount entropy scales with
the number of users; its perfect.

Nobody said you "can't generate random numbers".

Are you reading the same thread as I am?

"There is no such code without hardware that involves quantum-
mechanical behavior to generate the randomness. "

"No algorithm can produce a truly random number sequence."

"Deterministic computers can't generate actual random numbers."

"No, nobody can show you such code, whether as a skeleton, or a fully
developed package. Because there is no such thing - True random
numbers
from pure software are currently considered impossible."

Though in rereading the thread I must admit I missed William Ahern's
reply which is passable (though he still thinks a special device is
needed -- you don't need more than what a Pentium, a mouse/keyboard
and an end user already gives you, of course.)

[...]  You just can't generate truly random numbers by a deterministic process.  But
for some purposes you might not need to.

I don't even know what you are talking about here. I already gave the
definition of random. Your first sentence is just tautological with
the definition. "Truly random" is like "true logic" or "dark black"
or "quickly fast" or something like that ... what is the word "truly"
even doing there?

In the second, you are just questioning the motives of the OP. But I
have chosen not to, so there's no point in you directing that comment
towards me.

The OP asked for "*real* random numbers".  A reasonable
interpretation of that phrase, though the OP apparently didn't
realize it, excludes pseudo-random numbers.

If you are just talking about random, then you are really talking
about the entropy kind of random. PRNG's are a particular device for
helping generate unbiased streams from a typically entropic source
(for repeatable testing, its often desirable to make the seed
deterministic) but the OP made no mention of that, and therefore its
fair to assume that was not what he was asking for.

 

[Bill Cunningham]

I can't figure out why anyone is wasting time with this at all. The
idea of Bill writing a crypto program for his hard drive is laughable,
considering that he can't reliably write code the even opens files. Or
does anything else for that matter.

Not that anyone cares what you think but atleast make truthfull
statements.

Bill

 

[Phil Carmody]

Bill Cunningham a écrit :

This is a good one.

/*
A C-program for MT19937, with initialization improved 2002/1/26.
Coded by Takuji Nishimura and Makoto Matsumoto.

[192 lines deleted]

The code you posted appears to be an implementation of the Mersenne
Twister. My understanding is that it's a very good *pseudo*-random
number generator, but it doesn't generate truly random numbers
(nor can any algorithm).
Absolutely.

Bill: srand and rand themselves do not depend on the clock,
though the current time is often used as a seed. The Mersenne
Twister is likely to give you better pseudo-random numbers than
your implementation's rand(), but (a) they're still pseudo-random,
and (b) you still have to provide it with a seed.

(b) is _vital_. Most people who use and recommend MTs tend to simply
be wowwed by its period, and are completely ignorant about correct
use. They'll seed it with some low entropy source, and then generate
many thousands of incredibly predictable values. The correlation is
so strong that most time I see use of an MT I *presume* ignorance
about PRNGs.

<OT>
Take a look at /dev/random and /dev/urandom if your system provides
them.
</OT>

What are you *really* trying to accomplish?

Almost certainly something which does not require a true RNG. For
most hobby tasks, a blend of a few trivial (period 2^64-ish) PRNGs is
more than enough. George Marsaglia has published C sources for this.
(Sci.crypt seems a likely location for such info.)

Phil

 

[Bill Cunningham]

His statement certainly looks true to me. That is not intended to be
an attack on you. Objectively speaking, your current level of C
knowledge is barely sufficient for you to write a temperature
conversion program, let alone an encryption program that could
actually have a use for genuine randomly-generated numbers.

The best way for you to address this would be to learn more about C,
and endeavour to retain that knowledge, perhaps by writing it down.

Perhaps but but I can open strreams, and write and read files. That was
what I got out of his statement. I am looking at gpg anyway. It was
suggested so I'm going to see what it does.

Bill