Discussion:
True random number generator
Arnaud Carr?
2004-10-03 14:19:48 UTC
Hi,

I want to do a random number generator, using sampling of an external
source of entropy. I read somewhere on the net that sampling entropy
source is not necessary random data. Generally, sampled entropy must
be "blended" with strong HASH function. Let's say I choose MD5 as hash
function ( I know MD5 is not reputed as secure as SHA for signature,
but it's quite ok for my purpose ).
What's the best way to combine my entropy sampling and the HASH func ?
I though of this, tell me if you see any problem:

a) Sample 128 bits of entropy source
b) "MD5" it
c) output the 128bits Md5 result as random value
d) goto a)

Is it "good" for random ? What's the improvement if I repeat several
times b) on itself ?

Second question: As my sampling processing is quite slow (as often
with sampling), do you think it's ok for a "crypto secure" random
generator to do this:

a) Sample 128bits of entropy source
begin a loop of, say, 4 passes
b) Md5 it
c) output 128bits
end of loop

So I generate 128*4=512bits of random numbers with only 128bits of
entropy source.
What do you think of that idea ?

Generally, how does work a "cryptographic" secure random generator (
more precisly how is mixed the entropy sampling with the HASH function
?)

Arnaud
News Subsystem
2004-10-05 06:22:31 UTC
Post by Arnaud Carr?
( I know MD5 is not reputed as secure as SHA for signature,
but it's quite ok for my purpose ).
MD5 will not probably be ok for this purpose (you should use a hash
function that has not been broken).
Post by Arnaud Carr?
What's the best way to combine my entropy sampling and the HASH func ?
a) Sample 128 bits of entropy source
b) "MD5" it
c) output the 128bits Md5 result as random value
d) goto a)
In d) I would output c) XOR a) [instead of c) only]
This will enrich the entropy and will prevent the system from relying
completely on the strength of the hash function.
Post by Arnaud Carr?
Is it "good" for random ? What's the improvement if I repeat several
times b) on itself ?
Redundant (and in some cases it might actually reduce the amount
entropy).
Post by Arnaud Carr?
Second question: As my sampling processing is quite slow (as often
with sampling), do you think it's ok for a "crypto secure" random
a) Sample 128bits of entropy source
begin a loop of, say, 4 passes
b) Md5 it
c) output 128bits
end of loop
Again, you are completely relying on the strength of the hash
function. Depending on your threat model and on the level of security
you are targeting, you might want to avoid doing so.
David Eather
2004-10-05 16:21:52 UTC
Post by News Subsystem
Post by Arnaud Carr?
( I know MD5 is not reputed as secure as SHA for signature,
but it's quite ok for my purpose ).
MD5 will not probably be ok for this purpose (you should use a hash
function that has not been broken).
MD5 would be fine. You are not using it as a cryptographic hash function
but as a pseudeo random number generator and as a function to concentrate
the entropy.
Post by News Subsystem
Post by Arnaud Carr?
What's the best way to combine my entropy sampling and the HASH func
a) Sample 128 bits of entropy source
b) "MD5" it
c) output the 128bits Md5 result as random value
d) goto a)
In d) I would output c) XOR a) [instead of c) only]
This will enrich the entropy and will prevent the system from relying
completely on the strength of the hash function.
Better is to grab the 512 bits in one go and input that into the hash
function rather than have 4 goes at it.
MD5 is fine you don't need a cryptographically strong hash function - only a
randomising function.
Post by News Subsystem
Post by Arnaud Carr?
Is it "good" for random ? What's the improvement if I repeat several
times b) on itself ?
Redundant (and in some cases it might actually reduce the amount
entropy).
Agreed.
Better is to grab the 512 bits in one go and input that into the hash
function rather than have 4 goes at it.
MD5 is fine you don't need a cryptographically strong hash function - only a
randomising function.
Post by News Subsystem
Post by Arnaud Carr?
Second question: As my sampling processing is quite slow (as often
with sampling), do you think it's ok for a "crypto secure" random
a) Sample 128bits of entropy source
begin a loop of, say, 4 passes
b) Md5 it
c) output 128bits
end of loop
Again, you are completely relying on the strength of the hash
function. Depending on your threat model and on the level of security
you are targeting, you might want to avoid doing so.
News Subsystem
2004-10-09 19:06:18 UTC
On Tue, 5 Oct 2004 16:21:52 +0000 (UTC), "David Eather"
Post by David Eather
Post by News Subsystem
Post by Arnaud Carr?
( I know MD5 is not reputed as secure as SHA for signature,
but it's quite ok for my purpose ).
MD5 will not probably be ok for this purpose (you should use a hash
function that has not been broken).
MD5 would be fine. You are not using it as a cryptographic hash function
but as a pseudeo random number generator and as a function to concentrate
the entropy.
Post by News Subsystem
Post by Arnaud Carr?
What's the best way to combine my entropy sampling and the HASH func
a) Sample 128 bits of entropy source
b) "MD5" it
c) output the 128bits Md5 result as random value
d) goto a)
In d) I would output c) XOR a) [instead of c) only]
This will enrich the entropy and will prevent the system from relying
completely on the strength of the hash function.
Better is to grab the 512 bits in one go and input that into the hash
function rather than have 4 goes at it.
MD5 is fine you don't need a cryptographically strong hash function - only a
randomising function.
What if MD5 output is biased? For instance, if two thirds of generated
MD5 hashes show some pattern? We do not know yet, but MD5 has been
broken, so it is not unlikely. I believe that this should be a concern
when building a cryptographically strong random number generator.
David Eather
2004-12-14 05:04:13 UTC
there
would have been no conflict and no frustration generated by them.)

49. For primitive societies the natural world (which usually changes
only slowly) provided a stable framework and therefore a sense of
security. In the modern world it is human society that dominates
nature rather than the other way around, and modern society changes
very rapidly owing to technological change. Thus there is no stable
framework.

50. The conservatives are fools: They whine about the decay of
traditional values, yet they enthusiastically support technological
progress and economic growth. Apparently it never occurs to them that
you can't make rapid, drastic changes in the technology and the
economy of a society with out causing rapid changes in all other
aspects of the society as well, and that such rapid changes inevitably

51.The breakdown of traditional values to some extent implies the
breakdown of the bonds that hold together traditional small-scale
social groups. The disintegration of small-scale social groups is also
promoted by the fact that modern conditions often require or tempt
individuals to move to new locations, separating themselves from their
communities. Beyond that, a technological society HAS TO weaken family
ties and local communities if it is to function efficiently. In modern
society an individual's loyalty must be first to the system and only
secondarily to a small-scale community, because if the internal
loyalties of small-scale small-scale communities were stronger than
loyalty to the system, such communities would pursue their own
advantage at the expense of the system.

52. Suppose that a public official or a corporation executive appoints
his cousin, his friend or his co-religionist to a position rather than
appointing the person best qualified for the job. He has permitted
a***@gmail.com
2004-12-11 07:16:27 UTC
Post by Arnaud Carr?
( I know MD5 is not reputed as secure as SHA for signature,
but it's quite ok for my purpose ).
I don't know your purpose. If you say so, than probably MD5 is OK.
generator"
rather than to global solutions.
And if you are bulding a cryptographically strong random generator than
this what you've mentioned is far away from "strong".
a***@gmail.com
2004-12-14 04:03:35 UTC
the American Constitution went into effect, yet there
was more personal freedom in pre-industrial America, both before and
after the War of Independence, than there was after the Industrial
Revolution took hold in this country. We quote from "Violence in
America: Historical and Comparative perspectives," edited by Hugh
Davis Graham and Ted Robert Gurr, Chapter 12 by Roger Lane, pages
476-478: "The progressive heightening of standards of property, and
with it the increasing reliance on official law enforcement (in 19th
century America). . .were common to the whole society. . .[T]he change
in social behavior is so long term and so widespread as to suggest a
connection with the most fundamental of contemporary social processes;
that of industrial urbanization itself. . ."Massachusetts in 1835 had
a population of some 660,940, 81 percent rural, overwhelmingly
preindustrial and native born. It's citizens were used to considerable
personal freedom. Whether teamsters, farmers or artisans, they were
all accustomed to setting their own schedules, and the natu