0

I know there are existing questions about how Truecrypt uses mouse input to increase entropy. My question is, how much of a difference does it make? I don't know of any other encryption utilities that do this, so does this mean the rest of them (like 7-zip) are unsafe? To my knowledge the typical way of doing this is to use the computer time as the seed to the random number generator, which in a sense is the same as user input as an attack doesn't know (to the millisecond) when the user presses the button. How much more secure is encryption if it uses user input like moving the mouse or random keyboard strokes?

1

Basically zero.

Operating systems already integrate every source of potential randomness that they can get their hands on in order to seed their randomness APIs (examples being CryptGenRandom() on Windows, /dev/urandom on POSIX variants, getrandom(2) on Linux, and getentropy(2) on FreeBSD). These sources include mouse movements, disk timings, and other unpredictable events.

The thing is, once you reach a certain point — say 256 bits of collected entropy, which takes less than a few seconds in practice — the operating system can generate an effectively unlimited stream of unpredictably random numbers for the remaining lifetime of the system. Many operating systems even save this internal state upon reboots, preventing the need to reinitialize the system random number generator from scratch ever again. More entropy at that point doesn't really get you more unpredictability, and collecting mouse movements is already done as part of this process anyway.

Additional entropy does allow for the operating system to recover from theoretical exposure or tainting of its internal random state, but this is very unlikely to occur in practice on a non-compromised machine.

To my knowledge the typical way of doing this is to use the computer time as the seed to the random number generator…

No cryptographically-secure RNG uses the system clock for this purpose. As @CBHacking points out, this is an exceedingly weak source of random numbers, since "what time is it" is highly predictable (and sometimes easily influenced by outside sources). Microsecond-level timings of human input can also be semi-predictable, but collecting and mixing this data repeatedly can very quickly yield a good source of entropy. Modern RNG mixing functions are very good at extracting and combining even small amounts of entropy.

2

TL;DR:

None, really. Modern computers generate high-quality entropy ("randomness", essentially) fast enough that you wiggling your mouse is irrelevant.

More detail:

Programs like Truecrypt (and possibly older versions of things like ssh-keygen, gpg, and so on) that tell you to do stuff during key generation are operating on the assumption that the OS may not have very fast entropy sources other than user interaction and/or a very small entropy pool for its cryptographically secure pseudo-random number generator (CSPRNG). On old computers, especially without Internet connections or enough resources to run a lot of background processes, this was probably true at least some of the time.

Modern computers are pretty good at entropy generation and have relatively large entropy pools that can easily cough up enough pits to generate a key. Additionally, these days it is common to use CSPRNGs that support stretching entropy (on *nix OSes, this would be the difference between /dev/random, which pulls from the entropy pool directly, and /dev/urandom which can take a small amount of entropy from the pool and use it to generate a large number of slightly-less-random bits; /dev/urandom is, on modern OSes, still generally good enough for key generation). It's still theoretically possible to end up with machines that have predictable kernel entropy pools (a bunch of identical VMs running on identical headless machines running identical software versions started at the same time, etc. may sometimes have the same kernel entropy initially), but it's not easy. This kind of thing is why modern VM hosts have ways to feed some entropy to the VM guests based on the hardware states, etc. that are usually used in kernel entropy generation these days.

Most modern CPUs even have what amount to hardware RNGs based on things like the thermal state of the different parts of the CPU chip, which vary rapidly depending on things like exactly what instructions have been run recently and whether they caused cache misses or not, miniscule variations in voltage from the power supply, air movement in the room, and other stuff like that; the differences are slight, but taken together there's a lot of entropy there and the CPU has dedicated hardware for harvesting it and new opcodes for providing it to the OS. Many OSes mix this into their kernel entropy pool, along with other inputs, making it very hard to exhaust entropy under normal "user" workloads on a modern PC.

IMPORTANT:

There is no CSRPNG in the world that is seeded to any significant degree off of the system clock! The reason why is simple. You seem to think that "to the millisecond" timing is sufficiently random for crypto, but you're quite wrong about that. Let's take something like generating a GPG key pair as an example. Those generally have a validity period on their public keys, which tells me (I have your public key, it is after all public) when the key was generated, to the day. There are 86400000 ms in a day (ignoring the fact that I can probably narrow that down a lot by considering hours when a person is likely to be awake). Log2(86400000) is 26.36 bits. Your supposedly super-secure 4096-bit RSA key pair actually has less entropy than a decent-quality password! Brute-forcing 86400000 different possible key pairs to find the corresponding private key will take a while, but a hell of a lot less time than trying to factor a 4096-bit RSA public key. In fact, there aren't enough milliseconds since the dawn of electronic computing to produce a fully-random DES key (56 bits) by choosing from among them, and we can brute-force DES in under a day using off-the-shelf hardware (yes, RSA key generation takes a lot more work than just taking 56 bits and computing their parity for DES key generation, but it's still fast enough for this purpose).

Instead, any crypto program that isn't purely worthless garbage (and quite a few that are) use a CSPRNG (such as /dev/urandom on Unix-like systems, or CryptGenRandom() on Windows) for key generation. Similarly, most programming language standard libraries include at least two PRNGs: a fast but insecure one for stuff where it doesn't actually matter if somebody could theoretically predict the output (in Java, this is java.util.Random), and a cryptographically-secure one, usually either seeded by or directly just returning the output of the OS CSPRNG, for stuff like crypto (in Java, this is java.security.SecureRandom). No PRNG seeded by the current time, regardless of algorithm it uses, could ever be considered cryptographically secure; the search space is just too small.

  • Upvoted your answer for mentioning part of the question I missed — seeding from the system clock. – Stephen Touset Apr 20 '17 at 0:59
  • I didn't mean the time on the clock, I meant the time() function which returns the milliseconds from Unix time. Isn't this still used? cplusplus.com/reference/ctime/time – northerner Apr 20 '17 at 5:26
  • 1
    time is the system clock function I mentioned above, yes, and is used by default to seed many of the insecure forms of PRNG such as libc's rand (which should not be used for anything more sensitive than shuffling a deck of cards, and not even that if there's money riding on the game). One should certainly never use it for any kind of crypto. CSPRNGs need to be indistinguishable from true randomness even if somebody is trying really hard, while insecure PRNGs are not intended for use in scenarios where such adversaries exist, and need only casually resemble true randomness. – CBHacking Apr 20 '17 at 5:38
  • timing info can be a really unpredictable source of entropy, if it's done correctly. randomize timer is not correctly; you need multiple samples an indeterminate amount of time apart. For example, the ESP8266's 32b CPU clock rolls over in 30 seconds, so time % 2^24 is basically "new" each time it's called. If you use a slow clock like network events, human typing, etc, to know when to sample the fast one, outputs will be unpredictable. If i asked you to drive across the country and back, you might be able to guess the # of miles, but could you guess the # of inches % 256 any > 1/256? – dandavis Apr 20 '17 at 20:59
  • @dandavis: You still only get a fairly small amount of entropy out of every sample If you take enough samples, and if there's no bias to those samples (which, given that mice sample at regular and predictable rates, there would be), you can get usable entropy this way - such hardware interrupts are used to feed kernel entropy pools on most systems - but it's not going to happen fast enough that wiggling your mouse during key generation vs. not doing that is going to have a meaningful impact. – CBHacking Apr 21 '17 at 21:38

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.