mktmp: improve our temp file creation by ethomson · Pull Request #6207 · libgit2/libgit2

ethomson · 2022-02-08T20:25:01Z

Hey, why are our CI builds taking four hours?

I was hasty about merging #6178 and ignored @boretrk's sage advice about adding randomness to mktemp. It turns out that mingw64's mktemp is... just terrible. It's a single alphabetic character (a-z) followed by the process id. Which meant that in our test where we add a bunch of data to the repository in different threads caused temp file races against each other. At some point when 26 threads had temp files, we would end up in a big loop retrying new filenames, but having exhausted them, we would just sit in that loop for a while until one of the threads that had a temp file would eventually finish.

(Or we deadlocked, and never ended up writing anything at all, and the lack of error checking simply means that the failures were ignored.)

Okay, so what are we going to do about it?

This PR gets rid of our reliance on mktemp and mkstemp, a) because they might suck, and b) it's not what we want anyway. We're not writing temp files into writable directories (/tmp) and need something that gives us a mode 0600 file. Instead, we're writing temp files into repositories and need something that respects umask.

Regrettably, this is not entirely trivial. We do not want to use rand, because we cannot guarantee that the process calling us has ever called srand. And we cannot call srand ourselves, because the process calling us may have called srand and depends on a particular sequence number. (Test harnesses and fuzzers will often srand with a random seed, and report that seed so that if there's a failure, it's reproducible by using the same seed in subsequent runs).

So this PR:

Introduces the xoroshiro256** pseudo-random number generator. xoroshiro256** is fast and simple, and has the uncommon attribute of being easy to reason about code (64 bit types are uint64_t) instead of very academic (the code in my paper is a long int, what do you mean portable?). This is git_rand_next, and I've run the output against PractRand to ensure that there were no copy-pasta errors.
Introduces git_rand_seed which will seed the PRNG. We do this by pulling 64 bits out of the system's entropy pool (CryptGenRandom on Windows, or getentropy on *BSD and Linux). If we're on a non-Windows system and getentropy is not available (or fails), we'll fall back to trying to read from /dev/urandom. If none of those work, we'll use the system time (hopefully with a resolution better than a second) and xor with some system values like load average, uptime, process ID, etc. This strategy was largely borrowed from libressl, but not as aggressive, since we're putting a temp file in a directory that we control, not sending your credit card numbers across the internet.
Update our mktemp function to use our new PRNG and use it consistently.

Notes:

I'm not a cryptanalyst, but I feel confident about xoroshiro256** based on its adoption by Java.
Even if I didn't, we don't need to worry too much about attacks here, since we're only ever writing within the repository and our goal is race/collision-avoidance. That said, we should probably not use this in /tmp or world-writable directories.
We put a mutex around our state boxes for thread safety. It's probably fine for our needs. We could, I guess, try to pull it into a thread-local, but then we'd need to re-seed each thread independently and try to ensure that they were separate seeds. This is easy in the getentropy() case, hard in the time(NULL) ^ getpid() case. It's probably fine for our needs.

/cc @boretrk

boretrk · 2022-02-08T22:20:27Z

+	*seed ^= (((uint64_t)((uintptr_t)printf)) << SEED_SHIFT);
+	*seed ^= (((uint64_t)((uintptr_t)errno)));
+
+	*seed ^= ((uint64_t)git__timer());


Given that this one returns a double I'm thinking that we could possibly get some more bits out of it either by multiplying with some constant to get some of the sub-second information into the seed or write it to a union {double, uint64_t} to get access to all the bits.

🤔 Isn't double 64-bit on all data models?

The idea with using a union would be to write the double and read it as an integer to get all 64 bits into the seed.
It could be interesting to do this with the loadavg values too.

Technically double can be other sizes if __STDC_IEC_559__ isn't defined but I haven't seen this outside of some 8-bit processors where double is equivalent to float. I don't think that is something we need to take into consideration.

Oh, yes, I see what you're saying. Apologies; I never work with floats and so I was just thinking about it as a big hunk of bytes. Indeed a simple cast here will drop a lot of the data we wanted in this first place.

boretrk · 2022-02-08T23:29:37Z

+	*seed ^= (((uint64_t)((uintptr_t)getseed)) << SEED_SHIFT);
+	*seed ^= (((uint64_t)((uintptr_t)seed)));
+	*seed ^= (((uint64_t)((uintptr_t)printf)) << SEED_SHIFT);
+	*seed ^= (((uint64_t)((uintptr_t)errno)));


I'm thinking that getseed and printf are the same for all threads here and probably doesn't add much. (And because of some microcontrollers with separate address spaces for functions and data C99 doesn't allow casting function pointers to data pointers.)

Are seed and errno at unique addresses for each thread?
Otherwise &tv should give a pointer to a stack variable.

I wasn't aiming for uniqueness across threads - we'll seed once for the library at git_libgit2_init time for all threads - I was aiming for uniqueness across process invocations to avoid a replay attack. But for pthread, that will be a noop on anything that doesn't do ASLR, which I actually assumed was more common than it is - my Mac doesn't do ASLR, at least not by default. 🤔

And that should have been &errno, not errno. Meh.

In any case, I think that I got a bit belt-and-suspenders here; certainly I can remove the function pointers here for broader compatibility, especially since it's not the macOS and Linux cases that are going to fall into this function.

Sorry, I got a bit of a tunnel vision here. The cases that doesn't have either getentropy or /dev/urandom probably lacks most other security functions.

I do, too, at this point. This feels like a lot of code for "temp file in a place that we own", but there are always surprises.

boretrk · 2022-02-09T00:01:05Z

+	*seed |= ((uint64_t)kerneltime.dwLowDateTime << 32);
+	*seed |= ((uint64_t)kerneltime.dwHighDateTime);
+	*seed |= ((uint64_t)usertime.dwLowDateTime);
+	*seed |= ((uint64_t)usertime.dwHighDateTime << 32);


Is this supposed to be |= for these 6?
It "feels" like they were supposed to be ^=

Meh, I actually meant to compose the high and low bits into a single 64 bit number and then xor that.

boretrk · 2022-02-09T09:50:32Z

LGTM

An alternative to the shift/xor deal for the seed generation could have been to just feed the values into one of the SHA algorithms and let it deal with shuffling the bits around, but that is probably overkill.

ethomson · 2022-02-09T14:36:10Z

An alternative to the shift/xor deal for the seed generation could have been to just feed the values into one of the SHA algorithms and let it deal with shuffling the bits around, but that is probably overkill.

Yeah, I thought about that - and I actually think that it's a good followup when we have SHA-256. If we seeded with 256 bits instead of 64, we could easily pull 256 bits out of the system's entropy store, and then feed system state into SHA-256 as a fallback. This would let us drop the intermediate shiftmix64. But I didn't want to deal with that when we live in a SHA-1 only world, and I didn't really want to merge even the implementation bits of SHA-256 until we get v1.4.0 out the door.

Even this feels like a lot of changes at the last minute for v1.4.0 (which I wanted to get out... last month... 😢 ) but it does feel safe "enough".

Introduce `git_rand`, a PRNG based on xoroshiro256**, a fast, all-purpose pseudo-random number generator: https://prng.di.unimi.it The PRNG will be seeded by the system's entropy store when possible, falling back to current time and system data (pid, uptime, etc). Inspiration for this was taken from libressl, but since our PRNG is not used for cryptographic purposes (and indeed currently only generates a unique temp file name that is written in a protected directory), this should be more than sufficient. Our implementation of xoroshiro256** was taken almost strictly from the original author's sources, but was tested against PractRand to ensure that there were no foolish mistranslations: ``` RNG_test using PractRand version 0.94 RNG = RNG_stdin64, seed = unknown test set = core, folding = standard (64 bit) rng=RNG_stdin64, seed=unknown length= 256 megabytes (2^28 bytes), time= 2.9 seconds no anomalies in 210 test result(s) rng=RNG_stdin64, seed=unknown length= 512 megabytes (2^29 bytes), time= 6.2 seconds no anomalies in 226 test result(s) rng=RNG_stdin64, seed=unknown length= 1 gigabyte (2^30 bytes), time= 12.7 seconds no anomalies in 243 test result(s) rng=RNG_stdin64, seed=unknown length= 2 gigabytes (2^31 bytes), time= 25.4 seconds no anomalies in 261 test result(s) rng=RNG_stdin64, seed=unknown length= 4 gigabytes (2^32 bytes), time= 50.6 seconds no anomalies in 277 test result(s) rng=RNG_stdin64, seed=unknown length= 8 gigabytes (2^33 bytes), time= 104 seconds no anomalies in 294 test result(s) ```

`mktemp` on mingw is exceedingly deficient, using a single monotonically increasing alphabetic character and the pid. We need to use our own random number generator for temporary filenames.

We have our own temporary file creation function now in `git_futils_mktmp`, remove the others since they may be terrible on some platforms.

ethomson · 2022-02-12T14:09:45Z

Shipping it to unblock our CI

ethomson added the v1.4.0 label Feb 8, 2022

boretrk reviewed Feb 8, 2022

View reviewed changes

boretrk reviewed Feb 9, 2022

View reviewed changes

ethomson force-pushed the ethomson/prng branch from a72d260 to 004af89 Compare February 9, 2022 03:38

Edward Thomson and others added 5 commits February 9, 2022 09:41

str: add hexadigit encoding to strings

86c58a5

futils: use our random function for mktemp

53063e7

`mktemp` on mingw is exceedingly deficient, using a single monotonically increasing alphabetic character and the pid. We need to use our own random number generator for temporary filenames.

fs_path: use new mktmp to query unicode support

97fade4

util: remove p_mktemp / p_mkstemp

b933c14

We have our own temporary file creation function now in `git_futils_mktmp`, remove the others since they may be terrible on some platforms.

ethomson force-pushed the ethomson/prng branch from 4bdb0d2 to b933c14 Compare February 9, 2022 14:41

ethomson merged commit 4467bd6 into main Feb 12, 2022

ethomson deleted the ethomson/prng branch February 12, 2022 14:09

ethomson added the bug label Feb 13, 2022

Navigation Menu

Uh oh!

mktmp: improve our temp file creation - #6207

mktmp: improve our temp file creation#6207
ethomson merged 5 commits into
mainfrom
ethomson/prng

ethomson commented Feb 8, 2022

Uh oh!

boretrk Feb 8, 2022

Uh oh!

ethomson Feb 8, 2022

Uh oh!

boretrk Feb 8, 2022 •

edited

Loading

Uh oh!

ethomson Feb 8, 2022

Uh oh!

boretrk Feb 8, 2022

Uh oh!

ethomson Feb 9, 2022

Uh oh!

boretrk Feb 9, 2022

Uh oh!

ethomson Feb 9, 2022

Uh oh!

boretrk Feb 9, 2022

Uh oh!

ethomson Feb 9, 2022

Uh oh!

boretrk commented Feb 9, 2022

Uh oh!

ethomson commented Feb 9, 2022 •

edited

Loading

Uh oh!

ethomson commented Feb 12, 2022

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Uh oh!

Conversation

ethomson commented Feb 8, 2022

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

boretrk Feb 8, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

boretrk commented Feb 9, 2022

Uh oh!

ethomson commented Feb 9, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ethomson commented Feb 12, 2022

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

boretrk Feb 8, 2022 •

edited

Loading

ethomson commented Feb 9, 2022 •

edited

Loading