| ▲ | sltkr an hour ago |
| And to show my objections are not just theoretical I wrote a little program to check: #include <time.h>
#include <stdio.h>
static int estimate_entropy(long l) {
int bits = 1; /* for the sign bit */
if (l < 0) l = -l;
while (l > 0) {
++bits;
l >>= 1;
}
return bits;
}
int main() {
struct timespec ts;
if (clock_getres(CLOCK_REALTIME, &ts) != 0) {
perror("clock_getres");
return 1;
}
printf("Clock resolution: %ld.%09ld\n", (long) ts.tv_sec, (long) ts.tv_nsec);
#define N 50 /* number of samples */
struct timespec samples[N];
for (int i = 0; i < N; ++i) {
clock_gettime(CLOCK_REALTIME, &samples[i]);
}
printf("Deltas (ns):");
long deltas[N - 1];
for (int i = 0; i < N - 1; ++i) {
deltas[i] =
(samples[i + 1].tv_sec - samples[i].tv_sec)*1000000000L
+ (samples[i + 1].tv_nsec - samples[i].tv_nsec);
printf(" %4ld", deltas[i]);
}
printf("\n");
long entropy = 0;
printf("Deltas of deltas: ");
for (int i = 0; i < N - 2; ++i) {
long dd = deltas[i + 1] - deltas[i];
printf(" %4ld", dd);
entropy += estimate_entropy(dd);
}
printf("\n");
printf("Maximum entropy: %lld\n", entropy);
}
On my system this prints: Clock resolution: 0.000000001
Deltas (ns): 55 51 23 23 25 24 24 24 24 24 25 25 24 24 24 24 24 25 24 24 24 25 25 24 24 23 25 24 24 25 24 23 25 25 26 23 25 24 24 25 26 24 23 25 25 26 24 25 24
Deltas of deltas: -4 -28 0 2 -1 0 0 0 0 1 0 -1 0 0 0 0 1 -1 0 0 1 0 -1 0 -1 2 -1 0 1 -1 -1 2 0 1 -3 2 -1 0 1 1 -2 -1 2 0 1 -2 1 -1
Maximum entropy: 92
So no, 50 iterations of that loop does not provide 256 bits of entropy due to random fluctuations in nanontime between calls. |
|
| ▲ | Taek 16 minutes ago | parent | next [-] |
| You don't need 256 bits of entropy, you only need 128. I have tested this method on over 100 different CPUs and I have never seen such consistent output. I'm genuinely surprised to see that you only hit 92 bits of entropy, but that can trivially be fixed by doing 10x the iterations. 500 iterations is still going to put you under a millisecond of cost. And, for what it's worth, code I've actually shipped has combined the above technique with Fortuna, and has typically targeted 2000 bits of entropy rather than 128 (for security buffer). |
|
| ▲ | strenholme 34 minutes ago | parent | prev [-] |
| Thanks for writing that code! The point is this: Getting micro-timing won’t give us as much entropy as we want, but it will still give us entropy. So it’s a perfectly good yet-another-source of entropy to feed in to an entropy pool (such as the input to a XOF). If those Coldcard devices had used this code as one source of entropy, and this source of entropy was the only entropy still working, they never would had been compromised. (I won’t update my 18-year-old PRNG to use this code, of course, since that code is now 18 years old and there are no known weaknesses in said code) |
| |
| ▲ | Taek 2 minutes ago | parent [-] | | Actually, it gives you as much entropy as you need, just increase the iterations. That guy's output is shockingly consistent, so to be conservative maybe we say 0.2 bits of entropy per iteration. So just do 1000 iterations. That's still only going to take a few milliseconds even on embedded hardware. |
|