Re: [Cryptography] randomness +- entropy

[D. J. Bernstein]

Theodore Ts'o writes, on the moderated crypto...@metzdowd.com list:
> What I am more woried about is ARM and MIPS platforms, where we don't
> have the high-resolution CPU cycle counter (I *am* working on pushing
> on ARM CPU vendors such as Samsung and Qualcomm to try to get this
> addressed for future products).

For several years now the standard ARM architecture (ARMv7-A) has
already supported a cycle counter ("PMCCNTR"):

unsigned int cc;
asm volatile("mrc p15, 0, %0, c9, c13, 0" : "=r"(cc));

Problem #1 is that this cycle counter is idle by default. Fortunately,
turning it on is easy:

asm volatile("mcr p15, 0, %0, c9, c12, 0" :: "r"(17));
asm volatile("mcr p15, 0, %0, c9, c12, 1" :: "r"(0x8000000f));
asm volatile("mcr p15, 0, %0, c9, c12, 3" :: "r"(0x8000000f));

Problem #2, more basic, is that the cycle counter is privileged by
default. One answer---the only reasonable answer on machines used for
serious benchmarking and performance optimization---is for the kernel to
make the instruction unprivileged:

asm volatile("mcr p15, 0, %0, c9, c14, 0" :: "r"(1));

But this isn't necessary when the kernel itself is reading the cycle
counter, and it creates the threat of unprivileged code setting the
cycle counter back to idle. There are other performance monitors, but
there seems to be only one PMUSERENR bit that controls access to all of
them. The x86/amd64 situation is much more reasonable: there's a cycle
counter that everyone can use by default and that is never idle (outside
suspend mode, where it doesn't matter).

Problem #3, even more basic, is that the kernel developers are obviously
unaware that this cycle counter exists. Unfortunately, this problem
isn't something that can be addressed through software, but maybe email
will do the trick.

Of course, one can also ask whether this is actually a useful source of
entropy. That's the topic of the following paper:

http://cseweb.ucsd.edu/~hovav/dist/earlyentropy.pdf

I should also mention another entropy-gathering technique that's harder
to implement portably but that works even on tiny single-clock devices:

http://eprint.iacr.org/2013/304
http://puffin.eu.org/WS/Van_Herrewege.pdf
http://dl.acm.org/citation.cfm?id=2512493&dl=ACM&coll=DL&CFID=261620465&CFTOKEN=10403779

---Dan

[Theodore Ts'o]

On Thu, Nov 14, 2013 at 11:16:37PM -0000, D. J. Bernstein wrote:
> Problem #3, even more basic, is that the kernel developers are obviously
> unaware that this cycle counter exists. Unfortunately, this problem
> isn't something that can be addressed through software, but maybe email
> will do the trick.

The term "the kernel developers" is general, and thus not very useful,
term. There are probably ARM specialists who know about this term,
but they might not be aware of the need to enable its use as far as
the RNG's quality is concerned. We had a similar issue with one
architecture (IIRC, MIPS) where the cycle counter was disabled because
there were CPU bugs that could cause serious problems if you lost a
race, and I only discovered this when I started asking questions.

I certianly wasn't aware of PMCCNTR (not being an ARM expert myself).
So thank you. I'll have to start asking some questions. It may turn
out there are good reasons why they've disabled it, either because of
power utilization, of CPU bugs, or maybe just it wasn't reliably
included on all ARM processors. But I can certainly find out.

Cheers,

- Ted