Re: [RFC][PATCH] Entropy generator with 100 kB/s throughput
I'm so sorry, something went terribly wrong with gmail/thunderbird :-( 2013/2/22 Nick Kossifidis mickfl...@gmail.com: Hello all, It's nice to see there is still discussion on the matter of using cpu timings for entropy. In general using cpu timings for gathering entropy is a nice idea but it's not that unpredictable. If someone can profile the system he/she can get enough infos to predict (to some point) the generator's outcome, especially during boot/reboot. You might pass the tests on a single run but if you try to compare the runs e.g. when booting the system multiple times you'll see they are correlated. Take a look at this: http://dl.dropbox.com/u/11670313/runtime-data.tar.bz2 It's the output of this patch, before passing data to the entropy pool (btw did anyone review this patch or should I resend it ?): https://patchwork.kernel.org/patch/1759821/ If you plot the datasets you'll see e.g. that across reboots you get a very similar distribution. It is somehow different across boots but still there is some correlation there too, notice the difference when fsck runs, still not much. The distribution is good in general, for mixing it with the rest in the system's entropy pool, but on its own I don't think it's enough, especially without crypto post-processing. -- GPG ID: 0xEE878588 As you read this post global entropy rises. Have Fun ;-) Nick -- 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
Apologies if this is misthreaded, I had to hand-craft the headers. The patch offers an entropy generator based on CPU timing jitter. The entropy collector has the following properties: * it does not maintain any state and therefore does not need any seed What is this pool if it's not state? /* Entropy pool of the RNG which is filled upon each request for entropy */ struct rand_data And, from looking at jitterentropy_entropy_calc(), it seems to think that the [source producing the] following sequence of timestamps: 1000, 1010, 1030, 1050, 1060, 1080, 1090, 1110, 1120, ... i.e. with absolutely metronomic deltas of 10, 20, 10, 20, 10, 20, ... has 4 bit of entropy per reading. I hope I don't have to explicitly say that it clearly it has 0 bits of entropy. Entropy harvesting is quite hard - entropy estimation is unimaginably harder. Phil -- In a world of magnets and miracles -- Insane Clown Posse, Miracles, 2009. Much derided. Magnets, how do they work -- Pink Floyd, High Hopes, 1994. Lauded as lyrical geniuses. -- 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 21.02.2013 15:07:12, +0100, Phil Carmody pc+l...@asdf.org wrote: Hi Phil, Apologies if this is misthreaded, I had to hand-craft the headers. The patch offers an entropy generator based on CPU timing jitter. The entropy collector has the following properties: * it does not maintain any state and therefore does not need any seed What is this pool if it's not state? There is no state between calls. Of course, you need a scratchpad to do calculations. /* Entropy pool of the RNG which is filled upon each request for entropy */ struct rand_data And, from looking at jitterentropy_entropy_calc(), it seems to think that the [source producing the] following sequence of timestamps: 1000, 1010, 1030, 1050, 1060, 1080, 1090, 1110, 1120, ... i.e. with absolutely metronomic deltas of 10, 20, 10, 20, 10, 20, ... has 4 bit of entropy per reading. I hope I don't have to explicitly say that it clearly it has 0 bits of entropy. I can always hand-craft some deltas that the entropy heuristics come up with a positive value although there is none. You can make the same statement for the entropy calculation of random.c. So, that example is not applicable. I am working on showing that the jitter has entropy. I will come back. Entropy harvesting is quite hard - entropy estimation is unimaginably harder. This is a statement that does not make sense. You CANNOT per definition calculate entropy! The entropy calculation shall ensure that the collector in the worst case is called as often to make sure that there is enough entropy. In other circumstances, it shall just save time! Ciao Stephan Phil -- | 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 Thu, Feb 21, 2013 at 12:46:45PM -0500, Sandy Harris wrote: Also, in some designs it is possible to get very close to calculating entropy. The Turbid generator, for example, uses physical measurements of sound card properties plus arguments from standard circuit physics to prove a lower bound on the Johnson noise that must exist in the circuit. From that plus some quite moderate assumptions about properties of the hash, you get a provable lower bound on output entropy. That's assuming you're talking to a real physical sound card, however. Suppose you have a set up where the user is running one or more VM's on their desktop, and the VM (possibly with some assist from PulseAudio) is multiplexing the host sound card and doing upmixing and/or downmixing as part of its multiplexing magic? Would the Turbid generator be able to detect this situation, and would its entropy estimates be correct? Even if they are correct, the fact that another VM might be getting the same stream of inputs, unbeknownst to the Turbid generator, might mean that an adversary might have access to the entropy being generated by the PulseAudio stream (And yes, there is the same potential issue with the current /dev/random sampling what it thinks is hardware noise generation from network and hdd interrupts; the point is that entropy collection in the VM is *hard* and extremely error-prone. In the end you're probably better off using paravirtualization for /dev/random and trust the Host OS to give you good randomness. After all, if you don't trust the Host OS, you're fundamentally screwed anyway) - 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
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
Re: [RFC][PATCH] Entropy generator with 100 kB/s throughput
On Sat, Feb 09, 2013 at 01:06:29PM -0500, Theodore Ts'o wrote:
For that reasons, what I would suggest doing first is generate a
series of outputs of jitterentropy_get_nstime() followed by
schedule(). Look and see if there is any pattern. That's the problem
with the FIPS 140-2 tests. Passing those tests are necessary, but
*NOT* sufficient to prove that you have a good cryptographic
generator. Even the tiniest amount of post-processing, even if they
aren't cryptographic, can result in an utterly predictable series of
numbers to pass the FIPS 140-2 tests.
In fact, Stephan's 'xor and shift a counter' design, even with zero
input entropy (a counter incrementing at a constant rate), passes FIPS
and a surprising fraction of dieharder tests (though some of the tests,
such as diehard_count_1s_str, have this generator dead to rights); it
also gives an ent entropy well in excess of 7. bits per byte. This
means it's hard to be confident that the entropy measured by ent is
coming from the input entropy as opposed to the (exceedingly
minimal-seeming on the surface!) amount of mixing done by the
xor-and-shift...
It appears the entropy counted is equal to the log2 of the difference
between successive samples (minus one?), but even if you have a good
argument why the ones bit is unpredictable it doesn't seem an argument
that applies as strongly to the weight-128 bit.
When the jitterrand loop runs 10 times, the LSB of that first loop has
only gotten up to the 30th bit, so there are 20+ MSBs of the register
that have not yet had bits rolled into them that are 'entropic' under
the definition being used.
Finally, in the 'turbid' random number generator
(http://www.av8n.com/turbid/), the author develops a
concept of hash saturation. He concludes that if you have a noise
source with a known (or assumed!) entropy and a has function that is
well-distributed over N bits, you'd better put in M N bits of entropy
in order to be confident that the output register has N bits. He
appears to suggest adding around 10 extra bits of randomness, or 74 bits
randomness for a 64-bit hash, relatively indepently of the size of the
hash. This design gathers only 64 bits if you trust the input entropy
calculation, which according to the hash saturation calculation means
that the output will only have about 63.2 bits of randomness per 64
bits output.
Here's my 'absolutely zero entropy' version of the jitter random
algorithm as I understand it:
#include stdint.h
#include unistd.h
const uint64_t dt = 65309;
uint64_t t, r;
static inline uint64_t rol64(uint64_t word, unsigned int shift)
{
return (word shift) | (word (64 - shift));
}
uint64_t jitterrand() {
int i;
// each sample from the 'stuck counter' will be accounted as 7 bits of
// entropy, so 10 cycles to get = 63 bits of randomness
for(i=0; i10; i++) {
t += dt;
r = rol64(r ^ t, 3);
}
return r;
}
int main() {
while(1) {
uint64_t val = jitterrand();
ssize_t res = write(1, val, sizeof(val));
if(res 0) break;
}
return 0;
}
// Jeff
--
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
