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?
6
-
7take 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.– DXMCommented Nov 3, 2013 at 21:51
-
15something nondeterministic can still be highly predictable– ratchet freakCommented Nov 3, 2013 at 22:43
-
7In 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.– user53141Commented Nov 3, 2013 at 22:50
-
4@DXM do you know of a good implementation for a cryptographically secure garbage collector? ;)– AJMansfieldCommented Nov 3, 2013 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 AdlerCommented Nov 4, 2013 at 0:19
|
Show 1 more comment
2 Answers
"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.
answered Nov 3, 2013 at 21:26
-
20I 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. Commented Nov 3, 2013 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.– asmeurerCommented Nov 4, 2013 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.– us2012Commented Nov 4, 2013 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.– MSaltersCommented Nov 4, 2013 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. Commented Nov 4, 2013 at 9:14
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.
