Re: OT: RFC, PRNG

cr88192 wrote:
for a project of mine, I have needed a fairly special PRNG. the point is to have a sufficiently large amount of entropy that it generates hopefully-unique strings.

There's nothing special about that -- any PRNG worthy of the name satisfies that criterion, if you ask it for enough bits (and no PRNG can possibly satisfy it if you don't ask for enough).

PRNGs have been extensively studied, and some good ones are known, and some of those have public domain C implementations. You should use one of them. You shouldn't try to design your own, because it's very hard. (Actually, your requirements are weak enough that even a weak PRNG /might/ satisfy them, but there's still no reason not to use a good one.)

I don't have access to '/dev/urandom', because in part, I am currently running on windows.

The Windows equivalent is CryptGenRandom(). You should probably use it, because it's probably the most easily obtainable source of good seed randomness on Windows, and you need that no matter which PRNG you use.

I am mostly just hoping that the probability of clashes is sufficiently low that they are unlikely in practice (anything much beyond 1.0/2^32 would probably be fine).

With any decent PRNG, you'll need to generate around 2^48 96-bit numbers before you get a clash (birthday paradox). In certain situations you can guarantee 2^96 distinct numbers (in a pseudorandom order) before a repeat, but that won't work if you have many installations running in parallel.

You also need at least 96 bits of /good/ entropy to seed your generator, or else that will be the limiting factor. The entropy you get from timing tricks is not very good.

they are for compiler-generated names, aka a gensym mechanism.
in the past, I had used a special prefix and sequential numbers, but this wont work if the files are stored externally.

It will if the prefix is random. At program startup get some random bits from CryptGenRandom, and then simply append increasing natural numbers to the end. This will work just as well for avoiding collisions, and you won't need a PRNG at all.

-- Ben
.

Relevant Pages

  • Re: new /dev/random
    ... For a proper PRNG, with the assumption that the algorithms are robust, ... is said to contain 40 bits of entropy if I could, ... If I want to attack a stream of 56 bits produced by a PRNG with a seed ... RNG resistance therefore relies on the same two classes of assumptions ...
    (sci.crypt)
  • Re: new /dev/random
    ... > is said to contain 40 bits of entropy if I could, ... > efficient attack would be to try the exhaustive search on the seed. ... > than the PRNG: evolution of computer science (the robustness of the ... > because, for a given length of random bits requested, the RNG will have ...
    (sci.crypt)
  • Re: strengthening /dev/urandom
    ... >>delivering true randomness should be somehow like the shelves ... >>has certain commodities in reserve. ... >>document that doesn't need any entropy. ... First discuss whether 'any' PRNG is needed. ...
    (sci.crypt)
  • Re: modulo
    ... [re one-time pads] ... PRNG has bits of entropy, then you no longer have a true OTP. ... call it a one-time pad, and I think a cryptographer would, too. ...
    (comp.programming)
  • Re: Key entropy, stream entropy, block entropy, block population entropy AKA uniique stream length
    ... output (PRNG block) from the internal states. ... Now I encrypt with the key-stream. ... entropy and nothing will change that. ... Now, you say, "But those key-streams (permutations) are not the only ...
    (sci.crypt)