Posted by BruceEel 6 hours ago
Do we now learn that they fixed "always generate all 1s" with "never generate all 0s"??
EDIT: I've been unable to reproduce the problem on my CPU, FWIW. It's a Ryzen 5 3600.
EDIT2: OK, update, I can reproduce it with rdrand16, rdrand32 is fine but rdrand16 can never generate all 0s. So my CPU does have this problem!
But it looks like the rdrand16 instruction can produce zeros just fine, it just sets CF=0 erroneously (indicating an error and that the user program should retry).
So keep that in mind when you try to reproduce it too and use some abstraction that could implement retries internally.
Here are some stats:
Rounds (N): 1000000000
Failed (F): 15312
Valid (V): 999984688
N/65536: 15258.789
V/65536: 15258.555
Failed, result was zero: 15312
Failed, result non-zero: 0
Bucket value for 0: 15312
Bucket value for 1: 15290
Bucket value for 65535: 15223
Min bucket value: 14670
Max bucket value: 15835
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
const size_t N = 1000000000; // 1e9
struct rdrand16_result {
uint16_t n;
bool ok;
};
static inline struct rdrand16_result rdrand16()
{
struct rdrand16_result result;
__asm__ __volatile__( "rdrand %0" : "=r" (result.n), "=@ccc" (result.ok) );
return result;
}
int main()
{
size_t buckets[0xFFFF + 1] = { 0 };
size_t notok = 0, notok_zero = 0, notok_nonz = 0;
for (size_t i = 0; i < N; ++i) {
struct rdrand16_result result = rdrand16();
++buckets[result.n];
if (! result.ok) {
++notok;
notok_zero += result.n == 0;
notok_nonz += result.n != 0;
}
}
size_t max = 0, min = N;
for (size_t i = 0; i <= 0xFFFF; ++i) {
size_t n = buckets[i];
min = n < min ? n : min;
max = n > max ? n : max;
}
printf("Rounds (N): %zu\n", N);
printf("Failed (F): %zu\n", notok);
printf("Valid (V): %zu\n", N - notok);
printf("N/65536: %.3f\n", (double)N / 65536);
printf("V/65536: %.3f\n", (double)(N - notok) / 65536);
printf("Failed, result was zero: %zu\n", notok_zero);
printf("Failed, result non-zero: %zu\n", notok_nonz);
printf("Bucket value for 0: %zu\n", buckets[0]);
printf("Bucket value for 1: %zu\n", buckets[1]);
printf("Bucket value for 65535: %zu\n", buckets[0xFFFF]);
printf("Min bucket value: %zu\n", min);
printf("Max bucket value: %zu\n", max);
return 0;
} return 4 # Determined by fair dice roll.Most of the console hacking talks are great, both informative and entertaining.
That presentation is awesome though, worth a watch either way!
$ ./a.out | rg '\b\-?\d\b' | sort -n | uniq -c
15281 -2
15192 -1
15273 0
15243 1
15269 2
#include <immintrin.h>
short rdrand16() { // gcc -mrdrnd
short ret;
while (1 != _rdrand16_step(&ret)) { }
return ret;
}I.e., we had `random.trust_cpu=off nordrand` in `GRUB_CMDLINE_LINUX`.
I thought the kernel would not replace anything just because it adds a potentially bad source.
E.g. if you have rand source A, and xor it with rand source B, then you get, at worst, the best of A and B,
Basically I'm wondering if it's a bug in the version of the instruction that writes to a 16-bit reg, or a bug in the underlying RNG
*: missed a word the first time around
To prove it, we'd need to examine the chip and its microcode.
It takes entropy from multiple different sources, makes it all input to the XOF, then the XOF uses cryptography to output a stream that has as much entropy as the combined entropy of all of its sources of randomness. So if an XOF, for example, takes 100 runs of rdrand16, along with the system time in microseconds and the number of milliseconds between receiving 100 packets over the network, the XOF will output a completely random stream without artifacts like never returning 0x0000, even if rdrand16 never outputs 0x0000.
I fail to see why one should either rely on a single random source nor roll their own.
getrandom() is often times suggested, but alas isn’t a standardized function, i.e. it’s not part of the POSIX specification. Considering how the C23 changes to the C specification caused a lot of perfectly good C code to no longer compile, I’m very anal about sticking to specs; I use '-std=C99' for my code these days (even though it can compile as C23 code) and stick to POSIX functions (except chroot() and setgroups(), but both of those predate POSIX, and even here I have a compile-time option to compile my code without those non-POSIX syscalls).
The code using a secure XOF (the algorithm was developed by the same team which later on made SHA-3, and includes people who helped make AES) has been around for nearly two decades (the code where I roll my own RNG to make secure random numbers has been around for over 25 years, but used AES before XOFs existed) and not one security problem has found with the RNG code has ever been found. [1] “Don’t roll your own RNG” is a suggestion, but it is possible to do so securely if one knows what they are doing (i.e. they have read Applied Cryptography and keep current with cryptographic developments).
For anything vibe coded (my code is 100% human written, for the record), rolling one’s own RNG is a really bad idea.
[1] There was a theoretical issue with cache timing attacks over two decades ago, so I put mitigations in place, and then chose to use an XOF for newer code.
[2] There was an issue where a separate implementation I made of this XOF would generate incorrect test vectors in clang, but only at some optimization levels. I now test the XOF in both GCC and clang at multiple optimization levels to make sure it acts correctly.
so instead you suggest trusting your own untested unlooked at implementation more?
>untested
The automated tests includes tests that make sure the XOF is correctly implemented. [1]
>unlooked at
People have been looking at my code for security holes for well over 20 years, and I have been getting multiple AI assisted security reports over the last year, things like “there’s a buffer overflow in this code which is nay to impossible to exploit, using code which hasn’t even been able to compile since 2022”.
[1] https://github.com/samboy/MaraDNS/tree/master/deadwood-githu... and https://github.com/samboy/MaraDNS/tree/master/deadwood-githu...
You’re correct about black and white thinking. Then you invoke multiple straw men in this thread to defend that you’ll roll your own.
Disclaimer: I’ve been hired for multiple DoD projects to break hardware and software security systems, and I nearly always succeed, because so many people (and companies) roll their own.
One reason why I don’t change the RNGs used in my code is because I know how dangerous playing with RNG code is. For example, one implemention I wrote of the XOF—not one I used in production code, mind you—generated incorrect vectors, but only in clang and only at some levels of optimization. Needless to say, I now have a test to make sure my XOF code generates correct vectors with both GCC and clang at multiple different optimization levels.
People have brought up CVE-2008-0166 in this thread, but the Coldcard incident from this year (where people literally lost millions of dollars) also comes to mind, so I’m aware how dangerous playing with RNG code is.
That’s why the code is basically the same code I had 18 years ago, and why I (as well as multiple people running AI-assisted security audits) have extensively tested that code.
The proof is in the pudding: No security issues have ever been found with the XOF PRNG, and it’s been nearly two decades.
(I also think “straw men” is being used incorrectly here; most likely the parent poster thinks I was implying that Linux’s /dev/urandom is insecure but the actual argument is that my code runs on a lot more than just Linux, and some of those systems could have an insecure /dev/urandom)
[1] As per https://blog.cr.yp.to/20140205-entropy.html as long as we’re not using a malicious source of entropy, but said malicious source will need to perform 2^n operations of the XOF to generate n bits of controlled output, and only in the case if said malicious entropy source can somehow know the output of the other entropy sources, especially since the XOF is seeded once then run indefinitely in my code.
https://maradns.blogspot.com/2010/07/radiogatun32-passes-all...
The POSIX standard function is getentropy(), which internally calls getrandom() on Linux.
> what if there’s a bug in the kernel which causes /dev/(u)ramdom to be less than secure?
It's often the other way around: the Linux kernel contains thousands of workarounds for buggy hardware, while the buggy hardware itself doesn't always get patched. Linux developers take this stuff very seriously. As a result it's often safer to rely on kernel APIs than to access the hardware directly.
The kernel code involving random number generation receives an exceptionally high amount of scrutiny because of its security implications, so I'd trust it to do the right thing over a naked call to RDRAND which nobody knows how exactly it's implemented in proprietary hardware or a handrolled solution to mix the RDRAND output with other entropy sources.
Remember the Debian openssl disaster from 2008? That happened exactly because someone had handrolled their entropy mixing solution, then someone else broke it.
“The intended use of this function is to create a seed for other pseudo-random number generators”
So, if I were to use genentropy() in a POSIX-compliant way, I would need to do what I already do: Use my own pseudo-random number generator.
The Debian openssl disaster (CVE 2008-0166, I remember it well) was caused because someone incorrectly patched secure code: Since the code used uninitialized memory as one of many entropy sources, which causes Valgrind to complain, they patched the code to not use uninitialized memory for entropy, but then accidentally disabled all other sources of entropy (except the 16-bit PID). It was caused because the person making the patch didn’t fully understand why it was a good idea to, in that context, use code which Valgrind complained about. [1]
As an aside, here’s how I deal with those Valgrind errors:
#ifdef VALGRIND_NOERRORS
/* Valgrind reports our intentional use of values of uncleared
* allocated memory as one source of entropy as an error, so we
* allow it to be disabled for Valgrind testing */
memset(noise,0,512);
#endif /* VALGRIND_NOERRORS */
[1] Debian has a lot of inflexible policies like this which can cause problems. Another issue Debian has is they have a policy a given piece of code must always compile to the same binary on a given architecture. That isn’t true with the unpatched version of my code, because the hash compression routine uses a 32-bit random number generated at compile time to avoid hash collision attacks (it also uses another 32-bit random number at runtime, and I make sure the hash compression values are never visible). So the Debian version of my code was forced to be patched to be less secure.
But it gets worse. If the optimizer sees that you're loading uninitialized memory, it can reason that since the result of uninitialized memory is garbage, doing any computation on that result is also garbage, and happily delete said computation as a result. The cascading effect of this is to delete all of the entropy-mixing code, leaving your entropy pool with only the very low entropy source--giving uninitialized memory effectively negative entropy.
The net effect is that, at least for me, seeing someone trying to seed an entropy pool with uninitialized memory is a giant neon flashing sign saying "do not trust this code." It provides at best very little entropy and at worst actively destroys entropy and has other calamitous effects like valgrind or sanitizer errors, so you need to have other entropy sources anyways, so why bother?
Matt Mackall: "It's worth noting that the maintainer of record (me) for the Linux RNG quit the project about two years ago precisely because Linus decided to include a patch from Intel to allow their unauditable RdRand to bypass the entropy pool over my strenuous objections. "
https://cryptome.wikileaks.org/2013/07/intel-bed-nsa.htm?utm...
The only legitimate reason to roll your own is when you're developing for an embedded system or a bootloader or something like that where there is no kernel API available.
hash = sha256(current_time());
for i := 0; i < n; i++ {
hash = sha256(hash.append(current_time()))
}
The reason I like doing it this way is that it happens entirely in userspace, it's genuinely a secure method of generating entropy, and it has no dependencies on potentially buggy firmware or microcode outside of the time() call, which is both fairly narrow, fairly heavily used (meaning a bug is likely to be discovered during testing, as the implementation is likely heavily scrutinized), and also fairly easy to test independently - 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. The above suggestions are assuming about 2.5 bits of variance between calls, meaning there should be a range of at least 20 nanoseconds between your slowest and fastest hash call. This has been true on every CPU I've ever measured, including microcontrollers.
The nice thing about using multiple entropy sources with a secure XOF is that the resulting entropy is at least as strong as the most secure entropy source given to the XOF.
https://blog.cr.yp.to/20140205-entropy.html
TL;DR adding a compromised source of entropy to a pool of already secure sources of entropy can catastrophically compromise the final result.
It's better to source entropy from a smaller number of harder-to-compromise sources. That's why I like the iterated hashes method; the security surface area is both very small and highly likely to be well tested.
From that page:
>>>what I'm advocating here, for security reasons, is a sharp transition between
* before crypto: the whole system collecting enough entropy;
* after: the system using purely deterministic cryptography, never adding any more entropy.<<<
Which is exactly how a XOF should be used, and how I used the XOF in my code. A malicious source of entropy will need to perform 2^n operations to control n bits of the XOF’s output, and that’s assuming the malicious entropy source somehow perfectly knows the other entropy the XOF is using.
The point here is to eliminate surface area for mistakes, and an XOF has a much larger and more complex implementation than iterated hashing against a timer.
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();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).
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.
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.
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.
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.
The value of the iterated hashing method is that it is dead simple and has little dependency on potentially buggy upstream code; it works even in very lightweight environments designed by engineers with no experience in security.
https://blog.cr.yp.to/20140205-entropy.html
Intel could much more easily compromise and attack systems than make an implementation of RdRand which is malicious in this manner.
It’s like the attacks I occasionally see which are like “once we have administrator, we can attack the process because of this insecurity”. Well, yeah, but once we have administrator, we can read the entire memory of the “vulnerable” process and completely control its output too.
I’ve seen in the real world attacks where things were insecure because the PRNG wasn’t given enough entropy (CVE 2008-0166, Coldcard, etc.). I’ve never seen real world attacks where a PRNG was insecure from getting too much entropy.
#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);
}
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
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).
EDIT: I reviewed his code, and he's not hashing between calls to check the clock; the hash call itself causes the CPU to heat up in arbitrary ways which changes the timing between hashes and introduces more entropy; removing that call basically entirely defeats the idea behind the technique, these results are fully invalid.
You are not hashing between calls to the timer. The sha256 hash itself is responsible for doing physical things to the chip (heating up some parts unevenly during the hashing computation) which introduces meaningful entropy between calls to the current time.
You can't just do calls to clock_gettime(), you have do an actual sequential sha256() call between them. Please run this code again and tell me what results you get.
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)
EDIT: I reviewed his code, and he's not hashing between calls to check the clock; the hash call itself causes the CPU to heat up in arbitrary ways which changes the timing between hashes and introduces more entropy; removing that call basically entirely defeats the idea behind the technique, these results are fully invalid.
Oh, I guess you have to ensure the inputs aren’t correlated, or they’ll cancel out?
The sources of entropy can be correlated and won’t cancel out with a well designed secure XOF. SHAKE-256 is an example of a secure XOF.
[edit to add]: Also, the bulletin is solely about RDSEED zeros, whereas the OP is also reporting RDRAND zeroes.
https://github.com/systemd/systemd/pull/12536/commits/1c53d4...
I found the thread about it,
https://news.ycombinator.com/item?id=19848953
Yikes at this: "I am so glad I resisted pressure from engineers working at Intel to let /dev/random in Linux rely blindly on the output of the RDRAND instructure." -Theodore Ts'o (2013)
" I am so glad I resisted pressure from Intel engineers to let /dev/random rely only on the RDRAND instruction. To quote from the article below:
"By this year, the Sigint Enabling Project had found ways inside some of the encryption chips that scramble information for businesses and governments, either by working with chipmakers to insert back doors...."
Relying solely on the hardware random number generator which is using an implementation sealed inside a chip which is impossible to audit is a BAD idea. "
https://web.archive.org/web/20180611180213/https://plus.goog...
Putting a backdoor into CSPRNG is a favored way to break crypto, for example Dual_EC_DRBG.
"
Weaknesses in the cryptographic security of the algorithm were known and publicly criticised well before the algorithm became part of a formal standard endorsed by the ANSI, ISO, and formerly by the National Institute of Standards and Technology (NIST). One of the weaknesses publicly identified was the potential of the algorithm to harbour a cryptographic backdoor advantageous to those who know about it—the United States government's National Security Agency (NSA)—and no one else. In 2013, The New York Times reported that documents in their possession but never released to the public "appear to confirm" that the backdoor was real, and had been deliberately inserted by the NSA as part of its Bullrun decryption program. In December 2013, a Reuters news article alleged that in 2004, before NIST standardized Dual_EC_DRBG, NSA paid RSA Security $10 million in a secret deal to use Dual_EC_DRBG as the default in the RSA BSAFE cryptography library, which resulted in RSA Security becoming the most important distributor of the insecure algorithm. RSA responded that they "categorically deny" that they had ever knowingly colluded with the NSA to adopt an algorithm that was known to be flawed, but also stated, "We have never kept this relationship [with the NSA] a secret and in fact have openly publicized it."
"
Anyone from the High-Performance Computing Center Stuttgart willing to play on the 720,320 Zen2 cores?
In theory an encryption algorithm could be biased or not totally uniform in its output, but I think no one has come up with a statistical distinguisher between AES-CTR and pure random values so it should be as good as random.
Obviously you'll want to append the secret part to a keyused.txt file every few hours as once an rng has been running for a few months it's tedious to wait for it to catch up, this way you only have to wait a few hours after any sort of power loss etc.
Brooks talks about this in _Mythical_Man-Month_... if you really could "just implement the specification", then the specification itself would be complete enough to serve as your code. There will always be bugs in both.
Looks like they tried 16-bit numbers. Does the odd behavior happen also on 32 and 64 (might take a long time to check - I'd start scratching my head after a couple hundred years of no zeroes) ones? Is the zero masking as some other fixed number, increasing its output count? Is RDRAND implemented as multiple reads of an internal state so that a larger random number takes longer?