* [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random @ 2013-10-11 18:38 Stephan Mueller 2013-10-12 1:45 ` Sandy Harris 2013-10-28 15:40 ` Stephan Mueller 0 siblings, 2 replies; 61+ messages in thread From: Stephan Mueller @ 2013-10-11 18:38 UTC (permalink / raw) To: Theodore Ts'o, sandy harris, linux-kernel, linux-crypto Hi, the CPU Jitter RNG [1] is a true random number generator that is intended to work in user and kernel space equally well on a large number of different CPUs. The heart of the RNG is about 30 lines of code. The current implementation allows seamless hooking into the kernel crypto API as well as the Linux /dev/random driver. With its inherent non- blocking behavior, it could solve the problem of a blocking /dev/random. Over the last months, new tests were executed. The list of tests now cover all major operating systems and CPU types as well as microkernels of NOVA, Fiasco.OC and Pistacio. More than 200 different systems are tested. And for those, the tests show that the Jitter RNG produces high- quality output. See [2] appendix F for details. When talking with developers from different chip manufactures, I was told that even they see the execution timing jitter in their tests and cannot eliminate the timing jitter. Nor are they able to explain to 100% certainty the root cause of the jitter. Therefore, the noise source looks appropriate for general use. 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) - inclusion into /dev/random as an entropy provider of last resort when the entropy estimator falls low. Patches for both are provided in the source code tarball at [1]. A full description of the RNG together with all testing is provided at [2] or [3]. 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. [1] http://www.chronox.de [2] http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.html [3] http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.pdf Ciao Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-11 18:38 [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random Stephan Mueller @ 2013-10-12 1:45 ` Sandy Harris 2013-10-12 3:28 ` Theodore Ts'o 2013-10-12 20:12 ` Stephan Mueller 2013-10-28 15:40 ` Stephan Mueller 1 sibling, 2 replies; 61+ messages in thread From: Sandy Harris @ 2013-10-12 1:45 UTC (permalink / raw) To: Stephan Mueller; +Cc: Theodore Ts'o, LKML, linux-crypto On Fri, Oct 11, 2013 at 2:38 PM, Stephan Mueller <smueller@chronox.de> wrote: I like the basic idea. Here I'm alternately reading the email and the page you link to & commenting on both. 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 (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 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 If what you are doing is not a parity computation, then you need a better description so people like me do not misread it. 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. 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. 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. 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. 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? > 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. > - 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 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? ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-12 1:45 ` Sandy Harris @ 2013-10-12 3:28 ` Theodore Ts'o 2013-10-12 19:04 ` Stephan Mueller 2013-10-12 20:12 ` Stephan Mueller 1 sibling, 1 reply; 61+ messages in thread From: Theodore Ts'o @ 2013-10-12 3:28 UTC (permalink / raw) To: Sandy Harris; +Cc: Stephan Mueller, LKML, linux-crypto Hi Stephan, I haven't had a chance to look at your paper in detail, yet, but a quick scan has found a huge red flag for me that puts the rest of your analysis in severe doubt for me. You say that you got really good results and perfect statistical entropy on a number of platforms, including on an MIPS embedded system. You also say that you are harvesting jitter by using get_cycles() yes? Well, on the MIPS platform, here is the definition of get_cycles: static inline cycles_t get_cycles(void) { return 0; } So if you are getting great entropy results when in effect you couldn't possibly be harvesting any jitter at all, then something is really, Really, REALLY wrong with your tests. One might be that you are just getting great statistical results because of the whitening step. This is why I have very little faith in statistical tests of randomness, given that they will return perfect results for the following "random number generator" AES_ENCRYPT(i++, NSA_KEY) Regards, - Ted ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-12 3:28 ` Theodore Ts'o @ 2013-10-12 19:04 ` Stephan Mueller 0 siblings, 0 replies; 61+ messages in thread From: Stephan Mueller @ 2013-10-12 19:04 UTC (permalink / raw) To: Theodore Ts'o; +Cc: Sandy Harris, LKML, linux-crypto Am Freitag, 11. Oktober 2013, 23:28:35 schrieb Theodore Ts'o: Hi Theodore, >Hi Stephan, > >I haven't had a chance to look at your paper in detail, yet, but a >quick scan has found a huge red flag for me that puts the rest of your >analysis in severe doubt for me. > >You say that you got really good results and perfect statistical >entropy on a number of platforms, including on an MIPS embedded >system. You also say that you are harvesting jitter by using >get_cycles() yes? > >Well, on the MIPS platform, here is the definition of get_cycles: > >static inline cycles_t get_cycles(void) >{ > return 0; >} There are multiple catches to this issue: - First, if the time gathering function does not work or is to coarse, the function jent_entropy_init() returns an error. As outlined in jitterentropy(3), the result of this function must be honored before using the RNG. - Second, the time stamp function of jent_get_nstime uses __getnstimeofday in case get_cycles returns zero (see implementation of jent_get_nstime()). On MIPS systems with missing get_cycles, the RNG would use the __getnstimeofday() as get_cycles returns 0. When using the RNG in user space, it calls clock_gettime(CLOCK_REALTIME) that is backed by the same timer of__getnstimeofday on MIPS. Please consider the use of the jent_entropy_init function in the two patches for /dev/random and kernel crypto API: /dev/random: + /* we are uninitialized, try to initialize */ + if(jent_entropy_init()) + { + /* there is no CPU Jitter, disable the entropy collector */ + r->jent_enable = 0; + return; + } kernel crypto API: static int __init jent_drng_init(void) { ... ret = jent_entropy_init(); if(ret) { printk(DRIVER_NAME ": Initialization failed with host not compliant with requirements: %d\n", ret); return -EFAULT; } > >So if you are getting great entropy results when in effect you >couldn't possibly be harvesting any jitter at all, then something is >really, Really, REALLY wrong with your tests. > >One might be that you are just getting great statistical results >because of the whitening step. This is why I have very little faith There is *no* whitening function (cryptographic or otherwise) involved in the generation of random data. All is done by harvesting time deltas and align them appropriately. This is the sole reason why the heart of the RNG is only 30 lines of code. I have added arguments about broken time stamp collections in section 4.3 of the documentation in [2]. These anti tests clearly show that broken time stamps would be immediately visible and not disguised by some whitening function. Note, the testing of the 200+ systems is tone by measuring the jitter of the core of the RNG. The measurement is logically similar to measure the different add_*_randomness functions for random.c. Thus, even the logic to arrange the timing values to a random value bit stream does not affect the measurements. >in statistical tests of randomness, given that they will return >perfect results for the following "random number generator" > > AES_ENCRYPT(i++, NSA_KEY) > >Regards, > > - Ted Ciao Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-12 1:45 ` Sandy Harris 2013-10-12 3:28 ` Theodore Ts'o @ 2013-10-12 20:12 ` Stephan Mueller [not found] ` <CACXcFm=_jmeKe2YYbHDi-jTGX-23hDsDeu_weWQkr2F_FpE_6g@mail.gmail.com> 1 sibling, 1 reply; 61+ messages in thread From: Stephan Mueller @ 2013-10-12 20:12 UTC (permalink / raw) To: Sandy Harris; +Cc: Theodore Ts'o, LKML, linux-crypto 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@chronox.de> >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 ^ permalink raw reply [flat|nested] 61+ messages in thread
[parent not found: <CACXcFm=_jmeKe2YYbHDi-jTGX-23hDsDeu_weWQkr2F_FpE_6g@mail.gmail.com>]
* Fwd: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random [not found] ` <CACXcFm=_jmeKe2YYbHDi-jTGX-23hDsDeu_weWQkr2F_FpE_6g@mail.gmail.com> @ 2013-10-14 13:38 ` Sandy Harris 2013-10-14 14:12 ` Stephan Mueller 2013-10-14 14:14 ` Sandy Harris 0 siblings, 2 replies; 61+ messages in thread From: Sandy Harris @ 2013-10-14 13:38 UTC (permalink / raw) To: Theodore Ts'o, LKML, linux-crypto, Stephan Mueller Stephan Mueller <smueller@chronox.de> wrote: >>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 ... > > As the RNG is not primarily about speed, the folding operation should > stay inefficient. OK, that makes sense. >>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). No. The AND is used in a trick; x&(x-1) gives a value with exactly one bit set, the lowest bit set in x. The code there just counts that way for efficiency. Parity asks whether the number of set bits is odd or even. For example this is another way to find the parity of x. for( p = 0; x ; x >>= 1 ) p ^= (x&1) ; >From your description (I haven't looked at the code) you are computing parity. If so, say that. If not, explain. >>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. ... > ... each bit from the folding operation therefore contains > one bit of entropy. So, why should I mix it even further with some > crypto function? That does make sense, but in security code I tend to prefer a belt-and-suspenders approach. Even believing that each individual bit is truly random, I'd still mix some just in case. > 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? Basically, sheer paranoia. I'd mix and whiten just on general principles. Since efficiency is not a large concern, there is little reason not to. On the other hand, most RNGs use a hash because they need to distill some large amount of low-entropy input into a smaller high-entropy output. With high input entropy, you do not need the hash and can choose some cheaper mixer. >>> I will present the RNG at the Linux Symposium in Ottawa this year. >>> .... >> >>I live in Ottawa, ... > > As mentioned before, I would really like to meet you there to have a cup > of coffee over that matter. Sounds good. Ted, will you be around? ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: Fwd: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-14 13:38 ` Fwd: " Sandy Harris @ 2013-10-14 14:12 ` Stephan Mueller 2013-10-14 14:26 ` Stephan Mueller 2013-10-14 14:14 ` Sandy Harris 1 sibling, 1 reply; 61+ messages in thread From: Stephan Mueller @ 2013-10-14 14:12 UTC (permalink / raw) To: Sandy Harris; +Cc: Theodore Ts'o, LKML, linux-crypto Am Montag, 14. Oktober 2013, 09:38:34 schrieb Sandy Harris: Hi Sandy, >Stephan Mueller <smueller@chronox.de> wrote: > >>>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). > >No. The AND is used in a trick; x&(x-1) gives a value with exactly >one bit set, the lowest bit set in x. The code there just counts that >way for efficiency. > >Parity asks whether the number of set bits is odd or even. For >example this is another way to find the parity of x. > > for( p = 0; x ; x >>= 1 ) > p ^= (x&1) ; > >From your description (I haven't looked at the code) you are >computing parity. If so, say that. If not, explain. I re-read the referenced documentation. Yes, what I do is a parity calculation. But I do not want to think that way, although technically it is. The reason and the goal of the implementation is the following: To maintain a mathematical model in which the entropy is preserved, I can only perform the following operations: 1. Use of concatenation which in terms of entropy implies that two values concatenated with each other add the entropy the two values contain. For example: string a contains 4 bits of entropy, string b contains 6 bits of entropy. Now, when concatenating both, I get 10 bits of entropy in the combined string. 2. The use of XOR implies that the resulting value has the maximum entropy of the two individual strings. With the same example above, a XOR b implies that the resulting string has 6 bits of entropy. Any other operation will loose entropy in a way that is not easily to be modeled. Now, back to the folding loop: I know that the lower bits have some entropy. When collapsing them into one single bit, I "slice" the 64 bit timer value into 64 1 bit values and XOR the 64 bit values together. The goal is to preserve the entropy each bit holds. (PS: I am aware that in case none of the individual bits would contain one full bit of entropy, the folding operation may --mathematically spoken-- not deliver one full bit of entropy. However, after speaking with a mathematician, that slight inconsistency is ok, if I can show that the distribution of the folded bit is 50% zeros and 50% ones. That is what I did in section 5.2.1. Thus, the conclusion is that I receive one bit of entropy after the folding loop.) Yes, that is equal to parity calculation. But the reference to a parity calculation is not defined when you want to apply a mathematical model to entropy maintenance. Thus, I would rather like to have a consistent design description that I can easily apply to the entropy discussion. > >>>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. ... >> >> ... each bit from the folding operation therefore contains >> one bit of entropy. So, why should I mix it even further with some >> crypto function? > >That does make sense, but in security code I tend to prefer a >belt-and-suspenders approach. Even believing that each >individual bit is truly random, I'd still mix some just in case. I am with you on the potential for further mixing. However, please note that the standard hashes are all surjective and not bijective. Thus, they implicitly loose entropy (albeit it is not much). Therefore, a good mixing function would be a symmetric cipher. Also, I tried to have my code portable to a large variety of target systems. All of them have crypto libraries with a great number of cipher implementation, but which suffer from the lack of entropy. Thus, I concluded that I do not want to re-invent the wheel by reimplementing some cipher, but only provide what is missing: a decentral entropy source that delivers entropy on demand in kernel and user space. Who would be a user of the CPU Jitter RNG? I hardly believe that a normal end user would use it, but rather it would be provided via some crypto lib. And the authors of a crypto lib surely know how to handle the seed source (I hope). This all is the reason why I implemented the different links to various crypto libraries, where the kernel crypto API is one of it. The CPU Jitter RNG is no a stand-alone system, but always linked with a DRNG that is frequently seeded by the CPU Jitter RNG. > >> 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? > >Basically, sheer paranoia. I'd mix and whiten just on general >principles. Since efficiency is not a large concern, there is little >reason not to. I am ok with that, when you consider the surjective/bijective argument above. Still, as mentioned above, I think that will be covered by the "users" of the CPU jitter RNG. > >On the other hand, most RNGs use a hash because they need >to distill some large amount of low-entropy input into a smaller >high-entropy output. With high input entropy, you do not need >the hash and can choose some cheaper mixer. IMHO, that decision is left to the user of the code. Some users are forced to use some DRNGs (e.g. FIPS comes to mind). Thus, I do not want to do things that will need to be re-done in a slightly different way again. This is what I see as inefficient complexity that I truly want to avoid. > >>>> I will present the RNG at the Linux Symposium in Ottawa this year. >>>> .... >>> >>>I live in Ottawa, ... >>> >> As mentioned before, I would really like to meet you there to have a >> cup of coffee over that matter. > >Sounds good. Ted, will you be around? Thanks Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: Fwd: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-14 14:12 ` Stephan Mueller @ 2013-10-14 14:26 ` Stephan Mueller 0 siblings, 0 replies; 61+ messages in thread From: Stephan Mueller @ 2013-10-14 14:26 UTC (permalink / raw) To: Sandy Harris; +Cc: Theodore Ts'o, LKML, linux-crypto Am Montag, 14. Oktober 2013, 16:12:24 schrieb Stephan Mueller: Hi Sandy, > >(PS: I am aware that in case none of the individual bits would contain >one full bit of entropy, the folding operation may --mathematically >spoken-- not deliver one full bit of entropy. However, after speaking >with a mathematician, that slight inconsistency is ok, if I can show >that the distribution of the folded bit is 50% zeros and 50% ones. That >is what I did in section 5.2.1. Thus, the conclusion is that I receive >one bit of entropy after the folding loop.) One followup on this issue: if one believes that he has a problem with that consideration, he can initialize the CPU Jitter RNG with an oversampling rate. That rate simply performs the folding operation 64 times oversampling rate. To fill the entropy pool completely once, the RNG needs 64 time deltas which are folded into the one bit. All the oversampling rate now does is to calculate more than once the complete entropy pool. For example, when you set the oversampling rate to 2, you need twice as long for the random value as each bit the random value is calculated twice. And the two independent 64 bit random values are simply XORed together. You can set the oversampling rate to any value above 1. Ciao Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-14 13:38 ` Fwd: " Sandy Harris 2013-10-14 14:12 ` Stephan Mueller @ 2013-10-14 14:14 ` Sandy Harris 2013-10-14 14:40 ` Stephan Mueller 1 sibling, 1 reply; 61+ messages in thread From: Sandy Harris @ 2013-10-14 14:14 UTC (permalink / raw) To: Theodore Ts'o, LKML, linux-crypto, Stephan Mueller On Mon, Oct 14, 2013 at 9:38 AM, Sandy Harris <sandyinchina@gmail.com> wrote: > Stephan Mueller <smueller@chronox.de> wrote: >> 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? > > Basically, sheer paranoia. I'd mix and whiten just on general > principles. Since efficiency is not a large concern, there is little > reason not to. > > On the other hand, most RNGs use a hash because they need > to distill some large amount of low-entropy input into a smaller > high-entropy output. With high input entropy, you do not need > the hash and can choose some cheaper mixer. You could use strong mixing/whitening: Feed into random(4) and let it do the mixing. Use some early outputs from your RNG to key an AES instance. Then encrypt later outputs; this gives a 64 in 64 out mixer that is cryptographically strong but perhaps a bit slow in the context. Alternately, quite a few plausible components for fast cheap mixing are readily available. The Aria cipher has one that is 128 in 128 out. It multiplies a 128-bit object by a fixed Boolean matrix, makes every output bit depend on many input bits. It is fairly cheap, used in every round and the cipher is acceptably fast. The column transform from AES is 32 in 32 out and makes every output byte depend on every input byte. It is fast; has to be since it is used four times in every round. A two-way pseudo-Hadamard transform (PHT) is 2n bits in and 2n out, requires only two additions, makes both n-bit outputs depend on both inputs. PHT can be applied recursively to mix 4n, 8n, ... My QHT is 32 in 32 out, makes every /bit/ of output depend on every bit of input. It is a tad expensive; two multiplications & two modulo operations. File qht.c at: ftp://ftp.cs.sjtu.edu.cn:990/sandy/maxwell/ To mix 64 bits, I'd use two qht() calls to mix the 32-bit halves then a two-way PHT. ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-14 14:14 ` Sandy Harris @ 2013-10-14 14:40 ` Stephan Mueller 2013-10-14 15:18 ` Sandy Harris 0 siblings, 1 reply; 61+ messages in thread From: Stephan Mueller @ 2013-10-14 14:40 UTC (permalink / raw) To: Sandy Harris; +Cc: Theodore Ts'o, LKML, linux-crypto Am Montag, 14. Oktober 2013, 10:14:00 schrieb Sandy Harris: Hi Sandy, >On Mon, Oct 14, 2013 at 9:38 AM, Sandy Harris <sandyinchina@gmail.com> wrote: >> Stephan Mueller <smueller@chronox.de> wrote: >>> 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? >> >> Basically, sheer paranoia. I'd mix and whiten just on general >> principles. Since efficiency is not a large concern, there is little >> reason not to. >> >> On the other hand, most RNGs use a hash because they need >> to distill some large amount of low-entropy input into a smaller >> high-entropy output. With high input entropy, you do not need >> the hash and can choose some cheaper mixer. > >You could use strong mixing/whitening: > >Feed into random(4) and let it do the mixing. That is exactly the goal with the patch found in patches/linux-3.9- random.patch in the code distribution. And that approach is exactly what I do in the linking code / patches for other crypto libs: - kernel crypto API - OpenSSL (implementation as an Engine that uses the internal DRNGs or a hook into RAND_poll that implements the seeding for the DRNGs) - libgcrypt (hook into the seeding of the DRNGs) > >Use some early outputs from your RNG to key an AES >instance. Then encrypt later outputs; this gives a 64 in 64 >out mixer that is cryptographically strong but perhaps a bit >slow in the context. That is exactly what the SP800-90A CTR DRBG or the X9.31 does. As these DRNGs are available for different crypto libs, I am simply reusing them with the crypto lib linking code. > >Alternately, quite a few plausible components for fast cheap >mixing are readily available. Thank you for the references. I have seen that in your maxwell(8) documentation. But again, I do not re-invent the wheel with the CPU Jitter RNG and therefore skipped the whitening step based on the reasons above. Another thing: when you start adding whitening functions, other people are starting (and did -- thus I added section 4.3 to my documentation) to complain that you hide your weaknesses behind the whiteners. I simply want to counter that argument and show that RNG produces white noise without a whitener. Ciao Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-14 14:40 ` Stephan Mueller @ 2013-10-14 15:18 ` Sandy Harris 2013-10-14 15:26 ` Stephan Mueller 2013-10-15 6:23 ` Stephan Mueller 0 siblings, 2 replies; 61+ messages in thread From: Sandy Harris @ 2013-10-14 15:18 UTC (permalink / raw) To: Stephan Mueller; +Cc: Theodore Ts'o, LKML, linux-crypto On Mon, Oct 14, 2013 at 10:40 AM, Stephan Mueller <smueller@chronox.de> wrote: > Another thing: when you start adding whitening functions, other people > are starting (and did -- thus I added section 4.3 to my documentation) > to complain that you hide your weaknesses behind the whiteners. I simply > want to counter that argument and show that RNG produces white noise > without a whitener. Yes, you absolutely have to test the unwhitened input entropy, and provide a way for others to test it so they can have confidence in your code and it can be tested again if it is going to be used on some new host. You do a fine job of that; your paper has the most detailed analysis I have seen. Bravo. However, having done that, I see no reason not to add mixing. Using bit() for getting one bit of input and rotl(x) for rotating left one bit, your code is basically, with 64-bit x: for( i=0, x = 0 ; i < 64; i++, x =rotl(x) ) x |= bit() Why not declare some 64-bit constant C with a significant number of bits set and do this: for( i=0, x = 0 ; i < 64; i++, x =rotl(x) ) // same loop control if( bit() ) x ^= C ; This makes every output bit depend on many input bits and costs almost nothing extra. In the unlikely event that the overhead here matters, your deliberately inefficient parity calculation in bit() could easily be made faster to compensate. ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-14 15:18 ` Sandy Harris @ 2013-10-14 15:26 ` Stephan Mueller 2013-10-14 15:46 ` Sandy Harris 2013-10-14 21:33 ` Sandy Harris 2013-10-15 6:23 ` Stephan Mueller 1 sibling, 2 replies; 61+ messages in thread From: Stephan Mueller @ 2013-10-14 15:26 UTC (permalink / raw) To: Sandy Harris; +Cc: Theodore Ts'o, LKML, linux-crypto Am Montag, 14. Oktober 2013, 11:18:16 schrieb Sandy Harris: Hi Sandy, >On Mon, Oct 14, 2013 at 10:40 AM, Stephan Mueller <smueller@chronox.de> wrote: >> Another thing: when you start adding whitening functions, other >> people >> are starting (and did -- thus I added section 4.3 to my >> documentation) >> to complain that you hide your weaknesses behind the whiteners. I >> simply want to counter that argument and show that RNG produces >> white noise without a whitener. > >Yes, you absolutely have to test the unwhitened input entropy, and >provide a way for others to test it so they can have confidence in your >code and it can be tested again if it is going to be used on some new >host. You do a fine job of that; your paper has the most detailed >analysis I have seen. Bravo. Thank you very much. > >However, having done that, I see no reason not to add mixing. >Using bit() for getting one bit of input and rotl(x) for rotating >left one bit, your code is basically, with 64-bit x: > > for( i=0, x = 0 ; i < 64; i++, x =rotl(x) ) > x |= bit() Ok, let me play a bit with that. Maybe I can add another flag to the allocation function so that the caller can decide whether to use that. If the user is another RNG, you skip that mixing function, otherwise you should take it. But I need a whitening / mixing function that should not add more dependencies on the underlying host. The code you have above would be ok. > >Why not declare some 64-bit constant C with a significant Which constant would you take? The CRC twist values? The SHA-1 initial values? Or the first few from SHA-256? >number of bits set and do this: > > for( i=0, x = 0 ; i < 64; i++, x =rotl(x) ) // same loop control > if( bit() ) x ^= C ; > >This makes every output bit depend on many input bits >and costs almost nothing extra. Good point. > >In the unlikely event that the overhead here matters, >your deliberately inefficient parity calculation in bit() >could easily be made faster to compensate. I will come back to you on this suggestion. Ciao Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-14 15:26 ` Stephan Mueller @ 2013-10-14 15:46 ` Sandy Harris 2013-10-14 21:33 ` Sandy Harris 1 sibling, 0 replies; 61+ messages in thread From: Sandy Harris @ 2013-10-14 15:46 UTC (permalink / raw) To: Stephan Mueller; +Cc: Theodore Ts'o, LKML, linux-crypto On Mon, Oct 14, 2013 at 11:26 AM, Stephan Mueller <smueller@chronox.de> wrote: >>Why not declare some 64-bit constant C with a significant > > Which constant would you take? The CRC twist values? The SHA-1 initial > values? Or the first few from SHA-256? The only essential requirement is that it not be something stupidly regular like a 64-bit string 0x5555555555555555. I'd pick an odd number so the low bit always changes, and a constant with about half the bits set, maybe 24 < n < 40 or some such. I'm not certain either of those is strictly required but I'd do them anyway. ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-14 15:26 ` Stephan Mueller 2013-10-14 15:46 ` Sandy Harris @ 2013-10-14 21:33 ` Sandy Harris 1 sibling, 0 replies; 61+ messages in thread From: Sandy Harris @ 2013-10-14 21:33 UTC (permalink / raw) To: Stephan Mueller; +Cc: Theodore Ts'o, LKML, linux-crypto Stephan Mueller <smueller@chronox.de> wrote: > [quoting me] >> ...your code is basically, with 64-bit x: >> >> for( i=0, x = 0 ; i < 64; i++, x =rotl(x) ) >> x |= bit() > > Why not declare some 64-bit constant C with a significant >>number of bits set and do this: >> >> for( i=0, x = 0 ; i < 64; i++, x =rotl(x) ) // same loop control >> if( bit() ) x ^= C ; >> >>This makes every output bit depend on many input bits >>and costs almost nothing extra. > Ok, let me play a bit with that. Maybe I can add another flag to the > allocation function so that the caller can decide whether to use that. > If the user is another RNG, you skip that mixing function, otherwise you > should take it. I'd say just do it. It is cheap enough and using it does no harm even where it is not strictly needed. Adding a flag just gives the calling code a chance to get it wrong. Better not to take that risk if you don't have to. ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-14 15:18 ` Sandy Harris 2013-10-14 15:26 ` Stephan Mueller @ 2013-10-15 6:23 ` Stephan Mueller 1 sibling, 0 replies; 61+ messages in thread From: Stephan Mueller @ 2013-10-15 6:23 UTC (permalink / raw) To: Sandy Harris; +Cc: Theodore Ts'o, LKML, linux-crypto Am Montag, 14. Oktober 2013, 11:18:16 schrieb Sandy Harris: Hi Sandy, Could you please review the following code to see that the mix is function right in your eyes? > >However, having done that, I see no reason not to add mixing. >Using bit() for getting one bit of input and rotl(x) for rotating >left one bit, your code is basically, with 64-bit x: > > for( i=0, x = 0 ; i < 64; i++, x =rotl(x) ) > x |= bit() > >Why not declare some 64-bit constant C with a significant >number of bits set and do this: > > for( i=0, x = 0 ; i < 64; i++, x =rotl(x) ) // same loop control > if( bit() ) x ^= C ; I only want to use the XOR function as this is bijective and fits to my mathematical model. The entropy_collector->data contains the random number. The code first produces the mixer value that is XORed as often as set bits are available in the input random number. Finally, it is XORed with the random number. The function is currently called unconditionally after the 64 bit random number is generated from the noise source. static inline void jent_stir_pool(struct rand_data *entropy_collector) { /* This constant is derived from the first two 32 bit initialization * vectors of SHA-1 -- 32 bits are set and 32 are unset */ __u64 constant = 0x67452301efcdab89; __u64 mixer = 0; int i = 0; for(i = 0; i < DATA_SIZE_BITS; i++) { /* get the i-th bit of the input random number and * XOR the constant into the mixer value only when that bit * is set */ if((entropy_collector->data >> i) & 0x0000000000000001) mixer ^= constant; mixer = rol64(mixer, 1); } entropy_collector->data ^= mixer; } The statistical behavior of the output looks good so far (just tested it with the ent tool -- the Chi Square value is good). It also does not compress with bzip2. Thanks a lot Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-11 18:38 [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random Stephan Mueller 2013-10-12 1:45 ` Sandy Harris @ 2013-10-28 15:40 ` Stephan Mueller 2013-10-28 16:06 ` Henrique de Moraes Holschuh 2013-10-28 21:45 ` Theodore Ts'o 1 sibling, 2 replies; 61+ messages in thread From: Stephan Mueller @ 2013-10-28 15:40 UTC (permalink / raw) To: Theodore Ts'o; +Cc: sandy harris, linux-kernel, linux-crypto Am Freitag, 11. Oktober 2013, 20:38:51 schrieb Stephan Mueller: Hi Ted, >Hi, > >the CPU Jitter RNG [1] is a true random number generator that is >intended to work in user and kernel space equally well on a large >number of different CPUs. The heart of the RNG is about 30 lines of >code. The current implementation allows seamless hooking into the >kernel crypto API as well as the Linux /dev/random driver. With its >inherent non- blocking behavior, it could solve the problem of a >blocking /dev/random. > >Over the last months, new tests were executed. The list of tests now >cover all major operating systems and CPU types as well as microkernels >of NOVA, Fiasco.OC and Pistacio. More than 200 different systems are >tested. And for those, the tests show that the Jitter RNG produces >high- quality output. See [2] appendix F for details. Apart from adding more test results from more systems (now including Windows), I added more updates: - The structure of the Linux kernel code is updated such that the common C code can go to straight to the lib/ directory or any other directory that seems suitable for common code. If it is of help, I can create a patch file to add the CPU Jitter RNG to the Linux kernel code instead of manually copying into a kernel tree for testing it with random.c. - Based on Sandy Harris' discussion in http://permalink.gmane.org/gmane.comp.encryption.general/16219, the patch for random.c is updated that the initialization function of the entropy pools init_std_data now contains a call to the CPU Jitter RNG to mix in 256 bits of entropy when the entropy pool is filled. If it is accepted that the CPU Jitter RNG delivers entropy, the latter update may now allow us to get rid of storing the seed file during shutdown and restoring it during the next boot sequence. Please see the latest patch to random.c in the file patches/linux-3.11- random.patch delivered with [1]. Ciao Stephan [1] http://www.chronox.de/jent/jitterentropy-20131028.tar.bz2 ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-28 15:40 ` Stephan Mueller @ 2013-10-28 16:06 ` Henrique de Moraes Holschuh 2013-10-28 16:15 ` Stephan Mueller 2013-10-28 21:45 ` Theodore Ts'o 1 sibling, 1 reply; 61+ messages in thread From: Henrique de Moraes Holschuh @ 2013-10-28 16:06 UTC (permalink / raw) To: Stephan Mueller Cc: Theodore Ts'o, sandy harris, linux-kernel, linux-crypto On Mon, 28 Oct 2013, Stephan Mueller wrote: > If it is accepted that the CPU Jitter RNG delivers entropy, the latter > update may now allow us to get rid of storing the seed file during > shutdown and restoring it during the next boot sequence. That's a 4096-bit safety net (uncredited entropy) which at least Debian shall not remove. I think Debian also dumps some low-entropy-per-bit crap into /dev/random during boot (again, not credited), such as the boot kernel logs. We could increase the density of that entropy a lot using gzip -0 or something like that... is an uncredited low-entropy-per-bit dump into the pool detrimental to its quality? -- "One disk to rule them all, One disk to find them. One disk to bring them all and in the darkness grind them. In the Land of Redmond where the shadows lie." -- The Silicon Valley Tarot Henrique Holschuh ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-28 16:06 ` Henrique de Moraes Holschuh @ 2013-10-28 16:15 ` Stephan Mueller 0 siblings, 0 replies; 61+ messages in thread From: Stephan Mueller @ 2013-10-28 16:15 UTC (permalink / raw) To: Henrique de Moraes Holschuh Cc: Theodore Ts'o, sandy harris, linux-kernel, linux-crypto Am Montag, 28. Oktober 2013, 14:06:23 schrieb Henrique de Moraes Holschuh: Hi Henrique, >On Mon, 28 Oct 2013, Stephan Mueller wrote: >> If it is accepted that the CPU Jitter RNG delivers entropy, the >> latter >> update may now allow us to get rid of storing the seed file during >> shutdown and restoring it during the next boot sequence. > >That's a 4096-bit safety net (uncredited entropy) which at least Debian >shall not remove. That is correct, and I did not want have such safety net removed. I have to correct my initial statement: there is a possibility where the CPU Jitter RNG may not deliver data: when the timer resolution is too coarse. Thus, please disregard my notion to remove the user space seeding. My goal is that the entropy pools are filled with entropy at the time when they are created so that they will deliver good random data if the system has a high resolution timer (which is almost always the case as shown with my tests). > >I think Debian also dumps some low-entropy-per-bit crap into >/dev/random during boot (again, not credited), such as the boot kernel >logs. We could increase the density of that entropy a lot using gzip >-0 or something like that... is an uncredited low-entropy-per-bit dump >into the pool detrimental to its quality? Any mixing of data into the entropy pools can never diminish the entropy, but just further mix the data. Note, a simple write of data into the device files will never update the entropy estimator that is behind the blocking of /dev/random. All that is done by the write to the device files is the mixing of the entropy pools of blocking_pool and nonblocking_pool (and not input_pool). Ciao Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-28 15:40 ` Stephan Mueller 2013-10-28 16:06 ` Henrique de Moraes Holschuh @ 2013-10-28 21:45 ` Theodore Ts'o 2013-10-29 8:42 ` Stephan Mueller 2013-10-30 12:59 ` [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random Sandy Harris 1 sibling, 2 replies; 61+ messages in thread From: Theodore Ts'o @ 2013-10-28 21:45 UTC (permalink / raw) To: Stephan Mueller; +Cc: sandy harris, linux-kernel, linux-crypto Fundamentally, what worries me about this scheme (actually, causes the hair on the back of my neck to rise up on end) is this statement in your documentation[1]: When looking at the sequence of time deltas gathered during testing [D] , no pattern can be detected. Therefore, the fluctuation and the resulting distribution are not based on a repeating pattern and must be considered random. [1] http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.html Just because we can't detect a pattern does **not** mean that it is not based on a repeating pattern, and therefore must be considered random. We can't detect a pattern in RDRAND, so does that mean it's automatically random? Why, no. If all you have is the output of "AES_ENCRPYT(NSA_KEY, i++)". and NSA_KEY is not known to you, you won't be able to detect a pattern, either. But I can guarantee to you that it's not random... It may be that there is some very complex state which is hidden inside the the CPU execution pipeline, the L1 cache, etc., etc. But just because *you* can't figure it out, and just because *I* can't figure it out doesn't mean that it is ipso facto something which a really bright NSA analyst working in Fort Meade can't figure out. (Or heck, a really clever Intel engineer who has full visibility into the internal design of an Intel CPU....) Now, it may be that in practice, an adversary won't be able to carry out a practical attack because there will be external interrupts that the adversary won't be able to put into his or her model of your CPU --- for example, from network interrupts or keyboard interrupts. But in that case, it's to measure just the interrupt, because it may be that the 32 interrupts that you got while extracting 128 bits of entropy from your jitter engine was only 32 bits of entropy, and the rest could be determined by someone with sufficient knowledge and understanding of the internal guts of the CPU. (Treating this obscurity as security is probably not a good idea; we have to assume the NSA can get its hands on anything it wants, even internal, super-secret, "black cover" Intel documents. :-) To be honest, I have exactly the same worry about relying on HDD interrupts. The theoretical basis of this resulting in true randomness is based on a 1994 paper by Don Davis: "Cryptographic randomness from air turbulence in disk drives"[2]: [2] http://world.std.com/~dtd/random/forward.pdf The problem is that almost two decades later, the technology of HDD's, and certainly SSD (which didn't exist back then) have changed quite a lot. It is not obvious to me how much entropy you can really get from observing the disk completion times if you assume that the adversary has complete knowledge to the relative timing and block numbers of the disk accesses from the OS (for example, if we boot multiple mobile phone from flash for the first time, how many bits of entropy are there really?) But at least back in 1994, there was an attempt to come up with a physical theory as to where the entropy was coming from, and then as much work as possible to rule out other possible causes of the uncertainty. So if you want to really convince the world that CPU jitter is random, it's not enough to claim that it you can't see a pattern. What you need to do is to remove all possible sources of the uncertainty, and show that there is still no discernable pattern after you do things like (a) run in kernel space, on an otherwise quiscent computer, (b) disable interrupts, so that any uncertainty can't be coming from interrupts, etc., Try to rule it all out, and then see if you still get uncertainty. If you think it is from DRAM timing, first try accessing the same memory location in kernel code with the interrupts off, over and over again, so that the memory is pinned into L1 cache. You should be able to get consistent results. If you can, then if you then try to read from DRAM with the L1 and L2 caches disabled, and with interrupts turned off, etc, and see if you get consistent results or inconsistent results. If you get consistent results in both cases, then your hypothesis is disproven. If you get consistent results with the memory pinned in L1 cache, and inconsistent results when the L1 and L2 cache are disabled, then maybe the timing of DRAM reads really are introducing entropy. But the point is you need to test each part of the system in isolation, so you can point at a specific part of the system and say, *that*'s where at least some uncertainty which an adversary can not reverse engineer, and here is the physical process from which the choatic air patterns, or quantum effects, etc., which is hypothesized to cause the uncertainty. And note that when you do this, you can't use any unbiasing or whitening techniques --- you want to use the raw timings, and then do things like look very hard for any kind of patterns; Don Davis used FFT's because he wanted to look for any patterns that might be introduced by the rotating plattern, which would presumably would show up in a frequency domain analysis even if it was invisible in the time domain. If you don't do all of this work, there is no way to know for sure where the entropy is coming from. And if you don't know, that's when you have to be very, very conservative, and use a very large engineering safety margin. Currently we use the high resolution CPU counter, plus the interrupted IP, and we mix all of this together from 64 interrupts, and we count this as a single bit of entropy. I *hope* that at least one of those interrupts has sufficient unpredictably, perhaps because the remote attacker can't know when a LAN interrupt has happened, such that have a single bit of entropy. Maybe someone can prove that there is more entropy because of some instability between the oscillator used by the CPU clock and the one used by the ethernet NIC, and so I'm being hopelessly over-conservative. Perhaps; but until we know for sure, using a similar analysis to what I described above, I'd much rather be slow than be potentially insecure. The jitter "entropy collector" may be able to generate more "randomness" much more quickly, but is the resulting numbers really more secure? Other people will have to judge for themselves, but this is why I'm not convinced. Best regards, - Ted ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-28 21:45 ` Theodore Ts'o @ 2013-10-29 8:42 ` Stephan Mueller 2013-10-29 13:24 ` Theodore Ts'o 2013-10-30 12:59 ` [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random Sandy Harris 1 sibling, 1 reply; 61+ messages in thread From: Stephan Mueller @ 2013-10-29 8:42 UTC (permalink / raw) To: Theodore Ts'o; +Cc: sandy harris, linux-kernel, linux-crypto Am Montag, 28. Oktober 2013, 17:45:49 schrieb Theodore Ts'o: Hi Theodore, first of all, thank you for your thoughts. And, before we continue any discussion, please consider that all the big testing that is done to analyze the jitter so far did (a) not include any whitening schema (cryptographic or otherwise) and (b) did not even include the processing done inside the RNG. The testing in appendix F of the documentation just measures the execution time of some instructions -- the very heart of the RNG, and not more. And only if these show variations, then I conclude the RNG can be used. [...] > >It may be that there is some very complex state which is hidden inside >the the CPU execution pipeline, the L1 cache, etc., etc. But just >because *you* can't figure it out, and just because *I* can't figure >it out doesn't mean that it is ipso facto something which a really >bright NSA analyst working in Fort Meade can't figure out. (Or heck, >a really clever Intel engineer who has full visibility into the >internal design of an Intel CPU....) I concur here. But so are all sources of /dev/random too. As you have outlined later, your HDD fluctuations may not be as trustworthy as we think. The key strokes and their timings can be obtained from electromagnetic emanation. Lastly, the use of the fast_pool using interrupts may still show a correlation with the other noise sources as they all generate interrupts. But I diverge as we talk about my RNG and do not analyze random.c. So, I guess we all agree on the notion that entropy is *relative*. Some information may be more entropic to one than to the other. However, for us, it shall be entropy enough to counter our adversary. > >Now, it may be that in practice, an adversary won't be able to carry >out a practical attack because there will be external interrupts that >the adversary won't be able to put into his or her model of your CPU >--- for example, from network interrupts or keyboard interrupts. But >in that case, it's to measure just the interrupt, because it may be >that the 32 interrupts that you got while extracting 128 bits of >entropy from your jitter engine was only 32 bits of entropy, and the >rest could be determined by someone with sufficient knowledge and >understanding of the internal guts of the CPU. (Treating this >obscurity as security is probably not a good idea; we have to assume >the NSA can get its hands on anything it wants, even internal, >super-secret, "black cover" Intel documents. :-) Again, I concur. But since I have seen the jitter with quite similar size on all the major CPUs we have around us (Intel, AMD, Sparc, POWER, PowerPC, ARM, MIPS, zSeries), I guess you need to update your statement to "... even internal, super-secret, "black cover" documents that are synchronized among all the different chip vendors". :-) [...] Thanks again to your ideas below in testing the issue more. > >So if you want to really convince the world that CPU jitter is random, >it's not enough to claim that it you can't see a pattern. What you >need to do is to remove all possible sources of the uncertainty, and >show that there is still no discernable pattern after you do things >like (a) run in kernel space, on an otherwise quiscent computer, (b) Re: (a) that is what I already did. The kernel implementation of the RNG is capable of that testing. Moreover, that is what I already did in section 5.1. It is easy for everybody to redo the testing by simply compiling the kernel module, load it and look into /sys/kernel/debug/jitterentropy. There you find some files that are direct interfaces to the RNG. In particular, the file stat-fold is the key to redo the testing that covers appendix F of my document (as mentioned above, there is no postprocessing of the raw variations when you read that file). >disable interrupts, so that any uncertainty can't be coming from >interrupts, etc., Try to rule it all out, and then see if you still >get uncertainty. When I did testing on all systems, interrupts are easily visible by the larger "variations". When compiling the test results in appendix F, all measurements that are a tad higher than the majority of the variations are simply removed to focus on the worst case. I.e. the measurements and the results *already* exclude any interrupts, scheduling impacts. Regarding, caches, may I ask you to look into appendix F.46 of the current document version? I conducted tests that tried to disable / remove the impact of: system call context switches, flushing the instruction pipeline, flushing of all caches, disabling preemtion, flushing TLB, executing the code exclusively on one CPU core, disabling of power management and frequency scaling. All these tests show *no* deterioration in jitter, i.e. the jitter is still there. The only exception is the power management where I see some small jitter drop off, which is analyzed and concluded to be unproblematic. > >If you think it is from DRAM timing, first try accessing the same >memory location in kernel code with the interrupts off, over and over >again, so that the memory is pinned into L1 cache. You should be able That is what the testing already does. I constantly access some piece of memory millions of times and measure the execution time of the operation on that memory location. As mentioned above, interrupts are disregarded in any case. And, jitter is there. >to get consistent results. If you can, then if you then try to read >from DRAM with the L1 and L2 caches disabled, and with interrupts Based on this suggestion, I now added the tests in Appendix F.46.8 where I disable the caches and the tests in Appendix F.46.9 where I disable the caches and interrupts. The results show that the jitter even goes way up -- thus, jitter that is sufficient is even more present when disabling the caches and interrupts. >turned off, etc, and see if you get consistent results or inconsistent >results. If you get consistent results in both cases, then your >hypothesis is disproven. If you get consistent results with the Currently, the hypothesis is *not* disproven. >memory pinned in L1 cache, and inconsistent results when the L1 and L2 >cache are disabled, then maybe the timing of DRAM reads really are >introducing entropy. But the point is you need to test each part of >the system in isolation, so you can point at a specific part of the >system and say, *that*'s where at least some uncertainty which an >adversary can not reverse engineer, and here is the physical process >from which the choatic air patterns, or quantum effects, etc., which >is hypothesized to cause the uncertainty. As I tried quite a number of different variations on disabling / enabling features in appendix F.46, I am out of ideas what else I should try. > >And note that when you do this, you can't use any unbiasing or >whitening techniques --- you want to use the raw timings, and then do >things like look very hard for any kind of patterns; Don Davis used Again, there is no whitening, and not even the RNG processing involved. All I am doing is simple timing analysis of some fixed set of instructions -- i.e. the very heart of the RNG. [..] > >The jitter "entropy collector" may be able to generate more >"randomness" much more quickly, but is the resulting numbers really >more secure? Other people will have to judge for themselves, but this >is why I'm not convinced. May I ask to recheck appendix F.46 again? Thanks Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-29 8:42 ` Stephan Mueller @ 2013-10-29 13:24 ` Theodore Ts'o 2013-10-29 14:00 ` Stephan Mueller 2013-11-13 3:37 ` [PATCH] CPU Jitter RNG: Executing time variation tests on bare metal Stephan Mueller 0 siblings, 2 replies; 61+ messages in thread From: Theodore Ts'o @ 2013-10-29 13:24 UTC (permalink / raw) To: Stephan Mueller; +Cc: sandy harris, linux-kernel, linux-crypto On Tue, Oct 29, 2013 at 09:42:30AM +0100, Stephan Mueller wrote: > Based on this suggestion, I now added the tests in Appendix F.46.8 where > I disable the caches and the tests in Appendix F.46.9 where I disable > the caches and interrupts. What you've added in F.46 is a good start, but as a suggestiom, instead of disabling one thing at a time, try disabling *everything* and then see what you get, and then enabling one thing at a time. The best thing is if you can get to the point where the amount of entropy is close to zero. Then as you add things back, there's a much better sense of where the unpredictability might be coming from, and whether the unpredictability is coming from something which is fundamentally arising from something which is chaotic or quantum effect, or just because we don't have a good way of modelling the behavior of the L1/L2 cache (for example) and that is spoofing your entropy estimator. Regards, - Ted ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-29 13:24 ` Theodore Ts'o @ 2013-10-29 14:00 ` Stephan Mueller 2013-10-29 22:25 ` Stephan Mueller 2013-11-02 11:01 ` Pavel Machek 2013-11-13 3:37 ` [PATCH] CPU Jitter RNG: Executing time variation tests on bare metal Stephan Mueller 1 sibling, 2 replies; 61+ messages in thread From: Stephan Mueller @ 2013-10-29 14:00 UTC (permalink / raw) To: Theodore Ts'o; +Cc: sandy harris, linux-kernel, linux-crypto Am Dienstag, 29. Oktober 2013, 09:24:48 schrieb Theodore Ts'o: Hi Theodore, >On Tue, Oct 29, 2013 at 09:42:30AM +0100, Stephan Mueller wrote: >> Based on this suggestion, I now added the tests in Appendix F.46.8 >> where I disable the caches and the tests in Appendix F.46.9 where I >> disable the caches and interrupts. > >What you've added in F.46 is a good start, but as a suggestiom, >instead of disabling one thing at a time, try disabling *everything* >and then see what you get, and then enabling one thing at a time. The >best thing is if you can get to the point where the amount of entropy >is close to zero. Then as you add things back, there's a much better I will try to do that. But please see the different lower boundary values in the different subsections of F.46: none of them fall when I disable or change anything in the base system (except the power management -- where I added additional analyses). Some of the changes imply that the jitter increases when I disable certain support. Thus, expect that we will not see a significant drop in the jitter as you fear or expect. Yet, I will try and report back. Though, does anybody has an idea how to flush/disable branch prediction on x86 (short of using an ARM where I can disable the branch prediction unit with CP15)? That is the last unit that I do not have a handle on. >sense of where the unpredictability might be coming from, and whether >the unpredictability is coming from something which is fundamentally >arising from something which is chaotic or quantum effect, or just >because we don't have a good way of modelling the behavior of the >L1/L2 cache (for example) and that is spoofing your entropy estimator. Please note: if the jitter really comes from the oscillator effect of the RAM clock vs. the CPU clock (which I suspect), we will not be able to alter the jitter software wise. The reason why I suspect that oscillating effect is the following: I spoke with two different employees from the research departments of major chip vendors. They mentioned that they see the very same jitter in their measurements albeit they tried to get rid of it. So, when they cannot get rid of that, I guess we will not be able to lower or even eliminate the jitter significantly. Ciao Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-29 14:00 ` Stephan Mueller @ 2013-10-29 22:25 ` Stephan Mueller 2013-11-02 11:01 ` Pavel Machek 1 sibling, 0 replies; 61+ messages in thread From: Stephan Mueller @ 2013-10-29 22:25 UTC (permalink / raw) To: Theodore Ts'o; +Cc: sandy harris, linux-kernel, linux-crypto Am Dienstag, 29. Oktober 2013, 15:00:31 schrieb Stephan Mueller: Hi Ted, >Am Dienstag, 29. Oktober 2013, 09:24:48 schrieb Theodore Ts'o: > >Hi Theodore, > >>On Tue, Oct 29, 2013 at 09:42:30AM +0100, Stephan Mueller wrote: >>> Based on this suggestion, I now added the tests in Appendix F.46.8 >>> where I disable the caches and the tests in Appendix F.46.9 where I >>> disable the caches and interrupts. >> >>What you've added in F.46 is a good start, but as a suggestiom, >>instead of disabling one thing at a time, try disabling *everything* >>and then see what you get, and then enabling one thing at a time. The >>best thing is if you can get to the point where the amount of entropy >>is close to zero. Then as you add things back, there's a much better > >I will try to do that. > >But please see the different lower boundary values in the different >subsections of F.46: none of them fall when I disable or change >anything in the base system (except the power management -- where I >added additional analyses). Some of the changes imply that the jitter >increases when I disable certain support. > >Thus, expect that we will not see a significant drop in the jitter as >you fear or expect. > >Yet, I will try and report back. Please have a look at the updated documentation, appendix F.46.10 provided in [1]. The interesting result is that some combinations of disabling CPU support do reduce the CPU execution jitter. However, disabling all support is not the lowest jitter measurement. Though, none of the tried combinations deteriorate the measurement so much that the execution jitter would be insufficient for use in the RNG. [...] >>sense of where the unpredictability might be coming from, and whether >>the unpredictability is coming from something which is fundamentally >>arising from something which is chaotic or quantum effect, or just >>because we don't have a good way of modelling the behavior of the >>L1/L2 cache (for example) and that is spoofing your entropy estimator. > >Please note: if the jitter really comes from the oscillator effect of >the RAM clock vs. the CPU clock (which I suspect), we will not be able >to alter the jitter software wise. My current conclusion is that software can have some impact on the execution jitter (as it is visible when executing different OSes on the same hardware system as outlined in appendix F.45. But none of the software impacts can deteriorate the jitter to the level that it is not usable any more for the RNG and still keep the claim that each output bit would have one bit of entropy. [1] http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.html Ciao Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-29 14:00 ` Stephan Mueller 2013-10-29 22:25 ` Stephan Mueller @ 2013-11-02 11:01 ` Pavel Machek 2013-11-02 11:12 ` Pavel Machek 2013-11-03 7:20 ` Stephan Mueller 1 sibling, 2 replies; 61+ messages in thread From: Pavel Machek @ 2013-11-02 11:01 UTC (permalink / raw) To: Stephan Mueller Cc: Theodore Ts'o, sandy harris, linux-kernel, linux-crypto Hi! > >sense of where the unpredictability might be coming from, and whether > >the unpredictability is coming from something which is fundamentally > >arising from something which is chaotic or quantum effect, or just > >because we don't have a good way of modelling the behavior of the > >L1/L2 cache (for example) and that is spoofing your entropy estimator. > > Please note: if the jitter really comes from the oscillator effect of > the RAM clock vs. the CPU clock (which I suspect), we will not be able > to alter the jitter software wise. Well... if it is really oscillator effect, there should be _no_ entropy when running with L1/L2 enabled (because DRAM will not be accessed at all at that case). There should be way to extract entropy more directly from various oscillator effects, no? For DRAM, just perform timing, have entropy. Plus we could for example measure PIT vs. other timer sources... (but I suspect that on PCs we already have enough entropy...) Pavel -- (english) http://www.livejournal.com/~pavelmachek (cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-02 11:01 ` Pavel Machek @ 2013-11-02 11:12 ` Pavel Machek 2013-11-03 7:20 ` Stephan Mueller 1 sibling, 0 replies; 61+ messages in thread From: Pavel Machek @ 2013-11-02 11:12 UTC (permalink / raw) To: Stephan Mueller Cc: Theodore Ts'o, sandy harris, linux-kernel, linux-crypto On Sat 2013-11-02 12:01:12, Pavel Machek wrote: > Hi! > > > >sense of where the unpredictability might be coming from, and whether > > >the unpredictability is coming from something which is fundamentally > > >arising from something which is chaotic or quantum effect, or just > > >because we don't have a good way of modelling the behavior of the > > >L1/L2 cache (for example) and that is spoofing your entropy estimator. > > > > Please note: if the jitter really comes from the oscillator effect of > > the RAM clock vs. the CPU clock (which I suspect), we will not be able > > to alter the jitter software wise. > > Well... if it is really oscillator effect, there should be _no_ > entropy when running with L1/L2 enabled (because DRAM will not be > accessed at all at that case). > > There should be way to extract entropy more directly from various > oscillator effects, no? Actually... bogomips calibrating loop already has jitter, measured from difference between CPU clock and system clock... Could that be used as entropy source? As a bonus, we should have it on most platforms... Pavel -- (english) http://www.livejournal.com/~pavelmachek (cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-02 11:01 ` Pavel Machek 2013-11-02 11:12 ` Pavel Machek @ 2013-11-03 7:20 ` Stephan Mueller 2013-11-03 12:41 ` Theodore Ts'o 2013-11-03 23:32 ` Pavel Machek 1 sibling, 2 replies; 61+ messages in thread From: Stephan Mueller @ 2013-11-03 7:20 UTC (permalink / raw) To: Pavel Machek; +Cc: Theodore Ts'o, sandy harris, linux-kernel, linux-crypto Am Samstag, 2. November 2013, 12:01:13 schrieb Pavel Machek: Hi Pavel, >Hi! > >> >sense of where the unpredictability might be coming from, and >> >whether >> >the unpredictability is coming from something which is fundamentally >> >arising from something which is chaotic or quantum effect, or just >> >because we don't have a good way of modelling the behavior of the >> >L1/L2 cache (for example) and that is spoofing your entropy >> >estimator. >> >> Please note: if the jitter really comes from the oscillator effect of >> the RAM clock vs. the CPU clock (which I suspect), we will not be >> able >> to alter the jitter software wise. > >Well... if it is really oscillator effect, there should be _no_ >entropy when running with L1/L2 enabled (because DRAM will not be >accessed at all at that case). That is a good one! Another friend of mine mentioned that he assumes the rise and fall times of transistors varies very slightly and could be the main reason for the jitter. I do not think that this is really the case, because our gates that form the CPU instructions comprise of many transistors. The combined raise/fall jitter should cancel each other out. That said, the full root cause is is not really known at this time considering that major chip vendors have no real clue either. > >There should be way to extract entropy more directly from various >oscillator effects, no? I am working a different way of measuring such oscillator effects by using the high-resolution timer of the CPU and measure it with a Jiffies-based snapshotting window. So, here I would combine two timers that are differently generated. If their frequencies would be relative prime to each other, we would measure a direct oscillator effect. This already was tried in the cryptlib RNG, but I try a slightly different approach. Yet, nothing is complete at this point. > >For DRAM, just perform timing, have entropy. Plus we could for example >measure PIT vs. other timer sources... (but I suspect that on PCs we >already have enough entropy...) I suspect so too, but my measurements as of now are not conclusive. > Pavel Ciao Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-03 7:20 ` Stephan Mueller @ 2013-11-03 12:41 ` Theodore Ts'o 2013-11-05 12:20 ` Stephan Mueller 2013-11-03 23:32 ` Pavel Machek 1 sibling, 1 reply; 61+ messages in thread From: Theodore Ts'o @ 2013-11-03 12:41 UTC (permalink / raw) To: Stephan Mueller; +Cc: Pavel Machek, sandy harris, linux-kernel, linux-crypto On Sun, Nov 03, 2013 at 08:20:34AM +0100, Stephan Mueller wrote: > Another friend of mine mentioned that he assumes the rise and fall times > of transistors varies very slightly and could be the main reason for the > jitter. I do not think that this is really the case, because our gates > that form the CPU instructions comprise of many transistors. The > combined raise/fall jitter should cancel each other out. The whole point of using a clocked architecture for digital circuitry is to avoid differences in the rise/fall times of transitors to lead to non-deterministic behavior --- which is important if you want to make sure that 2 * 2 == 4 and not 3.99999999..... The one place where you might find differences is when you have different subsystems which are clocked using different clock sources, and then there's extra circuitry that has to be needed to handle interfacing between those differently clocked circuit areas. The problem, though is that over time, these boundaries can change; it may be that on certain chipsets, things that had been in different clock circuits, have later been integrated onto a single system-on-chip device and all run off of a single clock source. > That said, the full root cause is is not really known at this time > considering that major chip vendors have no real clue either. I have trouble beliving that statement; they might not be willing to comment, since to do so would expose a internal CPU designs which they consider secret, or worse, it might cause people to depend on certain implementation details which might not be true in future chipsets --- which may either tie their hands, or they may even know that it won't be true for CPU version currently under development but not yet released. Sandy Harris pointed out a very good paper that I would definitely recommend that people read: http://lwn.net/images/conf/rtlws11/random-hardware.pdf It basically describes some efforts made in 2009 by folks to do exactly the sort of experiments I was advocating. What I actually think is more important, though, is not the doing of the experiments, but the development the tools to do these experiments. If people can create kernel modules (and they have to be done in the kernel, since you need to be able to disable interrupts, L1 caches, etc., while you run these tests), then it will be possible to do these experiments each time a new CPU comes out from Intel, or each time an ARM hardware vendor comes out with a new ARM SOC. It's important that these tests are done all time, and not, "OK, we did some tests in 2009 or 2013, and things looked good, and we don't have to worry about this any more; CPU-generated entropy is guaranteed to be good!" We need to make sure we can easily do these tests all the time, for every new piece of hardware out there --- and when we can't explain where the entropy is coming from, we need to be doubly on our guard. Regards, - Ted ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-03 12:41 ` Theodore Ts'o @ 2013-11-05 12:20 ` Stephan Mueller 2013-11-06 11:49 ` Stephan Mueller 0 siblings, 1 reply; 61+ messages in thread From: Stephan Mueller @ 2013-11-05 12:20 UTC (permalink / raw) To: Theodore Ts'o; +Cc: Pavel Machek, sandy harris, linux-kernel, linux-crypto Am Sonntag, 3. November 2013, 07:41:35 schrieb Theodore Ts'o: Hi Theodore, >On Sun, Nov 03, 2013 at 08:20:34AM +0100, Stephan Mueller wrote: > >Sandy Harris pointed out a very good paper that I would definitely >recommend that people read: > >http://lwn.net/images/conf/rtlws11/random-hardware.pdf > >It basically describes some efforts made in 2009 by folks to do >exactly the sort of experiments I was advocating. What I actually I am wondering whether you have seen my last measurements where I effectively performed the tests you were asking for: disabling all possible CPU features and selectively enabling them. The tests described in the above mentioned documents and much more are all already in the test suite and test results I present here. >think is more important, though, is not the doing of the experiments, >but the development the tools to do these experiments. If people can >create kernel modules (and they have to be done in the kernel, since >you need to be able to disable interrupts, L1 caches, etc., while you >run these tests), then it will be possible to do these experiments >each time a new CPU comes out from Intel, or each time an ARM hardware >vendor comes out with a new ARM SOC. The test code is available and it is executed in kernel space. > >It's important that these tests are done all time, and not, "OK, we Again, the code is there for the taking, including the analysis part. Yes, it can be easily converted into a fully automated test such that at the end a result of "CPU shows sufficient variations for the RNG" or not. Therefore, I am asking again: - Which other CPU mechanisms can I disable that I did not so far? - The execution time measurements when disabling CPU features show that there is still significant variations available. Given the fact that an adversary is not able to disable the features as I did, he will not be able to reduce the variations induced by the features. He may alter them potentially, but there are still variations which he cannot affect, let alone predict. Therefore, how shall an adversary make predictions of the variations to weaken the RNG? I heard a nice statement from the developer who implemented the /dev/random device of a different, respected operating system: the last step to accept the underlying root cause of uncertainty for an RNG always requires a leap of faith. Looking at typical noise sources that sounds about right. For example: - how can we be sure that nobody who measures the key stroke interrupts can do that with a precision that is higher than the estimated entropy the key stroke is awarded (note, an adversary has the means to observe key strokes)? Same applies to mouse movements. Note that X11 allows you to measure these events precisely (the xev application should give a glimpse). - how can we be sure that fast_pool exhibits no correlation with the other noise sources? - how can we be sure that the HDD fluctuations are random? We simply accept that these issues do not allow predicting sequences to the extent that weakens the RNG. My goal is to give another seed source to add even more uncertainty into the Linux RNG in addition to the existing seed sources. This would also support environments that were typically left in the rain so far, such as virtual machines, early boot sequences, Live CDs, or headless systems without a spinning disk. Ciao Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-05 12:20 ` Stephan Mueller @ 2013-11-06 11:49 ` Stephan Mueller 2013-11-06 12:43 ` Theodore Ts'o 0 siblings, 1 reply; 61+ messages in thread From: Stephan Mueller @ 2013-11-06 11:49 UTC (permalink / raw) To: Theodore Ts'o Cc: Pavel Machek, sandy harris, linux-kernel, linux-crypto, Nicholas Mc Guire Am Dienstag, 5. November 2013, 13:20:57 schrieb Stephan Mueller: Hi Ted, >Am Sonntag, 3. November 2013, 07:41:35 schrieb Theodore Ts'o: > >Hi Theodore, > >>On Sun, Nov 03, 2013 at 08:20:34AM +0100, Stephan Mueller wrote: >> >>Sandy Harris pointed out a very good paper that I would definitely >>recommend that people read: >> >>http://lwn.net/images/conf/rtlws11/random-hardware.pdf >> >>It basically describes some efforts made in 2009 by folks to do >>exactly the sort of experiments I was advocating. What I actually > >I am wondering whether you have seen my last measurements where I >effectively performed the tests you were asking for: disabling all >possible CPU features and selectively enabling them. > >The tests described in the above mentioned documents and much more are >all already in the test suite and test results I present here. After this comment, I got back to one of the authors of the cited paper (he is in CC). Here is a quote from his answer to my question whether he was able to identify the root cause: "its inherent in the microtiming of Hardware and there is nothing you can do about it if you want the root cause is quantum physics" That means, no matter how much CPU support you disable, you will always have some jitter -- as I showed in my latest test results in appendix F.46 of [1]. This statement is supported by my tests on even microkernels which have no other job running than my test application. Furthermore, as we see that phenomenon on every tested CPU type on every tested operating system with every tested compiler, I am wondering what else argument is needed to have this solution considered. [1] http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.html Ciao Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-06 11:49 ` Stephan Mueller @ 2013-11-06 12:43 ` Theodore Ts'o 2013-11-06 12:51 ` Stephan Mueller 0 siblings, 1 reply; 61+ messages in thread From: Theodore Ts'o @ 2013-11-06 12:43 UTC (permalink / raw) To: Stephan Mueller Cc: Pavel Machek, sandy harris, linux-kernel, linux-crypto, Nicholas Mc Guire On Wed, Nov 06, 2013 at 12:49:45PM +0100, Stephan Mueller wrote: > Here is a quote from his answer to my question whether he was able to > identify the root cause: > > "its inherent in the microtiming of Hardware and there is nothing you > can do about it if you want the root cause is quantum physics" That's unfortunate, since it leaves open the question of whether this jitter is something that could be at least somewhat predictable if you had a lot more information about the internal works of the CPU or not.... - Ted ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-06 12:43 ` Theodore Ts'o @ 2013-11-06 12:51 ` Stephan Mueller 2013-11-06 13:04 ` Theodore Ts'o 2013-11-07 1:03 ` Nicholas Mc Guire 0 siblings, 2 replies; 61+ messages in thread From: Stephan Mueller @ 2013-11-06 12:51 UTC (permalink / raw) To: Theodore Ts'o Cc: Pavel Machek, sandy harris, linux-kernel, linux-crypto, Nicholas Mc Guire Am Mittwoch, 6. November 2013, 07:43:54 schrieb Theodore Ts'o: Hi Theodore, >On Wed, Nov 06, 2013 at 12:49:45PM +0100, Stephan Mueller wrote: >> Here is a quote from his answer to my question whether he was able to >> identify the root cause: >> >> "its inherent in the microtiming of Hardware and there is nothing you >> can do about it if you want the root cause is quantum physics" > >That's unfortunate, since it leaves open the question of whether this >jitter is something that could be at least somewhat predictable if you >had a lot more information about the internal works of the CPU or >not.... I do not understand that answer: I thought we are talking about the search of non-predictable noise sources. If you cannot predict the sequence even if you have the state of the CPU, that is what we are looking for, is it not? Besides, how on earth shall an attacker even gain knowledge about the state of the CPU or disable CPU mechanisms? Oh, I forgot, your NSA guy. But if he is able to do that, all discussions are moot because he simply disables any noise sources by flipping a bit, reads the memory that is used to hold the state of the RNG or just overwrites the memory locations where data is collected, because the general protection mechanisms offered by the kernel and the underlying hardware are broken. Also, does your answer mean you would disregard radioactive decay that is not predictable due to quantum physics and Heisenberg? Ciao Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-06 12:51 ` Stephan Mueller @ 2013-11-06 13:04 ` Theodore Ts'o 2013-11-06 13:24 ` Pavel Machek 2013-11-07 5:21 ` Stephan Mueller 2013-11-07 1:03 ` Nicholas Mc Guire 1 sibling, 2 replies; 61+ messages in thread From: Theodore Ts'o @ 2013-11-06 13:04 UTC (permalink / raw) To: Stephan Mueller Cc: Pavel Machek, sandy harris, linux-kernel, linux-crypto, Nicholas Mc Guire On Wed, Nov 06, 2013 at 01:51:17PM +0100, Stephan Mueller wrote: > >That's unfortunate, since it leaves open the question of whether this > >jitter is something that could be at least somewhat predictable if you > >had a lot more information about the internal works of the CPU or > >not.... > > I do not understand that answer: I thought we are talking about the > search of non-predictable noise sources. If you cannot predict the > sequence even if you have the state of the CPU, that is what we are > looking for, is it not? I was asking the question about whether someone who knew more about the internal _workings_ of the CPU, note of the state of the CPU. This is not necessarily "the NSA guy", but someone who knows more about the internal workings of the Intel CPU (such as an Intel engineer --- and I've had Intel express misgivings about approaches which depend on "CPU jitter" approaches), or just someone who has spent a lot more time trying to examine the black box of the Intel CPU from the outside. I remember making my own home-grown encryption algorithm before I entered college, secure in my arrogance that I had created something so complicated that no one could crack it. Of course, as I got older and wiser, I realized that it just meant it was just something *I* couldn't yet anaylze and crack. The argument "the internal state of the CPU is sooooo large, and the state transitions ar sooooo complex that it *must* be unpredictable, because *I* can't predict them" seems to be a very similar mistake that I made many years ago when I was in high school. Of course, some of the state in the CPU may not be unknown to the attacker, if it is derived by external events that are not visible to the attacker, such as a network interrupt. But if that's the case, why not measure network interrupts directly? We're much less likely to overestimate the amount of entropy we can extract the system in that case. > Also, does your answer mean you would disregard radioactive decay that > is not predictable due to quantum physics and Heisenberg? No, because that's uncertainty that we can tie to a physical source. My concern about CPU state is that we haven't yet tied that to a physical source of entropy, or to exactly what external inputs that are not available to an external attacker. We know that quantum events are not predictable. We also know that digital circuits in general are very carefully designed to *be* predictable. Regards, - Ted ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-06 13:04 ` Theodore Ts'o @ 2013-11-06 13:24 ` Pavel Machek 2013-11-07 0:36 ` Nicholas Mc Guire 2013-11-07 5:21 ` Stephan Mueller 1 sibling, 1 reply; 61+ messages in thread From: Pavel Machek @ 2013-11-06 13:24 UTC (permalink / raw) To: Theodore Ts'o, Stephan Mueller, sandy harris, linux-kernel, linux-crypto, Nicholas Mc Guire Hi! > Of course, some of the state in the CPU may not be unknown to the > attacker, if it is derived by external events that are not visible to > the attacker, such as a network interrupt. But if that's the case, > why not measure network interrupts directly? We're much less likely > to overestimate the amount of entropy we can extract the system in > that case. Actually, I believe Stephan is up to something here. We _can't_ measure network interrupts directly, because we do not have TSC. (And TSC-less machines are the ones that are problematic, right?) Extracting entropy from the CPU will allow us to pick up entropy from network packets (and timer interrupt jitter) even on machines that lack TSC. And that counts like very cool feature. (And yes, we could just increment variable to get tsc emulation in idle loop, and then extract entropy from that. But we would not be able to enter low power states at that point, and it would not work when cpu is busy computing.) Pavel -- (english) http://www.livejournal.com/~pavelmachek (cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-06 13:24 ` Pavel Machek @ 2013-11-07 0:36 ` Nicholas Mc Guire 0 siblings, 0 replies; 61+ messages in thread From: Nicholas Mc Guire @ 2013-11-07 0:36 UTC (permalink / raw) To: Pavel Machek Cc: Theodore Ts'o, Stephan Mueller, sandy harris, linux-kernel, linux-crypto On Wed, 06 Nov 2013, Pavel Machek wrote: > Hi! > > > Of course, some of the state in the CPU may not be unknown to the > > attacker, if it is derived by external events that are not visible to > > the attacker, such as a network interrupt. But if that's the case, > > why not measure network interrupts directly? We're much less likely > > to overestimate the amount of entropy we can extract the system in > > that case. > > Actually, I believe Stephan is up to something here. > > We _can't_ measure network interrupts directly, because we do not have > TSC. (And TSC-less machines are the ones that are problematic, right?) > If you are interested in entropy then there is no need to compare events against timestamps (which are just an event class) you can use any uncorrelated event (the assumption in using timestamps precisely is that they would be uncorrelated). If you are using jitter then the only question is how to extract it and how your extracter can be assured to be sensitive to time differences that are smaller than what can be impacted by external events. Specifically this also means that no mater how you extract jitter you can not assume it is unbiased and you would need to unbias it (e.g. using Neuman/Peres method) - e.g. look at the jitter distributions in the OSADL QA-Farm - it is clear that they are in none of the cases bias-free. E.g. practically all systems we looked at the jitter distribution is sensitive to the amount of memory in the box. > Extracting entropy from the CPU will allow us to pick up entropy from > network packets (and timer interrupt jitter) even on machines that > lack TSC. And that counts like very cool feature. if you use external events then I do not see the relation to using CPU inherent non-determinism - why do you want to bind the selectd events to an external and potentially contrtolable event at all ? > > (And yes, we could just increment variable to get tsc emulation in > idle loop, and then extract entropy from that. But we would not be > able to enter low power states at that point, and it would not work > when cpu is busy computing.) > there is so much global state information in the kernel that can be used to harvest entropy I do not see why we would neeed to implement a dedicated method (counter loop or the like) at all - rather all that would be needed is an extracter. Note that using global state though is not directly bound to microtiming (it might be too complex to systematically scew never the less but that would need tto be demonstrated). The only think that I believe is directly bound to microttiming are race conditions (also not unbiased though). thx! hofrat ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-06 13:04 ` Theodore Ts'o 2013-11-06 13:24 ` Pavel Machek @ 2013-11-07 5:21 ` Stephan Mueller 2013-11-09 22:04 ` Clemens Ladisch 1 sibling, 1 reply; 61+ messages in thread From: Stephan Mueller @ 2013-11-07 5:21 UTC (permalink / raw) To: Theodore Ts'o Cc: Pavel Machek, sandy harris, linux-kernel, linux-crypto, Nicholas Mc Guire Am Mittwoch, 6. November 2013, 08:04:32 schrieb Theodore Ts'o: Hi Theodore, >On Wed, Nov 06, 2013 at 01:51:17PM +0100, Stephan Mueller wrote: >> >That's unfortunate, since it leaves open the question of whether >> >this >> >jitter is something that could be at least somewhat predictable if >> >you >> >had a lot more information about the internal works of the CPU or >> >not.... >> >> I do not understand that answer: I thought we are talking about the >> search of non-predictable noise sources. If you cannot predict the >> sequence even if you have the state of the CPU, that is what we are >> looking for, is it not? > >I was asking the question about whether someone who knew more about >the internal _workings_ of the CPU, note of the state of the CPU. >This is not necessarily "the NSA guy", but someone who knows more >about the internal workings of the Intel CPU (such as an Intel >engineer --- and I've had Intel express misgivings about approaches >which depend on "CPU jitter" approaches), or just someone who has >spent a lot more time trying to examine the black box of the Intel CPU >from the outside. I try to get more information from my contacts to other vendors. But I am wondering what shall we do if the answer is (maybe even proven with some test results) that they see the same issue themselves and have no handle on it? I mean, what is it that I would need to test and demonstrate to prove or disprove my RNG? We can certainly test very much, but one thing we cannot prove, and that is the fundamental jitter, provided it is a result of quantum fluctuations. Just as with any other noise source, basic fundamental principles are hard if not impossible to test. I would again like to stress the fact that we see the root cause to a similar degree on all major CPUs that we have around us. All of these CPUs work differently and yet they show a common behavior, the execution time variations. I wonder whether this is already a good indication > >I remember making my own home-grown encryption algorithm before I >entered college, secure in my arrogance that I had created something >so complicated that no one could crack it. Of course, as I got older >and wiser, I realized that it just meant it was just something *I* >couldn't yet anaylze and crack. The argument "the internal state of >the CPU is sooooo large, and the state transitions ar sooooo complex >that it *must* be unpredictable, because *I* can't predict them" seems >to be a very similar mistake that I made many years ago when I was in >high school. Agreed, I do not want to state that nobody is able to obtain the state (especially considering that the CPUs *must* have some hardware debugging hooks somewhere that should allow dumping out the current state of the entire CPU to aid CPU development). However, we also have to consider our threat model: to me, an attacker can only reside in user state of the CPU. All that he can observe there can be used against us. Anything that he can only do when in supervisor state is not of interest, because gathering and maintaining entropy is the least of our worries in this case. > >Of course, some of the state in the CPU may not be unknown to the >attacker, if it is derived by external events that are not visible to >the attacker, such as a network interrupt. But if that's the case, >why not measure network interrupts directly? We're much less likely >to overestimate the amount of entropy we can extract the system in >that case. To aid that discussion, let us assume that the variations are solely based on the CPU state (which indications show that this is not the case). When you focus on only the interrupts (or only one interrupt for that matter) we limit the base from which we try to obtain entropy. If you are concerned about the entropy level we add with the proposed jitter RNG, what about the following: - when mixing in bits from the jitter RNG into the entropy pools of random.c, we increase the entropy estimator not by the equivalent amount of bits, but some fraction. For example: ... ret = jent_read_entropy(&r->entropy_collector, rand, JENTBLOCKSIZE); ... _mix_pool_bytes(r, rand, ret, NULL); credit_entropy_bits(r, (ret * 8) / 2); This code would only increase the entropy estimator by half of the obtained bits - The jitter RNG allows specifying an oversampling rate where it oversamples the jitter by multiples of the given value. The default is 1 (i.e. no oversampling). But we could set it to 2 (double oversampling). The code is here: r->entropy_collector.osr = 1; Ciao Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-07 5:21 ` Stephan Mueller @ 2013-11-09 22:04 ` Clemens Ladisch 2013-11-10 1:10 ` Stephan Mueller 0 siblings, 1 reply; 61+ messages in thread From: Clemens Ladisch @ 2013-11-09 22:04 UTC (permalink / raw) To: Stephan Mueller Cc: Theodore Ts'o, Pavel Machek, sandy harris, linux-kernel, linux-crypto, Nicholas Mc Guire Stephan Mueller wrote: > Am Mittwoch, 6. November 2013, 08:04:32 schrieb Theodore Ts'o: >> On Wed, Nov 06, 2013 at 01:51:17PM +0100, Stephan Mueller wrote: >>>> That's unfortunate, since it leaves open the question of whether this >>>> jitter is something that could be at least somewhat predictable if you >>>> had a lot more information about the internal works of the CPU or not.... >>> >>> I do not understand that answer: I thought we are talking about the >>> search of non-predictable noise sources. If you cannot predict the >>> sequence even if you have the state of the CPU, that is what we are >>> looking for, is it not? >> >> I was asking the question about whether someone who knew more about >> the internal _workings_ of the CPU, note of the state of the CPU. >> This is not necessarily "the NSA guy", but someone who knows more >> about the internal workings of the Intel CPU (such as an Intel >> engineer --- and I've had Intel express misgivings about approaches >> which depend on "CPU jitter" approaches), or just someone who has >> spent a lot more time trying to examine the black box of the Intel CPU >> from the outside. > > I try to get more information from my contacts to other vendors. But I > am wondering what shall we do if the answer is (maybe even proven with > some test results) that they see the same issue themselves and have no > handle on it? > > I mean, what is it that I would need to test and demonstrate to prove or > disprove my RNG? You need to prove that the CPU will never get into an internal state where the loop execution times happen to form a predictable pattern. Alternatively, detect this so that the measurements can be thrown away. > We can certainly test very much, but one thing we cannot prove, and > that is the fundamental jitter, provided it is a result of quantum > fluctuations. Just as with any other noise source, basic fundamental > principles are hard if not impossible to test. You cannot test if the noise source was replaced with fake hardware. But if you know the characteristics of the noise source, you can test for likely failure modes, such as the output value being stuck or oscillating. In the case of CPU jitter measurements, you do not have direct access to the noise source; you measure it indirectly through the CPU's internal state. So you need to know how the delta times of a noisy CPU are different from the delta times of a CPU without or with unsuitable noise source. Regards, Clemens ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-09 22:04 ` Clemens Ladisch @ 2013-11-10 1:10 ` Stephan Mueller 2013-11-10 16:31 ` Clemens Ladisch 0 siblings, 1 reply; 61+ messages in thread From: Stephan Mueller @ 2013-11-10 1:10 UTC (permalink / raw) To: Clemens Ladisch Cc: Theodore Ts'o, Pavel Machek, sandy harris, linux-kernel, linux-crypto, Nicholas Mc Guire Am Samstag, 9. November 2013, 23:04:49 schrieb Clemens Ladisch: Hi Clemens, > Stephan Mueller wrote: > > Am Mittwoch, 6. November 2013, 08:04:32 schrieb Theodore Ts'o: > >> On Wed, Nov 06, 2013 at 01:51:17PM +0100, Stephan Mueller wrote: > >>>> That's unfortunate, since it leaves open the question of whether this > >>>> jitter is something that could be at least somewhat predictable if you > >>>> had a lot more information about the internal works of the CPU or > >>>> not.... > >>> > >>> I do not understand that answer: I thought we are talking about the > >>> search of non-predictable noise sources. If you cannot predict the > >>> sequence even if you have the state of the CPU, that is what we are > >>> looking for, is it not? > >> > >> I was asking the question about whether someone who knew more about > >> the internal _workings_ of the CPU, note of the state of the CPU. > >> This is not necessarily "the NSA guy", but someone who knows more > >> about the internal workings of the Intel CPU (such as an Intel > >> engineer --- and I've had Intel express misgivings about approaches > >> which depend on "CPU jitter" approaches), or just someone who has > >> spent a lot more time trying to examine the black box of the Intel CPU > >> from the outside. > > > > I try to get more information from my contacts to other vendors. But I > > am wondering what shall we do if the answer is (maybe even proven with > > some test results) that they see the same issue themselves and have no > > handle on it? > > > > I mean, what is it that I would need to test and demonstrate to prove or > > disprove my RNG? > > You need to prove that the CPU will never get into an internal state > where the loop execution times happen to form a predictable pattern. > Alternatively, detect this so that the measurements can be thrown away. That statement sounds very nice, and I would love to prove it. But I do not see any way to do that except applying statistical tests on a large number of different systems and by disabling CPU features -- as I have done. I am fully aware that statistical tests cannot prove the conclusion that the noise source is proper. But we have to keep requirements to my RNG in league with the research applied to other noise sources. Let us look at physical noise sources we all know and love: - The conclusion that radioactive decay is random is based on the quantum theory. That theory contains a number of formulas which were all validated with a plethora of measurements. Yet, there is no proof (in the mathematical sense) that the formulas are correct. These formulas are based on deductive science but *not* inductive science (like math). - Oscillators: Again, the conclusion of oscillators being appropriate depends on deductive science. - Shot noise, Johnson noise, etc. of resistors, transistors is again based on deductive science. For software: - The noise sources of interrupts, HID events, HDD fluctuations are all based on deductive science. There is even no formulas or other mathematical model behind them to state that they are good for RNGs. So, there was never a proof in the sense of an inductive science of any noise source. That means I cannot be expected to show a full formulated proof based on inductive science of the noise source I offer here. Yet, I meet the deductive science approach with my RNG as I base my conclusions on a large array of measurements. And I give the tools to perform the measurements to everybody. So, everybody can easily redo the testing, or, if possible, prove me wrong! You may look into [1] and [2]. [1] mentions that inductive methods cannot reach absolute proof. > > > We can certainly test very much, but one thing we cannot prove, and > > that is the fundamental jitter, provided it is a result of quantum > > fluctuations. Just as with any other noise source, basic fundamental > > principles are hard if not impossible to test. > > You cannot test if the noise source was replaced with fake hardware. > But if you know the characteristics of the noise source, you can test > for likely failure modes, such as the output value being stuck or > oscillating. And here I am asking for help! What did I do so far: - Test the CPU in kernel and user mode. - Selectively and mutually disable CPU features (see appendix F.46 of my documentation). - Tested on quiet and heavily loaded CPUs. - Testing on the same physical system / CPU with different operating systems. What else can I do? When you ask for testing of stuck values, what shall I really test for? Shall I test adjacent measurements for the same or alternating values? The test for the same values is caught with the Von-Neumann unbiaser. If I test for alternating values, other people may come in and ask to check for pattern x or y. But then, section 4.3 of my document contains an analysis of patterns. As I do not use a whitener, any pattern WILL be visible with the Chi-Square test result. All tests I conducted show a good Chi-Square value! That leads me to the conclusion that there is NO pattern visible. > > In the case of CPU jitter measurements, you do not have direct access to > the noise source; you measure it indirectly through the CPU's internal > state. So you need to know how the delta times of a noisy CPU are > different from the delta times of a CPU without or with unsuitable > noise source. Please give me a practical example! This statement is again a nice theoretical wish, but my considerations above for the different noise sources can again be applied here: I have never seen elaborate stuck tests on any other physical or non-physical RNG. Yes, I have seen the FIPS 140-2 continuous test, but that is already implemented in my code. [1] https://en.wikipedia.org/wiki/Inductive_reasoning [2] https://en.wikipedia.org/wiki/Deductive_reasoning Ciao Stephan -- | Cui bono? | ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-10 1:10 ` Stephan Mueller @ 2013-11-10 16:31 ` Clemens Ladisch 2013-11-10 17:21 ` Stephan Mueller 0 siblings, 1 reply; 61+ messages in thread From: Clemens Ladisch @ 2013-11-10 16:31 UTC (permalink / raw) To: Stephan Mueller Cc: Theodore Ts'o, Pavel Machek, sandy harris, linux-kernel, linux-crypto, Nicholas Mc Guire Stephan Mueller wrote: > Am Samstag, 9. November 2013, 23:04:49 schrieb Clemens Ladisch: >> Stephan Mueller wrote: >>> Am Mittwoch, 6. November 2013, 08:04:32 schrieb Theodore Ts'o: >>>> On Wed, Nov 06, 2013 at 01:51:17PM +0100, Stephan Mueller wrote: >>>>>> That's unfortunate, since it leaves open the question of whether this >>>>>> jitter is something that could be at least somewhat predictable if you >>>>>> had a lot more information about the internal works of the CPU or >>>>>> not.... >>>>> >>>>> I do not understand that answer: I thought we are talking about the >>>>> search of non-predictable noise sources. If you cannot predict the >>>>> sequence even if you have the state of the CPU, that is what we are >>>>> looking for, is it not? >>>> >>>> I was asking the question about whether someone who knew more about >>>> the internal _workings_ of the CPU, note of the state of the CPU. >>>> This is not necessarily "the NSA guy", but someone who knows more >>>> about the internal workings of the Intel CPU (such as an Intel >>>> engineer --- and I've had Intel express misgivings about approaches >>>> which depend on "CPU jitter" approaches), or just someone who has >>>> spent a lot more time trying to examine the black box of the Intel CPU >>>> from the outside. >>> >>> I try to get more information from my contacts to other vendors. But I >>> am wondering what shall we do if the answer is (maybe even proven with >>> some test results) that they see the same issue themselves and have no >>> handle on it? >>> >>> I mean, what is it that I would need to test and demonstrate to prove or >>> disprove my RNG? >> >> You need to prove that the CPU will never get into an internal state >> where the loop execution times happen to form a predictable pattern. >> Alternatively, detect this so that the measurements can be thrown away. > > That statement sounds very nice, and I would love to prove it. But I do not > see any way to do that except applying statistical tests on a large number of > different systems Then you cannot say anything about unknown future CPU models. > But we have to keep requirements to my RNG in league with the research applied > to other noise sources. Let us look at physical noise sources we all know and > love: > > - The conclusion that radioactive decay is random is based on the quantum > theory. That theory contains a number of formulas which were all validated > with a plethora of measurements. Yet, there is no proof (in the mathematical > sense) that the formulas are correct. But we assume that the unpredictability of quantum mechanics is a limit for _everyone_. In the case of CPUs, the jitter you observe in delta times results in part from the complexities of the inner state, and in part from real random noise. The first part is deterministic and might be predicted by anyone who has enough knowledge about the CPU's internals. Additionally, physical noise sources allow us to estimate the entropy of our measurements. There is no such estimate for the CPU jitter RNG. (BTW, the entropy calculations in the paper are meaningless, because the Shannon formula assumes the values are created independently. Entropy calculation always depends on the process that created those values. For example, the entropy of 11001001000011111101101010100010001000 is zero if you know that this is just pi. To take a more relevant example, assume a completely deterministic CPU where each measuring loop takes exactly one timer tick; the delta times would look like this: 1 1 1 1 1 1 1 1 1 1 1 1 ... Now assume that the timer runs at a speed of 4/3 relative to the CPU, i.e., every third loop, another tick has accumulated: 1 1 2 1 1 2 1 1 2 1 1 2 ... Now assume that in every fourth loop iteration, the instruction decoder falls behind and stalls the pipeline for the same time as one loop iteration: 1 1 2 2 2 1 1 3 1 2 1 3 ... This sequence still has zero entropy.) > For software: > > - The noise sources of interrupts, HID events, HDD fluctuations are all based > on deductive science. There is even no formulas or other mathematical model > behind them to state that they are good for RNGs. Indeed. However, in the absence of a 'real' RNG, these are the best that the kernel has. And at least these events come from multiple sources and are mostly independent. >>> We can certainly test very much, but one thing we cannot prove, and >>> that is the fundamental jitter, provided it is a result of quantum >>> fluctuations. Just as with any other noise source, basic fundamental >>> principles are hard if not impossible to test. >> >> You cannot test if the noise source was replaced with fake hardware. >> But if you know the characteristics of the noise source, you can test >> for likely failure modes, such as the output value being stuck or >> oscillating. > > And here I am asking for help! [...] > When you ask for testing of stuck values, what shall I really test for? > Shall I test adjacent measurements for the same or alternating values? Same or alternating delta time values happen even on random CPUs. You need a theory of how random and non-random CPUs work, and how this difference affects the delta times, before you can test for that. (You might take the deterministic toy CPU from above, use more realistic timings, and add several layers of cache, write buffers, timer I/O wait states, and out-of-order execution, while still staying deterministic. Then add real randomness to the I/O or bus clocks, or power management delays, and check if the result has the same characteristics as your measurements of real CPUs.) > The test for the same values is caught with the Von-Neumann unbiaser. No, the von Neumann unbiaser is run on the whitened bitstream, i.e., _after_ the folding operation. The unbiasing should happen _before_ the whitener. This implies that you cannot use the von Neumann unbiaser because the sequence of delta times is not a sequence of single, independent bits. (Even for single bits, independence is strictly needed. Otherwise, a von Neumann unbiaser could _remove_ entropy. For example, consider a noise source that outputs bits in groups of two, where the first bit is perfectly random, but the second bit is always zero, or the same as the first.) > If I test for alternating values, other people may come in and ask to > check for pattern x or y. Well, if those people know a pattern that can _actually_ differentiate between random and non-random delta times, then you should test for it. (And I'd buy them a beer; with an entropy estimate, the CPU jitter RNG would be perfect.) Regards, Clemens ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-10 16:31 ` Clemens Ladisch @ 2013-11-10 17:21 ` Stephan Mueller 2013-11-10 20:28 ` Clemens Ladisch 2013-11-11 2:58 ` H. Peter Anvin 0 siblings, 2 replies; 61+ messages in thread From: Stephan Mueller @ 2013-11-10 17:21 UTC (permalink / raw) To: Clemens Ladisch Cc: Theodore Ts'o, Pavel Machek, sandy harris, linux-kernel, linux-crypto, Nicholas Mc Guire Am Sonntag, 10. November 2013, 17:31:07 schrieb Clemens Ladisch: Hi Clemens, > Stephan Mueller wrote: > > Am Samstag, 9. November 2013, 23:04:49 schrieb Clemens Ladisch: > >> Stephan Mueller wrote: > >>> Am Mittwoch, 6. November 2013, 08:04:32 schrieb Theodore Ts'o: > >>>> On Wed, Nov 06, 2013 at 01:51:17PM +0100, Stephan Mueller wrote: > >>>>>> That's unfortunate, since it leaves open the question of whether this > >>>>>> jitter is something that could be at least somewhat predictable if > >>>>>> you > >>>>>> had a lot more information about the internal works of the CPU or > >>>>>> not.... > >>>>> > >>>>> I do not understand that answer: I thought we are talking about the > >>>>> search of non-predictable noise sources. If you cannot predict the > >>>>> sequence even if you have the state of the CPU, that is what we are > >>>>> looking for, is it not? > >>>> > >>>> I was asking the question about whether someone who knew more about > >>>> the internal _workings_ of the CPU, note of the state of the CPU. > >>>> This is not necessarily "the NSA guy", but someone who knows more > >>>> about the internal workings of the Intel CPU (such as an Intel > >>>> engineer --- and I've had Intel express misgivings about approaches > >>>> which depend on "CPU jitter" approaches), or just someone who has > >>>> spent a lot more time trying to examine the black box of the Intel CPU > >>>> from the outside. > >>> > >>> I try to get more information from my contacts to other vendors. But I > >>> am wondering what shall we do if the answer is (maybe even proven with > >>> some test results) that they see the same issue themselves and have no > >>> handle on it? > >>> > >>> I mean, what is it that I would need to test and demonstrate to prove or > >>> disprove my RNG? > >> > >> You need to prove that the CPU will never get into an internal state > >> where the loop execution times happen to form a predictable pattern. > >> Alternatively, detect this so that the measurements can be thrown away. > > > > That statement sounds very nice, and I would love to prove it. But I do > > not > > see any way to do that except applying statistical tests on a large number > > of different systems > > Then you cannot say anything about unknown future CPU models. I concur. But neither can we say anything about future HDDs (note, they now start to fill them with Helium instead of air -- does that change anything in the disturbances?) or timers or interrupt hardware. Also, we know for a fact that the reliance on HDD as seed sources breaks down even today with SSDs! Again, we are not discussing about random.c, so please let us not further elaborate on HDDs/SSDs and their significance. But I am asking that my RNG is treated with the *same* level of rigor we apply to other seed sources. Thus, we can safely assume that future CPUs have that jitter too, because chip vendors will NOT simply drop all their existing effort and start at zero designing a new CPU. Besides, all my measurements show that the newer the CPU is, the more jitter it shows. Nonetheless, even the oldest ones I tested contain good jitter. > > > But we have to keep requirements to my RNG in league with the research > > applied to other noise sources. Let us look at physical noise sources we > > all know and love: > > > > - The conclusion that radioactive decay is random is based on the quantum > > theory. That theory contains a number of formulas which were all validated > > with a plethora of measurements. Yet, there is no proof (in the > > mathematical sense) that the formulas are correct. > > But we assume that the unpredictability of quantum mechanics is a limit Here you say it: we *assume*. And please bear in mind that we all know for a fact that the theory behind quantum physics is not complete, because it does not work together with the theory of relativity. That again is a hint that there is NO proof that decay is really unpredictable. But we disgres again, and I will skip more discussions about that theory. > for _everyone_. In the case of CPUs, the jitter you observe in delta > times results in part from the complexities of the inner state, and in > part from real random noise. The first part is deterministic and might > be predicted by anyone who has enough knowledge about the CPU's > internals. Right, and that is why I tried to eliminate the CPU mechanisms that may be having a deterministic impact. If I miss a mechanism or your have other suggestions, please help me. > > Additionally, physical noise sources allow us to estimate the entropy of > our measurements. There is no such estimate for the CPU jitter RNG. Well, I thought I have hints on the estimations of entropy in all my graphs by calculating a Shannon Entropy value. Granted, that is over the execution duration of my folding loop. Yet, that gives a good hint on the variations in place. > > (BTW, the entropy calculations in the paper are meaningless, because the > Shannon formula assumes the values are created independently. Entropy > calculation always depends on the process that created those values. > For example, the entropy of 11001001000011111101101010100010001000 is > zero if you know that this is just pi. To take a more relevant example, > assume a completely deterministic CPU where each measuring loop takes > exactly one timer tick; the delta times would look like this: > 1 1 1 1 1 1 1 1 1 1 1 1 ... > Now assume that the timer runs at a speed of 4/3 relative to the CPU, > i.e., every third loop, another tick has accumulated: > 1 1 2 1 1 2 1 1 2 1 1 2 ... > Now assume that in every fourth loop iteration, the instruction decoder > falls behind and stalls the pipeline for the same time as one loop > iteration: > 1 1 2 2 2 1 1 3 1 2 1 3 ... > This sequence still has zero entropy.) First, the patterns you mention will be immediately obvious with the Chi- Square measurements -- see section 4.3 of my document. So, I disregard the discussion of patterns. Second, we have to establish that entropy is *relative*. What is entropic to me, may be fully deterministic to you (when I look at the desk of my wife, it is all chaos to me, but when I ask her to get me some information, she needs 5 seconds to dig through her heaps and get me the stuff -- i.e. it is no chaos for her). That said, of course if I have full knowledge of all mechanisms that affect my RNG, I have zero entropy. But what I am saying is that I do not have that knowledge. The key now is to explain that nobody else has that either. > > > For software: > > > > - The noise sources of interrupts, HID events, HDD fluctuations are all > > based on deductive science. There is even no formulas or other > > mathematical model behind them to state that they are good for RNGs. > > Indeed. However, in the absence of a 'real' RNG, these are the best > that the kernel has. And at least these events come from multiple > sources and are mostly independent. Great, and here we are together. All I am offering is yet *another* noise source that is *added* to the existing ones. The only big difference is that my noise source works on demand whereas the others work by being triggered by the kernel operation. Therefore, I tried to provide the patch in a way that my RNG is used as the last resort before /dev/random blocks. Yet, my RNG as a seed source is available way earlier than any of the other seed sources. Moreover, it works in environments the others start to fail. That is why I am pushing my RNG in, because I have an itch (the missing /dev/random entropy in environments I care about -- embedded, Live CDs and virtual environments) that I want to scratch. > > >>> We can certainly test very much, but one thing we cannot prove, and > >>> that is the fundamental jitter, provided it is a result of quantum > >>> fluctuations. Just as with any other noise source, basic fundamental > >>> principles are hard if not impossible to test. > >> > >> You cannot test if the noise source was replaced with fake hardware. > >> But if you know the characteristics of the noise source, you can test > >> for likely failure modes, such as the output value being stuck or > >> oscillating. > > > > And here I am asking for help! [...] > > When you ask for testing of stuck values, what shall I really test for? > > Shall I test adjacent measurements for the same or alternating values? > > Same or alternating delta time values happen even on random CPUs. You > need a theory of how random and non-random CPUs work, and how this > difference affects the delta times, before you can test for that. Are you telling me that I should invent a formula and apply it? Where have you seen such an approach in existing RNGs? > > (You might take the deterministic toy CPU from above, use more realistic Your toy CPU from above contains some artificially created deterministic behavior. Sure I can check for that. But then somebody else tells me, why not checking for pattern X or Y. So, that effort is bound to failure, IMHO. > timings, and add several layers of cache, write buffers, timer I/O wait > states, and out-of-order execution, while still staying deterministic. > Then add real randomness to the I/O or bus clocks, or power management > delays, and check if the result has the same characteristics as your > measurements of real CPUs.) I have no idea how that proposal would look like in real live. > > > The test for the same values is caught with the Von-Neumann unbiaser. > > No, the von Neumann unbiaser is run on the whitened bitstream, i.e., > _after_ the folding operation. The folding is whitened? How do you reach that conclusion? Yes, the folding is my (very simple) post-processing. But I am not calling it whitened as all statistical problems the underlying variations have *will* be still visible in the folded value. Patterns in the underlying timer *will* be visible -- and I have demonstrated that in section 4.3. > > The unbiasing should happen _before_ the whitener. This implies that > you cannot use the von Neumann unbiaser because the sequence of delta > times is not a sequence of single, independent bits. You are right when the processing is a whitening. But it is not! Whitening implies that you somehow are able to hide statistical problems with the applied whitening. My folding DOES NOT do that. So, it is no whitening. > > (Even for single bits, independence is strictly needed. Otherwise, > a von Neumann unbiaser could _remove_ entropy. For example, consider > a noise source that outputs bits in groups of two, where the first bit > is perfectly random, but the second bit is always zero, or the same as > the first.) I know that. But from what I see, there is no patterns so far and therefore, the only conclusion I can reach is that they are independent. But if you do not like the Von-Neumann unbiaser, take it out. And still, the statistical tests will pass. > > > If I test for alternating values, other people may come in and ask to > > check for pattern x or y. > > Well, if those people know a pattern that can _actually_ differentiate > between random and non-random delta times, then you should test for it. > (And I'd buy them a beer; with an entropy estimate, the CPU jitter RNG > would be perfect.) What would you expect me to do when I should do to come up with an entropy estimate that I not already have done? There are so many assessments on entropy I make, I am surprised that I am said to have no entropy assessment. Ciao Stephan -- | Cui bono? | ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-10 17:21 ` Stephan Mueller @ 2013-11-10 20:28 ` Clemens Ladisch 2013-11-13 3:12 ` Stephan Mueller 2013-11-11 2:58 ` H. Peter Anvin 1 sibling, 1 reply; 61+ messages in thread From: Clemens Ladisch @ 2013-11-10 20:28 UTC (permalink / raw) To: Stephan Mueller Cc: Theodore Ts'o, Pavel Machek, sandy harris, linux-kernel, linux-crypto, Nicholas Mc Guire Stephan Mueller wrote: > Am Sonntag, 10. November 2013, 17:31:07 schrieb Clemens Ladisch: >> In the case of CPUs, the jitter you observe in delta >> times results in part from the complexities of the inner state, and in >> part from real random noise. The first part is deterministic and might >> be predicted by anyone who has enough knowledge about the CPU's >> internals. > > Right, and that is why I tried to eliminate the CPU mechanisms that may be > having a deterministic impact. If I miss a mechanism or your have other > suggestions, please help me. Many CPUs allow to disable branch prediction, but this is very vendor specific (try to find MSR documentation). The biggest offender probably is the out-of-order execution engine, which cannot be disabled. >>> When you ask for testing of stuck values, what shall I really test for? >>> Shall I test adjacent measurements for the same or alternating values? >> >> Same or alternating delta time values happen even on random CPUs. You >> need a theory of how random and non-random CPUs work, and how this >> difference affects the delta times, before you can test for that. > > Are you telling me that I should invent a formula and apply it? I was not implying that the theory has nothing to do with the physical device. It must correctly _describe_ the relevant physical processes. >>> The test for the same values is caught with the Von-Neumann unbiaser. >> >> No, the von Neumann unbiaser is run on the whitened bitstream, i.e., >> _after_ the folding operation. > > The folding is whitened? How do you reach that conclusion? Yes, the folding is > my (very simple) post-processing. But I am not calling it whitened as all > statistical problems the underlying variations have *will* be still visible in > the folded value. If you don't want to call it "whitening", call it "randomness extraction" instead. But its input is a series of delta times like this: 00000000000000000000000001010011 00000000000000000000000010011010 00000000000000000000000001011011 00000000000000000000000001100100 00000000000000000000000010111000 and the purpose of the folding is to remove these zero patterns. > What would you expect me to do when I should do to come up with an entropy > estimate that I not already have done? I do not expect you (or anybody) to be able to come up with a correct entropy estimate for CPU jitter. > There are so many assessments on entropy I make, I am surprised that I > am said to have no entropy assessment. Again: Shannon entropy assumes that you have a sequence of independent and identically distributed random variables. And you cannot prove these properties from the output; you need to know the process that generates the values. Regards, Clemens ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-10 20:28 ` Clemens Ladisch @ 2013-11-13 3:12 ` Stephan Mueller 2013-11-13 11:51 ` Clemens Ladisch 0 siblings, 1 reply; 61+ messages in thread From: Stephan Mueller @ 2013-11-13 3:12 UTC (permalink / raw) To: Clemens Ladisch Cc: Theodore Ts'o, Pavel Machek, sandy harris, linux-kernel, linux-crypto, Nicholas Mc Guire Am Sonntag, 10. November 2013, 21:28:06 schrieb Clemens Ladisch: Hi Clemens, > Stephan Mueller wrote: > > Am Sonntag, 10. November 2013, 17:31:07 schrieb Clemens Ladisch: > >> In the case of CPUs, the jitter you observe in delta > >> times results in part from the complexities of the inner state, and in > >> part from real random noise. The first part is deterministic and might > >> be predicted by anyone who has enough knowledge about the CPU's > >> internals. > > > > Right, and that is why I tried to eliminate the CPU mechanisms that may be > > having a deterministic impact. If I miss a mechanism or your have other > > suggestions, please help me. > > Many CPUs allow to disable branch prediction, but this is very vendor > specific (try to find MSR documentation). The biggest offender probably > is the out-of-order execution engine, which cannot be disabled. I was also digging around in this area. My research showed so far that only on ARM one can disable the branch prediction unit. Unfortunately, I do not have an ARM available where I can do that. I have my Samsung phone, but that runs Android and I am not sure how to generate a kernel module here. For x86, I have not found a way to disable the unit. Nonetheless, I tried to bring down the effect by "warming" the caches and the branch prediction up (see section 6.1.1 of the new version of the documentation). There I execute the testing 1000 times and use only the last result for further analysis. > > >>> When you ask for testing of stuck values, what shall I really test for? > >>> Shall I test adjacent measurements for the same or alternating values? > >> > >> Same or alternating delta time values happen even on random CPUs. You > >> need a theory of how random and non-random CPUs work, and how this > >> difference affects the delta times, before you can test for that. > > > > Are you telling me that I should invent a formula and apply it? > > I was not implying that the theory has nothing to do with the physical > device. It must correctly _describe_ the relevant physical processes. Right, but currently I am not sure how I can find such description. In particular, I created a new round of testing which is even more interesting as the results do not allow to pinpoint the exact root cause. More to that in a separate email. Do you have an idea? > > >>> The test for the same values is caught with the Von-Neumann unbiaser. > >> > >> No, the von Neumann unbiaser is run on the whitened bitstream, i.e., > >> _after_ the folding operation. > > > > The folding is whitened? How do you reach that conclusion? Yes, the > > folding is my (very simple) post-processing. But I am not calling it > > whitened as all statistical problems the underlying variations have > > *will* be still visible in the folded value. > > If you don't want to call it "whitening", call it "randomness extraction" > instead. But its input is a series of delta times like this: > 00000000000000000000000001010011 > 00000000000000000000000010011010 > 00000000000000000000000001011011 > 00000000000000000000000001100100 > 00000000000000000000000010111000 > and the purpose of the folding is to remove these zero patterns. Not quite. Let me explain the motive behind the folding loop. To maintain entropy mathematically, there are only a few operations allowed. One of them is a bijective operation which implies that two strings combined with a bijective operation will form a new string which contains the maximum entropy of the initial strings. XOR is a bijective operation. Hence, if you have a string with 10 bits that holds 5 bits of entropy and XOR it with a 20 bit string that holds 2 bits of entropy, you receive a string that is 20 bits in length and holds 5 bits of entropy. In any case, with the bijective operation, it is not possible to loose entropy even when you use the bijective operation to add fully deterministic values to a bit stream that is believed to have entropy. That said, the folding loop uses that line of thought. The loop XORs each bit with every other bit to receive one bit at the end. The idea is to collapse the initial bit stream by still retaining the entropy present in each individual bit. The goal is now that the resulting bit will hold one bit of entropy by "collecting" the combined entropy found in the individual bits. That folding operation will loose entropy, if the overall entropy in the folded bit stream is more than one bit. But that point is our advantage, because it provides a safety margin, if the value to be folded really holds more than one bit of entropy. All my measurements in section 5.1 and appendix F just try to show that on every CPU there is always more than one bit of entropy. There is a catch, however: what happens if each individual bit of the bit stream holds less than one bit? I.e. the entire bit stream may hold more than one bit, but when chopping the bit stream, the none of the individual bits may have one bit of entropy. As XOR only retains entropy but never enlarges entropy (like a concatenation would do), this would be a problem for the RNG. However, measurements and analyses given in section 5.2.1 come to the rescue: The measurements show that the folded value behaves like having one bit of entropy. To support that conclusion, the folding loop is sometimes executed in multiples of 64. This looks strange at first look, but these multiples ensure that the distribution of the folding loop bits discussed in section 5.2.1 stabilizes quickly. And with these multiple execution of the folding loop, the upper boundary of the entropy is defined. Now coming back to your concern: It is surely possible to put the Von-Neumann unbiaser before the folding loop. But considering the argument above, no information is lost apart from entropy exceeding one bit due to the use of a bijective operation. This means, it would not matter whether to put the Von- Neumann unbiaser before or after the folding. However, when putting it after the folding, the unbiaser will throw away more values and it would be more conservative with this approach (it is more likely to find adjacent 0 0 or 1 1 combinations than identical adjacent time deltas). Finally, the Von-Neumann unbiaser applies to individual bits. I am unsure how that would fit to the 64 bit time delta value that is the input to the folding loop. > > There are so many assessments on entropy I make, I am surprised that I > > am said to have no entropy assessment. > > Again: Shannon entropy assumes that you have a sequence of independent > and identically distributed random variables. And you cannot prove > these properties from the output; you need to know the process that > generates the values. I am absolutely on your side here. And as we cannot (yet?) fully conclude that the observations are independent, a safety margin must always be considered. The RNG has the following safety margins where it is more conservative than measurements indicate: - the folding loop produces one bit where measurements of the time deltas that go into the folding loop are typically above 2 bits with the lower boundary. The upper boundary is typical at 6 bits or higher. Some systems (especially older CPUs) show variations that are less than 2 bits with the lower boundary. But all of them are well above one bit. (note, my first designs had a folding loop that results in three bits, but then I reduced it to two and finally to one bit to ensure a safety margin) - the placement of the Von-Neumann unbiaser will throw away more bits than it would when it would be placed before the folding loop. That means that the noise source must produce more bits which are assembled into the final random number - the execution of the folding loop with multiples of 64 chosen with another time stamp adds more uncertainty over the folding timing -- therefore we have an upper boundary for the entropy estimation. I am almost certain that the selection of the multiplier value is not independent of the time stamps gathered for the time delta measurement (due to using the four lowest bits of that time stamp to determine the multiplexer value). That means that the upper boundary calculated with the Shannon Entropy formula is certainly too high. But the "real" value is above the lower boundary. Thanks for your thoughts. Ciao Stephan -- | Cui bono? | ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-13 3:12 ` Stephan Mueller @ 2013-11-13 11:51 ` Clemens Ladisch 2013-11-13 15:15 ` Stephan Mueller 0 siblings, 1 reply; 61+ messages in thread From: Clemens Ladisch @ 2013-11-13 11:51 UTC (permalink / raw) To: Stephan Mueller Cc: Theodore Ts'o, Pavel Machek, sandy harris, linux-kernel, linux-crypto, Nicholas Mc Guire Stephan Mueller wrote: > Am Sonntag, 10. November 2013, 21:28:06 schrieb Clemens Ladisch: >> Many CPUs allow to disable branch prediction, but this is very vendor >> specific (try to find MSR documentation). The biggest offender probably >> is the out-of-order execution engine, which cannot be disabled. > > For x86, I have not found a way to disable the unit. My AMD processor can do this in the IC_CFG/DC_CFG MSRs. (See the BKDG.) The Intel Core family has other settings (such as data prefetching) that are configurable in the IA32_MISC_ENABLE MSR. (And any setting that increases accesses to main memory is likey to introduce more entropy due to clock drift between the processor and the memory bus. Or where do you assume the entropy comes from?) BTW: MFENCE is not guaranteed to flush the instruction pipeline; you need CPUID for that. > XOR is a bijective operation. Only XOR with a constant, which is not what you're doing. >>> There are so many assessments on entropy I make, I am surprised that I >>> am said to have no entropy assessment. >> >> Again: Shannon entropy assumes that you have a sequence of independent >> and identically distributed random variables. And you cannot prove >> these properties from the output; you need to know the process that >> generates the values. > > I am absolutely on your side here. And as we cannot (yet?) fully conclude that > the observations are independent, a safety margin must always be considered. If the observations are not independent, you cannot just assume that the estimate is off by a certain factor. It means that the estimate is not applicable _at all_. > The RNG has the following safety margins where it is more conservative than > measurements indicate: You _cannot_ measure entropy by looking at the output. How would you differentiate between /dev/random and /dev/urandom? Regards, Clemens ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-13 11:51 ` Clemens Ladisch @ 2013-11-13 15:15 ` Stephan Mueller 2013-11-13 17:14 ` Pavel Machek 2013-11-14 10:51 ` Clemens Ladisch 0 siblings, 2 replies; 61+ messages in thread From: Stephan Mueller @ 2013-11-13 15:15 UTC (permalink / raw) To: Clemens Ladisch Cc: Theodore Ts'o, Pavel Machek, sandy harris, linux-kernel, linux-crypto, Nicholas Mc Guire Am Mittwoch, 13. November 2013, 12:51:44 schrieb Clemens Ladisch: Hi Clemens, >Stephan Mueller wrote: >> Am Sonntag, 10. November 2013, 21:28:06 schrieb Clemens Ladisch: >>> Many CPUs allow to disable branch prediction, but this is very >>> vendor >>> specific (try to find MSR documentation). The biggest offender >>> probably is the out-of-order execution engine, which cannot be >>> disabled.> >> For x86, I have not found a way to disable the unit. > >My AMD processor can do this in the IC_CFG/DC_CFG MSRs. (See the >BKDG.) Thanks for the hint, I will look into that one. > >The Intel Core family has other settings (such as data prefetching) >that are configurable in the IA32_MISC_ENABLE MSR. Thanks for the hint, I will check that as well. > >(And any setting that increases accesses to main memory is likey to >introduce more entropy due to clock drift between the processor and the >memory bus. Or where do you assume the entropy comes from?) You nailed it. When I disable the caches using the CR0 setting, I get a massive increase in variations and thus entropy. > >BTW: MFENCE is not guaranteed to flush the instruction pipeline; you >need CPUID for that. I was not aware of that. Can I simply call the CPUID instruction to read it or do I have to do something special? > >> XOR is a bijective operation. > >Only XOR with a constant, which is not what you're doing. If you want to regain the full 64 bit input bit stream, then you are right. But still, XOR is bijective with respect to the two bits that go into the operation. Before I released the RNG work, I had the mathematical side and the entropy consideration analyzed by a mathematician who is specialized in the field of cryptography and statistics. She actually said that this folding based on XOR is an appropriate way to collapse the string and yet retain entropy. > >>>> There are so many assessments on entropy I make, I am surprised >>>> that I >>>> am said to have no entropy assessment. >>> >>> Again: Shannon entropy assumes that you have a sequence of >>> independent >>> and identically distributed random variables. And you cannot prove >>> these properties from the output; you need to know the process that >>> generates the values. >> >> I am absolutely on your side here. And as we cannot (yet?) fully >> conclude that the observations are independent, a safety margin must >> always be considered. >If the observations are not independent, you cannot just assume that >the estimate is off by a certain factor. It means that the estimate >is not applicable _at all_. Well, I am not so sure here. If there are concerns on independence (which I currently do not have, but more to that below), I have always seen that safety margins are put in place. And that is what I tried here as well. > >> The RNG has the following safety margins where it is more >> conservative than >> measurements indicate: >You _cannot_ measure entropy by looking at the output. How would you >differentiate between /dev/random and /dev/urandom? I think regarding the independence you can very well draw the conclusion based on the output, because any dependencies will ultimately form a pattern. That pattern would initially be visible in the measurements that go into the folding loop. What I now must show is that these measurements do not have a pattern. In addition, we need to keep in mind that the independence claim is relative just like the entropy itself. If you have an output string that has no detectable patterns, i.e. looks like white noise, you can only assume that the observations are independent of each other. If there are patterns, you know that there are dependencies. That statement may *not* apply any more if you look at the internals of the RNG. In such a case, you may have even strong dependencies. The best example on this matter are deterministic RNGs with a cryptographic output function. When you see the output string, you only see white noise. As you cannot detect a pattern, you have to assume that the string provides independent observations. At least for you who looks from the outside cannot draw any conclusions from observing some output bit stream which would be the future bit stream. Yet, when you know the state of the RNG, you entire future output bit stream has no independence. Coming back to the jitter RNG: I applied a large array of statistical tests and all of them concluded that the output is white noise, as explained in the documentation. That means when looking from the outside, there are no dependencies visible. Now you may say that this conclusion does not mean that there are no dependencies -- but I reply again, if there would be any, none of the array of statistical tests can detect it. So, how would an attacker detect patterns? And again, I cannot prove it just like nobody else cannot prove it for other hardware noise sources. In addition, when we conclude that the output bit stream has no dependencies due to the absence of patterns and considering the folding operation not disguising patterns from the underlying measurements, I draw the conclusion that there are no patterns in the underlying measurements. The "Anti-Tests" I outline in section 4.3 show that if there would be patterns in the underlying measurements, it is immediately visible in the output bit stream. > > >Regards, >Clemens Ciao Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-13 15:15 ` Stephan Mueller @ 2013-11-13 17:14 ` Pavel Machek 2013-11-14 10:51 ` Clemens Ladisch 1 sibling, 0 replies; 61+ messages in thread From: Pavel Machek @ 2013-11-13 17:14 UTC (permalink / raw) To: Stephan Mueller Cc: Clemens Ladisch, Theodore Ts'o, sandy harris, linux-kernel, linux-crypto, Nicholas Mc Guire Hi! > >BTW: MFENCE is not guaranteed to flush the instruction pipeline; you > >need CPUID for that. > > I was not aware of that. Can I simply call the CPUID instruction to read > it or do I have to do something special? Simply call CPUID (warning, it clobbers some registers.). Pavel -- (english) http://www.livejournal.com/~pavelmachek (cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-13 15:15 ` Stephan Mueller 2013-11-13 17:14 ` Pavel Machek @ 2013-11-14 10:51 ` Clemens Ladisch 2013-11-14 18:01 ` Stephan Mueller 1 sibling, 1 reply; 61+ messages in thread From: Clemens Ladisch @ 2013-11-14 10:51 UTC (permalink / raw) To: Stephan Mueller Cc: Theodore Ts'o, Pavel Machek, sandy harris, linux-kernel, linux-crypto, Nicholas Mc Guire Stephan Mueller wrote: > Am Mittwoch, 13. November 2013, 12:51:44 schrieb Clemens Ladisch: >> (And any setting that increases accesses to main memory is likey to >> introduce more entropy due to clock drift between the processor and the >> memory bus. Or where do you assume the entropy comes from?) > > You nailed it. When I disable the caches using the CR0 setting, I get a > massive increase in variations and thus entropy. Now this would be an opportunity to use the number of main memory accesses to estimate entropy. (And when you're running out of the cache, i.e., deterministically, is there any entropy?) >>> XOR is a bijective operation. >> >> Only XOR with a constant, which is not what you're doing. > > If you want to regain the full 64 bit input bit stream, then you are > right. > > But still, XOR is bijective with respect to the two bits that go into > the operation. Please look up what "bijective" actually means: <http://en.wikipedia.org/wiki/Bijection> > folding based on XOR is an appropriate way to collapse the string and > yet retain entropy. Correct, but the reason for that is not being bijective. >> If the observations are not independent, you cannot just assume that >> the estimate is off by a certain factor. It means that the estimate >> is not applicable _at all_. > > Well, I am not so sure here. So, what is the factor that you are saying is large enough? >>> The RNG has the following safety margins where it is more conservative than >>> measurements indicate: >> >> You _cannot_ measure entropy by looking at the output. How would you >> differentiate between /dev/random and /dev/urandom? > > I think regarding the independence you can very well draw the conclusion > based on the output, because any dependencies will ultimately form a > pattern. The output of a pure PRNG (such as /dev/urandom without entropy) is dependent on the internal state, but there are no patterns detectable from the output alone. > In addition, we need to keep in mind that the independence claim is > relative No, independence is a property of the process that generates the samples. > If you have an output string that has no detectable patterns, i.e. looks > like white noise, you can only assume that the observations are > independent of each other. If there are patterns, you know that there > are dependencies. > > That statement may *not* apply any more if you look at the internals of > the RNG. In such a case, you may have even strong dependencies. > > The best example on this matter are deterministic RNGs with a > cryptographic output function. When you see the output string, you only > see white noise. As you cannot detect a pattern, you have to assume that > the string provides independent observations. At least for you who looks > from the outside cannot draw any conclusions from observing some output > bit stream which would be the future bit stream. Yet, when you know the > state of the RNG, you entire future output bit stream has no > independence. You cannot restrict the analysis to observations from the outside; there are many people who can know about the CPU's internal structure. > Coming back to the jitter RNG: I applied a large array of statistical > tests and all of them concluded that the output is white noise, as > explained in the documentation. That means when looking from the > outside, there are no dependencies visible. Now you may say that this > conclusion does not mean that there are no dependencies -- but I reply > again, if there would be any, none of the array of statistical tests can > detect it. So, how would an attacker detect patterns? An attacker would not try to detect patterns; he would apply knowledge of the internals. Statistical tests are useful only for detecting the absence of entropy, not for the opposite. All your arguments about the output of the CPU jitter RNG also apply to the output of /dev/urandom. So are you saying that it would be a good idea to loop the output of /dev/urandom back into /dev/random? Regards, Clemens ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-14 10:51 ` Clemens Ladisch @ 2013-11-14 18:01 ` Stephan Mueller 2013-11-14 18:30 ` Clemens Ladisch 0 siblings, 1 reply; 61+ messages in thread From: Stephan Mueller @ 2013-11-14 18:01 UTC (permalink / raw) To: Clemens Ladisch Cc: Theodore Ts'o, Pavel Machek, sandy harris, linux-kernel, linux-crypto, Nicholas Mc Guire Am Donnerstag, 14. November 2013, 11:51:03 schrieb Clemens Ladisch: Hi Clemens, >Stephan Mueller wrote: >> Am Mittwoch, 13. November 2013, 12:51:44 schrieb Clemens Ladisch: >>> (And any setting that increases accesses to main memory is likey to >>> introduce more entropy due to clock drift between the processor and >>> the memory bus. Or where do you assume the entropy comes from?) >> >> You nailed it. When I disable the caches using the CR0 setting, I get >> a massive increase in variations and thus entropy. > >Now this would be an opportunity to use the number of main memory >accesses to estimate entropy. (And when you're running out of the >cache, i.e., deterministically, is there any entropy?) > I seem to have found the root cause with my bare metal tester, but I am yet unable to make sense of it. I will report back with more analyses. >An attacker would not try to detect patterns; he would apply knowledge >of the internals. I do not buy that argument, because if an attacker can detect or deduce the internals of the CPU, he surely can detect the state of the input_pool or the other entropy pools behind /dev/random. And then, /dev/random is not so entropic any more for that attacker. > >Statistical tests are useful only for detecting the absence of entropy, >not for the opposite. Again, I fully agree. But it is equally important to understand that entropy is relative. And all I want and all I care about is that an attacker has only the knowledge and ability to make measurements that are less precise than 1 bit. Ciao Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-14 18:01 ` Stephan Mueller @ 2013-11-14 18:30 ` Clemens Ladisch 2013-11-14 18:34 ` Stephan Mueller 0 siblings, 1 reply; 61+ messages in thread From: Clemens Ladisch @ 2013-11-14 18:30 UTC (permalink / raw) To: Stephan Mueller Cc: Theodore Ts'o, Pavel Machek, sandy harris, linux-kernel, linux-crypto, Nicholas Mc Guire Stephan Mueller wrote: > Am Donnerstag, 14. November 2013, 11:51:03 schrieb Clemens Ladisch: >> An attacker would not try to detect patterns; he would apply knowledge >> of the internals. > > I do not buy that argument, because if an attacker can detect or deduce > the internals of the CPU, he surely can detect the state of the > input_pool or the other entropy pools behind /dev/random. With "internals", I do not mean the actual state of the CPU, but the behaviour of all the CPU's execution engines. An Intel engineer might know how to affect the CPU so that the CPU jitter code measures a deterministic pattern, but he will not know the contents of my memory. >> Statistical tests are useful only for detecting the absence of entropy, >> not for the opposite. > > Again, I fully agree. But it is equally important to understand that > entropy is relative. In cryptography, we care about absolute entropy, i.e., _nobody_ must be able to predict the RNG output, not even any CPU engineer. Regards, Clemens ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-14 18:30 ` Clemens Ladisch @ 2013-11-14 18:34 ` Stephan Mueller 0 siblings, 0 replies; 61+ messages in thread From: Stephan Mueller @ 2013-11-14 18:34 UTC (permalink / raw) To: Clemens Ladisch Cc: Theodore Ts'o, Pavel Machek, sandy harris, linux-kernel, linux-crypto, Nicholas Mc Guire Am Donnerstag, 14. November 2013, 19:30:22 schrieb Clemens Ladisch: Hi Clemens, >Stephan Mueller wrote: >> Am Donnerstag, 14. November 2013, 11:51:03 schrieb Clemens Ladisch: >>> An attacker would not try to detect patterns; he would apply >>> knowledge >>> of the internals. >> >> I do not buy that argument, because if an attacker can detect or >> deduce the internals of the CPU, he surely can detect the state of >> the input_pool or the other entropy pools behind /dev/random. > >With "internals", I do not mean the actual state of the CPU, but the >behaviour of all the CPU's execution engines. > >An Intel engineer might know how to affect the CPU so that the CPU >jitter code measures a deterministic pattern, but he will not know the >contents of my memory. Here I agree fully. > >>> Statistical tests are useful only for detecting the absence of >>> entropy, not for the opposite. >> >> Again, I fully agree. But it is equally important to understand that >> entropy is relative. > >In cryptography, we care about absolute entropy, i.e., _nobody_ must be >able to predict the RNG output, not even any CPU engineer. With your clarification above, I agree here fully. And now my task is to verify the root cause which I seem to have found. Let me do my homework. Ciao Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-10 17:21 ` Stephan Mueller 2013-11-10 20:28 ` Clemens Ladisch @ 2013-11-11 2:58 ` H. Peter Anvin 1 sibling, 0 replies; 61+ messages in thread From: H. Peter Anvin @ 2013-11-11 2:58 UTC (permalink / raw) To: Stephan Mueller, Clemens Ladisch Cc: Theodore Ts'o, Pavel Machek, sandy harris, linux-kernel, linux-crypto, Nicholas Mc Guire On 11/10/2013 09:21 AM, Stephan Mueller wrote: > > Here you say it: we *assume*. And please bear in mind that we all know for a > fact that the theory behind quantum physics is not complete, because it does > not work together with the theory of relativity. That again is a hint that > there is NO proof that decay is really unpredictable. > Honestly, if you want to be taken seriously, this is not the kind of thing to put in your discussion. -hpa ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-06 12:51 ` Stephan Mueller 2013-11-06 13:04 ` Theodore Ts'o @ 2013-11-07 1:03 ` Nicholas Mc Guire 2013-11-07 5:26 ` Stephan Mueller 1 sibling, 1 reply; 61+ messages in thread From: Nicholas Mc Guire @ 2013-11-07 1:03 UTC (permalink / raw) To: Stephan Mueller Cc: Theodore Ts'o, Pavel Machek, sandy harris, linux-kernel, linux-crypto [-- Attachment #1: Type: text/plain, Size: 2667 bytes --] On Wed, 06 Nov 2013, Stephan Mueller wrote: > Am Mittwoch, 6. November 2013, 07:43:54 schrieb Theodore Ts'o: > > Hi Theodore, > > >On Wed, Nov 06, 2013 at 12:49:45PM +0100, Stephan Mueller wrote: > >> Here is a quote from his answer to my question whether he was able to > >> identify the root cause: > >> > >> "its inherent in the microtiming of Hardware and there is nothing you > >> can do about it if you want the root cause is quantum physics" > > > >That's unfortunate, since it leaves open the question of whether this > >jitter is something that could be at least somewhat predictable if you > >had a lot more information about the internal works of the CPU or > >not.... > > I do not understand that answer: I thought we are talking about the > search of non-predictable noise sources. If you cannot predict the > sequence even if you have the state of the CPU, that is what we are > looking for, is it not? unpredictabilitty of the individual event does not imply that you do not have the ability to "guess" with more than 50% - that is just because it is not predictable does not mean itt is bias-free (and more importantly here that the bias is not influenced by controllable factors like load). Attached is a simple demonstration of this problem (gauss.c) that runs in user-space and harvestts entropy by race occurrence, while the distribution is a nice normal distribution (on multticore it is an overlay of multtiple normal distributions - one per core-pairing possible) it is not load independent. Never the less the individual event (race/no-race) is not predictable. > > Besides, how on earth shall an attacker even gain knowledge about the > state of the CPU or disable CPU mechanisms? Oh, I forgot, your NSA guy. > But if he is able to do that, all discussions are moot because he simply > disables any noise sources by flipping a bit, reads the memory that is > used to hold the state of the RNG or just overwrites the memory > locations where data is collected, because the general protection > mechanisms offered by the kernel and the underlying hardware are broken. No need to gain knowledge of the internal CPU state itt would be sufficient to be able to put the CPU in a sub-state-space in which the distribution is shifted. it may be enough to reduce the truely random bits of some key only by a few bits to make it suceptible to brute force attacks. > > Also, does your answer mean you would disregard radioactive decay that > is not predictable due to quantum physics and Heisenberg? > maybe I missed something - but what does radioactive decay induced emission have to do with Heissenberg ? thx! hofrat [-- Attachment #2: gauss.c --] [-- Type: text/x-csrc, Size: 4360 bytes --] /* gauss.c: * A complicated way of producing normal distribution plots with a * modern CPU by harvesting the intherent randomness. * * This code is striped of almost all error checking and all argument * handling - this is intended to show the prinicple only. * * compile: gcc -O2 gause.c -o gause -lpthread * run: ./gause | tee logfile * * be patient - this will take time if you want a smoth curve (hours..days !) * once you have a suitably long recording plot the distribution - brute force * might be * sort -n logfile | uniq -c > data * gnuplot * ... * gnuplot> plot "data" using 2:1 with lines * * this will give you a nice gauss cure on all systems - if it does not then * your N needs adjusting ! * * The only thing you must adjust to your hardware is N * here are some examples 32 bit: * AMD Duron UP : 12000000 * 32 bit install: * AMD Sempron UP : 5000000 * Core Duo E7400 SMP : 100000 * 64 bit intsll: * Intel Nehalem 8 core : 10000 * Intel CoreDuo 2 Quad : 5000 * * if the runs shows all samples close to 0 then increas N * if you get values all samples close to SAMPLES decrease N * * One could now speculate that this number actually is a metric for the * complexity of the CPU... * * further NUM_THREADS can be adjusted - in general 3 seems to be the best * though I have no clue why. Default 2 gives nice curves eventually as well. * if you fiddle with NUM_THREADS you also need to re-adjust N. * * what is this doing ? Its letting a set of threads race on a unprotected * global variable cnt - the run of the thread set is equivalent to drawing * a ball from an urn of infinetly many read and blue balls. If a race is * detected (cnt != N*NUM_THREADS) we assign this the color red, otherwise * blue. * The claim is that the occurance of red/blue is truely random and as evidence * this code produces close to perfect gause curves on and IDLE system. So this * is not driven by any peripheral interrupts or the like, in fact on high * loads things get a bit distorted... In my opinion this demonstrates that at * the core of a modern CPU there is in fact a true entropy source at work :) * * Copyright Der Herr Hofrat <der.herr@hofr.at> 2009,2010,2011 * License GPL V2 or later (http://www.gnu.org/copyleft/gpl.html) * * If you use this code for anything useful I would be happy to here from you ! * * thx! * hofrat */ #include <pthread.h> /* pthread_* */ #include <stdio.h> /* printf,perror,fflush */ #include <stdlib.h> /* exit */ #define NUM_THREADS 2 /* number of concurrent threas */ volatile long cnt = 0; /* the global object to race on */ unsigned long SAMPLES=256; /* how many balls to draw from the urn */ unsigned long NUM_TRIALS=262144; /* how many samples to draW */ unsigned long N=10000000; /* some large number - depends on hardware */ void *Thread(void *); /* This is the ESRNG that emits a ball * cnt describes the color of the ball */ void * Thread(void *v) { unsigned long n; for (n = 1; n <= N; ++n) { ++cnt; } return NULL; } /* draw the requested sampls from urn * returns number of red balls * * Note that return values of pthread_create/join * are checked as this would be critical if they failed * silent - all "unnecessary" error checking through was * removed. */ int draw_balls(int *samples){ int i,n; unsigned long red; pthread_t t[NUM_THREADS]; red=0; for(i=0;i<*samples;i++){ cnt=0; /* sample the urn */ for (n = 0; n < NUM_THREADS; ++n){ if(pthread_create( t+n, NULL, Thread, NULL)){ perror("pthread_create"); exit(-1); } } /* wait for the sample to complete */ for (n = 0; n < NUM_THREADS; ++n){ if(pthread_join(t[n],NULL)){ perror("pthread_join"); exit(-1); } } /* check the color * race occurs => red * no race => blue */ if(N*NUM_THREADS - cnt){ /* count the red */ red++; } } return red; } /* simply get NUM_TRIALS sets of balls from * the urn and print out how many were red * and how many blue - plot this to get a * nice gause curv. */ int main(int argc, char **argv) { int i; int num_red,num_blue; int sample_size=SAMPLES; i=0; while(i++<NUM_TRIALS){ num_red=draw_balls(&sample_size); num_blue=sample_size-num_red; printf("%d %d\n",num_red,num_blue); fflush(stdout); } return 0; } ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-07 1:03 ` Nicholas Mc Guire @ 2013-11-07 5:26 ` Stephan Mueller 2013-11-09 22:04 ` Clemens Ladisch 0 siblings, 1 reply; 61+ messages in thread From: Stephan Mueller @ 2013-11-07 5:26 UTC (permalink / raw) To: Nicholas Mc Guire Cc: Theodore Ts'o, Pavel Machek, sandy harris, linux-kernel, linux-crypto Am Donnerstag, 7. November 2013, 02:03:57 schrieb Nicholas Mc Guire: Hi Nicholas, >On Wed, 06 Nov 2013, Stephan Mueller wrote: >> Am Mittwoch, 6. November 2013, 07:43:54 schrieb Theodore Ts'o: >> >> Hi Theodore, >> >> >On Wed, Nov 06, 2013 at 12:49:45PM +0100, Stephan Mueller wrote: >> >> Here is a quote from his answer to my question whether he was able >> >> to >> >> identify the root cause: >> >> >> >> "its inherent in the microtiming of Hardware and there is nothing >> >> you >> >> can do about it if you want the root cause is quantum physics" >> > >> >That's unfortunate, since it leaves open the question of whether >> >this >> >jitter is something that could be at least somewhat predictable if >> >you >> >had a lot more information about the internal works of the CPU or >> >not.... >> >> I do not understand that answer: I thought we are talking about the >> search of non-predictable noise sources. If you cannot predict the >> sequence even if you have the state of the CPU, that is what we are >> looking for, is it not? > >unpredictabilitty of the individual event does not imply that you do >not have the ability to "guess" with more than 50% - that is just >because it is not predictable >does not mean itt is bias-free (and more importantly here that the bias >is not influenced by controllable factors like load). Attached is a >simple demonstration of this problem (gauss.c) that runs in user-space >and harvestts entropy by race occurrence, while the distribution is a >nice normal distribution (on multticore it is an overlay of multtiple >normal distributions - one per core-pairing possible) it is not load >independent. Never the less the individual event (race/no-race) is not >predictable. Thank you for sharing your ideas and code. There is one deviation of my RNG from your considerations. My RNG is not around race contention (i.e. your software-based uncertainty) but a simple measurement of how long some instruction take to execute. So, how can I induce skews? By trying to disable CPU logic or fudge with the CPU support (like cache attacks, etc). My tests have shown that disabling some CPU logic may diminish timing variations, but they are still sufficiently large to support the RNG. So, when we already have variations that are sufficient (i.e. the entropy is sufficient), using the CPU features that initially have been disabled but are now added on top of an already sufficient set of variations cannot diminish the entropy that is already present. Even when we assume we have full control over the CPU features, I do not see a way how we can use these features to cancel already existing variations out. Or do you have an idea how that can be established? Note, we all must assume that an attacker is only in user state. Anything else is meaningless. >> Besides, how on earth shall an attacker even gain knowledge about the >> state of the CPU or disable CPU mechanisms? Oh, I forgot, your NSA >> guy. But if he is able to do that, all discussions are moot because >> he simply disables any noise sources by flipping a bit, reads the >> memory that is used to hold the state of the RNG or just overwrites >> the memory locations where data is collected, because the general >> protection mechanisms offered by the kernel and the underlying >> hardware are broken. >No need to gain knowledge of the internal CPU state itt would be >sufficient to be able to put the CPU in a sub-state-space in which >the distribution is shifted. it may be enough to reduce the truely >random bits of some key only by a few bits to make it suceptible to >brute force attacks. Note, the proposed RNG contains an unbias operation (the Von-Neumann unbiaser) which is proven to remove any bias when it is established that the individual observations are independent. And the way the observations are generated ensures that they are independent. Thus, a skew should not be a concern here. Ciao Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-07 5:26 ` Stephan Mueller @ 2013-11-09 22:04 ` Clemens Ladisch 2013-11-10 1:16 ` Stephan Mueller 0 siblings, 1 reply; 61+ messages in thread From: Clemens Ladisch @ 2013-11-09 22:04 UTC (permalink / raw) To: Stephan Mueller Cc: Nicholas Mc Guire, Theodore Ts'o, Pavel Machek, sandy harris, linux-kernel, linux-crypto Stephan Mueller wrote: > Am Donnerstag, 7. November 2013, 02:03:57 schrieb Nicholas Mc Guire: >> On Wed, 06 Nov 2013, Stephan Mueller wrote: >>> Besides, how on earth shall an attacker even gain knowledge about the >>> state of the CPU or disable CPU mechanisms? Oh, I forgot, your NSA >>> guy. But if he is able to do that, all discussions are moot because >>> he simply disables any noise sources by flipping a bit, reads the >>> memory that is used to hold the state of the RNG or just overwrites >>> the memory locations where data is collected, because the general >>> protection mechanisms offered by the kernel and the underlying >>> hardware are broken. >> >> No need to gain knowledge of the internal CPU state itt would be >> sufficient to be able to put the CPU in a sub-state-space in which >> the distribution is shifted. it may be enough to reduce the truely >> random bits of some key only by a few bits to make it suceptible to >> brute force attacks. > > Note, the proposed RNG contains an unbias operation (the Von-Neumann > unbiaser) which is proven to remove any bias when it is established that > the individual observations are independent. And the way the > observations are generated ensures that they are independent. "Independent" does not mean that your own code avoids reusing data from the previous loop iteration; it means that the _entire_ process that generates the bits is not affected by any memory of the past. The observations are derived from the internal CPU state, which is *not* reset between measurements. Regards, Clemens ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-09 22:04 ` Clemens Ladisch @ 2013-11-10 1:16 ` Stephan Mueller 0 siblings, 0 replies; 61+ messages in thread From: Stephan Mueller @ 2013-11-10 1:16 UTC (permalink / raw) To: Clemens Ladisch Cc: Nicholas Mc Guire, Theodore Ts'o, Pavel Machek, sandy harris, linux-kernel, linux-crypto Am Samstag, 9. November 2013, 23:04:07 schrieb Clemens Ladisch: Hi Clemens, > Stephan Mueller wrote: > > Am Donnerstag, 7. November 2013, 02:03:57 schrieb Nicholas Mc Guire: > >> On Wed, 06 Nov 2013, Stephan Mueller wrote: > >>> Besides, how on earth shall an attacker even gain knowledge about the > >>> state of the CPU or disable CPU mechanisms? Oh, I forgot, your NSA > >>> guy. But if he is able to do that, all discussions are moot because > >>> he simply disables any noise sources by flipping a bit, reads the > >>> memory that is used to hold the state of the RNG or just overwrites > >>> the memory locations where data is collected, because the general > >>> protection mechanisms offered by the kernel and the underlying > >>> hardware are broken. > >> > >> No need to gain knowledge of the internal CPU state itt would be > >> sufficient to be able to put the CPU in a sub-state-space in which > >> the distribution is shifted. it may be enough to reduce the truely > >> random bits of some key only by a few bits to make it suceptible to > >> brute force attacks. > > > > Note, the proposed RNG contains an unbias operation (the Von-Neumann > > unbiaser) which is proven to remove any bias when it is established that > > the individual observations are independent. And the way the > > observations are generated ensures that they are independent. > > "Independent" does not mean that your own code avoids reusing data from > the previous loop iteration; it means that the _entire_ process that > generates the bits is not affected by any memory of the past. In the other email, I explained the different types of tests I performed. All of these tests show proper statistical results. Now, I also performed these tests without the Von-Neumann unbiaser. All of the statistical tests results still showed a white noise (note, in the next code release, I will have an allocation flag added that you can use to very simply deactivate the Von-Neumann unbiaser for testing). So, the Von-Neumann unbiaser is to be considered a line of defence against (not yet observed, but potential) skews. Similarly, the optional whitening (non-cryptographic) function of jent_stir_pool is yet another line of defence. So, bottom line: I fully concur that using two separate measurements may not imply that they are independent. But testing shows that it does not matter. > > The observations are derived from the internal CPU state, which is *not* > reset between measurements. > > > Regards, > Clemens Ciao Stephan -- | Cui bono? | ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-03 7:20 ` Stephan Mueller 2013-11-03 12:41 ` Theodore Ts'o @ 2013-11-03 23:32 ` Pavel Machek 2013-11-05 12:25 ` Stephan Mueller 1 sibling, 1 reply; 61+ messages in thread From: Pavel Machek @ 2013-11-03 23:32 UTC (permalink / raw) To: Stephan Mueller Cc: Theodore Ts'o, sandy harris, linux-kernel, linux-crypto Hi! > Another friend of mine mentioned that he assumes the rise and fall times > of transistors varies very slightly and could be the main reason for the > jitter. I do not think that this is really the case, because our gates > that form the CPU instructions comprise of many transistors. The > combined raise/fall jitter should cancel each other out. Plus, there's clock that should make sure that this jitter does not matter. > >There should be way to extract entropy more directly from various > >oscillator effects, no? > > I am working a different way of measuring such oscillator effects by > using the high-resolution timer of the CPU and measure it with a > Jiffies-based snapshotting window. So, here I would combine two timers > that are differently generated. If their frequencies would be relative > prime to each other, we would measure a direct oscillator effect. I guess main problem is machines that do not have high-resolution timer on the CPU (rdtsc). They do not get enough entropy during boot, and the hell breaks loose. But they usually _do_ have RTC or other clock, not driven by CPU oscilator. Good. What about just while (!enough_entropy) { cur_time = read_rtc(); simulated_tsc = 0; while (cur_time == read_rtc()) simulated_tsc++; gain_entropy_from(simulated_tsc) } (Where enough_entropy should be something like 128 bits). This should work, we know why it works (drift between rtc and cpu clock) and it does _not_ need rdtsc-style fast source. Disadvantage is that it burns cpu, but, well, you only need 128 bits. Asuming the rtc used has 100Hz resolution, enough entropy should be collected in under 2 seconds. That's acceptable adition to time it takes generating ssh keys on slow cpu. Pavel -- (english) http://www.livejournal.com/~pavelmachek (cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-03 23:32 ` Pavel Machek @ 2013-11-05 12:25 ` Stephan Mueller 2013-11-05 13:45 ` Stephan Mueller 0 siblings, 1 reply; 61+ messages in thread From: Stephan Mueller @ 2013-11-05 12:25 UTC (permalink / raw) To: Pavel Machek; +Cc: Theodore Ts'o, sandy harris, linux-kernel, linux-crypto Am Montag, 4. November 2013, 00:32:07 schrieb Pavel Machek: Hi Pavel, >Hi! > >> Another friend of mine mentioned that he assumes the rise and fall >> times of transistors varies very slightly and could be the main >> reason for the jitter. I do not think that this is really the case, >> because our gates that form the CPU instructions comprise of many >> transistors. The combined raise/fall jitter should cancel each other >> out. > >Plus, there's clock that should make sure that this jitter does not >matter. > >> >There should be way to extract entropy more directly from various >> >oscillator effects, no? >> >> I am working a different way of measuring such oscillator effects by >> using the high-resolution timer of the CPU and measure it with a >> Jiffies-based snapshotting window. So, here I would combine two >> timers >> that are differently generated. If their frequencies would be >> relative >> prime to each other, we would measure a direct oscillator effect. > >I guess main problem is machines that do not have high-resolution >timer on the CPU (rdtsc). They do not get enough entropy during boot, >and the hell breaks loose. That is right. That is also why I try to use the clocksource framework if the get_cycles righ-resolution timer is not available. > >But they usually _do_ have RTC or other clock, not driven by CPU >oscilator. Good. > >What about just > >while (!enough_entropy) { > cur_time = read_rtc(); > simulated_tsc = 0; > while (cur_time == read_rtc()) > simulated_tsc++; > gain_entropy_from(simulated_tsc) >} That is an interesting piece of code -- what would you do in the gain_entropy_from function? > >(Where enough_entropy should be something like 128 bits). > >This should work, we know why it works (drift between rtc and cpu >clock) and it does _not_ need rdtsc-style fast source. > >Disadvantage is that it burns cpu, but, well, you only need 128 That disadvantage should be no problem, because at the time we need entropy, burning some CPU cycles are ok. Encryption burns even more CPU cycles :-) >bits. Asuming the rtc used has 100Hz resolution, enough entropy should >be collected in under 2 seconds. That's acceptable adition to time it >takes generating ssh keys on slow cpu. > Pavel Ciao Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-05 12:25 ` Stephan Mueller @ 2013-11-05 13:45 ` Stephan Mueller 2013-11-06 11:42 ` Stephan Mueller 0 siblings, 1 reply; 61+ messages in thread From: Stephan Mueller @ 2013-11-05 13:45 UTC (permalink / raw) To: Pavel Machek; +Cc: Theodore Ts'o, sandy harris, linux-kernel, linux-crypto Am Dienstag, 5. November 2013, 13:25:40 schrieb Stephan Mueller: Hi Pavel, >Am Montag, 4. November 2013, 00:32:07 schrieb Pavel Machek: >>But they usually _do_ have RTC or other clock, not driven by CPU >>oscilator. Good. >> >>What about just >> >>while (!enough_entropy) { >> >> cur_time = read_rtc(); >> simulated_tsc = 0; >> while (cur_time == read_rtc()) >> >> simulated_tsc++; >> >> gain_entropy_from(simulated_tsc) >> >>} > >That is an interesting piece of code -- what would you do in the >gain_entropy_from function? Please disregard my question. I plugged that idea into my current Jitter RNG processing and disabled the other jitter measurements to get a clear, isolated picture. The result is also a white noise! And it is even quite fast. That means with this approach, even another noise source is available that I could combine with the jitter measurements. I will have to perform more tests on that noise source. But the smoke test is already quite interesting. Ciao Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-05 13:45 ` Stephan Mueller @ 2013-11-06 11:42 ` Stephan Mueller 2013-11-06 13:26 ` Pavel Machek 0 siblings, 1 reply; 61+ messages in thread From: Stephan Mueller @ 2013-11-06 11:42 UTC (permalink / raw) To: Pavel Machek; +Cc: Theodore Ts'o, sandy harris, linux-kernel, linux-crypto Am Dienstag, 5. November 2013, 14:45:58 schrieb Stephan Mueller: Hi Pavel, >Am Dienstag, 5. November 2013, 13:25:40 schrieb Stephan Mueller: > >Hi Pavel, > >>Am Montag, 4. November 2013, 00:32:07 schrieb Pavel Machek: >>>But they usually _do_ have RTC or other clock, not driven by CPU >>>oscilator. Good. >>> >>>What about just >>> >>>while (!enough_entropy) { >>> >>> cur_time = read_rtc(); >>> simulated_tsc = 0; >>> while (cur_time == read_rtc()) >>> >>> simulated_tsc++; >>> >>> gain_entropy_from(simulated_tsc) >>> >>>} >> >>That is an interesting piece of code -- what would you do in the >>gain_entropy_from function? > >Please disregard my question. > >I plugged that idea into my current Jitter RNG processing and disabled >the other jitter measurements to get a clear, isolated picture. > >The result is also a white noise! And it is even quite fast. After doing some more research on this approach, I have to admit that the output not good (i.e. white noise) in all situations. Therefore, I dropped that (for now). But thank you very much for your suggestion. Ciao Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-06 11:42 ` Stephan Mueller @ 2013-11-06 13:26 ` Pavel Machek 2013-11-07 3:12 ` Stephan Mueller 0 siblings, 1 reply; 61+ messages in thread From: Pavel Machek @ 2013-11-06 13:26 UTC (permalink / raw) To: Stephan Mueller Cc: Theodore Ts'o, sandy harris, linux-kernel, linux-crypto Hi! > >I plugged that idea into my current Jitter RNG processing and disabled > >the other jitter measurements to get a clear, isolated picture. > > > >The result is also a white noise! And it is even quite fast. > > After doing some more research on this approach, I have to admit that > the output not good (i.e. white noise) in all situations. Therefore, I > dropped that (for now). Is there chance to extract at least some entropy from it? (Can you post the code you used for testing?) Because in this case we know where the entropy comes from, which is important for Ted. Thanks, Pavel -- (english) http://www.livejournal.com/~pavelmachek (cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-11-06 13:26 ` Pavel Machek @ 2013-11-07 3:12 ` Stephan Mueller 0 siblings, 0 replies; 61+ messages in thread From: Stephan Mueller @ 2013-11-07 3:12 UTC (permalink / raw) To: Pavel Machek; +Cc: Theodore Ts'o, sandy harris, linux-kernel, linux-crypto Am Mittwoch, 6. November 2013, 14:26:35 schrieb Pavel Machek: Hi Pavel, >Hi! > >> >I plugged that idea into my current Jitter RNG processing and >> >disabled >> >the other jitter measurements to get a clear, isolated picture. >> > >> >The result is also a white noise! And it is even quite fast. >> >> After doing some more research on this approach, I have to admit that >> the output not good (i.e. white noise) in all situations. Therefore, >> I >> dropped that (for now). > >Is there chance to extract at least some entropy from it? (Can you >post the code you used for testing?) Because in this case we know >where the entropy comes from, which is important for Ted. The code is as follows -- it hooks into the framework of the RNG I already have, so the code folds the obtained data into one bit (use the following function as a drop-in replacement to my RNG code. static __u64 jent_measure_jitter(struct rand_data *entropy_collector) { __u64 starttime = 0; __u64 currtime = 0; __u64 counter = 0; __u64 data = 0; jent_get_ustime(&starttime); jent_get_ustime(&currtime); while(starttime == currtime) { jent_get_ustime(&currtime); counter++; } jent_fold_time(counter, &data, 1); return data; } Consider the following in addition: static inline void jent_get_ustime(__u64 *out) { __u64 tmp = 0; struct timeval time; if(gettimeofday(&time, NULL) == 0) tmp = time.tv_usec; *out = tmp; } For the kernel land, I implemented jent_get_ustime to be identical to do_gettimeofday(). The result is the following on my i7 2nd gen without using the Von- Neumann unbias operation: - user space: looks like good white noise based on the results of ent (Chi square, etc). When I print out the counter variable above and calculate the Shannon Entropy, I get about 1.5 bits, so we have variations. But when you look at the data manually, you see quite some streaks that alternate between two values. Here is an example: 4 6 10 2 3 2 3 4 4 4 4 4 5 3 4 5 4 4 4 5 4 4 5 4 4 5 4 4 5 4 4 5 4 4 4 5 4 4 - kernel space: the resulting binary string is not very good: the chi square is very bad. Moreover, the resulting data string is slightly skewed. The reason is simple by looking at the counter value which I obtained with another debugfs file: there are very very long streaks of the same or alternating values. So, I guess you may get some entropy, but I am not sure how much. Also, when I enlarge the timer value to look something like that: if(gettimeofday(&time, NULL) == 0) tmp = time.tv_usec>>3; the counter value is not getting really better, it is still alternating between two or three values. > >Thanks, > Pavel Ciao Stephan ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: Executing time variation tests on bare metal 2013-10-29 13:24 ` Theodore Ts'o 2013-10-29 14:00 ` Stephan Mueller @ 2013-11-13 3:37 ` Stephan Mueller 1 sibling, 0 replies; 61+ messages in thread From: Stephan Mueller @ 2013-11-13 3:37 UTC (permalink / raw) To: Theodore Ts'o Cc: sandy harris, linux-kernel, linux-crypto, Nicholas Mc Guire, Clemens Ladisch, Pavel Machek Am Dienstag, 29. Oktober 2013, 09:24:48 schrieb Theodore Ts'o: Hi Theodore, > On Tue, Oct 29, 2013 at 09:42:30AM +0100, Stephan Mueller wrote: > > Based on this suggestion, I now added the tests in Appendix F.46.8 where > > I disable the caches and the tests in Appendix F.46.9 where I disable > > the caches and interrupts. > > What you've added in F.46 is a good start, but as a suggestiom, > instead of disabling one thing at a time, try disabling *everything* > and then see what you get, and then enabling one thing at a time. The > best thing is if you can get to the point where the amount of entropy > is close to zero. Then as you add things back, there's a much better > sense of where the unpredictability might be coming from, and whether > the unpredictability is coming from something which is fundamentally > arising from something which is chaotic or quantum effect, or just > because we don't have a good way of modelling the behavior of the > L1/L2 cache (for example) and that is spoofing your entropy estimator. I was now able to implement two more test buckets that were in my mind for quite some time. They are documented in the new sections 6.3 and 6.4 in [1]. The tests for the time variation measurements are now executed on bare metal, i.e. without *any* operating system underneath. For achieving that, I used the memtest86+ tool, ripped out the memory tests and added the time variation testing into it. The time variation tests now execute single threaded without any interference from an underlying operating system. Again, I added all the variations of disabling CPU support (TLB flushes, L1/2 flushes, cache disabling, ...). And, surprise: all the jitter is still there. Furthermore, I use the same vehicle to just measure the variations by obtaining two timestamps immediately after each other and calculate the difference. As before, there are various tests which disable the different CPU mechanisms. And, surprise: there is still variations visible. Granted, these variations are smaller than the ones for the folding loop. But the smallest variations still have way more than 1 bit when applying the Shannon Entropy formula. The code is uploaded to [2] and can be used to play with. In addition, I added test resutls with varying loads as explained in section 6.2 (thanks to Nicholas Mc Guire for helping here). [1] http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.html [2] http://www.chronox.de/ Ciao Stephan -- | Cui bono? | ^ permalink raw reply [flat|nested] 61+ messages in thread
* Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random 2013-10-28 21:45 ` Theodore Ts'o 2013-10-29 8:42 ` Stephan Mueller @ 2013-10-30 12:59 ` Sandy Harris 1 sibling, 0 replies; 61+ messages in thread From: Sandy Harris @ 2013-10-30 12:59 UTC (permalink / raw) To: Theodore Ts'o, Stephan Mueller, sandy harris, LKML, linux-crypto Theodore Ts'o <tytso@mit.edu> wrote: > Fundamentally, what worries me about this scheme (actually, causes the > hair on the back of my neck to rise up on end) is this statement in > your documentation[1]: > > When looking at the sequence of time deltas gathered > during testing [D] , no pattern can be detected. Therefore, the > fluctuation and the resulting distribution are not based on a > repeating pattern and must be considered random. > > [1] http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.html > > Just because we can't detect a pattern does **not** mean that it is > not based on a repeating pattern, and therefore must be considered > random. We can't detect a pattern in RDRAND, so does that mean it's > automatically random? Why, no. > ... > It may be that there is some very complex state which is hidden inside > the the CPU execution pipeline, the L1 cache, etc., etc. But just > because *you* can't figure it out, and just because *I* can't figure > it out doesn't mean that it is ipso facto something which a really > bright NSA analyst working in Fort Meade can't figure out. (Or heck, > a really clever Intel engineer who has full visibility into the > internal design of an Intel CPU....) > > Now, it may be that in practice, an adversary won't be able to carry > out a practical attack ... It seems worth noting here that Ted's reasons for skepticism apply not just to Stephan's Jitter generator, but to others such as Havege (already in Debian) which are based on differences in speed of arithmetic operations, presumably due to cache & TLB misses, pipeline stalls, etc. Also to ones based on variations in delays from timer calls such as my maxwell(8). It is also worth mentioning that, while Stephan has done thorough testing on a range of CPUs, others have test & rationale info as well. The Havege papers have a lot, my maxwell paper has a little, and there's: McGuire, Okech & Schiesser, Analysis of inherent randomness of the Linux kernel, http://lwn.net/images/conf/rtlws11/random-hardware.pdf I know my stuff is not an adequate answer to Ted, but I suspect some of the others may be. ^ permalink raw reply [flat|nested] 61+ messages in thread
end of thread, other threads:[~2013-11-14 18:34 UTC | newest] Thread overview: 61+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2013-10-11 18:38 [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random Stephan Mueller 2013-10-12 1:45 ` Sandy Harris 2013-10-12 3:28 ` Theodore Ts'o 2013-10-12 19:04 ` Stephan Mueller 2013-10-12 20:12 ` Stephan Mueller [not found] ` <CACXcFm=_jmeKe2YYbHDi-jTGX-23hDsDeu_weWQkr2F_FpE_6g@mail.gmail.com> 2013-10-14 13:38 ` Fwd: " Sandy Harris 2013-10-14 14:12 ` Stephan Mueller 2013-10-14 14:26 ` Stephan Mueller 2013-10-14 14:14 ` Sandy Harris 2013-10-14 14:40 ` Stephan Mueller 2013-10-14 15:18 ` Sandy Harris 2013-10-14 15:26 ` Stephan Mueller 2013-10-14 15:46 ` Sandy Harris 2013-10-14 21:33 ` Sandy Harris 2013-10-15 6:23 ` Stephan Mueller 2013-10-28 15:40 ` Stephan Mueller 2013-10-28 16:06 ` Henrique de Moraes Holschuh 2013-10-28 16:15 ` Stephan Mueller 2013-10-28 21:45 ` Theodore Ts'o 2013-10-29 8:42 ` Stephan Mueller 2013-10-29 13:24 ` Theodore Ts'o 2013-10-29 14:00 ` Stephan Mueller 2013-10-29 22:25 ` Stephan Mueller 2013-11-02 11:01 ` Pavel Machek 2013-11-02 11:12 ` Pavel Machek 2013-11-03 7:20 ` Stephan Mueller 2013-11-03 12:41 ` Theodore Ts'o 2013-11-05 12:20 ` Stephan Mueller 2013-11-06 11:49 ` Stephan Mueller 2013-11-06 12:43 ` Theodore Ts'o 2013-11-06 12:51 ` Stephan Mueller 2013-11-06 13:04 ` Theodore Ts'o 2013-11-06 13:24 ` Pavel Machek 2013-11-07 0:36 ` Nicholas Mc Guire 2013-11-07 5:21 ` Stephan Mueller 2013-11-09 22:04 ` Clemens Ladisch 2013-11-10 1:10 ` Stephan Mueller 2013-11-10 16:31 ` Clemens Ladisch 2013-11-10 17:21 ` Stephan Mueller 2013-11-10 20:28 ` Clemens Ladisch 2013-11-13 3:12 ` Stephan Mueller 2013-11-13 11:51 ` Clemens Ladisch 2013-11-13 15:15 ` Stephan Mueller 2013-11-13 17:14 ` Pavel Machek 2013-11-14 10:51 ` Clemens Ladisch 2013-11-14 18:01 ` Stephan Mueller 2013-11-14 18:30 ` Clemens Ladisch 2013-11-14 18:34 ` Stephan Mueller 2013-11-11 2:58 ` H. Peter Anvin 2013-11-07 1:03 ` Nicholas Mc Guire 2013-11-07 5:26 ` Stephan Mueller 2013-11-09 22:04 ` Clemens Ladisch 2013-11-10 1:16 ` Stephan Mueller 2013-11-03 23:32 ` Pavel Machek 2013-11-05 12:25 ` Stephan Mueller 2013-11-05 13:45 ` Stephan Mueller 2013-11-06 11:42 ` Stephan Mueller 2013-11-06 13:26 ` Pavel Machek 2013-11-07 3:12 ` Stephan Mueller 2013-11-13 3:37 ` [PATCH] CPU Jitter RNG: Executing time variation tests on bare metal Stephan Mueller 2013-10-30 12:59 ` [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random Sandy Harris
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).