https://sourceware.org/bugzilla/show_bug.cgi?id=32030
Bug ID: 32030
Summary: Algorithmic complexity vulnerability (CWE-407) in BFD
Product: binutils
Version: 2.37
Status: UNCONFIRMED
Severity: normal
Priority: P2
Component: binutils
Assignee: unassigned at sourceware dot org
Reporter: nhweideman at gmail dot com
Target Milestone: ---
Note: This vulnerability is reported publicly by request of a Debian team
member.
# Overview
We discovered an algorithmic complexity vulnerability (CWE-407) in
Binutils-BFD. With a maliciously crafted executable, an attacker can disable
debugging tools that use BFD to process this executable. This is a problem,
because BFD is frequently used in tools created to analyze untrusted
executables, e.g. GDB. Therefore, a malicious executable can avoid analysis by
exploiting this vulnerability.
# Description
## The Vulnerability
BFD implements a hash table in `binutils-gdb/bfd/hash.c`, with a hash function
named `bfd_hash_hash` (code: [1]) and implementing separate chaining as
collision resolution (code: [2]). The hash function `bfd_hash_hash` is weak,
since it does not protect against reliable collision generation. Therefore,
an attacker can arbitrarily degrade the performance, by forcing the hash table
to execute in worst-case computational complexity `O(N**2)` by inserting
colliding entries. This is an algorithmic complexity vulnerability (CWE-407).
## The Exploit
The BFD hash table is used to store section names (`sh_name`) in an ELF
executable. By creating an executable with a large number of sections `N`,
each with a name that hashes to the same value when processed by
`bfd_hash_hash`, an attacker can exploit the vulnerability. When BFD inserts
each of these colliding section names, the linked list of previously inserted
(colliding) section names is traversed. Additionally, with each insertion of a
section name, this linked list grows in length with `1` entry. So, with each
insertion the length of the traversed linked list is `0, 1, 2, ..., N - 1`.
Overall execution time is quadratic in the number of section names `O(N**2)`.
# Steps to Reproduce / Proof of Concept
We include two ELF executables `malicous.elf` and `benign.elf`. These two
executables are exactly the same size (`79004968` bytes) and have exactly the
same number of sections (`1000006` sections). However, `malicous.elf` has
malicious (colliding) section names, whereas `benign.elf` does not. To prove
we are exploiting the algorithmic complexity vulnerability, we measure the run
time of various tools (that use BFD) when processing `malicous.elf` and
`benign.elf`. Below, observe that processing the benign executable takes
negligible time. Processing the malicious executable, on the other hand, takes
hours.
GDB:
```
$ time gdb --eval-command 'q' -q ./malicious.elf
...
real 450m49.024s
user 450m40.011s
sys 0m6.644s
$ time gdb --eval-command 'q' -q ./benign.elf
...
real 0m2.380s
user 0m1.935s
sys 0m0.428s
```
Objdump:
```
$ time objdump -M intel -d ./malicious.elf
...
real 487m6.085s
user 444m27.121s
sys 0m4.663s
$ time objdump -M intel -d ./benign.elf
...
real 0m1.146s
user 0m0.794s
sys 0m0.351s
```
Strings:
```
time strings --data ./malicious.elf
...
real 464m42.581s
user 464m36.781s
sys 0m3.748s
time strings --data ./benign.elf
...
real 0m1.151s
user 0m0.778s
sys 0m0.373s
```
Nm:
```
$ time nm malicious.elf
...
real 456m4.917s
user 455m57.435s
sys 0m5.036s
$ time nm benign.elf
...
real 0m1.040s
user 0m0.716s
sys 0m0.318s
```
# Included Files
The two PoC executables `benign.elf` and `malicious.elf` can be found here:
https://drive.google.com/file/d/1Z6gIpeqqvaIS-h-N_zyq1fG0hGIWzTCo/view?usp=drive_link
The password for the archive is 43817
# Remedial action
To mitigate the vulnerability, the weak hash function used by BFD
(`bfd_hash_hash`) should be changed to implement a fast, strong hash function
instead (e.g. [4]).
# References:
[1]:
https://sourceware.org/git/?p=binutils-gdb.git;a=blob;f=bfd/hash.c;h=059e315a632ac62c0c129f183060465b92c47eea;hb=HEAD#l509
[2]:
https://sourceware.org/git/?p=binutils-gdb.git;a=blob;f=bfd/hash.c;h=059e315a632ac62c0c129f183060465b92c47eea;hb=HEAD#l617
[3]:
https://sourceware.org/git/?p=binutils-gdb.git;a=blob;f=bfd/hash.c;h=059e315a632ac62c0c129f183060465b92c47eea;hb=HEAD#l559
[4]: https://github.com/google/highwayhash
--
You are receiving this mail because:
You are on the CC list for the bug.
