Random numbers seeded with System.currentTimeMillis

Discussion in 'Java' started by Roedy Green, Mar 3, 2006.

  1. Roedy Green

    Roedy Green Guest

    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

    --
    Canadian Mind Products, Roedy Green.
    http://mindprod.com Java custom programming, consulting and coaching.
     
    Roedy Green, Mar 3, 2006
    #1
    1. Advertising

  2. Roedy Green

    Guest

    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
    >
    > --
    > Canadian Mind Products, Roedy Green.
    > http://mindprod.com Java custom programming, consulting and coaching.


    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/
     
    , Mar 4, 2006
    #2
    1. Advertising

  3. Roedy Green

    Daniel Dyer Guest

    On Sat, 04 Mar 2006 11:02:31 -0000, <> wrote:

    >
    > 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
    >>
    >> --
    >> Canadian Mind Products, Roedy Green.
    >> http://mindprod.com Java custom programming, consulting and coaching.

    >
    > 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.

    --
    Daniel Dyer
    http://www.dandyer.co.uk
     
    Daniel Dyer, Mar 4, 2006
    #3
  4. Roedy Green

    Roedy Green Guest

    Roedy Green, Mar 4, 2006
    #4
  5. wrote:

    > 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
     
    tom fredriksen, Mar 9, 2006
    #5
  6. Roedy Green

    Daniel Dyer Guest

    Re: ----- Mersenne Twister -----

    On Thu, 09 Mar 2006 18:40:58 -0000, tom fredriksen <> wrote:

    > wrote:
    >
    >> 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.


    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
    http://www.dandyer.co.uk
     
    Daniel Dyer, Mar 9, 2006
    #6
  7. Roedy Green

    Daniel Dyer Guest

    Re: Random numbers seeded with System.currentTimeMillis (Was: accidentally cut-and-pasted junk)

    On Thu, 09 Mar 2006 20:33:04 -0000, Daniel Dyer
    <> wrote:
    >


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

    Sorry,

    Dan.

    --
    Daniel Dyer
    http://www.dandyer.co.uk
     
    Daniel Dyer, Mar 9, 2006
    #7
  8. Re: ----- Mersenne Twister -----

    Daniel Dyer wrote:
    > On Thu, 09 Mar 2006 18:40:58 -0000, tom fredriksen <> wrote:
    >
    >> wrote:
    >>
    >>> 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.

    >
    > 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
     
    tom fredriksen, Mar 9, 2006
    #8
  9. Roedy Green

    Daniel Dyer Guest

    On Thu, 09 Mar 2006 21:08:24 -0000, tom fredriksen <> wrote:

    > Daniel Dyer wrote:
    >> 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.


    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.
    >
    > > (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)


    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.


    --
    Daniel Dyer
    http://www.dandyer.co.uk
     
    Daniel Dyer, Mar 9, 2006
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Nelson
    Replies:
    17
    Views:
    9,185
    Darryl L. Pierce
    May 20, 2004
  2. Jerry

    System.currentTimeMillis()

    Jerry, Aug 3, 2005, in forum: Java
    Replies:
    18
    Views:
    46,468
    Thomas G. Marshall
    Aug 6, 2005
  3. Alex
    Replies:
    15
    Views:
    2,711
  4. neoedmund
    Replies:
    1
    Views:
    1,184
  5. tak
    Replies:
    6
    Views:
    2,379
    James Kanze
    Sep 28, 2007
Loading...

Share This Page