13

I get that /dev/random is a good source of entropy, and is what is usually used-- It's just as I'm reading up on GC, at least in Java, it seems accepted that the garbage collection daemon executes non-deterministically. If this it true, why don't we use the timing of the garbage collection as a source of entropy instead of the variable /dev/random?

  • 7
    take a look at some of the docs for rand() functions in standard C-library. They specifically call out that while they give you what appears random numbers, they cannot be used for security. Your typical garbage collector probably would fall into the same category. If you are going to use one for security, you've got to make sure you use a cryptographically secure garbage collector. – DXM Nov 3 '13 at 21:51
  • 14
    something nondeterministic can still be highly predictable – ratchet freak Nov 3 '13 at 22:43
  • 7
    In this case "non-deterministic" is a poor description. A garbage collector is a completely deterministic system and if you have full knowledge of its state and the state of the program that uses it, you can deterministically predict the results. – Steven Burnap Nov 3 '13 at 22:50
  • 4
    @DXM do you know of a good implementation for a cryptographically secure garbage collector? ;) – AJMansfield Nov 3 '13 at 23:27
  • 7
    "Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin." - John von Neumann – Mark Adler Nov 4 '13 at 0:19
58

"Unspecified" and "random" are two entirely different concepts.

The exact workings of a garbage collector are not specified and are up to the garbage collector (usually implemented by a VM of sorts, but not necessarily).

Therefore, you have no specified (i.e. deterministic) time at which garbage will be collected.

However any given implementation will follow some rules and there is a high chance that two subsequent runs of the same program will have very similar garbage collection patterns.

Therefore the actual entropy provided by a garbage collector would be very low (and finding out which parts you can actually use as entropy will be tricky).

As a comparison: A HashMap in Java doesn't guarantee any order of retrieval for its members (basically because guaranteeing it would add an overhead that's not worth paying, most of the time). However for a given implementation and a given set of insertions/removals you can definitely calculate the resulting order. Just because there is no guarantee for any given order, doesn't mean that the order is random.

  • 20
    I think it would be a fair statement to say that if a computer ever does something that's actually non-deterministic, that computer is broken. – Schilcote Nov 3 '13 at 23:07
  • Non-deterministic could also mean that it relies on some state external to the program at hand, which itself may be deterministic, but will be completely unrelated to the program itself and so can be different each time the program runs. – asmeurer Nov 4 '13 at 1:31
  • @asmeurer I don't think I've heard these terms in any such context. In fact, I'm not even sure what you mean: Every program that takes external input (that is, most useful programs) "relies on some external state", but that doesn't make it non-deterministic. – us2012 Nov 4 '13 at 3:38
  • 2
    @Schilcote: Some modern CPUs have non-deterministic (true) RNG's implemented in hardware. These are truly non-deterministic down to quantum level physics. – MSalters Nov 4 '13 at 8:42
  • 2
    @Schilcote Even without specialized RNG instructions (Intel's RDRAND and RDSEED) a computer isn't completely deterministic. Some timings aren't completely specified and can depend on external factors like temperature. – CodesInChaos Nov 4 '13 at 9:14
8

Firstly, we have to be careful not to fall into the trap of reasoning by manipulation of mere words. For instance, we could ask, since a NFA is a "non-deterministic finite automaton", why don't we use it to obtain random numbers? In that case, it would be because that's not what "non-deterministic" means in an NFA; in fact, when we simulate an NFA, on a given input, the behavior of the simulation is perfectly deterministic.

"Deterministic" is a loaded phrase. To a computer programmer or computer scientist, non-deterministic behavior just means "determining the exact behavior is complicated to think about", and depends on too many factors, including the program input.

However, that doesn't mean it's not deterministic to someone motivated to attack a cryptosystem. Sometimes environmental factors and inputs can be pinned down, and repeatable patterns emerge from "non-deterministic" behavior.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.