Random numbers seeded with System.currentTimeMillis

[Roedy Green]

What happens when you seed your Random number generator with the
current time?

If I knew for example that you did that between 12:00 and 12:05, there
are only

5*60*1000 = 300,000 possible seeds you could have used, each of which
starts off a predetermined chain of "random" numbers.

If I know a few of your results, I can with brute force figure out
which seed you used, and hence PREDICT your entire stream of random
numbers.

This is one reason you use SecureRandom instead of Random for any sort
of process where you don't want people guessing the seed, e.g. in
generating lottery results or generating passwords.

see http://mindprod.com/products1.html#PASSWORD

 

[iksrazal]

Roedy Green escreveu:

What happens when you seed your Random number generator with the
current time?

If I knew for example that you did that between 12:00 and 12:05, there
are only

5*60*1000 = 300,000 possible seeds you could have used, each of which
starts off a predetermined chain of "random" numbers.

If I know a few of your results, I can with brute force figure out
which seed you used, and hence PREDICT your entire stream of random
numbers.

This is one reason you use SecureRandom instead of Random for any sort
of process where you don't want people guessing the seed, e.g. in
generating lottery results or generating passwords.

see http://mindprod.com/products1.html#PASSWORD

Have you looked at java 5.0 java.util.UUID getRandom() ? UUID type 4
has 2^122 bits and is a standard that both java and m$ recognize.
Internally, java.util.UUID uses SecureRandom.

http://en.wikipedia.org/wiki/UUID
http://www.asciiarmor.com/blog/default/2005/01/03/C62D35145B8464302800D42AB64B5036.txt

BTW, UUID type 1 has an associated time stamp. However, java can parse
type 1 but cannot generate them. Some other implementations, such as
jakarta commons-id might though.

HTH,
Robert
http://www.braziloutsource.com/

 

[Daniel Dyer]

Roedy Green escreveu:


Have you looked at java 5.0 java.util.UUID getRandom() ? UUID type 4
has 2^122 bits and is a standard that both java and m$ recognize.
Internally, java.util.UUID uses SecureRandom.

http://en.wikipedia.org/wiki/UUID
http://www.asciiarmor.com/blog/default/2005/01/03/C62D35145B8464302800D42AB64B5036.txt

BTW, UUID type 1 has an associated time stamp. However, java can parse
type 1 but cannot generate them. Some other implementations, such as
jakarta commons-id might though.

I seem to have missed Roedy's post so I'll reply to this one. This link
is an interesting story of how pseudorandom numbers can be exploited
(though the page doesn't render very well in Opera or IE):

"How we learned to cheat at online Poker"
http://www.developer.com/java/other/article.php/616221

Dan.

 

[Roedy Green]

has 2^122 bits

It has 122 bits giving 2^122 possible different values.

see http://mindprod.com/jgloss/pseudorandom.html#UUID

 

[tom fredriksen]

Have you looked at java 5.0 java.util.UUID getRandom() ? UUID type 4
has 2^122 bits and is a standard that both java and m$ recognize.
Internally, java.util.UUID uses SecureRandom.

According to the documentation of UUID it should produce a "pseudo
random number", which is not as strong as a cryptographically secure
random number. A crypto number is cleansed of any statistical
nonrandomness that could exists in the number, while a pseudo random
number is not free of that can be determined by way of different algorithms.

The fact that this specific implementation of UUID uses SecureRandom,
is an implementation detail and is not part of the contract, hence you
should not use it for that.

/tom

 

[Daniel Dyer]

According to the documentation of UUID it should produce a "pseudo
random number", which is not as strong as a cryptographically secure
random number. A crypto number is cleansed of any statistical
nonrandomness that could exists in the number, while a pseudo random
number is not free of that can be determined by way of different
algorithms.

How exactly do you "cleanse" a number of its non-randomness? Take the
number 7, is that random enough? If not, what will it look like when it
has been cleansed of its non-randomness?

Many (most?) cryptographically strong random number generators are
pseudo-random number generators, though they may be seeded from "true"
sources of randomness. The reason that they are preferred to other PRNG
implementations for sensitive applications has nothing to do with the
statistical properties of the output. I can see what you are getting at
though, it's to do with predictability. It is because, even with
knowledge of the algorithm being used, it is computationally infeasible to
reverse engineer the state of a cryptographically strong generator from
observations of its output. This is because cryptographically strong
PRNGs are typically based on ciphers or secure hash algorithms (the
default Java SecureRandom implementation, on Windows platforms at least,
is based on SHA-1). These non-linear transformations are designed to be
practically impossible to reverse since they are more typically used for
encryption. This is important because if you could reverse engineer the
state of the generator you could predict all of its future output.

Dan.

 

[Daniel Dyer]

I seem to have magically changed the title of this thread to something
confusing with some careless cut-and-pasting.

Sorry,

Dan.

 

[tom fredriksen]

How exactly do you "cleanse" a number of its non-randomness? Take the
number 7, is that random enough? If not, what will it look like when it
has been cleansed of its non-randomness?

Many (most?) cryptographically strong random number generators are
pseudo-random number generators, though they may be seeded from "true"
sources of randomness. The reason that they are preferred to other PRNG
implementations for sensitive applications has nothing to do with the
statistical properties of the output.

Its the input the must be statistically cleansed for the output to be
truly random. for example, if you are using the network as an entropy
for a number generator, you need about 2.5 bits per packet as a starting
pointy to construct a truly random number. After getting enough data you
need to create a secure hash to further remove any statistical non
randomness. So creating cryptographically strong random number are not
easy or fast.

Have a look at the book "Secure programming cookbook for c and c++" by
john viega and Matt Mesier. It has an 80 pages chapter on random number,
it should explain everything perfectly.

(the default Java SecureRandom implementation, on Windows platforms

at > least, is based on SHA-1)

Just so you know, SHA-1 was found to have a too large collision rate to
be acceptable last year, so the advice now is to move to SHA-256,
SHA-512 or create an entirely new one. (See Bruce Schneiers blog for
more info)

FYI, if you want to use the best secure methods for communication or for
random numbers, you should not use commercial implementations but
open-source 3rd party libraries of industry wide reputable origin, such
as cryptix.

/tom

 

[Daniel Dyer]

Its the input the must be statistically cleansed for the output to be
truly random. for example, if you are using the network as an entropy
for a number generator, you need about 2.5 bits per packet as a starting
pointy to construct a truly random number. After getting enough data you
need to create a secure hash to further remove any statistical non
randomness. So creating cryptographically strong random number are not
easy or fast.

OK, sorry I seem to have misunderstood what you were proposing in your
previous message. It read like you could take a single number and "make
it more random", which doesn't make much sense.

Have a look at the book "Secure programming cookbook for c and c++" by
john viega and Matt Mesier. It has an 80 pages chapter on random number,
it should explain everything perfectly.

at > least, is based on SHA-1)

Just so you know, SHA-1 was found to have a too large collision rate to
be acceptable last year, so the advice now is to move to SHA-256,
SHA-512 or create an entirely new one. (See Bruce Schneiers blog for
more info)

I'm aware of that, and take your point that for new applications SHA-1 is
not advisable, but it doesn't change the fact that Sun use that as the
default on Windows (not on Linux, as I discovered the other day if you
were following the other thread about RNGs). Ferguson and Schneier
advocate a block cipher such as AES, Twofish or Serpent as the basis for
their Fortuna design, with SHA-256 used where hashing is required.

Dan.