Hi crypto hackers,
[1] patch at http://www.chronox.de/jitterentropy-0.1.tar.gz
The Linux kernel RNG which we all use via /dev/random or /dev/urandom
received a lot of merits over the long years it exists. In particular
it was subject to countless researches and assessments and was determined
to deliver appropriate entropy to the caller.
However, we all know that the RNG also has deficiencies, which makes
the appropriate use not entirely clear to everybody. In the past we heard
about weak keys in embedded systems and the like. It is not the RNG's fault,
but rather the problem of designers of such systems. Nonetheless, things
could be easier with the use of the Linux RNG . In particular I met the
following shortcomings over the years:
* /dev/random is regarded as high-quality RNG as it is constantly reseeded,
but suffers from its blocking nature
* there is no in-kernel equivalent for /dev/random -- i.e. how can you
really
seed the DRNG that is present in the kernel crypto API with high quality
entropy?
* at boot time the data /dev/random or /dev/urandom spits out is
questionable
which requires a reseed during reboot. Also, that seed file must first be
written, which may not be trivial in all circumstances. For example, in
embedded systems or live CDs, this may be a challenge. Or what about
system
outages -- there is no clean shutdown and no new seed file.
* in virtual environments (i.e. the Linux kernel operates as guest),
/dev/random does not have access to all the devices to collect entropy.
* when generating the key for full disk encryption configuration, there
may be
limited entropy in the entropy pools
* random.c contains complex processing which enlarges the device event
processing for every event
In the patch, I try to provide an entropy collector without these
shortcomings.
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
* it delivers entropy on demand with a throughput of about 100 kB/s and does
not block -- it performs a synchronous entropy generation for the caller
* it should work well in virtualized environments
* the heart of the entropy collector is about 10 lines of code and does not
use cryptography
* an array of statistical test suites pass the output of the entropy
collector
(again, the output is not mangled with cryptography)
The design and concepts are documented in source code comments.
The source code is available at [1]. The code can be compiled as kernel
module
as well as user space application. In case the code finds its way to the
kernel, the user space code will be removed -- currently it remains to ease
the analysis. To compile as kernel module, just run make. To compile as user
space application, run make -f Makefile.user. Note, the user space part
can also
be used in user space libraries to avoid /dev/random.
Is such entropy collector of interest for the kernel? Do you see weaknesses
in the design or its implementation?
In a recent discussion about the Linux RNG Theodore Ts'o indicated that
in the long run, he would like to see an RNG based on AES
(see http://lkml.org/lkml/2012/12/15/162).
In addition to the entropy collector, the kernel module also includes a link
to the kernel crypto API X9.31 DRNG based on AES. Two instances of the DRNG
are maintained. The first instance is reseeded once in a while (after
1024 bytes
of random data) with the CPU jitter entropy. The second is reseeded with 16
bytes of entropy when 16 bytes are read from the DRNG. The first DRNG
therefore
is a fast delivering DRNG which is information theoretical weaker than the
second DRNG (which is much slower, but the information theoretical entropy
equals about 1 bit per 1 bit of output).
For testing purposes, debugfs interface files are implemented to read from
the entropy collector and the two DRNGs. The test mode is triggered with the
parameter "insmod jitterentropy.ko testmode=1". The interface files are
/sys/kernel/debug/jitterentropy/[seed|drng|strong-drng].
Detailed design description is given as comments in the source code file.
Thanks
Stephan
On Fri, Feb 08, 2013 at 11:04:54PM +0100, Stephan Mueller wrote:
> * an array of statistical test suites pass the output of the entropy
> collector
> (again, the output is not mangled with cryptography)
You're not mangling the output with cryptography, but you are doing
some mangling in jitterentropy_cpu_jitter().
So let's be clear about what the heart of your entropy source is:
You're getting the nanoseconds out of clock_gettime(CLOCK_REALTIME),
and then mixing it using XOR and a ROL(3) into a 64-bit buffer, and
interspersing the calls to clock_gettime() with schedule().
So what a code breaker at the NSA would probably try to do first is to
measure is whether there is any kind of bias or non-entropy in the
nanoseconds returned by CLOCK_REALTIME after calls to schedule(). If
they can find any kind of bias, they can use that to calculate what
kind of patterns or non-random bits might end up showing up after you
do your non-cryptographic mangling.
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.
Regards,
- Ted
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.9999 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; i<10; 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
On 09.02.2013 19:06:29, +0100, Theodore Ts'o <[email protected]> wrote:
Hi Ted,
thank you for the review.
> On Fri, Feb 08, 2013 at 11:04:54PM +0100, Stephan Mueller wrote:
>> * an array of statistical test suites pass the output of the entropy
>> collector
>> (again, the output is not mangled with cryptography)
> You're not mangling the output with cryptography, but you are doing
> some mangling in jitterentropy_cpu_jitter().
>
> So let's be clear about what the heart of your entropy source is:
>
> You're getting the nanoseconds out of clock_gettime(CLOCK_REALTIME),
> and then mixing it using XOR and a ROL(3) into a 64-bit buffer, and
> interspersing the calls to clock_gettime() with schedule().
Correct.
>
> So what a code breaker at the NSA would probably try to do first is to
> measure is whether there is any kind of bias or non-entropy in the
> nanoseconds returned by CLOCK_REALTIME after calls to schedule(). If
> they can find any kind of bias, they can use that to calculate what
> kind of patterns or non-random bits might end up showing up after you
> do your non-cryptographic mangling.
I thought I have countered such possibility already with the following 2
concepts:
1. Before entropy is extracted from the pool, at the minimum 9 * 16
clock measurements (we have 16 rounds in jitterentropy_cpu_jitter and at
least 9 rounds in jitterentropy_gen_entropy due to the entropy
calculation and the limit of 7 bits of entropy per round) are fed into
the pool with the strong possibility of more. The number of measurements
mixed into the pool depends on the amount of entropy the heuristic
applies to the time needed to perform the 16 rounds of measurements and
the previous delta.
2. The entropy heuristic is measuring the delta of deltas to calculate
the entropy -- and thus implicitly how often the 16 clock measurements
are applied. With the use of deltas of deltas (i.e. kind of the 2nd
derivation of the absolute time measurements), the code implies 0 bit of
entropy for evenly spaced time measurements (i.e. no jitter) and time
measurements with a too coarse timer.
>
> 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
Note, I am not using FIPS 140-2 tests as there are none. I try to use
the tests NIST and the German BSI would require when you come along with
an RNG for validation. In addition, I use the dieharder test suite with
its tons of tests.
> *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.
Thank you very much for the suggestions. I will perform the suggested test.
On the other hand the entropy generator is intended to serve as a seed
source for the DRNGs. One of the goals I tried to achieve is ease of use
without the possibility to misuse the implementation. With that in mind,
for the kernel implementation, I guess jitterentropy_read_entropy should
not be exported with EXPORT_SYMBOL and should be static.
This change implies that in the kernel only the DRNGs are accessible
where the strong DRNG (jitterentropy_strong_drng) should conceptually be
as strong as blocking_pool (without the blocking nature) and the regular
DRNG (jitterentropy_reg_drng) is conceptually the equivalent to
nonblocking_pool which is guaranteed to be reseeded.
Thanks
Stephan
>
> Regards,
>
> - Ted
>
> --
> Ciao
> Stephan
>
> atsec information security GmbH, Steinstra?e 70, 81667 M?nchen, Germany
> P: +49 89 442 49 830 - F: +49 89 442 49 831
> M: +49 172 216 55 78 - HRB: 129439 (Amtsgericht M?nchen)
> GF: Salvatore la Pietra, Staffan Persson
> atsec it security news blog - atsec-information-security.blogspot.com
>
> --
> | Cui bono? |
On 10.02.2013 02:57:51, +0100, Jeff Epler <[email protected]> wrote:
Hi Jeff,
> 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.9999 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...
I am totally on your side that passing the tests is a necessary
prerequisite for a good RNG but by no means a proof that the RNG
produces entropy.
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.
>
> 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.
Why are you mentioning 128 bit? The pool I try to fill is 64 bit and it
is filled with at least 16 * 9 clock measurements and an equal amount of
code in-between due to the schedule call.
>
> 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.
If you apply this argument to my suggested code, after executing the 16
loops in jitterentropy_cpu_jitter once, you rolled up to bit 48 (3 *
16). Now, you have at least 9 invocations of this loop of 16. This
implies you rolled over the pool buffer several times.
>
> 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.
I am not sure how that applies to the suggested code. The entropy source
just generates raw entropy without using a hash. The entropy then is
used to seed a DRNG. The so-called "strong DRNG" is initially seeded
with 48 bytes out of my entropy source. After generating 16 bytes of
output, it is reseeded with another 16 bytes of entropy. And after
reaching 1024 bits of output, it is also re-keyed.
Only the "regular DRNG" is reseeded after 1024 bytes of output and
rekeyed after 1MB of output.
Only those two DRNGs are supposed to be interface for a user to obtain
random data.
Note: reseeding and rekeying are not yet implemented in the kernel
crypto API, but can easily be added.
Thanks
Stephan
>
>
> 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; i<10; 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
--
| Cui bono? |
OK, my original reading of the mixing code was not accurate. This time
around, I started with the original posted tarball and turned the use of
the CPU clock into a very simple and clearly bad "clock" that will
provide no entropy.
--- jitterentropy-0.1/jitterentropy.c 2013-02-08 15:22:22.000000000 -0600
+++ jitterentropy-0.1-me/jitterentropy.c 2013-02-10 09:45:07.000000000 -0600
@@ -270,12 +270,13 @@
typedef uint64_t __u64;
static int fips_enabled = 0;
-#define jitterentropy_schedule sched_yield()
+#define jitterentropy_schedule (0)
static inline void jitterentropy_get_nstime(__u64 *out)
{
- struct timespec time;
- if (clock_gettime(CLOCK_REALTIME, &time) == 0)
- *out = time.tv_nsec;
+ static __u64 t = 0;
+ const __u64 delta2 = 257;
+ static __u64 delta;
+ *out = (t += (delta += delta2));
}
/* note: these helper functions are shamelessly stolen from the kernel :-) */
This give a generator that has Entropy = 7.999907 bits per byte
and fails 6 in 10000 FIPS 140-2 tests. It also passes some (but not
all) dieharder tests.
Jeff
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?
Depending on the hardware and CPU that you are using, CLOCK_REALTIME
might be quantized in no more than 4ms intervals. Even on systems
with a TSC register, the TSC register has all sorts of effects which
can limit its granularity, and in fact is generally quantized as a
multiple of the bus cycles. Intel states that the quantization
effects mean that for timing purposes, you can't really accurately
time anything under 1000 cycles. So at that point, you're not
measuring CPU timing jitter, but something else; perhaps the frequency
beats between the CPU clock and the bus clock. Also, consider what
might happen if you are booted on a VM; at that point, I can pretty
much guarantee that whatever you are measuring, it will almost
certainly _not_ be from CPU timer jitter. It may be some very
hard-to-predict pattern generated from the timing interactions of the
host OS scheduler and the guest OS's scheduler, but that does _not_
necessarily mean that there is true randominess which you are getting.
After all, if I give you a sequence of numbers which is generated by
encrypting a counter with a secret AES key which only I know, that
does _not_ mean that you have a strong cryptographic random number
generator. If you use that sequence to generate session keys, I will
be able to break all of your encrypted traffic. The mere fact that
the sequence of numbers is one which passes pretty much all RNG tests,
whether they be FIPS 140, or the BSI tests, or the dieharder tests,
and just because _you_ can't figure out the pattern, does not mean
that therefore the sequence is random.
> I am not sure how that applies to the suggested code. The entropy source
> just generates raw entropy without using a hash.
And what's your proof that your entropy source really is an entropy
source?
After all, I can claim that the dice rolls are random based on the
chaotic air movements influencing how the die spins through the air.
The fact that there are chaotic air movements isn't the question. The
question is whether or not the die is perfectly balanced. If the die
is weighted unevenly, the fact that there are all sorts of subtle
chaotic effects which could be influencing the roll of the dice is
utterly irrelevant.
Similarly, if the time stamp counter, even though supposedly it is
giving you granularity measured in nanoseconds, is in fact getting
granularized somewhere in the hardware in in the thousands of cycles,
even if there are apparently many digits of precision, does not mean
that you actually have that many significant digits.
Regards,
- Ted
On Sun, Feb 10, 2013 at 1:50 PM, Theodore Ts'o <[email protected]> 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?
On 10.02.2013 19:50:02, +0100, Theodore Ts'o <[email protected]> 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? |
On Sun, Feb 10, 2013 at 2:32 PM, Stephan Mueller <[email protected]> wrote:
> On 10.02.2013 19:50:02, +0100, Theodore Ts'o <[email protected]> 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.
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
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.
On 21.02.2013 15:07:12, +0100, Phil Carmody <[email protected]> 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? |
On Thu, Feb 21, 2013 at 9:17 AM, Stephan Mueller <[email protected]> wrote:
> There is no state between calls. Of course, you need a scratchpad to do
> calculations.
But in general you need a buffer. It is quite easy to construct scenarios where
several K bits of entropy are needed very -- for example, reboot an IPsec
gateway the supports a few dozen tunnels and needs a few hundred bits
to rekey each. Without state, it is quite difficult to demonstrate that you can
meet such requirements. Given a reasonable size of buffer, some saved
random data and the assumption that the enemy does not already have
root on your server, it is trivial.
> ... I am working on showing that the jitter has entropy. I
> will come back.
I think that has already been shown. See the McGuire et al. paper
I cited earlier in the thread and the HAVEGE papers. Of course it
needs more analysis to be sure we have really good estimates of
that entropy, but it seems clear there is some at any rate.
>> Entropy harvesting is quite hard - entropy estimation is unimaginably harder.
Yes.
> This is a statement that does not make sense. You CANNOT per definition
> calculate entropy!
The question is not /calculating/ it, but /estimating/ it. That is a perfectly
reasonable thing to do, and it is done in most generators. It is a hard
problem, though, and requires care in both design and implementation.
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.
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
I'm so sorry, something went terribly wrong with gmail/thunderbird :-(
2013/2/22 Nick Kossifidis <[email protected]>:
> 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