Difference between revisions of "Обработка запросов над зашифрованными базами данных"

From CryptoWiki
Jump to: navigation, search
(Постановка задачи)
 
Line 83: Line 83:
  
 
Перейти к [[Список литературы к разделу «Обработка запросов над зашифрованными базами данных (Processing Queries on an Encrypted Database )»|списку литературы]] раздела «Обработка запросов над зашифрованными базами данных (Processing Queries on an Encrypted Database )».
 
Перейти к [[Список литературы к разделу «Обработка запросов над зашифрованными базами данных (Processing Queries on an Encrypted Database )»|списку литературы]] раздела «Обработка запросов над зашифрованными базами данных (Processing Queries on an Encrypted Database )».
 +
 +
Перейти к статье ''"Обработка запросов над зашифрованными базами данных"'' [[Processing Queries on an Encrypted Database| на английском языке]].
  
 
[[ Часть II. Приложения криптографии (Криптографические протоколы) | Назад ]]
 
[[ Часть II. Приложения криптографии (Криптографические протоколы) | Назад ]]
  
 +
[[ Main_Page | Перейти на главную страницу]]
  
 
''Арсентьев И.А., 2015''
 
''Арсентьев И.А., 2015''

Latest revision as of 21:42, 19 November 2015

Contents

Постановка задачи

В настоящее время в связи с ростом информационных систем и требований к их производительности становятся особо популярными облачные СУБД. Модель базы данных как сервиса в облаке (Database-as-a-service, DBaaS) предоставляет клиенту доступ к удаленной базе данных, все задачи по поддержке которой (администрирование, масштабирование, резервное копирование, восстановление после сбоев и др.) выполняются провайдером облачного сервиса [L10]. В связи с этим использование облачной СУБД требует значительно меньших затрат, чем запуск и управление собственной СУБД. База данных как сервис в облаке представляет собой выгодное решение, однако оно обладает одним существенным недостатком: необходимостью обеспечивать безопасность информации, которая хранится в удаленной базе данных. Облачная СУБД должна гарантировать защиту конфиденциальных данных как от внешних атак, так и от самого провайдера облачного сервиса.

Решение данной проблемы

Как решение данной проблемы была предложена модель защищенной базы данных, которая для обеспечения безопасности информации использует различные криптографические алгоритмы. Защищенная база данных должна хранить конфиденциальную информацию в зашифрованном виде и никогда не производить операций дешифрования данных, кроме того, она не должна содержать в себе ключи шифрования. Все операции шифрования и дешифрования необходимо выполнять на стороне клиента облачного сервиса. В настоящее время существует несколько проектов, занимающихся разработкой защищенных баз данных: CryptDB, MONOMI, Cipherbase, TrustDB [PoReZeBa11],[HaIyLiMe02],[TuKaMaZe13],[CuJoPo11]. Для выполнения операций над зашифрованными данными обычно используются алгоритмы шифрования, сохраняющего порядок, и алгоритмы гомоморфного шифрования. Первый тип алгоритмов позволяет сортировать и сравнивать зашифрованные данные, второй – выполнять арифметические операции над ними.

Защищенная база данных CryptDB

Наиболее известным решением в области защищенных баз данных является проект CryptDB, разрабатываемый группой ученых Массачусетского Технологического Университета (MIT) [PoReZeBa11]. В модели CryptDB используются следующие криптографические алгоритмы:

  • Вероятностное шифрование (RND) — обеспечивает максимальную секретность, но не позволяет выполнять никакие операции над зашифрованными сообщениями;
  • Детерминированное шифрование (DET) — позволяет выявлять эквивалентные исходные сообщения, проверяя эквивалентность соответствующих им зашифрованных сообщений;
  • Шифрование, сохраняющее порядок (OPE) — позволяет выполнять операции сравнения и сортировки над зашифрованными данными;
  • Соединение (JOIN and OPE-JOIN) — позволяет осуществлять выборку зашифрованных данных из двух таблиц;
  • Поиск (SEARCH) — позволяет осуществлять поиск над зашифрованными данными;
  • Гомоморфное шифрование (HOM) — позволяет выполнять арифметические операции над зашифрованными данными.

Алгоритмы шифрования перечислены в порядке уменьшения криптографической стойкости, то есть наибольшую секретность обеспечивает вероятностное шифрование, а наименьшую – гомоморфное.

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

Рисунок 1. Луковые слои шифрования и классы позволяют выполнять вычисления. Имена слоев определяют операции, которые выполняются на определенных слоях (сравнение, сортировка, поиск и сложение). На практике, некоторые слои могут быть опущены, в зависимости от типов столбцов или аннотаций схем, предусмотренных разработчиками приложений. DET и JOIN часто объединены в один слой, так как JOIN является объединением DET и Join-ADJ

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

Рисунок 2. Принцип работы луковичной модели

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

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

Защищенная база данных IBM

В отличие от модели CryptDB, в модели защищенной базы данных, разработанной компанией IBM, для хранения секретных данных кроме шифрования используются также безопасные индексы, позволяющие выполнять запросы над зашифрованными данными. Для каждого отношения ОбЗапФор3.png на сервере облачной СУБД сохраняется зашифрованное отношение ОбЗапФор4.png, где атрибут ОбрЗапФор 4.png соответствует кортежу отношения ОбЗапФор12.png, зашифрованному блочным алгоритмом шифрования (DES или AES). Каждый атрибут ОбЗапФор5.png является индексом для атрибута ОбЗапФор6.png, необходимым для выполнения операций над зашифрованными данными. Таким образом, кортеж ОбЗапФор7.png хранится на сервере в виде ОбЗапФор8.png. Для вычисления индекса атрибута ОбЗапФор6.png используются отображающие функции ОбЗапФор9.png. В проекте используется два типа отображающих функций: сохраняющие порядок исходных значений и вероятностные. Использование безопасных индексов позволяет выполнять операции сортировки и сравнения данных (за счет сохраняющих порядок отображающих функций), а также эффективно выполнять запросы на выборку данных по одному или нескольким параметрам. Параметры выборки шифруются с помощью отображающих функций, полученные значения сравниваются с индексами, хранящимися в защищенной базе данных, на основе совпадения выбираются зашифрованные отношения ОбЗапФор10.png, которые отправляются на клиентскую машину, где расшифровывается атрибут ОбЗапФор11.png, и формируется результат выборки [HaIyLiMe02].

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

Защищенная база данных MONOMI

MONOMI — это система для безопасного выполнения аналитических операций над конфиденциальными данными на ненадежном сервере базы данных. MONOMI работает путем шифрования всей базы данных и выполнения запросов над зашифрованными данными. MONOMI вводит новый подход на основе клиент/сервер модели исполнения запросов. Сплит выполнение позволяет MONOMI выполнить часть запроса над зашифрованными данными на не доверенном сервере. Для другой части запроса, которая либо не сможет быть вычислена на сервере, либо может быть более эффективно вычислена на клиенте, MONOMI загружает промежуточные результаты клиенту и выполняет окончательный расчет уже на клиентской стороне. Поэтому она может выполнять сколь угодно сложные запросы над зашифрованными данными. MONOMI вводит ряд методик, позволяющих повысить производительность для таких операций, в том числе для строки предварительных вычислений, эргономичного шифрования данных, сгруппированных гомоморфных дополнений и предварительной фильтрации. Поскольку эти оптимизации являются хорошими для некоторых запросов, но не для других, MONOMI вводит дизайнера для выбора эффективного физического проектирования сервера при указанной нагрузке, и планировщик, чтобы выбрать эффективный план выполнения для данного запроса во время его выполнения. Прототип MONOMI, работающий поверх Postgres, может выполнить большинство TPC-H ориентированных запросов при этом средние накладные расходы всего 1.24× (начиная от 1.03× до 2,33×) по сравнению с незашифрованной базой данных Postgres, где скомпрометированный сервер откроет все данные [TuKaMaZe13].

КЛИЕНТ/СЕРВЕРНАЯ МОДЕЛЬ ОБРАБОТКИ ЗАПРОСОВ MONOMI

Чтобы выполнить запросы, которые не могут быть вычислены на одном только сервере, MONOMI делит выполнение каждого запроса между сервером, которому не доверяют, у которого есть доступ только к зашифрованным данным, и машиной клиента, которой доверяют, у которой есть доступ к ключам, необходимым, чтобы расшифровать зашифрованные данные. Рассмотрим TPC-H запрос 11, как показано на рисунке 3. Этот запрос требует проверки того, что является ли SUM() для каждой группы больше, чем подвыражение, которое вычисляет собственные SUM(), умноженное на константу. Схема шифрования MONOMI не поддерживает такие запросы непосредственно над зашифрованными данными, потому что дополнение и сравнение вовлекают несовместимые схемы шифрования, и потому что никакая эффективная схема шифрования не позволяет умножение двух зашифрованных значений.

Рисунок 3. TPC-H запрос 11

Чтобы ответить на такие запросы, MONOMI делит выполнение запроса между клиентом и сервером, с помощью построения дерева SQL-операторов для запроса, состоящего из регулярных операторов SQL и операторов расшифрования, которые выполняются на клиенте, а также операторы RemoteSQL, которые выполняют инструкции SQL над зашифрованными данными на сервере, которому не доверяют. Например, рисунок 3 показывает потенциальный план разделения выполнения TPC-H запроса 11. Общий алгоритм определения плана сплит-запроса представлен в Алгоритме 1. Этот алгоритм может обрабатывать произвольные SQL-запросы, но мы объясняем его выполнение, используя TPC-H запрос 11 в качестве примера, следующим образом [TuKaMaZe13].

Строки 6-13, стараемся найти способ выполнить, WHERE n_name =:1 команду на сервере. REWRITESERVER (expr, E, enctype) функция возвращает вычисленное на сервере значение expr, зашифрованное enctype, учитывая множество зашифрованных столбцов Е. При enctype=PLAIN REWRITESERVER генерирует открытый текст стоимостью expr. В нашем примере это преобразует n_name =:1 в n_name_DET=encrypt (:1), которое генерирует тот же самый открытый текст (булево значение), не показывая n_name.

Строки 14-18 пытаются переместить пункт GROUP BY на сервер, с помощью REWRITESERVER найти детерминированные шифрованные групповые ключи (в нашем примере, ps_partkey), передав их в DET enctype. В нашем примере REWRITESERVER возвращает ps_partkey_DET, который помещается в RemoteQ, и запрос, который будет выполняться на сервере.

Строки 22-26 пытаемся выполнить оператор HAVING на сервере, предполагая, что GROUP BY может быть выполнена на сервере. Поскольку в нашем примере оператор HAVING не может быть вычислен в сервере, REWRITESERVER возвращает Nil. Чтобы выполнить оператор HAVING на клиенте, как показывает строка 26, используется вспомогательная функция EXPRS(expr) для определения, какие подвыражения могут быть вычислены на сервере, чтобы тогда вычислить весь expr на клиенте, и добавляет эти выражения к списку значений, возвращаемых RemoteQ. Поскольку оператор HAVING включает в себя вложенный SELECT, EXPRS рекурсивно вызывает GENERATEQUERYPLAN, который определяет, как запустить под-select на сервере. Это в конечном итоге возвращает RemoteSQL, LocalDecrypt, а операторы LocalProjection показаны в нижнем правом ветви рисунка 4.

Строки 32-37 определяют, как лучше всего принести проекции с сервера, передавая ЛЮБОЙ enctype к REWRITESERVER, так как любая схема шифрования была бы достаточна. В нашем примере, это переводит ps_partkey в ps_partkey_DET, и SUM (..) в GROUP(precomp_DET). Здесь мы предполагаем, что сервер имеет предварительно вычисленные детерминированное шифрованное ps_supplycost * ps_availqty, обозначенное как precomp_DET, но не имеет гомоморфного шифрования (как указано в аргументе E). Таким образом, оператор GROUP() объединяет все значения из группы, и SUM() будет вычисляться на клиенте. Планировщик может выбрать этот набор схем шифрования Е, если вычисление SUM() на клиенте выполняется быстрее, чем расшифровка гомоморфно зашифрованного текста. Наконец, алгоритм строит локальную часть плана запроса.

Строка 38, создаем оператор RemoteSQL в сочетании с оператором LocalDecrypt, как показано на обоих ветвях на рисунке 4.

Строки 39-40 выполняют любые оставшиеся операторы WHERE или JOIN. Строки 41-44 добавляют операторы для клиентской стороны GROUP BY или HAVING.

Рисунок 4. Пример плана сплит запроса для TPC-H запроса 11. “Местные” операторы запускаются на доверенном клиенте, а “удаленные” операторы работают на ненадежных серверах. GROUP() обозначает конкатенацию всех значений из каждой GROUP BY группы, 0xabcdef обозначает детерминированное шифрование аргумента :1, и precomp_DET обозначает детерминированное шифрование предварительно вычисляемого выражения ps_supplycost * ps_availqty. $n относится к n-му столбцу производного оператора.
Алгоритм 1. Псевдокод GENERATEQUERYPLAN. Для краткости, псевдокод предполагает, что запрос – это оператор SELECT, и не содержит ORDER BY и LIMIT компоненты. Псевдокод также не отслеживает позиции проекций, необходимых для восстановления выражения на клиенте

Защищенная база данных Microsoft Cipherbase

На рисунке 5 представлена архитектура Cipherbase. Приложение взаимодействует с Cipherbase через клиентский модуль Cipherbase. Клиент Cipherbase представляет собой простой текстовый интерфейс базы данных и скрывает детали конфиденциальных данных из приложения. Этот клиент выполняет шифрование перед отправкой запроса на сервер Cipherbase и расшифровывает возвращенные результаты перед отправкой их в приложение. Для реализации этой функциональности, клиент Cipherbase берет схемы шифрования и ключ шифрования клиента в качестве входных данных. Сервер Cipherbase состоит из доверенного модуля (ТМ) и модифицированной системы баз данных (SQL Server) (незащищенного модуля UM, или UMDBMS). Клиентское приложение взаимодействует с Cipherbase как это было бы со стандартной системой баз данных: с помощью не регламентированных (ad-hoc) запросов, хранимых процедур и сценариев SQL. Клиент библиотека (Cipherbase клиент) является посредником между приложением и сервером Cipherbase, обеспечивая применение с прозрачным интерфейсом. Требования конфиденциальности данных для каждого столбца могут быть независимо определены с использованием схемы шифрования на уровне столбцов. Неофициально, Cipherbase гарантирует, что всякий раз, когда значение (или производное значение) находится в облаке, за пределами безопасного аппаратного модуля, оно зашифровано с помощью заданной схемы шифрования. Поддерживаемые алгоритмы шифрования утверждаются стандартами: (1) стойкое шифрование, которое является недетерминированным (это означает, что каждый раз при шифровании одного и того же открытого текста будет получаться различные шифртексты). Это формально обеспечивает мощную защиту данных, неразличимость против атак по выбранному открытому тексту (IND-CPA). Оно реализовано в Cipherbase с AES в режиме CTR; (2) детерминированное шифрование, которое всегда создает один и тот же шифртекст из разных значений открытого текста. Это позволяет сравнивать открытый текст без предварительной его расшифровки, непосредственно сравнивая зашифрованное значение, это полезно для таких операций, как фильтры сравнения, присоединение, и группировка. Оно реализовано в Cipherbase с использованием AES работающим в режиме ECB и формате сохранения шифрования [ArEgJoKaKoRa15].

Рисунок 5. Архитектура Cipherbase

Глоссарий

Библиографический указатель

Перейти к списку литературы раздела «Обработка запросов над зашифрованными базами данных (Processing Queries on an Encrypted Database )».

Перейти к статье "Обработка запросов над зашифрованными базами данных" на английском языке.

Назад

Перейти на главную страницу

Арсентьев И.А., 2015