Base84はファイル名に場所を占めるべきだ

Base84はファイル名に採用されるべきだ

TurboCryptというGitおよびファイル暗号化ツールは、元々Unixシステム向けに設計されていました。

そして、ファイル名を暗号化し、結果の暗号文をBase91でエンコードしていました。

なぜBase91なのか？それは暗号化されたファイル名に最適で、UnixやmacOSで有効なファイルとして保存できる文字列を生成するからです。

「でも、私のファイルシステムは任意のファイル名を保存できる！」それは一部のファイルシステムでは真実かもしれませんが、ライブラリやアプリケーションを考慮に入れていません。例えば、macOSのFinderはこれを全く好まないでしょう。

そのため、Base91は暗号化されたファイル名やディレクトリ名にはうまく機能していました。

その後、Windowsサポートが求められるようになり、Unixファイルシステムで安全なアルファベットのいくつかの文字が禁止されていることがわかりました。

そこで、TurboCryptはBase84に切り替えています。

驚くべきことに、これはどこにも定義されておらず、（明らかに）使用されてもいませんが、ポータブルなファイルシステムセーフな名前としてエンコードされるべきものには完璧に適合します。

なぜBase84なのか？

スペースを除くと、94個の表示可能なASCII文字があります。しかし、Windowsのルールではそのうち9つが除外されます。

< > : " / \ | ? *

これにより85文字が残ります。

しかし、ドットで終わる名前はWindowsシェルや通常のファイルAPIでは確実に機能しません。

ドットも削除すると、84文字になり、これはファイル名のコンポーネントのどこにでも現れることができます。Microsoftはこれらの制限について文書化しています。

ドットを削除することで、Unixでの隠しファイル名や、. および .. という特殊な名前も回避できます。

エンコード順のアルファベットは以下の通りです。

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

すべての文字は、一般的なLinux、macOS、Windowsファイルシステムでファイル名として許容されます。そして設計上、Base84の名前はWindowsのデバイス名になることは決してありません。

これらの暗号化されたファイル名は、ソフトウェアによって生成され、ソフトウェアによって消費されるように設計されています。これらはリモートストレージに使用される不透明な名前です。誰もこれを手入力することを期待していないため、私たちが望むのはファイルシステムの互換性とBase64よりも小さい拡張率だけです。

ビットのパッキング

zig-base84はBase84の実装です。

これは5文字のグループを出力します。5文字がスイートスポットです：84^5 = 4,182,119,424、これは2^32（4,294,967,296）よりわずか2.6%少ないだけです。

実装は簡単で、グループには約95%の確率で32ビット、それ以外の場合は31ビットを格納できます。

エンコーダーは次の31ビットを見ます。その値が845 - 2^31 より小さい場合、32ビット目のためのスペースがあります。それ以外の場合は、その31ビットだけを消費します。いずれにしても、値は5つのBase-84数字に収まります。非常に簡単です。

ランダムな入力では、これはグループあたり約31.95ビット、つまり文字あたり6.39ビットになります。出力はバイナリ入力より約25.2%大きくなります。ほぼBase85です。

これらの拡張率は、最後の部分的なグループを無視しています。平均値はランダムな入力を想定しています。

0xffで満たされた入力は、すべてのフルグループが31ビットしか消費しないことを強制します。これが最悪ケースで、約29%の拡張率になります。

ほとんどのファイルシステムは、名前を255バイトに制限しています。アルファベットはASCIIなので、これは255文字です。5は255を割り切れるため、最大長のファイル名でさえ、部分的なグループに失われるビットがない、完全なグループのみを保持します。Base84は、パディングされていないBase64の191バイトに対して、197バイトの入力のスペースを保証します。

Unix専用の名前

Unixのファイル名には、Windowsが拒否するほとんどの句読文字を含めることができます。NULと/はファイル名内では禁止されています。Linuxのパス名ドキュメントには、ルールとファイルシステム固有の制限が記載されています。

zig-base91のfilesystemバリアントは、標準Base91アルファベットのスラッシュをアポストロフィに置き換えます。ランダムな入力で文字あたり約6.51ビットをパックし、約23%の拡張率をもたらします。

Unix専用の名前の場合は、そのバリアントを使用してください。標準Base91にはまだ/が含まれており、両方のアルファベットにはWindowsが拒否する文字が含まれています。

Base91はhf-mount-encryptedで使用されており、これはHugging Faceバケットをマウントするためのツールの透過的な暗号化を追加します。バックエンドはLinuxで実行されるため、Windows互換性は関係ありません。

Windowsデバイス名

Windowsは、大文字小文字を区別せずに CON、NUL、COM1 などのデバイス名を予約しています。

Base84の5文字パッキングには便利な副作用があります。標準アルファベットを使用すると、エンコーダーは短い入力であっても予約デバイス名をスペルできません。

3文字の出力は常にAからJで終わります。これにより、大文字小文字を区別せずに CON、PRN、AUX、NUL が除外されます。

4文字の出力は常に大文字またはa、b、cで終わります。数字で終わることはできないため、COM1からCOM9およびLPT1からLPT9も不可能です。Windowsが予約する上付き数字もアルファベットにはありません。

アルファベットにはドットがないため、予約名に拡張子が続くことも不可能です。

Base64などの他のスキームとは異なり、これらの名前を回避するためにパディングや特別な処理は必要ありません。

大文字小文字を区別しないファイルシステムはどうなるか？

Base84は大文字と小文字を区別するため、異なるエンコードされた名前が大文字小文字を区別しないファイルシステムで等しく比較される可能性があります。

暗号化された名前の場合、衝突確率はエンコードされる疑似乱データの量に依存します。TurboCryptは、HCTR2を適用する前に短い名前を16バイトにパディングします。この暗号化をランダムな置換としてモデル化すると、最も短い名前でさえ128ビットの暗号文が得られます。

これらの16バイトは20または21文字にエンコードされます。すべての文字がアルファベットであると仮定しても、大文字小文字のみが異なるスペルは最大で2^21通りあります。

有効なスペルごとに、2^128通りの可能な入力のうち最大1つを表すため、2つの異なる暗号化された名前間のケース衝突の上限は、2^21 / 2^128 = 2^-107 となります。より長い暗号文は、よりタイトな境界を与えます。

同じディレクトリ内のn個の異なる名前の場合、バースデーバウンドは最大でn(n - 1) / 2^108 の衝突確率を与えます。10億個の名前があっても、これは3.1 × 10^-15 未満です。無視できるレベルです。