TL;DR: В статье рассказано, какие утечки метаданных могут возникать при хранении зашифрованных файлов, почему фрагментация это не лучший способ с ними бороться, и как решение одних проблем создает другие.

1. Небольшое теоретическое вступление

Предположим, что нам надо организовать локальное хранение чувствительных данных в формате файлов, содержимое которых должно быть защищено. Посмотрим на распространенные способы организации такого хранения:

Container / block device. Единицей хранения является контейнер, раздел или диск целиком. Внутренняя файловая система полностью скрыта. Очевидно, что определить количество файлов, структуру каталогов или размеры отдельных объектов внутри такого хранилища невозможно. Такой подход обеспечивает минимальную утечку метаданных, но очень плохо подходит для синхронизации и резервного копирования на уровне отдельных файлов. Примеры: VeraCrypt, LUKS.
Per-file. Единицей хранения является отдельный файл. Каждый исходный файл хранится в виде отдельного зашифрованного файла, а каталоги отображаются в структуру каталогов зашифрованного хранилища. Такой подход обеспечивает высокую производительность, эффективную синхронизацию и простое резервное копирование, но раскрывает часть метаданных: структуру дерева, количество объектов, относительные размеры файлов. Примеры готовых реализаций: gocryptfs, EncFS, eCryptfs, SecureFS.
Chunk / block-based. Файлы разбиваются на множество независимых блоков, каждый из которых становится независимой единицей хранения. Это может существенно уменьшить количество раскрываемых метаданных, однако требует более сложной организации хранения и увеличивает накладные расходы на управление блоками. При этом синхронизация и резервное копирование могут по-прежнему эффективно работать на уровне отдельных блоков. Самый распространенный пример — CryFS.
Application-managed. Единицей хранения является отдельный файл, но его шифрованием управляет приложение, а файловая система используется только как носитель данных. Иными словами, приложение самостоятельно шифрует файлы и раскладывает их по файловой системе. Такой подход дает максимальную свободу проектирования, но и несет дополнительные риски.

Выбор конкретного подхода определяется требованиями задачи. Например, контейнерное хранилище плохо подходит для инкрементного резервного копирования, тогда как шифрование отдельных объектов на уровне приложения удобно для передачи данных между независимыми системами без общего файлового окружения.

И правильный выбор необходимо сделать еще на этапе проектирования архитектуры приложения. Цена исправления такой ошибки в будущем может оказаться очень высокой. И я совершил такую ошибку.

2. Моя первая ошибка

Я работал над файловым хранилищем, рассчитанным на автономную работу в пределах одного хоста. Иными словами, это была архитектура local-first и на это следует обратить внимание — готовые файловые системы с прозрачным шифрованием очень хорошо подходили для такой задачи.

Но по какой-то причине я решил сделать шифрование на уровне приложения: каждый файл шифровался независимо от остальных и сохранялся в нужной директории. Настоящие названия файлов и директорий заменялись случайными uuid-ами, а в базу данных записывались метаданные, необходимые для быстрого поиска по содержимому хранилища.

Опустим пока что подробности разработки (это отдельная тема для обсуждения), перемотаем время вперед и перейдем к моменту, когда приложение было практически готово. Передо мной встал вопрос оценки рисков, связанных с хранением данных.

В тот момент я и увидел проблему в архитектуре: файлы хранились внутри зашифрованного слоя, а база данных — нет. При этом в рамках выбранной модели угроз, предполагавшей компрометацию физического хоста, и то, и другое должно было являться единым объектом защиты. То есть граница шифрования была проведена не там, где проходила граница атаки.

Сама по себе компрометация хоста не позволяла расшифровать файлы — ключ шифрования хранился отдельно и в состоянии покоя был недоступен. Однако база данных могла дать полный обзор структуры хранилища: иерархию директорий, названия файлов, их размеры, временные метки и другие метаданные. Более того, база позволяла быстро найти и извлечь любой зашифрованный файл для дальнейшего анализа.

Ситуация требовала исправления. И тогда я допустил вторую ошибку.

3. Моя вторая ошибка

Обнаруженная проблема носила фундаментальный характер и нуждалась в полном пересмотре всей архитектуры. В конечном счете пришлось бы переписать приложение почти с нуля, но я решил срезать путь.

Вместо этого я поступил обычным образом: разбил одну большую проблему на несколько маленьких и стал решать их по отдельности.

Во-первых, нужно было скрыть метаданные, хранившиеся в базе данных. Я решил, что достаточно будет зашифровать чувствительные поля. Другими словами, я попытался частично распространить слой шифрования на базу данных. Решение выглядело рабочим, если бы не одно обстоятельство: по многим из этих полей предполагалась сортировка. И реализация этой сортировки — это отдельная история со своими драматическими поворотами. Она описана в этой статье: Как я решал задачу сортировки зашифрованных строк.

Во-вторых, мне хотелось уменьшить количество доступных метаданных и осложнить возможность атаки на отдельные файлы. Проблема заключалась в соответствии «один исходный файл — один зашифрованный файл». Поскольку каждый файл представлял собой самостоятельный криптографический объект, его можно было извлечь из хранилища и анализировать независимо от остальных.

И тогда, чтобы осложнить анализ отдельных зашифрованных файлов, я решил использовать фрагментацию. Другими словами, я решил дополнить архитектуру application-managed механизмом фрагментации, характерным для подхода chunk / block-based.

4. Ставим задачу

Итак, задача — представить каждый зашифрованный файл в виде набора фрагментов. Это не усилит криптографическую защиту, но сделает границы отдельных файлов неочевидными. Атакующий по-прежнему сможет видеть зашифрованные объекты, но для извлечения конкретного зашифрованного файла ему нужно будет определить, какие фрагменты и в каком порядке собирать.

Базу данных пришлось дополнить таблицей «один-ко-многим», связывающей файлы с их фрагментами. Это позволяло приложению автоматически собирать исходный файл, а для пользователя весь процесс оставался полностью прозрачным. Содержимое таблицы было зашифровано, на первый взгляд этого было достаточно, и я перешел к самой фрагментации.

5. Фрагментация на фиксированное количество частей

Самый простой и очевидный вариант — разбивать каждый файл на фиксированное количество фрагментов. Например, на 4, 8 или 16 частей независимо от его размера. Но почти сразу становится заметен недостаток.

При фиксированном количестве фрагментов размер каждого из них напрямую зависит от размера исходного файла. Например, файл размером 80 МБ после разделения на восемь частей превратится в восемь фрагментов примерно по 10 МБ каждый.

Получается, что метаданные, связанные с размерами файлов, никуда не исчезают. Они просто перемещаются с уровня файлов на уровень фрагментов. Достаточно найти заданное количество фрагментов близкого размера, и с высокой вероятностью они будут принадлежать одному файлу.

Я устраняю одно соответствие, но сразу создаю другое.

Решение неполноценное. Оно действительно размывает границы файлов, но одновременно создает новые закономерности, доступные для анализа.

6. Фрагментация на части фиксированного размера

Недостатки предыдущего подхода подсказывают очевидную альтернативу: вместо количества фрагментов зафиксировать их размер.

Например, разбивать все зашифрованные данные на блоки по 1 МБ. Тогда почти все фрагменты будут иметь одинаковый размер независимо от размера исходного файла. Выглядит лучше, но возникают новые проблемы.

Во-первых, количество фрагментов определяется размером исходного файла. Например, файл размером 400 МБ породит около 400 фрагментов, тогда как файл размером 40 КБ по-прежнему будет представлен единственным объектом. В результате большие файлы потребуют больше ресурсов, а вероятность их повреждения возрастет (потеря любого из множества фрагментов означает потерю всего файла).

Во-вторых, если файл полностью помещается в один блок, он снова становится единственным объектом хранения.

Дополнительно возникает практический вопрос выбора размера блока. Маленькие блоки лучше скрывают структуру файлов, но резко увеличивают количество объектов в хранилище. Большие блоки уменьшают накладные расходы, но для небольших файлов фрагментация теряет смысл.

Другими словами, утечка метаданных никуда не исчезает — она лишь меняет форму. Я снова устраняю одну закономерность, но создаю другую.

7. Адаптивный выбор размера фрагментов

Оба предыдущих подхода имеют общий недостаток: они используют одно правило на все случаи. Напрашивается более гибкое решение: отказаться от единственного правила и выбирать размер фрагмента в зависимости от размера самого файла.

Можно заранее определить размерную линейку фрагментов (например, 256 Кб, 512 Кб, 1 Мб, 2 Мб и так далее), а затем для каждого файла выбирать тот, который обеспечивает разумное количество частей. Большие файлы больше не будут распадаться на тысячи объектов, а небольшие не будут избегать фрагментации.

Однако, если алгоритм выбора размера будет детерминированным, то одинаковые файлы всегда будут фрагментироваться одинаково. Это означает, что связь между размером файла и структурой хранения становится слабее, но не исчезает полностью.

Следующий шаг напрашивался сам собой: отказаться от полностью детерминированного поведения и для каждого случая выбирать размер фрагмента из нескольких близких вариантов. Например, если оптимальный размер определен как 1 МБ, алгоритм может выбрать 512 КБ, 1 МБ или 2 МБ. Все варианты остаются достаточно близкими к первоначальному, но итоговая структура становится менее предсказуемой. В результате даже две копии одного и того же файла могут храниться по-разному.

Полностью устранить утечку метаданных такой подход не способен, но он значительно ослабляет связь между размером файла и структурой его хранения.

На тот момент мне казалось, что этого уже достаточно. И тогда обнаружилась следующая проблема.

8. Время

Новой проблемой стало время. При записи одного файла все его фрагменты создавались практически одновременно. В результате они получали почти одинаковые временные метки ctime и mtime, что снова позволяло группировать их между собой.

Первой мыслью было принудительно изменять эти метки. Но если с mtime все достаточно просто, то ctime (время изменения inode) определяется файловой системой и недоступно для модификации извне.

К этому моменту бесконечный поиск новых компромиссов мне уже порядком надоел, но сдаваться было рано. И на этот раз я видел два возможных варианта.

Первый вариант — при каждой записи файла создавать несколько пустых фрагментов, а саму запись производить в случайные пустые фрагменты, которые были созданы ранее.

Второй вариант — при каждой записи файла дополнительно перезаписывать несколько случайных фрагментов из записанных ранее.

Мне не очень хотелось подмешивать к настоящим данным мусорные и я выбрал второй вариант.

9. Алгоритм перемешивания

Далее возник логичный вопрос: сколько именно фрагментов нужно затрагивать?

Одной крайностью была перезапись всех фрагментов. Это полностью бы разрушало связи, основанные на времени создания файлов. Но цена была непомерной: даже изменение одного файла приводило бы к полной перезаписи всех остальных. Фактически стоимость записи любого файла становилась пропорциональной размеру всего хранилища.

Другой крайностью было пересоздание только одного случайного фрагмента. Накладные расходы становились минимальными, но по мере роста хранилища такой объем перемешивания уже почти не влиял на общую картину.

Понятно, что нужен был очередной компромисс.

Казалось очевидным сделать объем перемешивания пропорциональным размеру хранилища. Простой расчет показал, что прямая зависимость была слишком агрессивной: по мере роста хранилища стоимость каждой операции увеличивалась слишком быстро. Я остановился на логарифмической зависимости:

shuffle_count = ceil(log2(total_fragments + 1))

При таком подходе получается следующая картина:

100 fragments      → 7 recreations
1,000 fragments    → 10 recreations
10,000 fragments   → 14 recreations
100,000 fragments  → 17 recreations

Такое решение не уничтожает временные взаимосвязи полностью. Оно лишь постепенно размывает их, не заставляя систему постоянно переписывать значительную часть данных.

10. Атомарность

Когда казалось, что конец уже близок, фрагментация явила мне последнюю проблему — атомарность. Поскольку каждый файл теперь был представлен множеством независимых объектов, каждый из которых записывался отдельно, то любая ошибка в процессе операции могла оставить хранилище в несогласованном состоянии.

Да, POSIX предоставляет атомарность для операций над отдельными объектами, но не для группы независимых файлов. Эту проблему следовало решать самостоятельно на уровне приложения. И я стал размышлять над решением.

Сначала новые фрагменты нужно записать под промежуточными именами (на этом этапе они еще не являются частью хранилища). После записи каждого фрагмента нужно сбросить данные на диск и проверить их целостность. Только после успешной записи всех фрагментов приложение должно обновить базу данных. Именно эта операция должна стать точкой фиксации.

Но это все равно не делало всю последовательность операций атомарной. Файловая система и база данных по-прежнему оставались двумя независимыми системами, между которыми невозможно провести общую транзакцию. Это означало, что любое аварийное завершение приложения или отключение питания в неподходящий момент неизбежно оставляло на диске осиротевшие фрагменты.

Следовательно, нужен был механизм сборки мусора, который находил бы и удалял лишнее.

И тут я наконец признал, что с меня достаточно компромиссов. Каждый новый шаг действительно немного усложнял анализ хранилища, но логика приложения становилась несоразмерно сложнее, а данные — все более хрупкими. Стало очевидно, что проблема уже давно не в фрагментации, а в самой архитектуре.

11. Конец

Теперь мне нужно было по своим собственным шагам вернуться в тот момент, когда была допущена архитектурная ошибка, и исправить ее.

Если бы я изначально строил приложение поверх готовой файловой системы с прозрачным шифрованием (например, gocryptfs), вся цепочка последующих проблем просто не возникла бы. База данных и файлы находились бы внутри единого зашифрованного пространства, поэтому не пришлось бы бороться с утечками метаданных, придумывать алгоритмы фрагментации и перемешивания, ломать голову над псевдоатомарностью операций и сборкой мусора, изобретать сортировку зашифрованных данных.

Самый важный вывод, который я сделал для себя: архитектурные ошибки остаются навсегда. Их можно долго пытаться компенсировать, но рано или поздно за них придется заплатить. И стоимость исправления со временем будет только расти.

Как я при помощи фрагментации решал одни проблемы и создавал другие