Comment by 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
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:
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.
I concede the C99 specification (which I now have a copy of), on page 490 (502 of the PDF) states “The behavior is undefined in the following circumstances:” this is followed by a long list, and on page 501 (page 513 of the PDF) it says, one case where behavior is undefined is when “The value of the object allocated by the malloc function is used”
It’s not clear whether that is the memory location malloc() returns or the memory pointed to by malloc(), but based on the next item in the list of cases where behavior is undefined, we have “The value of any bytes in a new object allocated by the realloc function beyond the size of the old object are used [results in undefined behavior]”.
The good news is that, as Taek and sltkr have pointed out elsewhere in the thread, clock_gettime() gets us a tiny bit of entropy, not perfect, but better than nothing. clock_gettime() is also POSIX compliant, although I remember about 15 years ago macOS didn’t support clock_gettime() (I checked, and it does these days).
getentropy() will become better than /dev/urandom for kernel level random numbers, but the problem is that getentropy() was only standardized and added to POSIX in 2024—too recent for me to feel 100% sure it’s widely implemented. And, yes, /dev/urandom (like chroot(), like sergroups()) isn’t defined in POSIX but it’s widely used.
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...
>>>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<<<
That’s not what I have said. 35 issues (mostly minor, but a couple of remote denial of service attacks) have been found with my code in the last 25 years; of those, none have come from the PRNG code I used. Here in the age of AI, I get multiple security reports a year, so the code is being looked at.
With crypto, you can never know for sure the code doesn’t have weaknesses, but one can have confidence in code and algorithms which have been around for years without any weaknesses discovered in them.
My question is: If code being around for years doesn’t build confidence in it being secure, what would it take to build confidence in the code.
What you’re seeing here is two schools of thought: One is the issue with using uninitialized memory, which yes does result in undefined behavior as per the C99 spec—but, back two decades ago when I made that decision, GCC was the only compiler of significance (clang was just released but was not widely used until years later) and its behavior was to put randomish data in undefined allocated memory.
The other is the notion that only Linux Kernel developers can develop a secure PRNG, and obviously I find that attitude very condescending and arrogant.
> My question is: If code being around for years doesn’t build confidence in it being secure, what would it take to build confidence in the code.
One of my experiences with programmers is that we (and I do not exclude myself from this category) are extraordinarily bad at sufficiently imagining the failure paths that our code might take and making code work handle failure cases correctly. It's these erroneous failure paths that are the real issue with code, and age doesn't really indicate how much testing of those failure paths actually exist.
To build confidence in code, what we need is proactive testing of potential failure paths that don't rely on humans to think of them in the first place--that means investment in various exhaustive testing techniques. (And I'd also like to see formal verification be more of a thing, but the tech just isn't there.) A stepping stone in that regard is also heavy use of static and dynamic analyzers to catch things that at known to be Obviously Bad™. The gold standard here really is whitebox concolic execution that's specifically trying to get something akin to 100% path coverage by trying to synthesize inputs to test the unhit paths.
Saying that it's okay to seed an entropy pool with uninitialized memory in 2005 is maybe defensible. There is a shift in compiler design around that time from thinking of it as compiling to a set of instructions and then optimizing them (so that the basic 'structure' of the code is something that's inherent to the program) towards looking at program semantics as abstract things where the only thing you need to preserve are the observable semantics [1]. One of the side effects of that shift is that undefined behavior stops being something that is fairly reliable so you assume you get the 'equivalent' assembly effects for that machine and starts being something that really screws over code.
But it's not 2005; it's 2026, and this change in compilers has been heavily advertised, discussed, complained about for well over a decade. And if you're using the kind of tools that give me confidence in code, those tools would have been bitching about that behavior for decades. If this is a surprise to you in this time and age, then it suggests to me that you've not really been proactive in trying to test your code in the manner I suggest, or worse, you have been proactive and decided to ignore everything telling you your practices are wrong because you know better than the tools and your code isn't obviously wrong.
(I say obviously wrong because your code example does demonstrate, when I tried it in the latest version of clang on godbolt, that it is eliminating the seeding of the entropy pool, in a way that is actually pretty clear if you read the assembly.)
[1] One of the most concrete examples to really observe the difference is the concept of control flow. Compilers nowadays are really happy to turn control flow (if statements) into dataflow (conditional moves or funky bit manipulations) and vice versa, because the only thing that needs to be preserved is the final value. Of course, cryptographers keep complaining that we broke their code by turning their obfuscated dataflow-based if statement into an actual if statement and so it's no longer constant-time, no matter how many times we keep telling them that we do not make any pretense of guaranteeing constant-time execution of code.
3 replies →