Re: [cryptography] Fwd: [RFC][PATCH 0/6] /dev/random - a new approach
Am Montag, 25. April 2016, 15:44:04 schrieb Sven M. Hallberg: Hi Sven, > Hi Stephan, thanks for your reply! > > Stephan Mueller <smuel...@chronox.de> on Fri, Apr 22 2016: > >> > The main > >> > improvements compared to the legacy /dev/random is to provide > >> > sufficient > >> > entropy during boot time as well as in virtual environments and when > >> > using SSDs. > >> > >> After reading the paper, it is not clear to me how this goal is > >> achieved. > > > > May I ask you to direct your attention to section 1.1. The legacy > > /dev/random has three noise sources: block devices, HID and interrupts. > > With those noise sources, only the block device and HID noise sources are > > interpreted to collect entropy between zero to 11 bits per event. The > > interrupt noise source is credited one bit of entropy per 64 received > > interrupts (or the expiry of 1 second, whatever comes later). > > I see, thanks. But so it seems your main contribution is to change the > weights on the entropy estimation... This goes in the right direction, but does not hit the nail completely. > > > I interpret each interrupt to have about 0.9 bits of entropy. And I > > do not specifically look for block device and HID events > > > > As during boot, hundreds of interrupts are generated, and I have the > > valuation of about 0.9 bits of entropy per interrupt event, the LRNG will > > collect entropy much faster. > > No, as you explain, it will not collect it faster; it will increase its > counter faster. Your estimation bounds are (0.9, 0, 0) compared to Linux This is not correct. I only have 0.9 per interrupts. Thus the two following zeros are not correct. > with (0.015, 11, 11) or something. > > My criticism now would be the question what this has to do with the rest > of the design. Why not just argue for an adjustment of the current > kernel's estimator? You cannot change it without a design change of the current code, that is the crux: there is a correlation between the time stamp processed in add_interrupt_randomness and add_disk/input_randomness. To wash that correlation away, the conservative estimate of 1/64th bit per interrupt is applied to the interrupt timings. Thus, I changed the approach of collecting entropy right from the start. Furthermore, I replaced the SHA-1 (based on a C implementation) RNG with an SP800-90A DRBG which can use hardware acceleration -- see the performance measurements in 3.4.7. > > In addition I would be interested in a more fine-grained analysis of the > few hundred interrupts that you mention happen during early boot. Which > sources typically produce these? I tested a worst case analysis as outlined in section 3.3 of my documentation (single interrupt, controlled by external without too much interference by other entities). I provided the test tools so that you can re-test it with the interrupt load you like. Ciao Stephan ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Fwd: [RFC][PATCH 0/6] /dev/random - a new approach
Am Freitag, 22. April 2016, 15:58:19 schrieb Fedor Brunner: Hi Fedor, > Hi Stephan, > could you please compare your RNG design with OpenBSD arc4random based > on ChaCha20. Ok, I try in the following. But please bear with me as I have not studied the OpenBSD RNG design to the fullest extent. Hence, if I am mistaken about one or another aspect of the OpenBSD RNG, I would ask for being corrected. src/sys/dev/rnd.c Implements the OpenBSD RNG. - The OpenBSD RNG hooks itself into various devices like HID, interrupt handler (similar to the legacy /dev/random of Linux). It uses timing and additional data depending on the callback location. The LRNG hooks itself into the interrupt handler and obtains a high-resolution time stamp. - The OpenBSD RNG uses an LFSR which looks like the Mersenne Twister to inject data into the entropy pool. The LRNG collapses the timing data into one bit via XOR and concatenates the individual bits. - After extracting the data from the entropy pool, a SHA-512 hash is calculated over the extracted bits and returned to the caller (it does not use the hash as backtracking resistance, but injects a timestamp into the pool to prevent identical SHA values). The LRNG simply reads out the required data from the entropy, but ensures that only newly added data is used (i.e. no bit is used twice). - The OpenBSD RNG uses a DRNG based on Chacha. The LRNG uses an SP800-90A DRBG. I do not want to enter the discussion about the properties of the Chacha DRNG compared to the AIS20/31 or SP800-90C requirements as I have not studied the DRNG too much. - It *looks* like the OpenBSD does not block and produces a data stream like /dev/urandom. The purpose of the LRNG /dev/random (which *seems* to be not present in the OpenBSD code) is to provide random data with information theoretical entropy (see AIS20/31 NTG.1 requirements). - The OpenBSD RNG does not maintain any entropy counter logic just like the LRNG. Considering that the OpenBSD /dev/random does not block, a data stream with strong cryptographic protection is generated just like provided with the LRNG. In addition, the LRNG allows the generation of random numbers with information theoretical entropy. - The OpenBSD RNG uses Chacha as raw cipher. The LRNG uses the Linux kernel crypto API SP800-90A DRBG which allows at compile time to select whether the CTR, Hash or HMAC DRBG is used. Furthermore, the kernel crypto API allows the use of assembler or hardware-supported cipher implementations which are selected at runtime. Ciao Stephan ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Fwd: [RFC][PATCH 0/6] /dev/random - a new approach
Am Freitag, 22. April 2016, 16:49:54 schrieb Sven M. Hallberg: Hi Sven, > > I developed a different approach, which I call Linux Random Number > > Generator (LRNG) to collect entropy within the Linux kernel. The main > > improvements compared to the legacy /dev/random is to provide sufficient > > entropy during boot time as well as in virtual environments and when > > using SSDs. > > After reading the paper, it is not clear to me how this goal is > achieved. As far as I can see, no new sources of entropy are > introduced; in fact a point is made to use only interrupt timings, > arguing that these effectively include other events. Why does this > design make more entropy available during boot and with solid-state > storage? May I ask you to direct your attention to section 1.1. The legacy /dev/random has three noise sources: block devices, HID and interrupts. With those noise sources, only the block device and HID noise sources are interpreted to collect entropy between zero to 11 bits per event. The interrupt noise source is credited one bit of entropy per 64 received interrupts (or the expiry of 1 second, whatever comes later). With that, the legacy /dev/random values block device and HID events with much higher entropy than interrupts. And that is warranted given that there is a high correlation between block devices / HID and interrupts. Thus, it is not possible to value the interrupt events with higher entropy. During boot, there are no HID events. If the system has an SSD, the kernel will mark this block device to not be used for block device entropy collection as the legacy /dev/random block device noise source rests on the pick up of spinning disk turbulence and spin angle wait times. This all is simply not present with SSDs. This implies that during boot with SSDs, you only have the interrupt noise source which values an interrupt with at most 1/64th bit of entropy. The same applies to Device Mapper setups or the use of VirtIO block devices. My measurements show that even in worst case scenarios, interrupt timings using a high resolution timer have 11 and more bits of entropy. To be on the save side, I interpret each interrupt to have about 0.9 bits of entropy. And I do not specifically look for block device and HID events which does not introduce the correlation problem the legacy /dev/random noise sources have. As during boot, hundreds of interrupts are generated, and I have the valuation of about 0.9 bits of entropy per interrupt event, the LRNG will collect entropy much faster. > > I'm also having trouble telling at a glance the exact blocking behavior > of the interfaces proposed. It seems that /dev/random and getrandom() > will block when the estimated entropy in the "seed buffer" is below some > threshold. But numbers mentioned are 32, 112, and 256; which is it and > when? About /dev/urandom it says that reseeds are required periodically. > Are these subject to blocking? /dev/random gets its data from the primary DRBG. The primary DRBG is designed to only release as many bytes as it was seeded with entropy. Thus, if you noise sources can only deliver, say, 16 bytes of entropy, a read request will receive those 16 bytes. Then, the caller is blocked. If new entropy comes in, the caller is woken up when reaching the wakeup threshold. This has the same logic as the legacy /dev/random. getrandom(NONBLOCK) will block until the secondary DRBG is fully seeded during initialization (i.e. 256 bits when using the suggested DRBG types which have 256 bits of security strength). Afterwards, it operates like /dev/urandom. This has the same logic as getrandom has with the legacy /dev/random implementation where the getrandom call blocks until the nonblocking_pool is seeded (with 128 bits). I.e. getrandom(NONBLOCK) unblocks when /proc/sys/kernel/random/drbg_fully_seeded turns to one (or the dmesg shows the entry about the DRBG being fully seeded). /dev/urandom will not block as it is the case with the legacy /dev/urandom. Ciao Stephan ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Mixing RdRand with other CPU-based entropy sources?
Am Donnerstag, 19. Dezember 2013, 09:58:06 schrieb Natanael: Hi Natanael, It's always a good idea to use several entropy sources and cryptographically mix their outputs into your pool. They won't reduce your total entropy either way, any predictable sources will only be adding less entropy than promised. I would not concur with this statement, if the entropy collection process implies or heuristicially estimates some value of entropy associated with the incoming information. Assume you have two noise sources which draw more or less from the same phenomenon (like Haveged and my proposed Jitter RNG which both use CPU execution time variations), which independent of each other would produce a bit stream with some entropy X and Y. Now, you have a collection process which draws from both noise sources at more or less the same time, as a baseline (i.e. unless you can prove otherwise) you must assume that there are some dependencies / correlations between these two bit streams. That means, your entropy collector cannot assume that the two bit streams have the combined entropy of X + Y, but that combined entropy is expected to be less as a baseline (i.e. unless you have a rationale why you still have an independence). That said, using the CPU execution time variations as a noise source, all my research showed that each measurement is independent of the previous measurement. That said, even two noise sources running in parallel (which means that they never truly execute in parallel on the same CPU) are always independent. So, the use of two different implementations drawing from the CPU execution time variations should be ok. You clearly see that particular problem with /dev/random and the newly introduced fast_pool. The noise sources for HID and block devices also always generate interrupts. Now, it is important that the interrupt noise collection function is implemented in a way that breaks its dependency/correlation to the other noise sources. That is (hopefully, but I have not seen any analysis yet) achieved with the fast_pool that collects and mixes at least 64 interrupts before mixing its state into the input_pool. Furthermore, you see that also in the fact that any mix of fast_pool into input_pool is assumed to only provide 1 bit of entropy. Ciao Stephan ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] on using RDRAND [was: Entropy improvement: haveged + rngd together?]
Am Dienstag, 3. Dezember 2013, 15:25:22 schrieb coderman: Hi coderman, On Mon, Dec 2, 2013 at 11:02 PM, Stephan Mueller smuel...@chronox.de wrote: ... Interesting: I have the same type of discussion (SP800-90B) to prepare (and even went through it -- see [1]) and I do not see it that problematic, if you have the right hooks into your noise source implementation (and I could imagine that this is a challenge with the current RDSEED/RDRAND implementation). one of the beautiful aspects of the RDRAND/RDSEED design is that un-trusting consumers can use it concurrently without leaking any useful information between them. consider multiple guest OS'es using the instruction directly. raw sampling of the sources would provide bias that _might_ be useful to a malicious consumer attempting to compromise the entropy of other processes or domains, if done naively. I concur with you here. And I do not ask for the availability of that information in any privilege level. I would be fine if that is available only in ring 0 and in VM root mode. I spoke with several NIST folks involved in the RNG process in September. And they are not ignorant. Therefore, I would not suggest that we imply anything here! are there other organizations that might provide some weight to these efforts? IETF? The German BSI performs RNG analyses for quite some time. See https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Zertifizierung/Interpretationen/AIS_31_Functionality_classes_for_random_number_generators_e.pdf Ciao Stephan -- | Cui bono? | ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] on using RDRAND [was: Entropy improvement: haveged + rngd together?]
Am Sonntag, 1. Dezember 2013, 20:27:34 schrieb d...@deadhat.com: Hi dj, I would not characterize the Linux RNG issue as fully resolved in any way. Until every CPU maker includes a source of entropy by design (instead of by accident) and the Kernel gets off its high horse and chooses to use them and the kernel gets pre-configured in distros with sane parameters, crypto software will continue to fail from low entropy situations. I would suggest you reconsider your last statement. As the noise source offered by Intel or any other silicon is a black box by its nature, not everybody is comfortable in using it, considering that the noise sources are the very fundament the entire cryptography rests on. Thus, using RDRAND or any other black box noise source per default in the kernel is just wrong. And as long as even all aspects of the design are not published, being cautious about a noise source is good. I wish that Intel would release the detailed scematics and their analysis/testing of the noise source implementation. As a hardware RNG based on flip-flops or oscillators is not really rocket science, I do not understand why this information is held back. Moreover, it would have helped if access to the raw noise source would have been given for re-verifying the characteristics of the noise source. The only acceptable way IMHO that works with all is: choice. And that choice is given to us via rngd. Ok, you may move the choice to kernel land, but still, it shall stay as a choice. Ciao Stephan -- | Cui bono? | ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] on using RDRAND [was: Entropy improvement: haveged + rngd together?]
Am Montag, 2. Dezember 2013, 23:16:28 schrieb d...@deadhat.com: Hi dj, the work that you have done to make hardware entropy sources readily available in Intel chips should be commended, and i certainly appreciate it. i will however continue to complain until it is even better, with configurable access to the raw entropy samples for those who wish to evaluate or run the TRNG in this mode. I'm currently arguing with NIST about their specifications which make it hard to provide raw entropy while being FIPS 140-2 and NIST SP800-90 Interesting: I have the same type of discussion (SP800-90B) to prepare (and even went through it -- see [1]) and I do not see it that problematic, if you have the right hooks into your noise source implementation (and I could imagine that this is a challenge with the current RDSEED/RDRAND implementation). compliant. If I had a free hand, it would not be a configuration. Configurations suck in numerous ways. It would just be there. This is not acceptable for many. When you are involved in the Intel RNG development, you may have insights. But I do not. And I trust that some three- letter agencies are able to fumble with a large US vendor's implementation of a noise source (considering that they could hide their backdoored DRBG in plain sight for quite some time). Chip design is a slow process. Standards writing is a slow process, especially when NIST is involved. When one depends on the other it is even slower. So don't hold your breath waiting for anything to happen. Feel free to lean on NIST. I notice that they haven't even published the public comments yet. The comment period for SP800-90 ended over three weeks ago. Maybe they got quite a few (including from me)? The AES and SHA-3 competitions were not like this, even though RNG's are less glitzy, they are a more fundamental security feature but they're getting less attention from NIST. I spoke with several NIST folks involved in the RNG process in September. And they are not ignorant. Therefore, I would not suggest that we imply anything here! [1] https://www.bsi.bund.de/DE/Publikationen/Studien/LinuxRNG/index_htm.html Ciao Stephan -- | Cui bono? | ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Quality of HAVEGE algorithm for entropy?
Am Freitag, 29. November 2013, 11:31:49 schrieb Joachim Strömbergson: Hi Joachim, Aloha! Stephan Mueller wrote: The problem is that dieharder Co only show the statistical quality. Based on my real-world attempts to the CPU jitter issue used as a noise source for /dev/random, the questions around the entropy of the data still remains -- see the email threat on LKML. (I feel I need to read up on the LKLM discussion). Yes, but when having access to an entropy source - what other ways besides statistical tool such as Dieharder do we have to measure the quality of the entropy? Provide a rationale why: - your observed noise source is really random - explain the uncertainty in the noise source The problem as I have understood it is that we don't have direct access to the entropy source in Bull Mountain. And that we have to trust Intel on telling us the truth, that there actually is a nice entropy source, not simply a CSPRNG with a seed known by certain organizations. The lack of openness, transparency and control of the entropy source is what is missing. You are right. But when introducing a noise source that is not commonly understood, you have to make some explainig. Or am I missing something? That is why my current patch set only uses the jitter noise source as last resort, i.e. when /dev/random is about to block. As long as the other noise sources produce entropy, my jitter noise source is not even asked. With that approach, however, /dev/random will never block any more on any system. That is actually pretty neat. What bitrate do you get from your RNG? On an Intel 2nd gen i7 I get about 15kBytes/s. On an embedded MIPS (my Internet router), I get still 1kB/s. BTW: Just downloaded your PDF and OMG it is really big. I think I have my weekend reading identified. ;-) Do not be scared. about 75% is only in numbers and graphs of the 200+ systems I tested in appendix F. The rest is pretty small. :-) BTW2: You should probably reference jytter in your paper, it would be very interesting to see the comparison between them. I will first have to make myself familiar with this one. Ciao Stephan -- | Cui bono? | ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Quality of HAVEGE algorithm for entropy?
Am Freitag, 29. November 2013, 11:22:29 schrieb Joachim Strömbergson: Hi Joachim, Aloha! Stephan Mueller wrote: I am doing a lot of research in this area these days. If you imply that main storage means RAM outside the caches, I think your statement is not entirely correct. Yes, main store is RAM. From the first rounds of testing, I think I see the following: [...] What CPU is this? From your description it sounds to me like a x86, Indeed: Intel Core i7 2nd gen. modern high performance CPU with instructions that has different cycle times and multiple levels of caches. On these types of CPUs, yes you don't need to hit main memory to get execution time variance. Good, then we are on the same page What I was trying to say is that Havege running on MCUs (AVR, AVR32, PIC, PIC32, ARM Cortex M0 etc) where instructions in general takes the same number of cycles to execute and where caches are few (few levels), have simple or even no replacement policy (it is done by SW control), the assumptions in Havege is not really present. And that this change in physical setup _should_ affect the variance measured. But again, I haven't tested it yet. My RNG should runs there as well and I see variations without all this magic in HAVEGEd. - disabling the caches completely introduces massive variations That is interesting. For a sequence of the same type of instructions? Yes, if you even just call rdtsc twice immediately after each other and print out the delta, that delta fluctuates massively. My bare metal tester produces a histogramm with 25 slots. Typically all 25 slots are filled when creating such a delta for about 10,000 rounds. == My current hunch is that the differences in the clock speeds that drive the CPU versus the clock speed driving the memory locations that you access (either for instruction or data fetches) are the key driver of variations. It's more of a clock descynchronization effect? Not sure how you exactly define that term, but I think the core issue is the non-synchronized clocks for the CPU and the RAM. I do not concur here, because even IF the VM host does some RDTSC emulation, the emulation code is subject to the fundamental jitter problem outlined above. Hence, I do not think that the jitter can be eliminated by virtualization. I would say that Intel, Wind River would have a different opinion. It is I would be very interested in such an approach -- how can you a-priori estimate which variations your code (that should remove the variations) will have? Note, any code itself will produce variations. Thus, when you remove the variations from the base system, you will introduce variations with that code. in fact one of the things you can control. You can lock the RDTSC to provide all kinds of sequences in related to the CPU or clock or otherwise. This is actually what is being used to protect against timing side channel attacks between VMs, processes. [1] http://www.chronox.de Very cool. How does [1] compare functionally to jytter? http://jytter.blogspot.se/ I have to check. Side note, on [1] you state that it is a non-physical true random number generator. I would say that it is a physical RNG. It measures physical events. But it does not measure events _outside_ the CPU. That term is coined by the German BSI I sometimes have to work with. Maybe it is not fully right. But BSI thinks a physical RNG is a pure physical implementation. If you have software attached, it is called non-physical. Ciao Stephan -- | Cui bono? | ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Quality of HAVEGE algorithm for entropy?
Am Freitag, 29. November 2013, 11:22:29 schrieb Joachim Strömbergson: Hi Joachim, Very cool. How does [1] compare functionally to jytter? http://jytter.blogspot.se/ I very briefly checked, but it seems that the author's consideration takes interrupts and the like as the basis for the entropy. In addition, he assumes that the prediction of some events cannot be done with a good resolution. However, none of these considerations apply. My RNG is: rdtsc some small code rdtsc == now you simply measure the execution time of the code. That time shows variances. And I just pick them up and magnify them. The key is that you always have these varations on all kinds of CPUs. And as mentioned before, I think the key reason is that the clock cycles of the CPU mismatch with the RAM / Cache clock cycles. Ciao Stephan -- | Cui bono? | ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Quality of HAVEGE algorithm for entropy?
Am Freitag, 29. November 2013, 11:55:41 schrieb Stephan Mueller: Hi, Am Freitag, 29. November 2013, 11:22:29 schrieb Joachim Strömbergson: Hi Joachim, Very cool. How does [1] compare functionally to jytter? http://jytter.blogspot.se/ I very briefly checked, but it seems that the author's consideration takes interrupts and the like as the basis for the entropy. In addition, he assumes that the prediction of some events cannot be done with a good resolution. However, none of these considerations apply. Sorry, I meant, none of these considerations apply to my RNG My RNG is: rdtsc some small code rdtsc == now you simply measure the execution time of the code. That time shows variances. And I just pick them up and magnify them. The key is that you always have these varations on all kinds of CPUs. And as mentioned before, I think the key reason is that the clock cycles of the CPU mismatch with the RAM / Cache clock cycles. Ciao Stephan Ciao Stephan ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Quality of HAVEGE algorithm for entropy?
Am Freitag, 29. November 2013, 16:06:07 schrieb stef: Hi stef, On Fri, Nov 29, 2013 at 11:22:29AM +0100, Joachim Strömbergson wrote: What I was trying to say is that Havege running on MCUs (AVR, AVR32, PIC, PIC32, ARM Cortex M0 etc) where instructions in general takes the same number of cycles to execute and where caches are few (few levels), have simple or even no replacement policy (it is done by SW control), the assumptions in Havege is not really present. And that this change in physical setup _should_ affect the variance measured. But again, I haven't tested it yet. howdy, i tried out the default haveged code found under: http://www.irisa.fr/caps/projects/hipsor/misc.php#measure on an arm cortex m3 stm32f2xx and streamed the results over uart and plotted them here: https://www.ctrlc.hu/~stef/stm32f2x-jitter.png prefetch, data and instruction cache where enabled. Unfortunately, such graphs are not too helpful. If you want to test something, do either or all of the following: - gather 100 or more MB of output, run ent, ent -b and dieharder -a on them - check for the basic fundamental noise source (I am not fully sure what that is for havege), and run tests on that presence Still, after doing that you only checked the statistical side of things. Yet, the entropy side is uncovered by this testing (i.e. is there really entropy present. cheers,s Ciao Stephan -- | Cui bono? | ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Quality of HAVEGE algorithm for entropy?
Am Donnerstag, 28. November 2013, 10:01:06 schrieb Joachim Strömbergson: Hi Joachim, Aloha! coderman wrote: On Tue, Nov 26, 2013 at 10:09 AM, Joachim Strömbergson joac...@strombergson.com wrote: ... I have concerns though on embedded SSL stacks that use Havege as entropy source on MCUs such as AVR32 and ARM. ... On an x86-based server you can use Havege, but use it to feed /dev/random, not as a RNG directly. The same goes for Jytter. good points! haveged should work fine on StrongArm, A8, A9, Xscale, anything with a high res timer like ARM Cycle Counter (in place of TSC). older ARM processors and x86 without high res TSC (pre-pentium?) will have trouble. Note that Havege is based on the assumption that instruction execution time varies and can be forced to vary as much as possible. On single-issue, RISC architectures with no or simple (such as SW controlled) cache memories you basically will have to hit main store in order to get a lot of variance. Then you also need a cycle timer, high res timer to be able to measure the variance. I am doing a lot of research in this area these days. If you imply that main storage means RAM outside the caches, I think your statement is not entirely correct. As a background: I have implemented a test that checks for variances in the execution time of instructions to support my RNG implementation provided in [1]. That test runs on bare metal, i.e. without any operating system (as otherwise the test results are impacted by the OS operation). To do that, I use memtest86 and replaced the existing tests with my own code. That code now executes without any OS like interruption (no scheduling, no interrupts). From the first rounds of testing, I think I see the following: - execution variations exist in any case unless the state of the CPU is flushed with serialization instructions (like CPUID) -- assuming that you also disable speedstep, power management and the like (I assume that the SMM code produces variations). - after flushing the CPU state, any code that runs inside the CPU shows no variations (even when the caches are flushed). Eg. the code of cpuid, rdtsc, rdtsc produces zero variations - after flushing the CPU state, but executing a couple of instructions which access memory (a fixed destination of memory), variations start to occur (it is something like 5 iterations of mov/movsl instructions are required -- below that threshold, no variations) == caches do kick in here which means that the variations do NOT solely depend on direct memory access, but it seems you have to hit L2 for seeing variations - disabling the caches completely introduces massive variations - flushing the CPU pipeline using MFENCE does not change any variation readings == My current hunch is that the differences in the clock speeds that drive the CPU versus the clock speed driving the memory locations that you access (either for instruction or data fetches) are the key driver of variations. But more testing is needed. Another thing to note is that RDTSC is one of the instructions that VM-systems can (and will) simulate. This means that the source for Havege entropy will be synthetic and arbitrary from physical event. I do not concur here, because even IF the VM host does some RDTSC emulation, the emulation code is subject to the fundamental jitter problem outlined above. Hence, I do not think that the jitter can be eliminated by virtualization. [1] http://www.chronox.de Ciao Stephan -- | Cui bono? | ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Quality of HAVEGE algorithm for entropy?
Am Donnerstag, 28. November 2013, 10:12:19 schrieb Joachim Strömbergson: Hi Joachim, Aloha! Stephan Mueller wrote: The only challenge that I see with Havege is that the algorithm is quite complex and that the description does not fully explain why and where the entropy comes from. Looking into the source code of oneiteration.h, the code is also not fully clear. Havege is (if I remember correctly) a magnificent example of Duff's Device: https://en.wikipedia.org/wiki/Duff's_device The code tries to force instruction cache misses at different points on the switch-loop thereby causing a lot of pipe flushes and instruction loads from lower level caches all the way to main store. A goof comparison to Havege is Jytter that basically (AFAIK) is trying to get entropy from the same source (measuring variance in instruction timing). But Havege tries to force the creation of variance and can thus generate higher rate of entropy. In my measurements I get kbps from Jytter byt Mbps from Havege. I have yet to compare the quality as measured using Dieharder, but from my memory Havege was really good. The problem is that dieharder Co only show the statistical quality. Based on my real-world attempts to the CPU jitter issue used as a noise source for /dev/random, the questions around the entropy of the data still remains -- see the email threat on LKML. Considering the grilling I get with a similar RNG that I ask to be used as a seed source for /dev/random or other crypto libs (see thread http://lkml.org/lkml/2013/10/11/582), I would have concerns on the algorithm. As long as one does not rely on one source - and _always_ feed the entropy to the RNG-CSPRNG chain (not replace the chain and connect the source directly to /dev/random output like with Bull Mountain) I have a hard time to see where much controversy would emerge. As long as the source produces ok quality entropy. Then please chime in on the LKML discussion in my support :-D One issue I'm thinking of is if you have more than one source, but one of them dwafs the other sources in kapacity. Say having a microphone providing whitish noise at kbps rate and then having RdRand from your Haswell CPU generating data at Gbps speed, will the microphone entropy matter? You are absolutely on spot. The key difference with a CPU jitter noise source vs the other noise sources in /dev/random is that the jitter is an on-demand production of entropy whereas the others are generated during the operation of the OS. That means, if you are not careful, the on-demand generation can easily outpace all other noise sources. That is why my current patch set only uses the jitter noise source as last resort, i.e. when /dev/random is about to block. As long as the other noise sources produce entropy, my jitter noise source is not even asked. With that approach, however, /dev/random will never block any more on any system. Ciao Stephan -- | Cui bono? | ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Quality of HAVEGE algorithm for entropy?
Am Donnerstag, 28. November 2013, 10:19:08 schrieb Joachim Strömbergson: Hi Joachim, Aloha! Stephan Mueller wrote: I would not concur with this statment: at runtime, you cannot verify entropy beyond simple pattern checks. Moreover, compression (i.e. whitening) is not meaningful when mixing it into /dev/random as it has its own whitening function. What I have argumented for is to have sanity checks on the sources to at least capture pathological cases. Things like stuck at zero/one. Then one could add simpler tests to detect major bias and values spanning much less than the value space. In this case, I fully concur that such tests are feasible and desireable. Ciao Stephan -- | Cui bono? | ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Entropy improvement: haveged + rngd together?
Am Donnerstag, 28. November 2013, 15:36:59 schrieb Fabio Pietrosanti: Hi Fabio, Greetings, following the answer on thread on the HAVEGE algorithm as an additional entropy source, at GlobaLeaks Project we are evaluating whenever not to add also rngd that's said to be able to use other hardware entropy source chipset ( Intel/AMD/VIA), available on the motherboard (Target OS: Linux) I'd like to ask a couple of questions: - Will haveged and rngd works well together in additionally feeding the entropy pool, or they will conflict somehow? They will not conflict as they use an IOCTL on /dev/random for injecting data. The code behind the IOCTL is able to handle even concurrent injections. So, multiple gatherers are ok. Though, bear in mind that you may not want inject entropy from one noise source via multiple paths. E.g. the Intel RDRAND instruction IS picked up by /dev/random and should therefore not used by rngd. - Isn't Linux Kernel already using the internal cryptographic chip on it's own, if available? Hardly. Intel RDRAND is currently the only chip used in /dev/random. Even though, the use is very limited (the output of /dev/random is XORed with an equally sized string from RDRAND). Any other hardware RNGs have drivers -- drivers/char/hw_random/* -- but they export their interface only to user space via /dev/hw_random. This interface is automatically sourced by rngd and injected into /dev/random. So, you see that these hardware RNGs can only be used via user space, even though kernel drivers make them available. The GlobaLeaks target is to avoid requiring any additional hardware to maintain the deployment process simple and the technical requirements cheap, so we're not focusing on external entropy source. That entropy improvement is going to be used for the already existing PGP operations done on files. Ciao Stephan -- | Cui bono? | ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Quality of HAVEGE algorithm for entropy?
Am Dienstag, 26. November 2013, 14:33:54 schrieb coderman: Hi coderman, On Tue, Nov 26, 2013 at 10:09 AM, Joachim Strömbergson joac...@strombergson.com wrote: ... I have concerns though on embedded SSL stacks that use Havege as entropy source on MCUs such as AVR32 and ARM. ... On an x86-based server you can use Havege, but use it to feed /dev/random, not as a RNG directly. The same goes for Jytter. good points! haveged should work fine on StrongArm, A8, A9, Xscale, anything with a high res timer like ARM Cycle Counter (in place of TSC). older ARM processors and x86 without high res TSC (pre-pentium?) will have trouble. The way haveged is implemented, not really. The reason is that it uses clock_gettime, which uses the Linux kernel clocksource framework. That framework has drivers for a number of different timers on various architectures. and as mentioned, all entropy sources should feed into host entropy pool via an entropy daemon that verifies entropy, mixes / compresses it, and then feed into host pool. I would not concur with this statment: at runtime, you cannot verify entropy beyond simple pattern checks. Moreover, compression (i.e. whitening) is not meaningful when mixing it into /dev/random as it has its own whitening function. The key however is that the entropy estimation that you use to inject the data with the appropriate IOCTL into /dev/random must be conservative. This way, there is no need to have full entropy on the data stream to be added to the entropy pool. Ciao Stephan -- | Cui bono? | ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Quality of HAVEGE algorithm for entropy?
Am Mittwoch, 27. November 2013, 12:00:50 schrieb coderman: Hi coderman, On Wed, Nov 27, 2013 at 3:10 AM, Stephan Mueller smuel...@chronox.de wrote: ... The way haveged is implemented, not really. The reason is that it uses clock_gettime, which uses the Linux kernel clocksource framework. That framework has drivers for a number of different timers on various architectures. do you know if the list of supported clock sources is documented somewhere? Yes, it is documented. Check the contents of /sys/devices/system/clocksource/clocksource0/current_clocksource and /sys/devices/system/clocksource/clocksource0/available_clocksource. Note, current_clocksource is also writable where you can switch the used clocksource. ... you cannot verify entropy beyond simple pattern checks. Moreover, compression (i.e. whitening) is not meaningful when mixing it into /dev/random as it has its own whitening function. simple checks (sanity checks) are useful. I fully agree to have simple sanity checks. Though I would not call them checks for entropy. Ciao Stephan -- | Cui bono? | ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
