Обробка запитів над зашифрованими базами даних

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

Вирішення цієї проблеми

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

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

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

  • Імовірнісне шифрування (RND) – забезпечує максимальну секретність, але не дозволяє виконувати жодні операції над зашифрованими повідомленнями;
  • Детерміноване шифрування (DET) - дозволяє виявляти еквівалентні вихідні повідомлення, перевіряючи еквівалентність відповідних зашифрованих повідомлень;
  • Шифрування, що зберігає порядок (OPE) – дозволяє виконувати операції порівняння та сортування над зашифрованими даними;
  • З'єднання (JOIN and OPE-JOIN)- дозволяє здійснювати вибірку зашифрованих даних із двох таблиць;
  • Пошук (SEARCH) – дозволяє здійснювати пошук над зашифрованими даними;
  • Гомоморфне шифрування (HOM) – дозволяє виконувати арифметичні операції над зашифрованими даними.

Алгоритми шифрування перераховані в порядку зменшення криптографічної стійкості, тобто найбільшу секретність забезпечує шифрування ймовірності, а найменшу - гомоморфне.

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

запитів

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

зашифрованими

Згідно з цією моделлю всі значення в захищеній базі даних спочаткушифруються до максимального рівня таємності. Передбачається, що в результаті обробки кількох запитів сервер видалить непотрібні шари зашифрованих повідомлень і надалі зникне необхідність криптографічних операцій. Тобто цибулинна структура забезпечує динамічне регулювання рівня таємності. У процесі використання побудована на такому принципі захищена база даних досягає стану, в якому всі значення зашифровані криптографічними алгоритмами, що дозволяють виконувати найбільш часто знаходяться для даного типу значень операції.

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

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

На відміну від моделі CryptDB, у моделі захищеної бази даних, розробленої компанією IBM, для зберігання секретних даних, крім шифрування, використовуються також безпечні індекси, що дозволяють виконувати запити над зашифрованими даними. Для кожного відношення на сервері хмарної СУБД зберігається зашифроване відношення, де атрибут відповідає кортежу відношення, зашифрованого блоковим алгоритмом шифрування (DES або AES). Кожен атрибут є індексом для атрибута , необхідним виконання операцій над зашифрованими даними. Таким чином, кортеж зберігається на сервері як . Для обчислення індексу атрибута використовуються функції відображення . У проекті використовується два типи функцій, що відображають: що зберігають порядок вихідних значень і імовірнісні. Використання безпечних індексів дозволяє виконувати операції сортування та порівняння даних (за рахунок збереження порядку відображуючих функцій),а також ефективно виконувати запити на вибірку даних за одним або декількома параметрами. Параметри вибірки шифруються за допомогою функцій, що відображають, отримані значення порівнюються з індексами, що зберігаються в захищеній базі даних, на основі збігу вибираються зашифровані відносини , які відправляються на клієнтську машину, де розшифровується атрибут , і формується результат вибірки [HaIyLiMe02].

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

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

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

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

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

запитів

Щоб відповісти на такі запити, 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.