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

Проблема

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

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

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

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

Третий вариант — выполнять расшифровку непосредственно в SQL-функции. Тогда сортировка формально останется на стороне базы данных. Но тут возникают новые проблемы. Сортировка по результату функции не позволит использовать индексы B-tree по зашифрованным данным, поэтому планировщик, скорее всего, будет выполнять последовательное чтение и сортировку, что вызовет катастрофическое падение производительности. Можно было бы построить функциональный индекс, который заполнялся бы при вставке, но хранить его Postgres будет в открытом виде. В дополение к этому все так же будет актуальна проблема с утечкой ключа. Такой вариант тоже не подходит.

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

Криптографические схемы сортировки

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

  1. OPE (Order-Preserving Encryption) — порядок шифротекстов совпадает с порядком исходных значений. Для выполнения ORDER BY и выборки диапазонов такое решение подходит идеально, так как позволяет использовать стандартные B-Tree индексы. Однако такой подход раскрывает значительный объём информации о порядке и распределении данных, что в большинстве случаев делает возможными статистические атаки. Из-за этого OPE в настоящее время считается устаревшим и в основном используется более безопасный ORE.

  2. ORE (Order-Revealing Encryption) — порядок данных не сохраняется напрямую, однако существует специальная процедура сравнения шифротекстов. Готовых решений тут не много, но они есть. Например, расширение pg_enquo добавляет в Postgres новые типы данных и операторы, которые поддерживают сортировку и выборку диапазонов по зашифрованным данным. Тем не менее ORE неизбежно раскрывает относительный порядок значений, а также использует шифротексты довольно большой длины (от разов до десятков раз от исходных данных). При этом само pg_enquo требует компиляции из исходников и не поддерживается в облачных базах данных. Несмотря на все недостатки решение выглядит реалистичным, запомним его.

  3. SSE (Searchable Symmetric Encryption) — продвинутый криптографический подход, который создает отдельные безопасные структуры данных. Хорошо подходит для поиска по зашифрованным данным, но сам по себе не решает задачу их сортировки. STE (Structured Encryption) — комбинированный вариант, который совмещает в себе SSE и ORE, добавляя возможность сортировки. Для Postgres существует коммерческое решение по подписке — CipherStash Proxy, которое дополняет структуру базы данных новыми столбцами, и добавляет отдельный сервисный слой, который проксирует запросы между приложением и базой. Для моей задачи такое решение выглядело как стрельба по воробьям из Звезды Смерти.

  4. FHE (Fully Homomorphic Encryption) — священный грааль криптографии. В теории позволяет выполнять широкий спектр вычислений над зашифрованными данными без их предварительной расшифровки. Однако операции сравнения не относятся к числу базовых возможностей таких схем и, если реализуются, требуют дополнительных вычислительных конструкций. Для PostgreSQL существуют лишь отдельные экспериментальные проекты и исследовательские работы. При этом размер шифротекстов может увеличиваться в тысячи раз по сравнению с исходными данными, а вычислительный оверхед становится просто запредельным. Судя по открытым данным, потребляемые ресурсы настолько велики, что даже в серьёзных приложениях такой подход, если и используется, то лишь точечно. Что этот вариант для моей задачи невозможен, можно и не упоминать.

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

Шаг назад

Я решил посмотреть на условия задачи еще раз.

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

И тогда я понял, что решал не ту задачу.

Действительно ли сортировка обязательно должна выполняться именно по зашифрованному столбцу? На самом деле нет. Базе данных совершенно не важно, по какому значению выполнять ORDER BY, если это значение монотонно изменяется вместе с исходной строкой. Значит, вместо самих зашифрованных данных можно хранить отдельный числовой индекс и сортировать уже по нему.

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

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

Идея, которая пришла мне в голову, заключалась в том, чтобы строить такой индекс на основе кодовых точек Unicode. Они уже задают естественный порядок символов, который нам и нужен. Да, такой подход не учитывает правила лингвистической сортировки, реализованные, например, в ICU. Однако в рамках моей задачи это было не критично.

Оставалось лишь придумать способ объединить несколько символов в один индекс. Идея показалась вполне разумной, и я решил развить её.

Собираем собственный индекс

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

Сначала я попробовал использовать позиционное взвешивание с основанием 10. То есть кодовая точка каждого символа умножалась на 10 в степени, зависящей от его позиции в подстроке, после чего все значения суммировались:

INDEX = Σ (CODEPOINT(i) × 10^(N - 1 - i))

N — количество символов, участвующих в построении индекса;
i — порядковый номер символа, начиная с нуля (0 — первый символ);
CODEPOINT(i) — кодовая точка i-го символа.

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

"cut" = (99 × 100) + (117 × 10) + (116 × 1) = 11186
"eat" = (101 × 100) + (97 × 10) + (116 × 1) = 11186

Разумеется, при еще большей разнице между отдельными весами сортировка становилась полностью некорректной.

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

INDEX = Σ (CODEPOINT(i) × WEIGHT_FACTOR^(N - 1 - i))

Оставалось лишь подобрать параметры таким образом, чтобы они обеспечивали экспоненциальное доминирование старших позиций над младшими, не выходя при этом за пределы диапазона 64-битного типа BIGINT.

Добавляем квантование

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

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

Значит, одного индексирования недостаточно. Нужно было намеренно уменьшить точность индекса, сохранив при этом его пригодность для сортировки. Для этого можно было выполнить квантование — превратить множество точных значений в конечное число диапазонов (бакетов).

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

Тогда я попробовал выполнять квантование уже после вычисления итогового индекса:

FINAL_INDEX = INDEX // (2 ^ COARSE_SHIFT)

Это сохранило монотонность. Подстроки, попавшие в один диапазон, стали считаться эквивалентными, а их взаимный порядок база данных могла определять самостоятельно.

Подбираем параметры

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

В качестве рабочего варианта я остановился на следующих значениях:

WEIGHT_FACTOR = 40
COARSE_SHIFT = 17

Если считать, что строка может содержать любой символ Unicode (максимальная кодовая точка — 0x10FFFF), то при выбранных значениях WEIGHT_FACTOR и COARSE_SHIFT максимальное безопасное значение N, при котором итоговый индекс ещё помещается в BIGINT, получается равным 12.

Если предположить, что будут использоваться только символы ограниченного алфавита (например, латиницы или кириллицы), максимально допустимое значение N может быть больше 12. Однако практической необходимости в этом для меня не было. Я остановился на значении N = 6: оно оставляет большой запас по диапазону BIGINT и одновременно уменьшает объём информации, потенциально раскрываемой индексом.

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

Практическая реализация

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

Код для вычисления индекса выглядит следующим образом:

import unicodedata

INDEX_LENGTH = 6
WEIGHT_FACTOR = 40
COARSE_SHIFT = 17

# Precomputed position weights
_WEIGHTS = tuple(WEIGHT_FACTOR ** i for i in range(
    INDEX_LENGTH - 1, -1, -1))

# Precomputed quantization divisor
QUANT_DIVISOR = 2 ** COARSE_SHIFT

# Unicode normalization form used during canonicalization
NORMALIZATION_FORM = "NFC"


def _canonicalize(value: str) -> str:
    """Case-insensitive canonicalization of a string."""
    return unicodedata.normalize(NORMALIZATION_FORM, value.casefold())


def get_index(value: str) -> int:
    """Compute a quantized sorting index for ORDER BY clauses."""
    s = _canonicalize(value)

    idx = 0
    for pos, ch in enumerate(s[:INDEX_LENGTH]):
        idx += ord(ch) * _WEIGHTS[pos]

    return idx // QUANT_DIVISOR

Пример

При использовании подобранных параметров можно рассмотреть небольшой пример:

Значение

Индекс

Alan

77939

Albert

77939

Alice

77943

Brian

78841

Brittany

78841

Charles

79423

Daniel

80074

Нетрудно заметить, что после квантования строки Alan и Albert попадают в один диапазон, их порядок друг относительно друга база данных определит самостоятельно. То же самое происходит с Brian и Brittany.

В результате получается не идеальная алфавитная сортировка, а её детерминированное приближение, которое сохраняет полезную информацию о порядке, сознательно жертвуя точностью.

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

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

Прозрение

До сих пор не понимаю, как мне удалось пройтись по всем криптографическим схемам сортировки и ни разу не наткнуться на суррогатный ранг — OBI (Ordered Blind Index). Тот самый практический компромисс, часто используемый вместо криптографической акробатики.

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

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

a

b

c

d

CODE

97

98

99

100

RANK

0

1

2

3

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

INDEX = Σ (RANK(i) × ALPHABET_SIZE^(N - 1 - i))

RANK(i) — позиция символа в заранее заданном алфавите.

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

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

Так что мой первоначальный вариант всё же имел одну полезную особенность — он позволял уменьшать степень раскрытия информации, сознательно жертвуя точностью сортировки.

Конец

В моем случае все закончилось изменением архитектуры, так что в итоге ни один из рассмотренных вариантов не пригодился.

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

Напоследок хотелось бы спросить: сталкивался ли кто-нибудь с похожей задачей и удалось ли найти более удачный компромисс?