Remix.run Logo
sltkr an hour ago

This comment demonstrates everything that's wrong with people trying to be clever and rolling their own crypto.

The security of your system depends on time() providing enough entropy, even though that's not what it's designed to do. It's built on top of the wrong primitive from the start.

> The reason I like doing it this way is that it happens entirely in userspace

On Linux this is often true, but there is no portable way to get the current time that is _guaranteed_ not to do any system calls.

> If your time() function has a resolution of nanoseconds, you only need your loop to iterate about 50 times to get a cryptographically secure amount of entropy.

You haven't proven that at all. It's easy to imagine that on a CPU running at a fixed frequency the interval between reads is constant, so if anyone knows (or can guess) the start time the resulting seed is entirely predictable.

This is completely independent of timer resolution. You seem to realize that as you were writing that:

> just look at the number of nanoseconds that elapse at each consecutive call to sha256(current_time()) and verify that there's some statistical variance

Oh yes, because evaluating the quality of a random number generator is such a trivial thing to do, it's not like there is decades of research behind it or anything.

And assuming you are able to verify the statistical variance: are you going to put that logic in the loop, making it significantly more complex?

Or are you going to do this test on your machine and then ship your code on the assumption that if it works on your machine, it will work everywhere else, too?

> if your time() function has a resolution of seconds you need to let it run for more like 5 seconds.

So not only is it insecure, it's agonizingly slow by design. Why do a system call that takes milliseconds at best, when we can run a loop in userspace for 5 seconds?

All this just so you can avoid writing the obviously correct oneliner:

    if (getentropy(&seed, sizeof(seed)) != 0) abort();
Taek 10 minutes ago | parent | next [-]

The reason I roll entropy in userspace is because there's a very long history of "cryptographic" libraries getting it wrong (see the parent article for an example). Crypto tokens stolen because the underlying call to the web browser entropy only had 32 bits of actual randomness. Crypto tokens stolen because the underlying embedded system (like cold card) turned off some security critical features to improve performance and power.

Pretty much the only thing you can control when shipping software to many devices is that it runs on a physical CPU and has a timer. Every other RNG assumption over the decades has shown that sometimes someone upstream gets something catastrophically incorrect.

alerighi an hour ago | parent | prev | next [-]

Depends in what trust do you have over your hardware/OS. If you assume the hardware is potentially backdoored, and the OS is proprietary, or even if open could have malware/rootkits that can thinker around the random number generator, the solution of using a sole implementation inside the program (assuming the sha256 function is inside the program itself) maybe better.

Sure an infected system may as well fake time values, but that is much more difficult and it's possible to detect from a userspace program. For example you mention to use getentroy, but on a compromised system you know how easy it is to change something that is implemented in a system library (e.g. libc) or even if you read /dev/random directly without passing from the libc how easy it's to make it read whatever you want?

To me that is not that bad implementation, in fact it's an implementation that is used in a lot of security software (including GPG, not as the sole source of course but as one of many).

sltkr 12 minutes ago | parent [-]

If you cannot trust the platform you're running on, all bets are off. There is a reason so much effort is put in TPM and remote attestation and so on.

A compromised kernel doesn't even have to fake any data. It can just read the generated seed directly from user space without the program ever knowing about it.

> Sure an infected system may as well fake time values, but that is much more difficult

clock_gettime() just reads a value that the kernel has set, so that's not particularly difficult to fake.

If you're thinking of using RDTSC instructions directly, that's of course not portable, and at that point you might as well call RDRAND directly, which is at least designed to provide random data.

> it's possible to detect from a userspace program.

There is no detection that is guaranteed to work on a compromised system.

And whatever detection you have in mind to make the algorithm resistant to tampering was _not_ part of the original for-loop. You cannot claim the for-loop is superior to just calling getentropy() because it "can detect" clock tampering, while handwaving away the actual code to detect this clock tampering.

> it's an implementation that is used in a lot of security software (including GPG, not as the sole source of course but as one of many).

It's fine if you use it as a strictly additional source of entropy, but then the whole argument that it is superior because it avoids syscalls goes out of the window, because you're doing strictly _more_ work.

Taek 4 minutes ago | parent [-]

The strength in this method is that it has the littlest possible surface area for upstream bugs to compromise your final entropy. Because, in the applied world, upstream bugs in "secure" system RNGs have been the cause of stolen crypto and other critical security compromises on numerous occasions.

And, I agree that if the system is compromised to the level that the attacker can control the output of the timer, it's probably compromised to the level that the attacker can just read your generated entropy straight from memory.

The point here is not to be fast, it's to be protected against implementation bugs on systems that weren't designed by security professionals.

api 12 minutes ago | parent | prev | next [-]

Any good crypto library will have a solid secure random source that usually combines entropy from multiple sources with a provably secure hash based mixing scheme.

Hardware RNGs can be one source, but no single source is trusted, and they're all combined in a way where even an intentionally malicious source is lost in noise and cannot actually determine output.

sltkr 43 minutes ago | parent | prev [-]

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 14 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 33 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.

Taek a few seconds 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.