unpredictableSeed

[Dmitry Olshansky]

03-Mar-2013 12:58, Ivan Kazmenko пишет:
>> Can anyone advise on the theoretical basis for the unpredictableSeed
>> method in std.random?  I've tried googling around for the theory of
>> good thread-safe seed generation methods but haven't really found
>> anything. :-(
>
> I have to ask: what would be a good unpredictableSeed by definition?
> With the current implementation, three downsides come to my mind:
>
> 1. Process ID, thread ID and system tick are insecure sources of
> randomness and can provide just a few bits of randomness in certain
> situations.  I don't know how to address this in a portable way.

Do some cheap syscalls and measure effective latency, look at 
nanoseconds and such. It would give you a bit of good enough noise due 
to unpredictable mess of context switches in the OS.

> 2. Once we know the first seed, it is easy to predict all subsequent
> seeds.  A solution would be to use a secure RNG instead, not just the
> one which gives away its state.

Indeed would be nice to obtain each seed separately (and preferably by 
different means). That being said hashing and PRNG-ing of some initial 
vector is fine for basic unpredictable seed. (just don't include 
init-vector in the seed itself)

> 3. It would be a particularly bad idea to initialize MinstdRand0
> instances with consecutive unpredictableSeeds and then consider them
> independent.  This is just a consequence of a particular choice of RNG
> on the previous step.

> So, which of these do you consider the real problems, and what more do
> you need from unpredictableSeed?


AFAIK there are OS APIs that give you proper secure seeds.
Somewhere in Windows Crypto API:
http://msdn.microsoft.com/en-us/library/windows/desktop/aa379942(v=vs.85).aspx

Must be something equivalent for POSIX.

Also upcoming hardware like Intel's Ivy chips, and a lot of ARMs do have 
hardware random generators. Plus the devices that do generate true 
entropy. This would be a nice enhancement for std.random to include 
support for these and secureSeed (as opposed to "unpredictable").

There is a difference between seriously unpredictable (good enough for 
monte-carlo, games etc.) and cryptographically good - an overkill for 
monte-carlo and such, but a MUST for e.g. private key generation.




-- 
Dmitry Olshansky