Comment by strenholme

5 days ago

From https://pubs.opengroup.org/onlinepubs/9799919799/functions/g...

“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 */

I do believe the Linux Kernel does have secure RNG code, but I also write code which has run on a lot of different systems and environments, including embedded ones, and some of them might not have a secure /dev/urandom.

[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.

12 comments

strenholme

jcranmer 5 days ago

Uninitialized memory should never be used as source of entropy. Most release software these days compiles using hardening flags, which will (at some levels) replace uninitialized memory with sentinel values, making the entropy of uninitialized memory frequently around 0.

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?

mitxela 4 days ago

The code didn't rely on uninitialized memory as an entropy source. The patch was incorrect and cleared the buffer in two places: one with uninitialised memory, and one where it had been filled with seed entropy.
The code you're responsible for is the code that runs on the CPU. Compilers in the day could not optimize this away.
strenholme 5 days ago
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
This is an interesting assertion, and one that is easy enough to prove true.
Let’s take the following C code, which uses the same XOF algorithm (but not implementation) as my application (Deadwood):
#include<stdio.h> #include<stdint.h> #include<stdlib.h> #define b(z) for(c=0;c<z;c++) uint32_t c,e[42],f[42],g=19,h =13,n[45],i,j,k;void m(){j=0; b(12)f[c+c%3*h]^=e[c+1];b(g){ i=c*7%g;k=e[i++];k^=e[i%g]|~e [(i+1)%g];j=j+c;n[c]=n[c+g]=k >>j%32|k<<-j%32;}for(i=39;i-- ;f[i+1]=f[i])e[i]=n[i]^n[i+1] ^n[i+4];b(3)e[c+h]^=f[c*h]=f[ c*h+h];*e^=1;}int main(int c, char**v){char*q=malloc(2);if( q==0)return 0;q[0]&=31;q[0]|= 1;q[1]=0;for(;;m()){b(3){for( j=0;j<4;){f[c*h]^=k=(*q?255& *q:1)<<8*j++;e[c+16]^=k;if(! *q++){b(18)m();b(8){j=c;b(1) printf("%02x",(e[1+j%2]>>8*c) &255);c=j;if(c%2)m();}puts( "");return 0;}}}}}
This code, as I’m sure the parent poster can clearly see, uses four bits of uninitialized allocated memory as its source of entropy. As per the parent’s assertion, there should therefore exist a compiler whose optimizer will cause this XOF to not correctly run.
The above code can have one of the following possible 16 outputs:
0a5d51f3745c7266 f84b051f67115f1a f87105c4ecfefe67 92074ac8e1e7a42e 1441ac245f288e18 87023372e57ae001 047a3ddd14209546 340b2ff47c61172e bfb9289ed096f977 dfd56a7a8d7d723e 2151460954a80242 6822335c6e0160dc 3783ce3cae3d0774 4e0156df46c00bac 69795d939d211e7a
If the above code has any but one of the above 16 outputs, this is a real world case where a C compiler, seeing uninitialized memory being used, optimizes out the code which uses said uninitialized memory as an input, and therefore will not output one of the above 16 possible words.
I’ve tested the above code in GCC -O3 and clang -O3; both generate one of the above 16 possible outputs (each one generating a different output).
If there really is a compiler out there which does “happily delete said computation”, which would give a different output than one of the 16 outputs above, please name that compiler, the version of said compiler used, and all compile-time flags used with said compiler.
While I’ve never heard of a real world case where a compiler would refuse to run code using uninitialized memory as yet another source of entropy for a secure PRNG, I do know of a real world case where a very nasty security hole was caused because someone incorrectly removed code using uninitialized memory as part of an entropy pool: CVE-2008-0166
- wat10000 4 days ago
  
  Remember that a compiler is allowed to do anything when it sees undefined behavior, which includes doing the thing you want it to do.
  Here's a little example of code disappearing due to a read of uninitialized memory:
  void test(int x) { int uninit; puts("hello"); if (uninit) puts("non-zero"); else puts("zero"); }
  clang 23.1.0 -O3 targeting ARMv8 deletes both branches of the if. Not only that, it deletes the code to return from the function. The very last instruction of the function is `bl puts`, meaning that after puts returns, it will start executing whatever function happened to come after this one in memory. That's probably a good thing in context, because that's likely to crash or infinite loop and make it clear that something went badly wrong, but the failure could easily be something more subtle that just disables some random seeding while otherwise executing normally.
  
  1 reply →
- titzer 5 days ago
  
  Parent is right. Use of uninitialized memory is UB, and incidentally, the type of UB that the C standard is not working to define, but is relying on sanitizers to find in source programs, since it is considered always a bug.
  This entire thread has a lot of "no security issues have ever been found in my code, and I test a lot. Therefore no bugs will ever exist in my code and we're all safe." To see you doing this in an explicitly security-conscious setting is distressing.
  If anything, I see assertions like this and juxtaposed with blatant, willful misunderstanding of how C and C compilers work and it does the opposite of inspiring confidence.
  Look at CVE-2009-1897; this is the classic example of how C compilers are happy to try to optimize code in the face of UB and lead to worse problems.
  > If the above code has any but one of the above 16 outputs
  I don't think you understand how insane optimizations in the face of UB can be. Just go look at this issue:
  https://github.com/llvm/llvm-project/issues/174844?utm_sourc...
  
  5 replies →

wahern 4 days ago

On modern systems, including Linux and OpenBSD, getentropy will return entropy seeded from not just rdrand/rdseed, but other entropy sources on the system, e.g. many Intel NICs, the AMD PSP, etc, and at least on Linux some well-vetted jitter hacks as a backstop for embedded devices without hardware RNGs. These sources are unavailable to user space. You have nothing to lose and everything to gain by using getentropy as one source, among whatever else you're using, to seed your PRNG.