Random Seed Generation

Discussion in 'privacy technology' started by n33m3rz, Mar 8, 2009.

Thread Status:
Not open for further replies.
  1. n33m3rz

    n33m3rz Registered Member

    Joined:
    Jan 10, 2009
    Posts:
    114
    So I can find a lot of algorithms for random number generation (blum blum shub) but as far as seed generation goes that is much less documented. Of course a PRNG depends a great deal on a very random seed. How does this algorithm sound for random seed generation, using whirlpool as the hash function?

    Go easy on me please, this is the first time I tried to design a random seed generating program so if I made any naive (or retarded) errors keep in mind I never said I was a pro ;-) (or mentally competent!)

    Breakdown: The user is initially asked to randomly hit on their keyboard and hit a button called "Finish Initializing Seed" after they are done. Each time they press a key the microseconds between the key press (and initialization for the first key) are logged and stored as a string (B1, B2, B3, etc). After the user has hit random keys on the keyboard for a while, they hit the "Finish Initializing Seed" button and provided they have hit at least 50 characters, the string of characters they entered is whirlpool hashed, and then the resulting hash has (B1, B2, B3...etc) added to it and this is then also whirlpool hashed to get the initial seed (Z).

    Breakdown: In this stage the user is presented with a large box in which they are to move their mouse around. They must move the mouse for at least thirty seconds and click the mouse button at least fifty times. Every microsecond, E (first value being Z) + the current X-Y mouse coordinate is hashed with whirlpool to result in a new E. This process continues for the duration of this stage.

    As the user moves there mouse around the box and clicks, each time they click a value M is generated which is the X-Y coordinates of the mouse when clicked. Each time they pause and then continue to move the mouse the microseconds of the pause are recorded as D. Microseconds between the mouse being clicked (between new M values) are recorded as L.

    When the user has finished moving the mouse around long enough for their liking, they will click a "Finish Generating Seed" button. Provided they clicked the mouse fifty times and moved it around the screen for thirty seconds, a whirlpool hash value is taken of the whirlpool value of P combined with the whirlpool value of Q to create the random seed.

    Breakdown: The random seed is split into two parts, the first 64 characters of the whirlpool hash and the second 64 characters. These two values are then converted to binary, and from binary to decimal. These two decimal numbers are tested for primality using the Miller-Rabin primality test, and multiple whirlpool iterations are done (growing exponentially in the number of numbers tested) until two prime numbers are found. Both prime numbers will be 512 bits (1/2 of a whirlpool hash being 64 characters and 64 * 8 being 512).

    The generated primes will be used to seed (Represent P and Q) a pseudo random number generator such as blum blum shub.
     
    Last edited: Mar 8, 2009
  2. coderman

    coderman Registered Member

    Joined:
    Feb 12, 2009
    Posts:
    39
    first off, you don't want to code your own entropy gathering and mixing. this is hard and you'll get it wrong; your estimations of entropy in the previous post are way too generous. CryptGenRandom() is a good start for win32, and can be combined with other entropy sources for good seed entropy. see Gnu Privacy Guard's rndw32.c implementation if you decide to go this route.

    second, you want to use an existing cryptographically secure PRNG like Fortuna or Yarrow. preferably Fortuna: http://en.wikipedia.org/wiki/Fortuna_(PRNG) . blum blum shub is an excessive amount of work for the bits generated.

    last but not least, physical entropy sources (true random number generators) are more common these days across Intel/AMD/Via architectures. a hardware RNG is the best solution if you are concerned about entropy density and integrity.

    note that even with a hardware RNG you need an entropy gathering daemon to validate the bits from the physical sources against FIPS sanity checks before mixing into the host or application entropy pool. it is also recommended practice to mask any potential generator bias with a block cipher or digest on the raw RNG output before mixing into the pool.

    like the debian openssl flaw demonstrated, crypto is critical and best left to the experts. even the most subtle and seemingly inconsequential error in implementation can nullify all of the privacy expected by the ciphers and protocols layered above these critical crypto primitives.

    best regards,
     
  3. n33m3rz

    n33m3rz Registered Member

    Joined:
    Jan 10, 2009
    Posts:
    114
    Thanks a ton for the advice. Yeah heh I figured it would be better to use a professional seed generating algorithm, but despite a ton of PRNGs I couldn't for the life of me find a seed generator (that uses user input, I am not a big fan of it seeding itself with system data). I guess I will keep looking around for one, but better to try and find a pro one than try and make one and fail at it. Security > everything else. Thanks for your suggestions. Sometimes the best advice is to not even try it ;-).

    Fortuna seems to rely on windows registry?

    If you have any advice on a seed generator it would be greatly appreciated, and again thank you so much for the continued advice it is quite helpful =). PRNG I can figure out, generating seed for PRNG has been a headache to say the least.
     
    Last edited: Mar 8, 2009
  4. n33m3rz

    n33m3rz Registered Member

    Joined:
    Jan 10, 2009
    Posts:
    114
    Ok I did more research (a lot of which was based on your feedback, thanks!) and think I have found an acceptable solution. We will use the windows CryptGenRandom() function in windows implementations, and /dev/random in linux, mac etc implementations, and will take the values obtained from them and use them as variables. The variables will be combined with the output of a self made algorithm/program that attempts to extract and mix entropy from keyboard and mouse events, and the two will be hashed together. It is my understanding that even if the randomness obtained from CryptGenRandom() or /dev/random was combined with a known plaintext that is totally non random, that the resulting hash string will be as random as the random input.

    I feel this is safe as we will be using the OS native (hopefully expertly designed) entropy algorithms as a sort of safety net (the resulting entropy will be no weaker than the entropy of the most random variable), so even if a critical flaw exists in our own user input entropy algorithm, it will not result in a critical security failure (but would result in needless CPU time).

    Am I correct in understanding this, and do you think this is a wise choice?
     
  5. coderman

    coderman Registered Member

    Joined:
    Feb 12, 2009
    Posts:
    39
    assuming you don't mess up implementation in the application, that will provide a good source of entropy.

    combining 95% entropy and 50% entropy still gives you 95%, so there is no harm in conservatively mixing multiple sources. this is why most hardware entropy sources have two or more physical oscillator circuits. if one fails you have a back up and while both are working you've got an abundance of throughput and/or more conservative densities.

    best regards,
     
    Last edited: Mar 9, 2009
  6. n33m3rz

    n33m3rz Registered Member

    Joined:
    Jan 10, 2009
    Posts:
    114
    Sweet thanks man. Also thanks for helping me with my terminology. I know a bit about encryption but am not a pro, and also until recently I knew next to nothing about how exactly to gather entropy / make seeds / etc...
     
Loading...
Thread Status:
Not open for further replies.