Attached because the patch is pretty large
This is a new patch to follow up to my non-cryptographic hash patch
that is a little higher quality and has a PoC DoS script.
You can see my notes in the commit message, but basically, all it
takes is a 13 line C++ program to generate a script that completely
shuts down Dash.
#include <algorithm>
#include <cstdio>
int main() {
char var[] = "abcdefghijkl=\n";
std::FILE *f = fopen("this_kills_dash.sh", "wb");
for (int i = 0; i < 120000; i++) {
std::fputs(var, f);
std::next_permutation(var + 1, var + 12);
}
fclose(f);
}
I stop at 120000, because that is more than enough to see the effect.
When dash sources the file, it tries to set all of these variables
which have the same hash.
On my 2.0 GHz 2nd Gen i7, dash hangs for a minute or two on that file,
compared to bash, mksh, zsh, and ksh which only take one or two
seconds. This could be used for a denial of service attack by hash
flooding the variable table.
And as you can see, that is not difficult to generate, there is no
brute force required, just knowledge of the commutative property of
addition.
This version, while it is not perfect, reduces a lot of the issues
with the previous implementation:
1. Better hash function. I use GoodOAAT from SMHasher because it
is the only small single byte hash function that actually passes the
test suite. We could use something more secure like SipHash or
something, but that would require a lot of work for a very short
string, as well as needing a precomputed length.
2. Larger hash tables. 39? Really? Dash's own configure script has
over 400 variables! I changed it to be a prime that is similar to
Bash's sizes. This actually helps performance a lot.
3. Seeding at startup. I try to read from /dev/urandom and fall
back to using clock(). This serves as the seed for the hash functions,
and makes things much less predictable so it can't just be shut down
with a static script.
Rehashing could be implemented later, but at this point, it gives dash
some resistance to an attack like that instead of basically asking for
a massive DoS attack.
Attachment:
0001-Use-a-larger-table-and-a-better-hash-function-to-pre.patch
Description: Binary data
