I strongly agree with all of the above. I have developed an intense, burning hatred for people who submit ReDoS “vulns” with claimed CVSS scores >6 for libraries that do things like print colour codes to the terminal. The 7.5 score on the vuln linked to in that article is ludicrous: I have seen unauthenticated RCE bugs get lower scores than that!
I really wish something like CWSS came along to help with these sorts of things, or really anything else. From personal experience scoring findings in hundreds of reports, I’ve always found CVSS is really easy to conflate along impact, when the likelihood of something being actually exploited is low. Honestly, the only real thing I’ve liked out of CVSS is the Attacker Position, although I’ve found that many people struggle to understand Adjacent versus Network.
Really, something that takes:
likelihood of discovery (where the system sits, what information is needed, &c)
likelihood of exploitation (what factors go into actually exploiting the discovered vulnerability, what mitigating controls would dissuade someone from doing so)
system impact vs business impact
in a way that can describe libraries, systems, &c
would be a huge improvement over the status quo.
And I say all of this as someone who has reported ReDoS to clients, mostly as a “hey did you really intend to expose…” Low/Note finding.
The incidental swipes at the breathless “URGENT CRITICAL SUPPLY CHAIN ATTACK UNDERWAY MILLIONS OF SYSTEMS AT RISK” articles that just boil down to “we found a couple typosquatting packages, reported them, and the package index removed them”.
The side-eye at “beg bounties”, which are more prevalent than most people realize (the automated scanning tool you spent a total of five minutes learning to use in order to be a “Certified Ethical Hacker” defaults to alerting on a lot of stuff that doesn’t actually matter, and won’t get you huge bounty payout).
The ludicrousness of CVSS scores. The wheel “vulnerability” is a great example that I’m going to steal for future rants. For those unfamiliar: wheel is the reference implementation of the builder for Python’s .whl package format. If you are exposing that to arbitrary input from third parties in an exploitable way, you have problems that will not be solved by slightly improving one of the regexes used on the input arguments.
Kinda agree with where the author comes from, but not the practical result. Specifically:
Except, of course, that no attacker bothers to do this: it’s simpler, easier, and just as effective to perform a DoS the “good old fashioned” way.
That’s just not true for services that have $$$ reasons to care about availability. For “good old fashioned” DoS, I just wake up in the morning and read a notification from my DDoS shield provider about how many Gbps of traffic they blackholed at night. It happens every week. For ReDoS, you could effectively kill the site for hours with your mobile phone on 2G. (Or less than hours - depending on how easy it is to deploy the fix)
And yeah, it’s all context specific and many services won’t care. But the quoted fragment is just not true. It probably falls under the old “your threat model is not my threat model” idea.
There are regex libraries that avoid some of these regex DOS issues. Of course it comes with limitations: no support for backreferences in regex itself (\1, etc.), but for the vast majority of applications that would be an acceptable limitation.(I’m not sure whether matching with backreferences is even doable in linear time in the general case, but it is certainly not trivial, and I haven’t seen any major regex library implement it efficiently).
Fixing this “vulnerability” in each application doesn’t seem right, a better way to fix this is at the foundations level: almost all libcs (except OpenBSD’s) would be vulnerable to this, however a better regex engine would avoid the problem, e.g.
There is a good series of articles describing regex matching, and how to get actual linear time matching (although some care needs to be taken during the compilation of the regex itself to avoid exponential blowup, a combination of a NFA/DFA as in Google’s re2 achieves a good performance balance while still retaining linear time matching):
https://swtch.com/~rsc/regexp/
There is nothing “new” about this vulnerability, I switched ClamAV to use OpenBSD’s implementation of regex in 2007 already. Not necessarily due to DoS, but there were some platforms where the system provided regexec was orders of magnitude slower than the one in libc (quadratic or worse runtime performance even on non-malicious regexes) so using one with known runtime and performance characteristics was a good replacement.
Interesting, I have been wondering the same thing about hash bucket pile-up DoS. At one point ~10 years ago Python, Lua, etc. and many other languages (I think PHP, Ruby) all changed their hash values be unpredictable “from the outside”.
Then at some point, I had some build determinism bugs in .pyc files, which I think were due to this randomness.
I don’t remember exactly what happened, but I think I also saw around that time that there were bugs in Python 2’s solution.
Like if any attacker actually bothered, they could easily predict Python 2’s hash values, despite the mitigations.
But I don’t think anyone really cares to spend the time. It’s pretty much the last thing they would do to take down a service.
Python’s attempts to fix it were unsuccessful as long as Python stuck to FNV as the underlying hash function, which persisted until Python 3.4. At that point (see PEP 456 for the details), Python switched to using SipHash. For a while it was on SipHash 2-4, but as of Python 3.11 it’s SipHash 1-3, which apparently is used by multiple other languages.
Because of this there’s also a kind of tortured history behind the -R command-line flag to the interpreter, and the PYTHONHASHSEED environment variable. I don’t actually know off the top of my head all the changes to the combinations of defaults and whether the explicit config even did anything from version to version – the Python docs note that -R was added in 3.2.3, but also for a while was apparently just ignored because there’s a note saying that stopped in 3.7. The current state is:
Hash randomization – with a unique-per-process random hash seed – is on by default.
Setting the environment variable PYTHONHASHSEED to a positive integer value will replace the random seed with that fixed integer value.
Setting PYTHONHASHSEED to integer 0 will disable hash randomization, unless the -R command-line flag is passed to the Python interpreter.
Setting PYTHONHASHSEED to the string random restores the default hash randomization behavior.
Yup I noticed this evolution, and given that many people run older Python versions, I was wondering WHO actually relies on this attack being impossible. Probably very few people.
And the second question: did the people fixing this (over a long period time) actually have the problem? Or were they just following the vulnerability reports?
Possible third option: there were so many changes that, even if the solution wasn’t air tight, any attackers couldn’t be bothered … i.e. they would have to figure out what Python version someone was running, and then after that see what vulnerabilities were left. Doesn’t seem worth it :)
I was wondering WHO actually relies on this attack being impossible. Probably very few people.
For networked Python services which typically are collecting some sort of client-supplied headers or other data into a dict, the base case of no randomization at all is pretty easy to DoS and requires less effort on the part of the attacker than a traditional swamp-you-with-petabytes-of-traffic DDoS. For the later hardening I’m not sure how realistic the attack still was, but I feel like Python was backed into a corner of having to do something anyway because of the bad press that would come from not permanently fixing the issue.
A similar case is Python’s slow string-to-integer parsing, which led to the new digit limit in Python 3.11 – the fact that it’s so easy and requires so few resources to exploit makes it harder to ignore, even if “traditional” DDoS methods that don’t rely on bugs like this are still more common in the wild.
I strongly agree with all of the above. I have developed an intense, burning hatred for people who submit ReDoS “vulns” with claimed CVSS scores >6 for libraries that do things like print colour codes to the terminal. The 7.5 score on the vuln linked to in that article is ludicrous: I have seen unauthenticated RCE bugs get lower scores than that!
I really wish something like CWSS came along to help with these sorts of things, or really anything else. From personal experience scoring findings in hundreds of reports, I’ve always found CVSS is really easy to conflate along impact, when the likelihood of something being actually exploited is low. Honestly, the only real thing I’ve liked out of CVSS is the Attacker Position, although I’ve found that many people struggle to understand Adjacent versus Network.
Really, something that takes:
would be a huge improvement over the status quo.
And I say all of this as someone who has reported ReDoS to clients, mostly as a “hey did you really intend to expose…” Low/Note finding.
I love everything about this article, including:
wheel“vulnerability” is a great example that I’m going to steal for future rants. For those unfamiliar:wheelis the reference implementation of the builder for Python’s.whlpackage format. If you are exposing that to arbitrary input from third parties in an exploitable way, you have problems that will not be solved by slightly improving one of the regexes used on the input arguments.Kinda agree with where the author comes from, but not the practical result. Specifically:
That’s just not true for services that have $$$ reasons to care about availability. For “good old fashioned” DoS, I just wake up in the morning and read a notification from my DDoS shield provider about how many Gbps of traffic they blackholed at night. It happens every week. For ReDoS, you could effectively kill the site for hours with your mobile phone on 2G. (Or less than hours - depending on how easy it is to deploy the fix)
And yeah, it’s all context specific and many services won’t care. But the quoted fragment is just not true. It probably falls under the old “your threat model is not my threat model” idea.
There are regex libraries that avoid some of these regex DOS issues. Of course it comes with limitations: no support for backreferences in regex itself (\1, etc.), but for the vast majority of applications that would be an acceptable limitation.(I’m not sure whether matching with backreferences is even doable in linear time in the general case, but it is certainly not trivial, and I haven’t seen any major regex library implement it efficiently).
Fixing this “vulnerability” in each application doesn’t seem right, a better way to fix this is at the foundations level: almost all libcs (except OpenBSD’s) would be vulnerable to this, however a better regex engine would avoid the problem, e.g.
(Or their python bindings: https://pypi.org/project/tre/ and https://pypi.org/project/re2/)
There is a good series of articles describing regex matching, and how to get actual linear time matching (although some care needs to be taken during the compilation of the regex itself to avoid exponential blowup, a combination of a NFA/DFA as in Google’s re2 achieves a good performance balance while still retaining linear time matching): https://swtch.com/~rsc/regexp/
There is nothing “new” about this vulnerability, I switched ClamAV to use OpenBSD’s implementation of regex in 2007 already. Not necessarily due to DoS, but there were some platforms where the system provided regexec was orders of magnitude slower than the one in libc (quadratic or worse runtime performance even on non-malicious regexes) so using one with known runtime and performance characteristics was a good replacement.
Interesting, I have been wondering the same thing about hash bucket pile-up DoS. At one point ~10 years ago Python, Lua, etc. and many other languages (I think PHP, Ruby) all changed their hash values be unpredictable “from the outside”.
Then at some point, I had some build determinism bugs in
.pycfiles, which I think were due to this randomness.I don’t remember exactly what happened, but I think I also saw around that time that there were bugs in Python 2’s solution.
Like if any attacker actually bothered, they could easily predict Python 2’s hash values, despite the mitigations.
But I don’t think anyone really cares to spend the time. It’s pretty much the last thing they would do to take down a service.
Does anyone know otherwise?
It does have some consequence, as https://www.oilshell.org/ needs a hash table implementation :)
I guess I would summarize it as: are computational complexity attacks interesting? Probably in some unusual cases, but not in most cases.
The multi-language hash-table thing was this.
Python’s attempts to fix it were unsuccessful as long as Python stuck to FNV as the underlying hash function, which persisted until Python 3.4. At that point (see PEP 456 for the details), Python switched to using SipHash. For a while it was on SipHash 2-4, but as of Python 3.11 it’s SipHash 1-3, which apparently is used by multiple other languages.
Because of this there’s also a kind of tortured history behind the
-Rcommand-line flag to the interpreter, and thePYTHONHASHSEEDenvironment variable. I don’t actually know off the top of my head all the changes to the combinations of defaults and whether the explicit config even did anything from version to version – the Python docs note that-Rwas added in 3.2.3, but also for a while was apparently just ignored because there’s a note saying that stopped in 3.7. The current state is:PYTHONHASHSEEDto a positive integer value will replace the random seed with that fixed integer value.PYTHONHASHSEEDto integer0will disable hash randomization, unless the-Rcommand-line flag is passed to the Python interpreter.PYTHONHASHSEEDto the stringrandomrestores the default hash randomization behavior.Yup I noticed this evolution, and given that many people run older Python versions, I was wondering WHO actually relies on this attack being impossible. Probably very few people.
And the second question: did the people fixing this (over a long period time) actually have the problem? Or were they just following the vulnerability reports?
Possible third option: there were so many changes that, even if the solution wasn’t air tight, any attackers couldn’t be bothered … i.e. they would have to figure out what Python version someone was running, and then after that see what vulnerabilities were left. Doesn’t seem worth it :)
For networked Python services which typically are collecting some sort of client-supplied headers or other data into a
dict, the base case of no randomization at all is pretty easy to DoS and requires less effort on the part of the attacker than a traditional swamp-you-with-petabytes-of-traffic DDoS. For the later hardening I’m not sure how realistic the attack still was, but I feel like Python was backed into a corner of having to do something anyway because of the bad press that would come from not permanently fixing the issue.A similar case is Python’s slow string-to-integer parsing, which led to the new digit limit in Python 3.11 – the fact that it’s so easy and requires so few resources to exploit makes it harder to ignore, even if “traditional” DDoS methods that don’t rely on bugs like this are still more common in the wild.