15

My application would like to get a random number, preferably with entropy if available, but does not need cryptographic quality, and would like to do ensure that the call does not block if the system entropy pool is depleted (e.g. on a server in a farm).

I am aware of CryptGenRandom, but its behaviour with respect to blocking under adverse entropy conditions is not specified.

On Unix, /dev/urandom supports this use case. Is there equivalent functionality available on Windows? I would prefer to avoid using a non-system RNG simply to get non-blocking semantics.

Ian Boyd
  • 246,734
  • 253
  • 869
  • 1,219
mabraham
  • 2,806
  • 3
  • 28
  • 25
  • 1
    Uhm, where did you read that `CryptGenRandom` may block? Still, for non-crypto applications you can use "regular" PRNGs, perhaps as easy as a "dumb" LCG. – Matteo Italia Feb 26 '14 at 18:10
  • CryptoGenRandom says it relies on hardware state changes to fill its entropy pool, and its documentation does not specify its behaviour if the pool is empty. So it might block. I need a solution that will not block, not one whose blocking behaviour is unspecified. I could indeed use an external RNG, but I asked if there was equivalent functionality already available in Windows. Question updated. – mabraham Feb 27 '14 at 09:14
  • 1
    Are you asking if there is a function that never runs out of entropy, or are you asking if there is a function that fails instead of blocking if there is no entropy at the moment? – sashoalm Sep 09 '14 at 08:40
  • I asked for a call that returns a random number without blocking. I didn't ask for a call that fails if there is no entropy. Current proposed answers are for questions other than the one I have asked. – mabraham Sep 11 '14 at 14:35

3 Answers3

3

For a toy application, you could use the standard library function rand(), but the implementation on Windows is of notoriously poor quality. For cryptographically secure random numbers, you can use the rand_s() standard library function.

A better bet is simply to include a suitable pseudo-random number generator in your program. The Mersenne Twister is a good choice IMO, particularly as there are plenty of available implementations (including in the C++11 standard library and in Boost).

Ian Boyd
  • 246,734
  • 253
  • 869
  • 1,219
al45tair
  • 4,405
  • 23
  • 30
  • *Any* pseudo-random number generator has no entropy whatsoever. The question is asking for a source that has entropy. – Mark Ransom Feb 26 '14 at 17:59
  • @MarkRansom Disagree. The OP says explicitly that he “does not need cryptographic quality”, but does not want the call to block. – al45tair Feb 26 '14 at 18:00
  • 1
    @HansPassant It’s in the MSVC standard library. It’s also in the Windows NT crtdll (which isn’t part of MSVC, but actually *is* part of Windows). – al45tair Feb 26 '14 at 18:54
  • It is a CRT implementation, it doesn't have anything to do with the operating system. You can't even call it, there's no import library for it. – Hans Passant Feb 26 '14 at 18:56
  • 1
    There’s no point arguing about this. crtdll *is* part of Windows, and you can easily call functions in it if you like; you could even generate your own import library (it isn’t hard). The MSVC runtime is arguably part of Windows as well, given that it’s always installed and other (non-Microsoft) compilers make use of it. – al45tair Feb 26 '14 at 19:00
  • 1
    @alastair: Windows is not a Microsoft Visual C/C++ Run-Time delivery channel - http://blogs.msdn.com/b/oldnewthing/archive/2014/04/11/10516280.aspx – Mike Dimmick Jul 17 '14 at 13:40
  • 1
    @MikeDimmick I don't dispute that, or the comments in that article. However, the fact is that 99% of Windows software uses Microsoft's runtime, whether one of the ones that ships with Windows itself (which Microsoft obviously hates people using), or the one that comes with Visual C++. – al45tair Jul 17 '14 at 17:06
  • 1
    @MikeDimmick If it was the case that a substantial proportion of software linked against e.g. Intel, IBM or Borland runtimes, maybe I wouldn't regard the Visual C runtime as a de-facto part of Windows. But that isn't so. – al45tair Jul 17 '14 at 17:08
1

If I need non-blocking behaviour on random numbers, I generally pre-generate n numbers and store them in an in memory variable: ie if I know I will need 30 random numbers per second, takes 3 seconds to compute them (including blocks), then I will pre-generate 300 while the main code is loading, store them in an array or vector and use them at need; whilst using them I generate another one on a separate thread every time I use one up, replacing the utilised random number with the newly generated one and moving on to the next one in the list, that way when I hit the limit (in this case 300) I know when I can simply start again at the start of my array/vector/list and all the random numbers are fresh and will be non-blocking (as they are pre-generated).

This means you can use any random number generator you like and not worry about blocking behaviour, however it has the expense of utilising more ram, negligible however for the sort of coding I need random numbers for.

Hope this helps, as I couldn't fit this all into a comment:)

GMasucci
  • 2,834
  • 22
  • 42
  • If the RNG depends on the depleted entropy pool, then no amount of extra latency hiding is going to stop it from blocking. The system already gathers the entropy behind the scenes, so what are you ever gaining with your approach? – mabraham May 05 '14 at 00:03
  • 1
    they will be blocking but on a seperate thread which is used only to pupulate the list/vector/array of random numbers, therefore as it is processing them separately from the main thread I can rest safe in the knowledge that I have random numbers available instantly/non-blockingly to my main thread, whilst the blocking is carried out on a separate thread. The only time when the edge is lost from this is when the random numbers are used faster than they are generated, at which point exactly the same problem is encountered as in the original question. Planning will make sure enough are stored:) – GMasucci May 06 '14 at 14:20
  • If there's entropy available, you're adding overhead for no gain because a plain RNG call wouldn't block. If there's not entropy available, you're not gaining anything. You cannot plan to create entropy on a remote server when you are the author of code someone else will use - you need a non-blocking implementation, which was what I asked about. – mabraham May 07 '14 at 23:29
0

You could wait for one good seed full of entropy and follow GMasucci advice to pre-generate a long list of random numbers.

Unless your system is already compromised it seems that a good seed it's good enough to generate a series of non-related numbers as discussed in http://www.2uo.de/myths-about-urandom/

From the discussion I get that a continuous feed of ("true"/"fresh") random numbers it's only needed if your system state (your sources of entropy are known and the attacker knows their current state) it is compromised at some point. After feeding your block cypher more randomness, the predictability of its output will get lower.

Source of seeds? Two or more pieces of trusted software that are less likely to be already compromised. I try to blur out the predictability of the functions that use time functions as seed: local rand_function() + some variable delay + mysql's rand(). From there, a list of pseudo-random numbers generated by some good library.

Sdlion
  • 525
  • 8
  • 18
  • Thanks, but I am seeking non-blocking semantics. Implementing/using another RNG would indeed be useful to avoid a subsequent block after exhausting the pool, but this is a subset of what /dev/urandom does already, and doesn't solve the original problem - that the first call to the system RNG may block, and I probably can't even query whether it will block to know whether I can get the entropy that might exist. – mabraham Aug 05 '14 at 16:22
  • Modern Linux systems seems to handle that saving a few random numbers in a file before shutting down. That way when the system restarts it has already a pool of seeds ready to be fed to the RNG. The only way the system would block should be with an unclean shutdown or the first time the system it's initialized. – Sdlion Aug 06 '14 at 14:32
  • Startup is not the only time a pool can be empty. Pools can deplete through use, e.g. a server on a farm (like I said in the original question). The entropy supply in such a situation might be only from network packets, and in any case you can design a compute load to exhaust it. There ought to be a way to specify whether you want blocking semantics, but so far no-one has identified one. – mabraham Aug 07 '14 at 17:21
  • But as long nobody has broken up the RNG cypher block of your implementation why would you need a constant supply of entropy? As far as I understand in a good RNG the next random number has no relation to the last one, so the seed is only needed once (hence being called a "seed"). And as far the link provided explains it's how both /dev/urandom and /dev/random works (what you're looking for). Yes, pools can be exhausted --any pool since there's no such thing as infinite ram, but you don't need to wait for more entropy as explained in the link (and the links of the link). – Sdlion Aug 08 '14 at 16:11
  • I've never asked for a constant supply of entropy. I've asked for non-blocking random numbers, with entropy if available, on Windows. – mabraham Aug 09 '14 at 19:21