Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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: 01010011 10011010 01011011 01100100 10111000 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
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 110010011101101010100010001000 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
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 110010011101101010100010001000 is zero
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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: 01010011 10011010 01011011 01100100 10111000 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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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.
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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? | -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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
--
To unsubscribe from this list: send the line unsubscribe linux-crypto in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 so large, and the state transitions ar so 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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 /* 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 : 1200 * 32 bit install: * AMD Sempron UP : 500 * Core Duo E7400 SMP : 10 * 64 bit intsll: * Intel Nehalem 8 core : 1 * 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.h...@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 !
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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_usec3;
the counter value is not getting really better, it is still alternating
between two or three values.
Thanks,
Pavel
Ciao
Stephan
--
To unsubscribe from this list: send the line unsubscribe linux-crypto in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 so large, and the state transitions ar so 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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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
--
To unsubscribe from this list: send the line unsubscribe linux-crypto in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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
--
To unsubscribe from this list: send the line unsubscribe linux-crypto in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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.. 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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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
--
To unsubscribe from this list: send the line unsubscribe linux-crypto in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
Theodore Ts'o ty...@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. -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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,
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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) 0x0001)
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
--
To unsubscribe from this list: send the line unsubscribe linux-crypto in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Fwd: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
Stephan Mueller smuel...@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 ^= (x1) ; 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? -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Fwd: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
Am Montag, 14. Oktober 2013, 09:38:34 schrieb Sandy Harris: Hi Sandy, Stephan Mueller smuel...@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 ^= (x1) ; 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
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
On Mon, Oct 14, 2013 at 9:38 AM, Sandy Harris sandyinch...@gmail.com wrote: Stephan Mueller smuel...@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. -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Fwd: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
Am Montag, 14. Oktober 2013, 10:14:00 schrieb Sandy Harris: Hi Sandy, On Mon, Oct 14, 2013 at 9:38 AM, Sandy Harris sandyinch...@gmail.com wrote: Stephan Mueller smuel...@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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
On Mon, Oct 14, 2013 at 10:40 AM, Stephan Mueller smuel...@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. -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
Am Montag, 14. Oktober 2013, 11:18:16 schrieb Sandy Harris: Hi Sandy, On Mon, Oct 14, 2013 at 10:40 AM, Stephan Mueller smuel...@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 -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
On Mon, Oct 14, 2013 at 11:26 AM, Stephan Mueller smuel...@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 0x. 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. -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
Stephan Mueller smuel...@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. -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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
--
To unsubscribe from this list: send the line unsubscribe linux-crypto in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
On Fri, Oct 11, 2013 at 2:38 PM, Stephan Mueller smuel...@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? -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random
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
--
To unsubscribe from this list: send the line unsubscribe linux-crypto in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
