Эта статья будет полезна инженерам, работающим с базами данных SQL, и инженерам-криптографам. Searchable Encryption как раз находится на стыке баз данных и криптографии и требует знания обоих предметов. Статья освещает внутреннее инженерное исследование, которое проводилось в компании Cossack Labs перед созданием модуля поискового шифрования для одного из наших программных продуктов, ориентированного на комплексную защиту SQL баз данных (Acra).
Перед нашей инженерной командой стояла задача найти подходящий прототип схемы поискового шифрования, на основе которого можно было бы построить собственную схему. Основными критериями при отборе прототипов были:
Шифрование делает доступ к данным невозможным без знания криптографических ключей для внутренних и внешних атакующих, но в то же время исключает возможность поиска. Одно из тривиальных решений этой проблемы — загрузить всю базу данных, расшифровать ее локально и произвести поиск уже по открытым данным. Для большинства приложений такой подход будет непрактичным в связи со значительными объемами данных. Другой метод — позволить серверу расшифровать данные, выполнить запрос и вернуть пользователю результат. В этом случае снижается уровень безопасности, так как данные, защищенные шифрованием, раскрываются серверу. Вместо этого требуется поддержка максимально возможной функциональности поиска с минимальной потерей конфиденциальности данных. Это называется поисковым шифрованием (searchable encryption — SE). На рис. 1 изображен абстрактный принцип работы SE.
Рис. 1. Абстрактная схема поискового шифрования
Схема поискового шифрования позволяет удаленному сервису хранения данных производить поиск по зашифрованным данным без получения информации об открытых данных. Некоторые схемы реализуют это с помощью специальных техник шифрования, поддерживающих поиск, в то время как другие позволяют клиенту сгенерировать специальный индекс и сохранить его вместе с зашифрованными данными на стороне сервера. Для поиска клиент генерирует так называемый trapdoor — предикат, позволяющий серверу проверить, включать ли зашифрованное ключевое слово в результаты поиска.
В последнее время актуальность поискового шифрования существенно возросла в связи с принятием GDPR, который регламентирует порядок защиты персональных данных и приватность граждан Европейского союза. Другим примером могут быть требования международных стандартов и нормативные требования многих государств по всему миру о шифровании медицинских данных (HIPAA) или данных банковского сектора (PCI DSS).
Первая SE-схема (ее первое формальное научное описание) была предложена в 2000 г. Сегодня академическим сообществом предложено более 50 описаний схем с разнообразной функциональностью. Индустрия также предлагает большое количество решений, готовых к использованию (Bitglass, CipherCloud, Crypteron, IQrypt, Kryptnostic, Google’s Encrypted BigQuery, Microsoft’s SQL Server 2016, Azure SQL Database, PreVeil, SkyHigh, StealthMine и др.).
Хорошо известно [link 1, link 2], что проектирование SE-схемы — это нахождение компромисса (tradeoff) между безопасностью, функциональностью запросов, производительностью и удобством использования (рис. 2). Когда в схеме улучшается один из аспектов, обычно это приводит к ухудшению одного или сразу нескольких других аспектов. Безопасность обычно определяется информацией о пользовательских данных, которая становится известна атакующему в процессе работы схемы (leakage). Функциональность запросов определяется типами запросов, которые поддерживаются. Запросы обычно выражаются с помощью стандартных языков (например, SQL).
Производительность характеризуется структурами данных и механизмами индексирования в базе данных наряду с вычислительными и коммуникационными издержками.
Рис. 2. Баланс параметров схемы поискового шифрования
Предположим, что атакующий имеет доступ к зашифрованным данным на сервере и может наблюдать пользовательские запросы. Также атакующий знает, какое количество записей возвращается в ответ на каждый запрос. Если это количество уникальное, следовательно, запрос также уникален и его можно различить среди множества всевозможных запросов.
Другой способ извлечения метаданных о зашифрованной пользовательской информации заключается в следующем. Предположим, что атакующий получил знание об одном из запросов с поисковым выражением <Last_Name=Smith>. Предположим также, что оба различных запроса с поисковыми выражениями <Fisrt_Name=John> и <Fisrt_Name=Matthew> возвращают 1000 записей. Атакующий может проверить, сколько общих записей у последних (неизвестных) запросов вместе с первым (известным). К примеру, может быть 100 записей с именем John Smith и только 10 записей с именем Matthew Smith. Сверяя такие пересечения с ранее известными запросами, противник может идентифицировать Fisrt_Name. Такой подход итеративно идентифицирует запросы и использует их как дополнительные ограничения для дальнейшего определения неизвестных запросов.
Среди наиболее известных и мощных атак такого рода можно выделить count-атаку, способную восстанавливать до 40% ключевых слов, если их распределение невелико (до 5000), при условии, что атакующему известно 80% записей. Другой пример — атака иерархического поиска (hierarchical search attack). Она является расширением count-атаки и способна при таком же распределении восстанавливать до 80% ключевых слов при утечке только лишь 40% записей, однако с допущением, что противник активен и способен включать свои записи в зашифрованные пользовательские данные.
Примечание. Данные для СryptDB, Blind Seer, OSPIR-OXT и SisoSPIR взяты из оригинальных работ, описывающих эти системы. Данные для CipherSweet получены на основании собственного экспериментального анализа и могут носить субъективный характер.
CryptDB поддерживает максимальную функциональность современных систем управления базами данных SQL с потерей производительности до 30%. Авторы Blind Seer сообщают, что их падение производительности колеблется в пределах 20-300% для большинства запросов. Авторы OSPIR-OXT сообщают, что в некоторых случаях их система даже превосходит MySQL 5.5 с «холодным» кешем и на 1 порядок (1000%) медленнее, чем MySQL с «теплым» кешем. Падение производительности у SisoSPIR составляет порядка 500% на некоторых видах запросов (equality и range).
В то же время предоставляемый системами уровень безопасности различен. При использовании атрибута в запросе CryptDB раскрывает статистику всех значений этого атрибута в таблице. Blind Seer и OSPIR-OXT также раскрывают серверу метаданные о зашифрованной пользовательской информации, возвращаемой в результате запроса. Поэтому эти системы стоит использовать в случае редкого обращения к данным.
SisoSPIR обеспечивает высокий уровень защиты даже в случае регулярных запросов (что является одним из требований production-ready-систем) за счет введения дополнительного инфраструктурного компонента — helper-сервера. При этом SisoSPIR требует, чтобы сервер, на котором хранятся пользовательские данные, не имел возможности «сговориться» (collude) с helper-сервером.
CipherSweet поддерживает наименьшую функциональность запросов (equality) и имеет относительно низкую производительность, однако предоставляет высокий уровень безопасности за счет простого и понятного криптографического дизайна. Следует отметить, что CipherSweet (в отличие от систем, предложенных академическими исследователями) использует технику слепого индексирования (blind indexing technique), которая зародилась в инженерном сообществе и учитывает многие практические проблемы. Этот факт склонил нашу инженерную команду к выбору CipherSweet как прототипа для нашего программного продукта.
Для внесения нулевой строки в такую таблицу можно использовать такой INSERT-запрос (псевдо-SQL):
INSERT INTO table VALUES (data_1, data_2)
Для поиска записей по атрибуту Field_A можно использовать такой SELECT-запрос:
SELECT * FROM table WHERE Field_A = data_1
Результатом такого запроса будет таблица, содержащая две записи: record_0 и record_1.
При зашифровании данных сервер теряет возможность производить сравнение Field_A = data_1. Модифицируем исходную таблицу добавлением атрибута Field_A_index, в котором будут содержаться метаданные о данных, помеченных атрибутом Field_A (табл. 3). Теперь можно зашифровать данные, используя криптографически стойкий (CPA secure) блочный шифр (например, AES-256-GCM) по атрибуту Field_A, а для того, чтобы работало сравнение, нужно в индекс записать результат применения к данным криптографически стойкой (PRF) псевдослучайной функции (например, PBKDF2 или Argon2). Обозначим операцию шифрования с помощью функций Enc/Dec (зашифрование и расшифрование соответственно) и операцию вычисления псевдослучайной функции PRF. Табл. 4 демонстрирует порядок хранения данных на сервере.
Для реализации описанного принципа требуется:
INSERT INTO table VALUES (index_1, encrypted_data_1, data_2)
где index_1=PRF(data_1), encrypted_data_1=Enc(data_1).
SELECT-запрос для выборки по атрибуту Field_A преобразуется в такую форму:
SELECT * FROM table WHERE Field_A_index=index_1
где index_1 = PRF (data_1). После получения результата запроса приложение может воспользоваться функцией Dec и расшифровать данные по атрибуту Field_A из записей record_0 и record_1.
Отметим, что криптографические ключи опущены в описании для упрощения. Подразумевается, что шифрование и псевдослучайная функция используют два различных ключа.
Любопытный читатель может заметить важную особенность в контексте безопасности. Результат PRF будет всегда одним и тем же для двух одинаковых фрагментов данных: значения индексов (атрибут Field_A_index) для record_0 и record_1 будут одинаковыми, так как они оба вычислены по data_1. Это — потенциальная утечка, потому что сервер на основе анализа зашифрованных данных и их индексов (к которым он потенциально имеет доступ) может определить, какие записи в таблице содержат одинаковые значения зашифрованных данных по атрибутам, поддерживающим поиск (Field_A в рассматриваемом случае). Чтобы уменьшить негативные последствия этой утечки, CipherSweet предлагает хранить на сервере усеченное значение индексов (табл. 5).
Предположим, что псевдослучайная функция генерирует индексы размером 64 байта. «Отдавая» серверу усеченное значение индекса (размер < 64) можно снижать последствия потенциальной утечки схемы, тем самым повышая безопасность. Однако при этом сервер не сможет однозначно определять записи, которые необходимо включать в результат запроса. То есть растет вероятность ошибки включения в результат запроса неверной записи (false positive). В этом случае на приложение возлагается ответственность «отфильтровать» все нерелевантные записи после получения результата запроса от сервера и расшифрования данных.
Параметр усечения (один из параметров безопасности) может конфигурироваться пользователем. CipherSweet предоставляет специальный планировщик для его расчета:
<?php
use ParagonIE\CipherSweet\Planner\FieldIndexPlanner;
# First, instantiate the planner for a given field
$planner = new FieldIndexPlanner();
# How many rows do you anticipate?
$planner->setEstimatedPopulation(50000);
$recommended = $planner->recommend(14);
var_dump($recommended);
/* array(2) {["min"]=>int(8) ["max"]=>int(14) }*/
Для использования планировщика необходимо: оценить ожидаемое количество записей, включающих атрибуты с зашифрованными данными, и распределить данные, подлежащие защите. В примере выше верхняя граница ожидаемых записей составляет 50 000, а битовое распределение данных (input domain size) — 14 бит. Такое значение распределения характерно для данных, определяющих годы в календаре: 4 целые цифры (2019) могут составить 10 000 различных комбинаций, следовательно, распределение составляет log2 (10 000) ≈ 14. При этом планировщик рекомендует использовать индекс с размером от 8 до 14 бит.
После выбора прототипа схемы поискового шифрования перед нашей инженерной командой стояла задача внедрения схемы в нашу систему комплексной защиты баз данных SQL (Acra [link 1, link 2]).
Центральным компонентом этой системы является прокси-сервер, изолирующий функционал безопасности (шифрование, SQL firewall и Intrusion Detection System) таким образом, чтобы работа приложения с базой данных была прозрачной (transparent). При этом приложению не требуется система управления криптографическими ключами и их хранения (достаточно сложная проблема, возникающая при внедрении любых криптографических операций): эта функция делегируется прокси-серверу.
Использование проксирования в комбинации с техникой слепого индексирования позволяет прозрачным для приложения образом внедрить возможность поиска по зашифрованным данным (за счет введения дополнительного инфраструктурного компонента — proxy (рис. 3)).
Рис. 3. Использование прокси-сервера, реализующего функционал безопасности
Для обеспечения прозрачности прокси-сервер также отвечает за модификацию запросов, приходящих от приложения, перед отправкой на удаленный сервер управления базой данных (SQL query — изначальный запрос от приложения, SE query — модифицированный запрос от прокси-сервера).
Нам пришлось портировать реализацию техники слепого индексирования на Go (в CipherSweet она выполнена на PHP и Node.js) под уже существующий прокси-сервер. Криптографические операции реализованы с использованием стандартной библиотеки Go, а также криптографической библиотеки Themis. Система является production-ready и DevOps-friendly: поддерживает метрики, логирование, трейсинг и готова к интеграции и эксплуатации в существующие инфраструктуры и приложения.
Отметим также, что проксирование позволяет устранить неудобство, связанное с false positives, и вероятности включения сервером нерелевантных записей из базы данных в результат запроса при усечении индекса с целью повышения безопасности. Фактически прокси-сервер запоминает запрос от приложения (SQL query), модифицирует его (SE query) в соответствии с техникой слепого индексирования, отправляет на сервер и затем применяет его к ответу сервера после расшифрования (decrypted results). Однако при использовании такой фильтрации наблюдается падение производительности, так как нерелевантные записи могут быть отбракованы только после их расшифрования.
Для инициализации таблицы в базе данных использовались такие SQL-запросы:
DROP TABLE IF EXISTS test_raw;
DROP SEQUENCE IF EXISTS test_raw_seq;
CREATE SEQUENCE test_raw_seq START 1;
CREATE TABLE test_raw (id, INTEGER PRIMARY KEY DEFAULT nextval(‘test_raw_seq’), plaintext BYTEA, ciphertext BYTEA).
Стандартный функциональный индекс производительности для экспериментов с различной величиной усечения индекса создавался таким SQL-псевдозапросом:
CREATE INDEX IF NOT EXISTS test_raw_ciphertext_secure_index_idx ON test_raw (substr(ciphertext, 1, secureIndexSize));
Прокси-сервер был настроен на зашифрование и поиск по атрибуту ciphertext. Пример INSERT-псевдозапроса от приложения:
INSERT INTO test_raw (plaintext, ciphertext) VALUES (input, input);
Пример SELECT-псевдозапроса от приложения:
SELECT * FROM test_raw WHERE ciphertext=input;
Для оценки производительности мы измеряли общее время задержки запросов (query latency) с помощью следующего эксперимента:
Табл. 6 обобщает результаты (в среднем по 3 запускам) выполнения INSERT-запросов с одним значением записи.
Можно заметить, что шифрование занимает до 7-8% всего времени, вычисление индекса — до 1%, а другие операции (сетевое взаимодействие и логика приложения) занимают 92-93%. Очевидно, что существенное количество запросов соответственно нагружают сетевую подсистему операционной системы. Этим объясняется разброс относительных значений падения производительности, полученных в результате эксперимента.
Примерное значение падения производительности в этом случае находится в пределах 2-12%.
Табл. 7 обобщает результаты (в среднем по 10 запускам) выполнения INSERT-запросов с 1000 значений записей (так называемые bulk-запросы).
Можно заметить, что в этом случае шифрование заняло до 81-83% времени, вычисление индекса — менее 1%, а сетевые операции — до 18%.
Отметим, что в этом случае приложением было отправлено только 50 запросов (в сравнении с 50 000 в предыдущем испытании), поэтому влияние сетевых операций на производительность существенно меньше, но все же заметно.
Падение производительности составляет примерно 1 порядок (10 раз).
Табл. 8 обобщает результаты (в среднем по 10 000 запусков) выполнения SELECT-запросов, возвращающих в ответе пустой результат.
Можно видеть, что сетевые операции заняли до 92% всего времени, а вычисление индекса — оставшиеся 8%. Очевидно, что в этом случае не должны производиться операции расшифрования и фильтрации.
Примерное значение относительного падения производительности составило 170-191%.
Табл. 9 обобщает результаты (в среднем по 10 000 запусков) выполнения SELECT-запросов, возвращающих в точности 1 запись в ответе.
Можно заметить, что в эксперименте с набором данных с распределением в 25 000 ключевых слов и коротким индексом (2 байта) расшифрование занимает значительно больше времени, чем в экспериментах с другими параметрами. Трейсы показали, что функция расшифрования была вызвана 3 раза вместо 1 ожидаемого. Также 2 раза была вызвана функция фильтрации. Это объясняет тот факт, что в ответе от сервера содержались 2 нерелевантные строки, которые были отфильтрованы после расшифрования.
В итоге значение падения производительности существенно колеблется (в пределах 471-1006%).
Табл. 10 обобщает результаты (в среднем по 10 000 запусков) выполнения SELECT-запросов, возвращающих в точности 10 записей в ответе.
Снова можно заметить наличие «пустых» операций расшифрования и фильтрацию в эксперименте с набором данных с распределением в 25 000 ключевых слов и коротким индексом.
Относительная величина падения производительности находится в пределах 1934-2630%.
В соответствии с результатами из табл. 2-6 можно констатировать, что проксирование вносит достаточно значительное падение производительности (вплоть до 2 порядков). Наиболее существенное влияние оказывают криптографические операции (шифрование и расшифрование). Также следует отметить, что результаты SELECT-запросов могут содержать нерелевантные записи при коротких (1-2 байта) значениях индексов. Это может приводить к «пустым» вызовам функций расшифрования и дальнейшему ухудшению производительности.
На наш взгляд, ключевые особенности, которыми должна обладать система поискового шифрования, это:
dou.ua
Перед нашей инженерной командой стояла задача найти подходящий прототип схемы поискового шифрования, на основе которого можно было бы построить собственную схему. Основными критериями при отборе прототипов были:
- безопасность схемы;
- наличие исходного кода;
- практичность и простота интеграции в существующее приложение.
Введение
Быстрое продвижение интернет-технологий способствовало развитию модели «программное обеспечение как сервис» (software as a service) в корпоративном IT-секторе. Модель «база данных как сервис» обеспечивает пользователей возможностью создавать, сохранять, модифицировать и получать данные из удаленного источника, имея доступ к интернету. Поскольку все большее количество данных переносится в облачные сервисы хранения, пользователям требуются гарантии безопасности их данных от внешних угроз утечки из этих сервисов. Кроме этого, безопасность должна обеспечиваться и со стороны самих сервисов, фактически имеющих полный доступ к серверам и, следовательно, к сохраненным данным. Эта же проблема характерна и для сложных распределенных приложений с комплексной микросервисной архитектурой. Для безопасного хранения конфиденциальных данных на недоверенном удаленном сервисе данные должны быть зашифрованы.Шифрование делает доступ к данным невозможным без знания криптографических ключей для внутренних и внешних атакующих, но в то же время исключает возможность поиска. Одно из тривиальных решений этой проблемы — загрузить всю базу данных, расшифровать ее локально и произвести поиск уже по открытым данным. Для большинства приложений такой подход будет непрактичным в связи со значительными объемами данных. Другой метод — позволить серверу расшифровать данные, выполнить запрос и вернуть пользователю результат. В этом случае снижается уровень безопасности, так как данные, защищенные шифрованием, раскрываются серверу. Вместо этого требуется поддержка максимально возможной функциональности поиска с минимальной потерей конфиденциальности данных. Это называется поисковым шифрованием (searchable encryption — SE). На рис. 1 изображен абстрактный принцип работы SE.
Схема поискового шифрования позволяет удаленному сервису хранения данных производить поиск по зашифрованным данным без получения информации об открытых данных. Некоторые схемы реализуют это с помощью специальных техник шифрования, поддерживающих поиск, в то время как другие позволяют клиенту сгенерировать специальный индекс и сохранить его вместе с зашифрованными данными на стороне сервера. Для поиска клиент генерирует так называемый trapdoor — предикат, позволяющий серверу проверить, включать ли зашифрованное ключевое слово в результаты поиска.
В последнее время актуальность поискового шифрования существенно возросла в связи с принятием GDPR, который регламентирует порядок защиты персональных данных и приватность граждан Европейского союза. Другим примером могут быть требования международных стандартов и нормативные требования многих государств по всему миру о шифровании медицинских данных (HIPAA) или данных банковского сектора (PCI DSS).
Первая SE-схема (ее первое формальное научное описание) была предложена в 2000 г. Сегодня академическим сообществом предложено более 50 описаний схем с разнообразной функциональностью. Индустрия также предлагает большое количество решений, готовых к использованию (Bitglass, CipherCloud, Crypteron, IQrypt, Kryptnostic, Google’s Encrypted BigQuery, Microsoft’s SQL Server 2016, Azure SQL Database, PreVeil, SkyHigh, StealthMine и др.).
Хорошо известно [link 1, link 2], что проектирование SE-схемы — это нахождение компромисса (tradeoff) между безопасностью, функциональностью запросов, производительностью и удобством использования (рис. 2). Когда в схеме улучшается один из аспектов, обычно это приводит к ухудшению одного или сразу нескольких других аспектов. Безопасность обычно определяется информацией о пользовательских данных, которая становится известна атакующему в процессе работы схемы (leakage). Функциональность запросов определяется типами запросов, которые поддерживаются. Запросы обычно выражаются с помощью стандартных языков (например, SQL).
Производительность характеризуется структурами данных и механизмами индексирования в базе данных наряду с вычислительными и коммуникационными издержками.
Понятие безопасности схемы поискового шифрования
Для схем поискового шифрования характерно собственное понятие безопасности, поскольку все наиболее мощные криптографические атаки на такие системы строятся на основе эксплуатации утечек (leakage inference attacks), которым подвержена в большей или меньшей степени почти любая практическая SE-схема. В процессе работы SE-схемы происходит постоянное взаимодействие между клиентом и сервером. При наблюдении и статистическом анализе приходящих от клиента запросов и ответов сервера противник может получать существенное количество метаданных о зашифрованной пользовательской информации.Предположим, что атакующий имеет доступ к зашифрованным данным на сервере и может наблюдать пользовательские запросы. Также атакующий знает, какое количество записей возвращается в ответ на каждый запрос. Если это количество уникальное, следовательно, запрос также уникален и его можно различить среди множества всевозможных запросов.
Другой способ извлечения метаданных о зашифрованной пользовательской информации заключается в следующем. Предположим, что атакующий получил знание об одном из запросов с поисковым выражением <Last_Name=Smith>. Предположим также, что оба различных запроса с поисковыми выражениями <Fisrt_Name=John> и <Fisrt_Name=Matthew> возвращают 1000 записей. Атакующий может проверить, сколько общих записей у последних (неизвестных) запросов вместе с первым (известным). К примеру, может быть 100 записей с именем John Smith и только 10 записей с именем Matthew Smith. Сверяя такие пересечения с ранее известными запросами, противник может идентифицировать Fisrt_Name. Такой подход итеративно идентифицирует запросы и использует их как дополнительные ограничения для дальнейшего определения неизвестных запросов.
Среди наиболее известных и мощных атак такого рода можно выделить count-атаку, способную восстанавливать до 40% ключевых слов, если их распределение невелико (до 5000), при условии, что атакующему известно 80% записей. Другой пример — атака иерархического поиска (hierarchical search attack). Она является расширением count-атаки и способна при таком же распределении восстанавливать до 80% ключевых слов при утечке только лишь 40% записей, однако с допущением, что противник активен и способен включать свои записи в зашифрованные пользовательские данные.
Существующие схемы поискового шифрования для баз данных SQL
Исследования в области поискового шифрования преимущественно концентрируются на широком контексте, когда пользовательские данные структурированы в виде коллекции документов, а поиск выполняется по ключевым словам (Dropbox и Google Drive). Однако на практике организации часто используют реляционную модель структурирования данных по таблицам в соответствии с набором атрибутов. SQL-синтаксис хорошо определен и позволяет выполнять все необходимые операции с данными (загрузка, модификация, поиск и удаление). Следовательно, SE-схема должна адаптироваться под конкретные SQL-запросы, использующиеся в приложении. Кроме этого, с практической точки зрения крайне важны такие параметры:- подходящее соотношение производительности, безопасности и функциональности;
- наличие прототипа, реализующего схему с открытым исходным кодом;
- простота интеграции с приложением.
Табл. 1. Сравнение SE-схем
| SE schemes | Query expressiveness | Security | Performance overhead | Easy integration with application (deploy) | Open-source |
| CryptDB | Equality, Boolean, Range, Update, Sum | Low | ~30% | + | + |
| Blind Seer | Equality, Boolean, Range, Update | Average | ~20 — 300% | — | — |
| OSPIR-OXT | Equality, Boolean, Range, Update | Average | ~1000% | — | — |
| SisoSPIR | Equality, Range | High | ~500% | — | — |
| CipherSweet | Equality | High | ~1000 — 1500% | + | + |
CryptDB поддерживает максимальную функциональность современных систем управления базами данных SQL с потерей производительности до 30%. Авторы Blind Seer сообщают, что их падение производительности колеблется в пределах 20-300% для большинства запросов. Авторы OSPIR-OXT сообщают, что в некоторых случаях их система даже превосходит MySQL 5.5 с «холодным» кешем и на 1 порядок (1000%) медленнее, чем MySQL с «теплым» кешем. Падение производительности у SisoSPIR составляет порядка 500% на некоторых видах запросов (equality и range).
В то же время предоставляемый системами уровень безопасности различен. При использовании атрибута в запросе CryptDB раскрывает статистику всех значений этого атрибута в таблице. Blind Seer и OSPIR-OXT также раскрывают серверу метаданные о зашифрованной пользовательской информации, возвращаемой в результате запроса. Поэтому эти системы стоит использовать в случае редкого обращения к данным.
SisoSPIR обеспечивает высокий уровень защиты даже в случае регулярных запросов (что является одним из требований production-ready-систем) за счет введения дополнительного инфраструктурного компонента — helper-сервера. При этом SisoSPIR требует, чтобы сервер, на котором хранятся пользовательские данные, не имел возможности «сговориться» (collude) с helper-сервером.
CipherSweet поддерживает наименьшую функциональность запросов (equality) и имеет относительно низкую производительность, однако предоставляет высокий уровень безопасности за счет простого и понятного криптографического дизайна. Следует отметить, что CipherSweet (в отличие от систем, предложенных академическими исследователями) использует технику слепого индексирования (blind indexing technique), которая зародилась в инженерном сообществе и учитывает многие практические проблемы. Этот факт склонил нашу инженерную команду к выбору CipherSweet как прототипа для нашего программного продукта.
Принцип работы CipherSweet
Идея техники слепого индексирования, использующейся в CipherSweet, достаточно простая. Рассмотрим простую SQL-таблицу с двумя атрибутами Field_A и Field_B, содержащую три записи (табл. 2).Табл. 2. Таблица в базе данных SQL
| Records | Field_A | Field_B |
| record_0 | data_1 | data_2 |
| record_1 | data_1 | data_3 |
| record_2 | data_4 | data_5 |
INSERT INTO table VALUES (data_1, data_2)
Для поиска записей по атрибуту Field_A можно использовать такой SELECT-запрос:
SELECT * FROM table WHERE Field_A = data_1
Результатом такого запроса будет таблица, содержащая две записи: record_0 и record_1.
При зашифровании данных сервер теряет возможность производить сравнение Field_A = data_1. Модифицируем исходную таблицу добавлением атрибута Field_A_index, в котором будут содержаться метаданные о данных, помеченных атрибутом Field_A (табл. 3). Теперь можно зашифровать данные, используя криптографически стойкий (CPA secure) блочный шифр (например, AES-256-GCM) по атрибуту Field_A, а для того, чтобы работало сравнение, нужно в индекс записать результат применения к данным криптографически стойкой (PRF) псевдослучайной функции (например, PBKDF2 или Argon2). Обозначим операцию шифрования с помощью функций Enc/Dec (зашифрование и расшифрование соответственно) и операцию вычисления псевдослучайной функции PRF. Табл. 4 демонстрирует порядок хранения данных на сервере.
Табл. 3. Модификация исходной таблицы для CipherSweet
| Records | Field_A_index | Field_A | Field_B |
| record_0 | index_1 | data_1 | data_2 |
| record_1 | index_1 | data_1 | data_3 |
| record_2 | index_4 | data_4 | data_5 |
Табл. 4. Представление зашифрованных данных на недоверенном сервере
| Records | Field_A_index | Field_A | Field_B |
| record_0 | PRF(data_1) | Enc(data_1) | data_2 |
| record_1 | PRF(data_1) | Enc(data_1) | data_3 |
| record_2 | PRF(data_4) | Enc(data_4) | data_5 |
- модифицировать запросы для работы с данными и структуры таблиц;
- интегрировать три криптографические функции Enc, Dec и PRF в логику приложения.
INSERT INTO table VALUES (index_1, encrypted_data_1, data_2)
где index_1=PRF(data_1), encrypted_data_1=Enc(data_1).
SELECT-запрос для выборки по атрибуту Field_A преобразуется в такую форму:
SELECT * FROM table WHERE Field_A_index=index_1
где index_1 = PRF (data_1). После получения результата запроса приложение может воспользоваться функцией Dec и расшифровать данные по атрибуту Field_A из записей record_0 и record_1.
Отметим, что криптографические ключи опущены в описании для упрощения. Подразумевается, что шифрование и псевдослучайная функция используют два различных ключа.
Любопытный читатель может заметить важную особенность в контексте безопасности. Результат PRF будет всегда одним и тем же для двух одинаковых фрагментов данных: значения индексов (атрибут Field_A_index) для record_0 и record_1 будут одинаковыми, так как они оба вычислены по data_1. Это — потенциальная утечка, потому что сервер на основе анализа зашифрованных данных и их индексов (к которым он потенциально имеет доступ) может определить, какие записи в таблице содержат одинаковые значения зашифрованных данных по атрибутам, поддерживающим поиск (Field_A в рассматриваемом случае). Чтобы уменьшить негативные последствия этой утечки, CipherSweet предлагает хранить на сервере усеченное значение индексов (табл. 5).
Предположим, что псевдослучайная функция генерирует индексы размером 64 байта. «Отдавая» серверу усеченное значение индекса (размер < 64) можно снижать последствия потенциальной утечки схемы, тем самым повышая безопасность. Однако при этом сервер не сможет однозначно определять записи, которые необходимо включать в результат запроса. То есть растет вероятность ошибки включения в результат запроса неверной записи (false positive). В этом случае на приложение возлагается ответственность «отфильтровать» все нерелевантные записи после получения результата запроса от сервера и расшифрования данных.
Табл. 5. Усечение индекса в CipherSweet
| Records | Field_A_index | Field_A | Field_B |
| record_0 | index_1[64] | ENCRYPTED | data_2 |
| record_1 | index_1[64] | ENCRYPTED | data_3 |
| record_2 | index_4[64] | ENCRYPTED | data_5 |
| Field_A_index | Field_A | Field_B | |
| record_0 | index_1[<64] | ENCRYPTED | data_2 |
| record_1 | index_1[<64] | ENCRYPTED | data_3 |
| record_2 | index_4[<64] | ENCRYPTED | data_5 |
<?php
use ParagonIE\CipherSweet\Planner\FieldIndexPlanner;
# First, instantiate the planner for a given field
$planner = new FieldIndexPlanner();
# How many rows do you anticipate?
$planner->setEstimatedPopulation(50000);
$recommended = $planner->recommend(14);
var_dump($recommended);
/* array(2) {["min"]=>int(8) ["max"]=>int(14) }*/
Для использования планировщика необходимо: оценить ожидаемое количество записей, включающих атрибуты с зашифрованными данными, и распределить данные, подлежащие защите. В примере выше верхняя граница ожидаемых записей составляет 50 000, а битовое распределение данных (input domain size) — 14 бит. Такое значение распределения характерно для данных, определяющих годы в календаре: 4 целые цифры (2019) могут составить 10 000 различных комбинаций, следовательно, распределение составляет log2 (10 000) ≈ 14. При этом планировщик рекомендует использовать индекс с размером от 8 до 14 бит.
Интеграция
В предыдущих разделах мы рассмотрели базовый принцип работы техники слепого индексирования, реализованной в CipherSweet. Было показано, какие изменения необходимо внести в структуру таблиц базы данных и какие криптографические функции необходимо интегрировать в приложение для того, чтобы активировать шифрование данных приложения, хранящихся на недоверенном удаленном сервисе, и обеспечить возможность поиска.После выбора прототипа схемы поискового шифрования перед нашей инженерной командой стояла задача внедрения схемы в нашу систему комплексной защиты баз данных SQL (Acra [link 1, link 2]).
Центральным компонентом этой системы является прокси-сервер, изолирующий функционал безопасности (шифрование, SQL firewall и Intrusion Detection System) таким образом, чтобы работа приложения с базой данных была прозрачной (transparent). При этом приложению не требуется система управления криптографическими ключами и их хранения (достаточно сложная проблема, возникающая при внедрении любых криптографических операций): эта функция делегируется прокси-серверу.
Использование проксирования в комбинации с техникой слепого индексирования позволяет прозрачным для приложения образом внедрить возможность поиска по зашифрованным данным (за счет введения дополнительного инфраструктурного компонента — proxy (рис. 3)).
Для обеспечения прозрачности прокси-сервер также отвечает за модификацию запросов, приходящих от приложения, перед отправкой на удаленный сервер управления базой данных (SQL query — изначальный запрос от приложения, SE query — модифицированный запрос от прокси-сервера).
Нам пришлось портировать реализацию техники слепого индексирования на Go (в CipherSweet она выполнена на PHP и Node.js) под уже существующий прокси-сервер. Криптографические операции реализованы с использованием стандартной библиотеки Go, а также криптографической библиотеки Themis. Система является production-ready и DevOps-friendly: поддерживает метрики, логирование, трейсинг и готова к интеграции и эксплуатации в существующие инфраструктуры и приложения.
Отметим также, что проксирование позволяет устранить неудобство, связанное с false positives, и вероятности включения сервером нерелевантных записей из базы данных в результат запроса при усечении индекса с целью повышения безопасности. Фактически прокси-сервер запоминает запрос от приложения (SQL query), модифицирует его (SE query) в соответствии с техникой слепого индексирования, отправляет на сервер и затем применяет его к ответу сервера после расшифрования (decrypted results). Однако при использовании такой фильтрации наблюдается падение производительности, так как нерелевантные записи могут быть отбракованы только после их расшифрования.
Оценка производительности
Мы оценивали производительность всего решения на рабочей станции с такими характеристиками: Intel Core i7, 4000 MHz (12 ядер), 16 GB RAM под управлением операционной системы Ubuntu 18.04 LTS (x64). В качестве сервиса хранения данных использовалась система PostgreSQL (v. 11) в виде Docker-контейнера. Исходный код платформы для тестирования производительности, материал, а также все настройки сохранены в GitHub-репозитории Acra.Для инициализации таблицы в базе данных использовались такие SQL-запросы:
DROP TABLE IF EXISTS test_raw;
DROP SEQUENCE IF EXISTS test_raw_seq;
CREATE SEQUENCE test_raw_seq START 1;
CREATE TABLE test_raw (id, INTEGER PRIMARY KEY DEFAULT nextval(‘test_raw_seq’), plaintext BYTEA, ciphertext BYTEA).
Стандартный функциональный индекс производительности для экспериментов с различной величиной усечения индекса создавался таким SQL-псевдозапросом:
CREATE INDEX IF NOT EXISTS test_raw_ciphertext_secure_index_idx ON test_raw (substr(ciphertext, 1, secureIndexSize));
Прокси-сервер был настроен на зашифрование и поиск по атрибуту ciphertext. Пример INSERT-псевдозапроса от приложения:
INSERT INTO test_raw (plaintext, ciphertext) VALUES (input, input);
Пример SELECT-псевдозапроса от приложения:
SELECT * FROM test_raw WHERE ciphertext=input;
Для оценки производительности мы измеряли общее время задержки запросов (query latency) с помощью следующего эксперимента:
- Генерировался входной набор данных (обозначим его R) c n = 50 000 записей путем случайной выборки из исходного материала (коллекция из 25 000 уникальных имейлов).
- R записывался в базу данных.
- Производилась выборка несуществующей записи со следующим значением атрибута ciphertext: ciphertext=‘\xFFFFFFFFFFFFFFFFFFFFFF’, — и выполнялась проверка того, что в ответе не было получено ни одной строки.
- Один раз выполнялся INSERT-запрос с записью r1 c одинаковым значением атрибутов ciphertext и plaintext: plaintext = ciphertext = ‘\x62614C494E31353247444F437177657274793132333435363738393040686F746D61696C2E636F6D’, — затем производилась выборка r1 по указанному значению и выполнялась проверка того, что в ответе была получена в точности одна запись.
- Десять раз выполнялся INSERT-запрос с записью r2 c одинаковым значением атрибутов ciphertext и plaintext, затем производилась выборка r2 по указанному значению и выполнялась проверка того, что в ответе было получено в точности 10 записей.
Табл. 6 обобщает результаты (в среднем по 3 запускам) выполнения INSERT-запросов с одним значением записи.
Табл. 6
| Распределение ключевых слов | Выполнениe запросов без проксирования (время в с) | Длина индекса (байты) | Выполнение запросов с проксированием | Относительное падение производительности | |||
| Шифрование (вызовы / время в с) | Вычисление индекса (вызовы / время в мс) | Другие операции (время в с) | Общее (время в с) | ||||
| 350 | 707.1668 | 2 | 50000 / 57.6947 | 50000 / 620.1667 | 679.0150 | 737.3299 | ~4% |
| 15 | 50000 / 57.7494 | 50000 / 617.1465 | 736.5025 | 794.8690 | ~12% | ||
| 25000 | 691.9133 | 2 | 50000 / 59.1564 | 50000 / 619.2667 | 648.3589 | 708.1346 | ~2% |
| 15 | 50000 / 58.2443 | 50000 / 625.7523 | 670.7465 | 729.6166 | ~5% |
Примерное значение падения производительности в этом случае находится в пределах 2-12%.
Табл. 7 обобщает результаты (в среднем по 10 запускам) выполнения INSERT-запросов с 1000 значений записей (так называемые bulk-запросы).
Табл. 7
| Распределение ключевых слов | Выполнениe запросов без проксирования (время в с) | Длина индекса (байты) | Выполнение запросов с проксированием | Относительное падение производительности | |||
| Шифрование (вызовы / время в с) | Вычисление индекса (вызовы / время в мс) | Другие операции (время в с) | Общее время в с) | ||||
| 350 | 2.5993 | 2 | 50 / 23.7783 | 50000 / 230.4363 | 5.2013 | 29.2100 | ~1024% |
| 15 | 50 / 23.7612 | 50000 / 232.5844 | 4.5905 | 28.5843 | ~1000% | ||
| 25000 | 2.3125 | 2 | 50 / 23.6542 | 50000 / 229.2123 | 4.7324 | 28.6158 | ~1137% |
| 15 | 50 / 23.8756 | 50000 / 240.4962 | 4.5991 | 28.7152 | ~1142% |
Отметим, что в этом случае приложением было отправлено только 50 запросов (в сравнении с 50 000 в предыдущем испытании), поэтому влияние сетевых операций на производительность существенно меньше, но все же заметно.
Падение производительности составляет примерно 1 порядок (10 раз).
Табл. 8 обобщает результаты (в среднем по 10 000 запусков) выполнения SELECT-запросов, возвращающих в ответе пустой результат.
Табл. 8
| Распределение ключевых слов | Выполнениe запросов без проксирования (время в мс) | Длина индекса (байты) | Выполнение запросов с проксированием | Относительное падение производительности | ||||
| Расшифрование (вызовы / время в с) | Фильтрация (вызовы / время в мкс) | Вычисление индекса (вызовы / время в мкс) | Другие операции (время в мс) | Общее (время в мс) | ||||
| 350 | 0.1840 | 2 | — | — | 1 / 41.9543 | 0.4933 | 0.5353 | ~191% |
| 15 | — | — | 1 / 39.1419 | 0.4623 | 0.5014 | ~172% | ||
| 25000 | 0.1770 | 2 | — | — | 1 / 37.7230 | 0.4397 | 0.4774 | ~170% |
| 15 | — | — | 1 / 38.6630 | 0.4577 | 0.4964 | ~180% |
Примерное значение относительного падения производительности составило 170-191%.
Табл. 9 обобщает результаты (в среднем по 10 000 запусков) выполнения SELECT-запросов, возвращающих в точности 1 запись в ответе.
Табл. 9
| Распределение ключевых слов | Выполнениe запросов без проксирования (время в мс) | Длина индекса (байты) | Выполнение запросов с проксированием | Относительное падение производительности | ||||
| Расшифрование (вызовы / время в с) | Фильтрация (вызовы / время в мкс) | Вычисление индекса (вызовы / время в мкс) | Другие операции (время в мс) | Общее (время в мс) | ||||
| 350 | 0.1920 | 2 | 1 / 0.4988 | — | 1 / 32.2792 | 0.5747 | 1.1058 | ~476% |
| 15 | 1 / 0.4971 | — | 1 / 28.9147 | 0.5700 | 1.0960 | ~471% | ||
| 25000 | 0.1920 | 2 | 3 / 1.3528 | 2 / 73.6460 | 1 / 30.6646 | 0.6666 | 2.1237 | ~1006% |
| 15 | 1 / 0.5000 | — | 1 / 32.3181 | 0.5795 | 1.1120 | ~479% |
В итоге значение падения производительности существенно колеблется (в пределах 471-1006%).
Табл. 10 обобщает результаты (в среднем по 10 000 запусков) выполнения SELECT-запросов, возвращающих в точности 10 записей в ответе.
Снова можно заметить наличие «пустых» операций расшифрования и фильтрацию в эксперименте с набором данных с распределением в 25 000 ключевых слов и коротким индексом.
Относительная величина падения производительности находится в пределах 1934-2630%.
Табл. 10
| Распределение ключевых слов | Выполнениe запросов без проксирования (время в мс) | Длина индекса (байты) | Выполнение запросов с проксированием | Относительное падение производительности | ||||
| Расшифрование (вызовы / время в с) | Фильтрация (вызовы / время в мкс) | Вычисление индекса (вызовы / время в мкс) | Другие операции (время в мс) | Общее (время в мс) | ||||
| 350 | 0.2410 | 2 | 10 / 4.2650 | — | 1 / 29.7211 | 0.9265 | 5.2212 | ~2066% |
| 15 | 10 / 4.2619 | — | 1 / 28.9147 | 0.9682 | 5.2590 | ~2082% | ||
| 25000 | 0.2550 | 2 | 14 / 5.8788 | 4 / 69.5195 | 1 / 30.0456 | 0.9842 | 6.9626 | ~2630% |
| 15 | 10 / 4.2538 | — | 1 / 32.9155 | 0.9051 | 5.1878 | ~1934% |
Заключение и выводы
Поисковое шифрование — относительно новое направление в современной криптографии. Его актуальность крайне высока в связи с тем, что появляется все больше нормативных требований (например, GDPR и HIPAA) к хранению конфиденциальных данных в зашифрованном виде при использовании облачных/удаленных сервисов. В то же время требуется возможность эффективного поиска по зашифрованным данным. Несмотря на большое количество существующих академических исследований (предложено более 50 схем поискового шифрования), они не могут быть реализованы в виде практических, производительных и безопасных решений (в частности, для баз данных SQL), которые могли бы применяться в production-ready-системах и приложениях, в связи со сложными противоречиями в требованиях к таким системам.На наш взгляд, ключевые особенности, которыми должна обладать система поискового шифрования, это:
- безопасность (out-of-box), основанная на простом и понятном криптографическом дизайне;
- открытость исходного кода;
- простота интеграции в конечное приложение.
Список источников дополнительной информации
- SoK: Cryptographically Protected Database Search / Fuller B., Varia M., Yerukhimovich A., Shen E., Hamlin A., Gadepally V., Shay R., Mitchell J. D., Cunningham R. K. / 2017 / Reference;
- A Survey of Provably Secure Searchable Encryption / Bösch C. T., Hartel P. H., Jonker W., Peter A. / 2014 / Reference;
- CipherSweet GitHub repository;
- Acra Official Documentation;
- Acra GitHub repository;
- Themis GitHub repository;
- Acra Integration Examples.
DOU
DOU – Найбільша спільнота розробників України. Все про IT: цікаві статті, інтервʼю, розслідування, дослідження ринку, свіжі новини та події. Спілкування на форумі з айтівцями на найгарячіші теми та технічні матеріали від експертів. Вакансії, рейтинг IT-компаній, відгуки співробітників, аналітика...
dou.ua