[cryptography] Quality of HAVEGE algorithm for entropy?
smueller at chronox.de
Thu Nov 28 04:21:50 EST 2013
Am Donnerstag, 28. November 2013, 10:01:06 schrieb Joachim Strömbergson:
> coderman wrote:
> > On Tue, Nov 26, 2013 at 10:09 AM, Joachim Strömbergson
> > <Joachim at 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
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 . 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
==> 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
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
| Cui bono? |
More information about the cryptography