Out-of-bounds read and write in the glibc's qsort()
openwall.com
openwall.com
Somewhat tangentially, Microsoft at one point got in a bit of trouble for trying to use a randomized comparison function to implement shuffling on their "Browser choice" page:
https://www.robweir.com/blog/2010/02/microsoft-random-browse...
[0] https://www.reddit.com/r/cpp/comments/151cnlc/a_safety_cultu...
Not sure about the Microsoft C++ standard library since the Microsoft Windows system API does not provide the same softlink functionalty.
Can you say the same for Rust?
But parent's point is that some issues that count as a CVE for Rust do not count as such for C/C++ because the boundaries of undefined behavior are drawn elsewhere. This means that there are many fixes that are simply never made for C/C++, even though dynamic linking would make such a counterfactual fix easier to deploy.
If I have to reinstall the whole system to fix CVE in Rust stdlib in a brave new world where everything is written in Rust, then it's certainly not free fix.
"Memory safe" means that if the user is "holding it wrong", it won't cause a memory error.
In safe Rust, it is impossible to call free with the wrong address (simply by virtue of the `free` equivalent being unsafe, and with the pervasive use of smart pointers to make it practical to stay in safe land).
Similarly even if you "hold it wrong" and use a wrong comparison function in Rust's sort, you might get nonsensical results, but no memory errors.
That's precisely what safety means in this context
My misfortunate crate https://crates.io/crates/misfortunate is a library of types that just deliberately implement various traits "wrongly" in order that you can play with the consequences.
For example Clone promises to uh, clone things, but Rust can't know if this Doodad is really a "clone" of that Doodad, only that the result was really the correct type, so if your type only implements Default my Multiplicity type wrapper will cheerfully claim it can be cloned anyway, cloning the wrapper doesn't get you a "real" clone but only your Default - the types look correct but what's inside is not a "clone" in any reasonable sense.
Rust does have what it calls unsafe traits, traits which you cannot implement without writing the "unsafe" keyword. They are solemn promises that you did what the documentation told you to, if you messed up in writing the unsafe trait then the resulting software may have Undefined Behaviour.
For example, my type wrapper Comte (named after the guy who invented the trick with a hat you've seen magicians do) claims to be an ExactSizeIterator. If it has one rabbit inside it, duh, exact size. Nope, it's a trick, we can just tap the Comte with our wand and produce an unlimited number of rabbits despite claiming to be an ExactSizeIterator, that's a bad idea but it's not Undefined Behaviour.
On the other hand Rust has the unsafe TrustedLen, which also says we can trust this iterator knows exactly how big it is, but because it's unsafe that's a solemn promise, if we took the Comte code but claimed to implement TrustedLen we're just despicable liars.
I'm finding myself very fatigued by this about vulnerabilities and find myself just giving up about trying to keep track. Also because there is no good curated source it feels. I can run after 3 nonsense ones a week and the one that can rip my systems apart drops on Christmas eve anyway.
For example, the keycloak OIDC vulnerability would've allowed me to compromise any account of our internal authentication with ~1 bad click from a user, possibly fewer. Working that out to a point it was terrifying to all internal users took like 30 minutes at most and most time was wasted on realizing their version constraints for the exploit are wrong. That's a 7.8.
But then you have "Oh curl with high parameters can hang" and "Oh if you reload postgres many times a second it stops working" coming in at 9+. Like sure, a user with elevated privileges on a critical server sending signals to postgres causing a postgres DoS is my biggest issue at that point.
So I either have to evaluate everything for myself, or .. no idea.
Score 1: This is an implementation bug in the library. Update the library and you're done. It doesn't matter that this gives remote root on a machine with no services running, all you have to worry about is to install the patch and it's 100% fixed.
Score 2: This is a vulnerability discovered in multiple implementations. Some of them have fixed it and some of them haven't. Here is the list of known-good implementations, you need to check that the one you're using is on the list and if it isn't then switch to one of the ones that is.
Score 3: This is a flaw which some platforms don't currently provide a means to implement securely for any implementation. You need to pay attention to this if you use those platforms and possibly redesign your applications to do something else there.
Score 4: This is a design flaw in the API. We can't fix it without breaking compatibility so here's a new API and now you definitely have to update your applications to use it and the existing ones will continue to be vulnerable. Compilers should emit a deprecation warning for anything still using the old API.
Score 5: Spectre. We kind of mitigated it some and you need some patches but now you have to review all existing code, probably won't catch it all anyway, people will continue finding new variants for years and we're all totally screwed.
New Linux glibc flaw lets attackers get root on major distros - https://news.ycombinator.com/item?id=39250076 - Feb 2024 (93 comments)
Out-of-bounds read and write in glibc's qsort() - https://news.ycombinator.com/item?id=39206029 - Jan 2024 (1 comment)
CVE-2023-6246: Heap-based buffer overflow in the glibc's syslog() - https://news.ycombinator.com/item?id=39194093 - Jan 2024 (18 comments)
Safety vs. Performance. A case study of C, C++ and Rust sort implementations - https://news.ycombinator.com/item?id=37781612 - Oct 2023 (130 comments)
Have the auditors tried looking at musl libc? It seems a lot less convoluted from what I've seen so may be an easier thing to validate.
return (a > b) - (a < b);
Now, if you're exploiting that quirk for performance purposes, that's another story. But then the code should be labeled as such.
Also 7.18 makes the bool macros explicitly 1 and 0.
In fact comparison is really just subtraction where the result is ignored, only the condition flags are updated in the same way as by any other subtraction.
The difference is elsewhere. In machine language, after either an integer subtraction or an integer comparison, the relationship between the operands is not tested by using the sign of the result.
It is tested instead by using the true sign of the result, which is computed by the addition modulo 2 (a.k.a. XOR) between the sign of the result and the overflow flag.
In the currently popular high-level programming languages it is no longer possible to access the overflow flag. (In many early programming languages there were available facilities like "on overflow do ...".) Had this been possible, the qsort comparison function could have been implemented as a subtraction, with the result conditionally corrected in case of overflow.
Therefore in languages like C and derivatives one must always use the relational operators ">", "<", ">=" and "<=", because these are implemented by the compiler using conditional instructions that test the true sign computed with the overflow flag, after the subtraction of the operands.
Also, by default, Rust's integer operations trap on overflow, so if you wrote the obvious comparator (x-y) the program would panic instead of exhibiting undefined behavior.
I do not consider that the behavior of a debug build can be considered as "default".
I consider the disabling of the overflow traps a very bad practice, which is justified only for specific functions or code sequences that have been analyzed carefully to prove that overflows are impossible.
For example, the chain of exploits that have been used to gain complete remote control of any iPhone without detection during many years has included some that were based on integer overflows in the Apple system software.
For those interested, I found a blog post that covers an iMessage-based zero-click exploit, which was caused by unchecked integer overflow, and a lack of bounds checking done on allocated buffers:
https://googleprojectzero.blogspot.com/2021/12/a-deep-dive-i...
If you wrote this code in WUFFS it won't compile.
Though of course you wouldn't need to do either because the usual way to write a Rust API that takes comparators is for that comparator to return std::cmp::Ordering, not a signed integer.
And if you do make a PartialOrd / Ord impl that isn't transitive, it is guaranteed by the sorting fns in libstd that sorting may be incorrect, but it won't be undefined behavior.
And sure, overflow checks aren't free - but this is something that has been optimized in CPUs for decades.
Or more sensibly you can set clippy lints to disallow any operation that may overflow, forcing you to specify the desired behavior (either with the .{wrapping,checking,saturating}_{sub,add,mul,div} functions or the Saturating<Type> etc wrappers)
While the "signed" types in C are well defined kinds of integers, which nonetheless have unpredictable behavior on overflow, the "unsigned" types are ambiguous, because they correspond to 4 different primitive types (each of these 4 being available in various sizes, i.e. 1-bit, 8-bit, 16-bit, 32-bit, 64-bit or 128-bit).
By primitive types I mean types for which the modern CPUs implement distinct dedicated hardware instructions. The 4 types are non-negative integers, integer residues (a.k.a. modular numbers), binary polynomials and Galois-field binary polynomials.
The same operation, e.g. multiplication, is implemented with different algorithms for each of these 4 types.
Moreover, while a 64-bit "unsigned" may be interpreted as a 64-bit non-negative integer or a residue modulo 2^64 or a 64-bit binary polynomial or a value in GF(2^64), there are 2 additional interpretations between which there are subtle differences, as a 64-element array of 1-bit non-negative integers or as a 64-element array of residues modulo-2. The failure to be aware of the differences between the operations that can be performed with these 6 types and using a single name for all can easily lead to bugs.
The wraparound is correct for integer residues modulo 2^N, but it is wrong for non-negative integers, which are more frequent in most applications.
Also the implicit conversions of unsigned types are very bad in C and derivatives. They are some times correct for non-negative integers, but they are always wrong for integer residues. While a small-size non-negative integer may be converted without losses to a bigger size, for integer residues the reverse is true, they can be converted correctly only towards smaller sizes.
Therefore, the unsigned types of C are defined wrongly both when interpreted as non-negative integers and when interpreted as integer residues. Most other languages are not better.
While there are many applications where either non-negative integers, integer residues, binary polynomials or Galois-field binary polynomials are needed, so unsigned C types must be used for lack of a better alternative, the use of "unsigned" types requires extra care in comparison with using the signed types (e.g. all implicit conversions must be avoided) and it must be clearly documented what kind of "unsigned" is really meant (preferably by defining dedicated types for the various possible interpretations; in C++ it is possible to also define correct operations with them, replacing the built-in operators with undesirable behavior).
The conversions work, e.g. conversion to a smaller unsigned type are reduced. That some other conversion work does seem convenient to me and not a problem.
One can, of course, define types in C for Galois fields and access them using functions that do the correct operations (and by wrapping it in a struct one can also prevent regular operations to be used on such type). In C++ one can overload the builtin operators, but I am not terrible sure this is even a good idea.
I don't even think Rust can do something like
type Element is Integer range 100 .. 1000;WUFFS can do this, it calls such types "refined" types - and indeed WUFFS can also do:
assert n_bits < 12 via "a < b: a < c; c <= b"(c: width)
WUFFS doesn't know how to create such a proof, it's in quotes because WUFFS has a list of proofs a human gave it, baked in, and just accepts any of those proofs, after all a human mathematician assured it these are true. But it can check the rest of your assertion given this proof, and if that fails your software doesn't compile.
WUFFS requires that it can see why everything you're doing is OK, whether that's indexing into an array (if you write dogs[k] where dogs is an array of 16 dogs, WUFFS needs to be certain that k is strictly in the range from zero to fifteen inclusive, or the program won't compile) or arithmetic (if bits is supposed to be an integer between one and thirty two inclusive then we can't very well do bits = k * 2 can we, because k might be zero)
As a result WUFFS gets to be entirely safe. As a side effect (and also with the help of some clever SIMD friendly language design choices) WUFFS gets to go very, very fast. And all for the very affordable price of abandoning generality. The next Doom, Excel, Apache and Linux cannot be written in WUFFS. But the question is why your thumbnail making code, or your file compressor is written in anything else.
In Common Lisp, you can write
(deftype element () `(integer 100 1000))
(deftype even-element ()
`(and (integer 100 1000)
(satisfies evenp)))
int cmp(const float *a, const float *b) {
if (*a < *b) {
return 1;
} else if (*a == *b) {
return 0;
} else {
return -1;
}
}To make a point, here is a sorting function I'm using.
static int cmp_seqnos(const void *a, const void *b)
{
uint64_t x = (const uint64_t *) a;
uint64_t y = (const uint64_t *) b;
if (y - x < ((uint64_t) 1 << 63))
return -1;
return x != y;
}
Sorting such numbers can be useful when dealing with sliding windows.
Personally I believe, that blaming users for "holding it wrong" is not an effective way forwards. As a programming community we've tried that many times, and I've yet to see it succeed at scale.
C APIs were not all designed to be safe to call and can commonly crash or introduce a vulnerability.
So what I mean is: how much performance are we giving up with this "fix" for qsort?
Unfortunately, qsort is really slow and sometimes barely usable.
Maybe what's notable from a security perspective is that here's a contract about the behavior of an algorithm (comparison function) as opposed to the value of an argument (null pointer, negative, bigger than N, etc.).
Still qualifies as passing an invalid parameter.
Also IMO, the default should always be unsigned (modulus) integers, not signed. That would promote more correct consideration of integer types and operations. Yes, the ship has sailed on that, but it would also be nice if code linters added 'signed ' where not specified to remind everyone of the present default.
> This memory corruption in the GNU C Library through the qsort function is invoked by an application passing a non-transitive comparison function, which is undefined according to POSIX and ISO C standards. As a result, we are of the opinion that the resulting CVE, if any, should be assigned to any such calling applications and subsequently fixed by passing a valid comparison function to qsort and not to glibc.
Disappointing. Not unexpected, but still disappointing. Oh well, at least they fixed it.
I'm sure there are some Rust devs who would say the same thing about C. It's possible to write secure code in C, just as it's possible to write a sort with defined behavior using glibc.
Case in point: You can make the same error in Java (I think it's even included in the docs for Comparators that you shouldn't do a-b, because of integer overflow/underflow), but it cannot lead to an out-of-bounds read/write. And that's because Java (~glibc) handles the comparison function that you give it differently.
For instance, the bad comparator could be used in nested authentication checks:
if check_A { drop privilege to FOO } else if check_B { drop privilege to BAR } else { /* leave root bit set, because "not (A or B)" means root */ }
and it could lead to a privilege escalation in the face of malformed inputs.
I've seen this sort of thing happen in the wild with Java.
The closes thing there is 7.22.5.2 §4: "If two elements compare as equal, their order in the resulting sorted array is unspecified"
So I'd say blaming users for a bug in glibc isn't fair.
"When the same objects (consisting of size bytes, irrespective of their current positions in the array) are passed more than once to the comparison function, the results shall be consistent with one another. That is, for qsort they shall define a total ordering on the array, and for bsearch the same object shall always compare the same way with the key."
No, we blame the person that did not take proper training or exercise sufficient caution when using their tool.
If you shop specifically for an unsafe tool, surprise, you get one. Should have picked better.
2) There's no reason to not just have the footgun be opt-in rather than it being the default approach, if performance does matter so much
3) Why is trading safety for performance the right decision in the first place? It's funny to compare the way software engineers talk about software with the way any other kind of engineer talks about their domain, or even how software engineers talk about other domains.
How many threads have been had here over the past month about how unacceptable Boeing's "just turn off the de-icer" is to a hardware problem that could damage the engine, and other dodgy engineering decisions?
I'm complaining about the people that start projects in unsafe languages in exchange of a thin performance boost, and then blame the compiler/runtime maintainers for their own code being unsafe in exactly the ways the spec says it can be unsafe to give them such an extra boost.
Personally, I think all remaining C and C++ projects should consider either rewriting in a safer language or adopting additional tools to prove (not just test) the lack of undefined behaviour. Trying to compromise is just giving us memory safety CVEs one after another.
For example, it wouldn't be useful to assign a CVE to the concept of SQLi, but it can be useful to assign CVEs to particular products exhibiting SQLi vulnerabilities. This fault isn't quite as general as that, but the argument for non-CVE-assignment goes along the same lines.
The aftermath of issuing a CVE for this bug would have massive consequences all over the industry, fixing the bug and leaving the past - where you probably would have become aware of this by now if it affected you and you probably should have a look at your code regardless to see if the situation can occur - means that on the next scheduled update of glibc everybody will have the fix. If you have a way of getting this to escalate to RCE or some other nastiness, especially if it can be done remotely in some application that is networked and that uses qsort (which should be most of them so if it is that easy then it should be quick to prove).
Note that even something as mundane as the UTF-8 encoding scheme led to an exploit so it may well be possible. But I think classifying this as a security bug rather than just as a bug at this point is premature.
Consider being on the receiving side of a mandatory (for instance: regulated industry) upgrade requirement of all of your systems because a CVE was issued would carry substantial costs even if the risk of those systems being exploited was very small. So the glibc team likely took such costs into account and absent an easy or obvious way to exploit this that seems for the moment to be the right call. But it could change.
The odds of a setuid root program having this particular, exotic flaw are miniscule. None have been found in the wild.
The example they give is "a function cmp(int a, int b) that returns (a - b)", which is definitely a comparison function I've seen before. It's wrong because of overflow, but it's not egregiously wrong.
I think it's more significant than you're implying. I wouldn't be surprised if it were used as a step in an exploit chain somewhere in the wild.
In which setuid-root program?
It's possible to implement a nontransitive function without the first UB though.
Note however that the UB only actually happens if the dynamically-passed values are more than INT_MAX apart. So e.g. if the values are never negative in practice, or limited to a small maximum, there is no UB.
And i had always thought networked services avoid using plain qsort due to risk of dos
At a higher level, who's misusing qsort in this way? I'd say PBCAK.
Not only will it not sort them... it will lead to OOB memory accesses by qsort itself