Am Freitag, 11. Oktober 2013, 21:45:57 schrieb Sandy Harris: Hi Sandy, >On Fri, Oct 11, 2013 at 2:38 PM, Stephan Mueller <smueller@xxxxxxxxxx> >wrote: > >I like the basic idea. Here I'm alternately reading the email and the >page you link to & commenting on both. Thank you very much for reviewing both and sharing your thoughts. > >A nitpick in the paper is that you cite RFC 1750. That was superceded >some years back by RFC 4086 >http://tools.ietf.org/html/rfc4086 Thank you for the link. I updated the reference in the paper. Though, the Von-Neumann unbias operation is way older than this RFC and I just listed the RFC to give people a reference. > >(Ted's comments in the actual driver had the same problem last >I looked. That is excusable since they were written long ago.) > >I think you may be missing some other citations that should be >there, to previous work along similar lines. One is the HAVEGE >work, another: >McGuire, Okech & Schiesser, >Analysis of inherent randomness of the Linux kernel, >http://lwn.net/images/conf/rtlws11/random-hardware.pdf Thank you for the reminder. I added section 1.1. > >Paper has: > >" the time delta is partitioned into chunks of 1 bit starting at the >lowest bit " .... The 64 1 bit chunks of the time value are XORed with >each other to " form a 1 bit value. > >As I read that, you are just taking the parity. Why not use that >simpler description & possibly one of several possible optimised >algorithms for the task: >http://graphics.stanford.edu/~seander/bithacks.html I am fully aware that the bit operation is inefficient. Yet it is deliberately inefficient, because that "folding loop" performs actual work for the RNG (the collapse of 64 bits into one bit) and at the very same time, it is the fixed instruction set over which I measure the time variations. Thus, the folding loop can be considered as the entropy source at the same time. Thus, when making it shorter or more efficient, we alter the duration of the loop. With significantly shorter durations, the jitter measurements will get smaller. That issue is the sole reason why that code part of the RNG shall be compiled without optimizations. The compiler is clever enough to arrange my inefficient operation into something faster when optimizing. You clearly see that with Clang: the unoptimized folding loop code takes about 300 nanoseconds on my i7 2nd gen. Optimized, it takes about 40 ns! At the same time, the jitter is lower (it is still sufficient, but the cushion is smaller). As the RNG is not primarily about speed, the folding operation should stay inefficient. > >If what you are doing is not a parity computation, then you need a >better description so people like me do not misread it. It is not a parity computation that the folding loop performs. The code XORs each individual bit of the 64 bit stream with each other, whereas your cited document implies an ANDing of the bits (see section "Computing parity the naive way" of the cited document). The reason is that the different bits contain entropy -- the lower the bit index, the more entropy they are assumed to have. The only operation to retain entropy and yet collapse a bit string is to use XOR. Any other operation will result in the fact that you cannot make any statement about the entropy behavior any more. The rationale about the folding loop is given in section 5.1 [2]. > >A bit later you have: > >" After obtaining the 1 bit folded and unbiased time stamp, >" how is it mixed into the entropy pool? ... The 1 bit folded >" value is XORed with 1 bit from the entropy pool. > >This appears to be missing the cryptographically strong >mixing step which most RNG code includes. If that is >what you are doing, you need to provide some strong >arguments to justify it. The key here is that there is no cryptographic function needed for mixing as in fact I am not really mixing things. I am simply concatenating the new bit to the previously obtained bits. That is it. The argument for doing that is that the time deltas are independent of each other. Yet, these deltas show variations which are collapsed into the one bit that is the result of the folding loop. Therefore, the individual bits are independent of each other and yet contain the variations of the jitter. Now, there is no need to apply a cryptographic function for further mixing. The key here is that the variations in the time deltas must be *larger* than one bit. What does that mean? For example, if the variation would be, say 50% of 250 ns and 50% of 251 ns, we have 1 bit variation (considering that each individual measurement is independent of the others). Or, if you have 30% with 249ns, 20% with 250%, 25% with 251 and 25% with 252ns, you have more than one bit. You see, that this line of thought brings us to the Shannon Entropy formula. And now we come to the 200+ test systems that I tested on: all with the exception of one very old system showed a variation with the lower boundary of more than one bit. Therefore, each bit from the folding operation therefore contains one bit of entropy. So, why should I mix it even further with some crypto function? > >Sometimes doing without is justified; for example my >code along these lines >ftp://ftp.cs.sjtu.edu.cn:990/sandy/maxwell/ >does more mixing than I see in yours, but probably >not enough overall. That's OK because I am just >feeding into /dev/random which has plenty of >mixing. > >It is OK for your code too if you are feeding into >/dev/random, but it looks problematic if your code >is expected to stand alone. Please consider use case of the CPU Jitter RNG: it is intended as a seed source for deterministic RNGs. That is how the various integration patches for the kernel crypto API, /dev/random, OpenSSL, libgcrypt or even the stand-alone entropy feeding daemon operate. Thus, you have a whitening function when using it together with such DRNGs. Yet, the code allows other users that may want entropy (NSS or even stand-alone DRNGs come to mind) to simply use that noise source without the burden of another whitening function to their DRNGs. > >Ah! You talk about whitening a bit later. However, >you seem to make it optional, up to the user. I >cannot see that that is a good idea. Why is whitening a good idea in the first place when the statistical properties of your output already are white noise? When applying all kinds of statistical test to my non-whitened output, I do not see any statistical significant odd behavior -- ent (Chi-Square test, mean test, monte carlo simulation), dieharder tests, various tests from the German BSI, NIST test suite. And if you say that your entropy source has problems, then your whitening function only disguises the fact but does not remedy it. Please refer to section 4.3 of my document in [2] where I have some "anti" tests with broken timers. Such brokenness would be immediately visible for anybody without a whitening function (such as the jitter RNG). But if the jitter RNG would use a whitening function, the missing entropy would not be visible. Also, the RNG is intended as a seeding mechanism for all kinds of use cases. The typical one is the seeding of a DRNG of your choice. This is one more reason why I consider the use of a whitening function as not helpful. > >At the very least I think you need something like >the linear transform from the ARIA cipher -- fast >and cheap, 128 bits in & 128 out and it makes >every output bit depend on every input bit. That >might not be enough, though. Can you please help me understand why you think that a whitening function (cryptographic or not) is needed in the case of the CPU Jitter RNG, provided that I can show that each individual bit coming from the folding operation has one bit of entropy? > >You require compilation without optimisation. How does >that interact with kernel makefiles? Can you avoid >undesirable optimisations in some other way, such as >volatile declartions? That is very easy to implement, see the kernel Makefile for my code: ... obj-m += jitterentropy.o CFLAGS_jitterentropy-base.o = -O0 jitterentropy-y := jitterentropy-base.o jitterentropy-drng.o ... This code implies that only the compilation of jitterentropy-base.c is performed with -O0. Any other C file from my code or even the reminder of the kernel is compiled with the optimization the kernel developer deemed right. > >> I am asking whether this RNG would good as an inclusion into the >> Linux >> kernel for: >> >> - kernel crypto API to provide a true random number generator as part >> of this API (see [2] appendix B for a description) > >My first reaction is no. We have /dev/random for the userspace >API and there is a decent kernel API too. I may change my >mind here as I look more at your appendix & maybe the code. The concern with /dev/random and its get_random_bytes() function is that inside the kernel, we only have the equivalent of /dev/urandom. Therefore, in the worst case, you have *no* guarantee that you obtain random numbers that are freshly seeded with hardware entropy. For example, when you look into libgcrypt and you want to have "strong random numbers", libgcrypt seeds from /dev/random every 1000 or so random numbers produced from the DRNG. Due to the ability of user space to obtain data via the nonblocking_pool using /dev/urandom and the use of the same pool for get_random_bytes, equally strong random numbers as, for example, libgcrypt would produce would not be available. Therefore, the code linking with the kernel crypto API registers three RNGs: - one X9.31 DRNG that is seeded "once in a while" with the CPU jitter - one X9.31 DRNG that is seeded "frequently" with the CPU jitter - and one direct access to the CPU jitter RNG This is logically equivalent to what is done in libgcrypt. Of course, we may replace the X9.31 with, say, an SP800-90A DRBG, if that becomes available. Furthermore, one of the core ideas of the CPU jitter RNG is that you get away from the centralized noise source of /dev/random. Such central services are also the focus for hackers. The CPU Jitter RNG allows multiple instantiations of the noise source into independent components. Every "user" of random data may now have its own private copy of a noise source and its operation. > >> - inclusion into /dev/random as an entropy provider of last resort >> when the entropy estimator falls low. > >Why only 'of last resort'? If it can provide good entropy, we should >use it often. I did not dare to be more than a provider of last resort at this point. The CPU jitter RNG is new and I guess people may want to study it first. >From my point of view, it surely can become one "regular" source. But as it delivers entropy on demand, it may simply outpace any other entropy source of /dev/random. This means, in some normal use cases, my CPU jitter RNG would always be the provider of the majority of the entropy, by far. Therefore, my CPU Jitter RNG would alter the nature of /dev/random significantly. If Ted thinks that this is ok, I am all for it and will change the patch. But I tried to be cautious and not to overwhelm people :-) > >> I will present the RNG at the Linux Symposium in Ottawa this year. >> There I can give a detailed description of the design and testing. > >I live in Ottawa, don't know if I'll make it to the Symposium this >year. Ted; I saw you at one Symposium; are you coming this >year? As mentioned before, I would really like to meet you there to have a cup of coffee over that matter. Ciao Stephan -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
