[cryptography] Quality of HAVEGE algorithm for entropy?

Stephan Mueller smueller at chronox.de
Thu Nov 28 04:21:50 EST 2013


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
> > 
> > <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 
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? |


More information about the cryptography mailing list