Re: [RFC][PATCH] Entropy generator with 100 kB/s throughput
On Sun, Feb 10, 2013 at 1:50 PM, Theodore Ts'o ty...@mit.edu wrote: On Sun, Feb 10, 2013 at 01:46:18PM +0100, Stephan Mueller wrote: However, the CPU has timing jitter in the execution of instruction. And I try to harvest that jitter. The good thing is that this jitter is always present and can be harvested on demand. How do you know, though, that this is what you are harvesting? ... And what's your proof that your entropy source really is an entropy source? One paper that seems to show there is some randomness in such measurements is McGuire, Okech Schiesser Analysis of inherent randomness of the Linux kernel, http://lwn.net/images/conf/rtlws11/random-hardware.pdf They do two clock calls with a usleep() between, take the low bit of the difference and pack them unmixed into bytes for testing. Their tests show over 7.5 bits of entropy per byte, even with interrupts disabled. The same paper shows that simple arithmetic sequences give some apparent entropy, due to TLB misses, interrupts, etc. There are lots of caveats in how this should be used and it is unclear how much real entropy it gives, but is seems clear it gives some. My own program to feed into random(4) is based on such things: ftp://ftp.cs.sjtu.edu.cn:990/sandy/maxwell/ HAVEGE also uses them http://www.irisa.fr/caps/projects/hipsor/ there is a havegd daemon for Linux http://www.issihosts.com/haveged/ random(4) also mixed in timer data at one point, which seems the correct thing for it to do. Later I heard something about that code having been removed. What is the current status? -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [RFC][PATCH] Entropy generator with 100 kB/s throughput
On 10.02.2013 19:50:02, +0100, Theodore Ts'o ty...@mit.edu wrote: Hi Ted, On Sun, Feb 10, 2013 at 01:46:18PM +0100, Stephan Mueller wrote: However, the CPU has timing jitter in the execution of instruction. And I try to harvest that jitter. The good thing is that this jitter is always present and can be harvested on demand. How do you know, though, that this is what you are harvesting? ... Given all your doubts on the high-precision timer, how can you reasonably state that the Linux kernel RNG is good then? The data from add_timer_randomness the kernel feeds into the input_pool is a concatenation of the event value, the jiffies and the get_cycles() value. The events hardly contains any entropy, the jiffies a little bit due to the coarse resolution of 250 or 1000 Hz. Only the processor cycles value provides real entropy. Now you start doubting that with arguments that the resolution of that processor cycle timer is very coarse. If this is the case, why shall I trust random.c, especially considering the measurements observable events like key strokes, mouse movements, interrupts (network cards). Only if you have a high-precision time stamp, entropy can be derived from these events. Moreover, I cannot understand your comments on VMs -- on x86, the timer depends on the rdtsc instruction which should be available on current CPUs and is callable from user space. Hence, there should be no obstacle to use this instruction within a VM and get a good reading. Note, I will make measurements about the distribution of the timer values and will come back to you. Thanks Stephan -- | Cui bono? | -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [RFC][PATCH] Entropy generator with 100 kB/s throughput
On Sun, Feb 10, 2013 at 2:32 PM, Stephan Mueller smuel...@chronox.de wrote: On 10.02.2013 19:50:02, +0100, Theodore Ts'o ty...@mit.edu wrote: Given all your doubts on the high-precision timer, how can you reasonably state that the Linux kernel RNG is good then? The data from add_timer_randomness the kernel feeds into the input_pool is a concatenation of the event value, the jiffies and the get_cycles() value. The events hardly contains any entropy, the jiffies a little bit due to the coarse resolution of 250 or 1000 Hz. Only the processor cycles value provides real entropy. There are multiple sources of entropy, though. There are reasons not to fully trust any -- key strike statistics can be predicted if the enemy knows the language, the enemy might be monitoring the network. there is no keyboard or mouse on a headless server, a diskless machine has no disk timing entropy and one with an SSD or intelligent RAID controller very little, However, with multiple sources and conservative estimates, it is reasonable to hope there is enough entropy coming in somewhere. It is much harder to trust a system with single source of entropy, perhaps impossible for something that is likely to be deployed on the whole range of things Linux runs on, from a cell phone with a single 32-bit CPU all the way to beowulf-based supercomputers with thousands of multicore chips. Moeove, random(4) has both a large entropy pool (or three, to be more precise) and strong crypto in the mixing. If it /ever/ gets a few hundred bits of real entropy then no-one without the resources of a major government and/or a brilliant unpublished attack on SHA-1 can even hope to break it. In the default Linux setup, it gets few K bits of reasonably good entropy from the initialisation scripts, so attacks look impossible unless the enemy already has root privileges or has physical access to boot the machine from other media look at Linux storage. -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [RFC][PATCH] Entropy generator with 100 kB/s throughput
On Sun, Feb 10, 2013 at 08:32:37PM +0100, Stephan Mueller wrote: Given all your doubts on the high-precision timer, how can you reasonably state that the Linux kernel RNG is good then? Because we're measuring intervals that are substantially larger than CPU jitter. (i.e., inputs from keyboards and mice, interrupts from hard drives and networks, etc.) The data from add_timer_randomness the kernel feeds into the input_pool is a concatenation of the event value, the jiffies and the get_cycles() value. The events hardly contains any entropy, the jiffies a little bit due to the coarse resolution of 250 or 1000 Hz. Only the processor cycles value provides real entropy. Jiffies is defined by 250HZ (4ms) on modern Linux kernels, at least for x86 systems. Average seek times for common HDD's are 10ms, with full-stroke seek times being roughly twice that, and seek times perhaps 50% slower for laptop/mobile HDD's, and 50% faster for high-end server drives. So that's enough to get maybe a bit or two worth's of entropy for HDD interrupts. (Yes, this does imply that the entropy estimator for /dev/random is probably overestimating the entropy in a number of cases; in general, it's actually pretty difficult to measure entropy accurately in an automated way.) Moreover, I cannot understand your comments on VMs -- on x86, the timer depends on the rdtsc instruction which should be available on current CPUs and is callable from user space. Hence, there should be no obstacle to use this instruction within a VM and get a good reading. The problem is one of correctness versus performance. (The TSC is unsynchronized across different CPU cores, and the guest OS has no idea when it gets switched to running on a different core on the host CPU.) As a result, on many/most VM's the TSC is emulated or paravirtualized. For example, see: http://old-list-archives.xen.org/archives/html/xen-devel/2009-08/msg01103.html for a discussion of the issues involved. Regards, - Ted -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
