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
