Base84 deserves a place in file names

The TurboCrypt git and file encryption tool was originally designed for Unix systems.

And it used to encrypt file names and encode the resulting ciphertext using Base91.

Why Base91? Because it’s a perfect fit for encrypted file names, producing strings that can be stored as valid files on Unix and macOS.

“But my filesystem can store arbitrary file names”! That may be true for some filesystems, but this is without taking libraries and applications into consideration. For example, the macOS Finder would not like this at all.

So, Base91 worked fine for encrypted file and directory names.

Then people asked for Windows support, where several characters in the Unix filesystem-safe alphabet are forbidden.

So, TurboCrypt is switching to Base84.

Something surprisingly not defined nor (apparently) used anywhere, even though it’s a perfect fit for anything that should be encoded as portable filesystem-safe names.

Why Base84?

There are 94 printable ASCII characters excluding the space. But Windows rules exclude nine of them:

That leaves 85.

But a name ending in a dot doesn’t work reliably through the Windows shell and ordinary file APIs.

Remove the dot as well, and we have 84 characters that can appear anywhere in a filename component. Microsoft documents these restrictions.

Dropping dots also avoids hidden names on Unix and the special names . and ...

Here’s the alphabet, in encoding order:

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!#$%&'()+,-;=@[]^_`{}~

Every character is acceptable in a filename on the usual Linux, macOS and Windows filesystems. And by design, a Base84 name can never be a Windows device name.

These encrypted file names are designed to be generated by software and consumed by software. They are opaque names used for remote storage. Nobody is expected to type them, so all we want is filesystem compatibility and smaller expansion than Base64.

Packing the bits

zig-base84 is an implementation of Base84.

It emits groups of five characters. Five is the sweet spot: 84⁵ = 4,182,119,424, only 2.6% short of 2³².

It’s simple to implement, and that leaves enough room for a group to hold 32 bits about 95% of the time on uniformly random input, and 31 bits otherwise.

The encoder looks at the next 31 bits. If their value is below 84⁵ - 2³¹, there’s room for a 32nd bit. Otherwise, it consumes just those 31 bits. Either way, the value fits in five base-84 digits. Pretty straightforward.

On random input, that’s about 31.95 bits per group, or 6.39 bits per character. The output is about 25.2% larger than the binary input. Almost Base85.

These expansion rates ignore the final partial group; the averages assume random input:

An input filled with 0xff forces every full group to consume only 31 bits. That’s the worst case: about 29% expansion.

Most filesystems cap a name at 255 bytes. Since the alphabet is ASCII, that’s 255 characters. Five divides 255 exactly, so even a maximum-length name holds only complete groups, with no bits lost to a partial one. Base84 guarantees room for 197 bytes of input, compared with 191 for unpadded Base64.

Unix-only names

Unix filenames can contain most of the punctuation Windows rejects. NUL and / are forbidden inside a filename; the Linux pathname documentation lists the rules and filesystem-specific limits.

The filesystem variant in zig-base91 replaces the standard Base91 alphabet’s slash with an apostrophe. It packs about 6.51 bits per character on random input, giving roughly 23% expansion.

For Unix-only names, use that variant. Standard Base91 still contains /, and both alphabets contain characters Windows rejects.

Base91 is used in hf-mount-encrypted, which adds transparent encryption to the tool to mount Hugging Face buckets, because the backend runs Linux, so Windows compatibility is irrelevant.

Windows device names

Windows reserves device names such as CON, NUL and COM1, regardless of case.

The five-character packing in Base84 has a useful side effect: with the standard alphabet, the encoder can’t spell a reserved device name, even for short inputs.

A three-character output always ends with A through J. That rules out CON, PRN, AUX and NUL, regardless of case.

A four-character output always ends with an uppercase letter or a, b, c. It can’t end with a digit, so COM1 through COM9 and LPT1 through LPT9 are impossible too. The superscript digits Windows also reserves aren’t in the alphabet.

And the alphabet has no dots, so a reserved name followed by an extension is also impossible.

Unlike other schemes such as Base64, no padding or special handling is needed to avoid these names.

How about case-insensitive filesystems?

Base84 distinguishes uppercase and lowercase letters, so different encoded names can compare equal on a case-insensitive filesystem.

For encrypted names, the collision probability depends on how much pseudorandom data gets encoded. TurboCrypt pads short names to 16 bytes before applying HCTR2. Modeling that encryption as a random permutation gives us 128-bit ciphertexts even for the shortest names.

Those 16 bytes encode to 20 or 21 characters. Even pretending every character is a letter, there are at most 2²¹ spellings that differ only in case.

Each valid spelling represents at most one of the 2¹²⁸ possible inputs, so a conservative upper bound on a case collision between two distinct encrypted names is 2²¹ / 2¹²⁸ = 2^-107. And longer ciphertexts give tighter bounds.

For n distinct names in the same directory, the birthday bound gives a collision probability of at most n(n - 1) / 2¹⁰⁸. Even with a billion names, that’s below 3.1 × 10^-15. Negligible.