Схемы шифрования, сохраняющие порядок зашифрованных данных

From CryptoWiki
Jump to: navigation, search

Contents

Предпосылки

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

Данная концепция была названа «база данных как сервис» (Database as a Service, DBaaS) [B02]. Ее суть в том, что по запросу пользователю предоставляется база данных, для создания которой используются платформы облачных вычислений. Пользователь приобретает возможность хранения и доступа к информации из удаленной базы данных без необходимости её настройки, администрирования и привлечения дополнительных ресурсов, требуемых для обеспечения масштабируемости базы данных. Этот подход позволяет организовать динамическое предоставление услуг, что дает возможность пользователям производить оплату по факту использования ресурсов и регулировать их объем в зависимости от реальных потребностей без долгосрочных обязательств.

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

Вернуться к оглавлению

Введение

Шифрование, сохраняющее порядок зашифрованных данных, (Order-preserving encryption, OPE) является детерминированной схемой шифрования, при которой функция шифрования сохраняет численный порядок открытого текста.

OPE имеет долгую историю в виде одной из частей кода (onepartcodes), которые представляют собой списки открытых текстов и соответствующих им шифртекстов, как в алфавитном, так и числовом порядке, поэтому только одна копия необходима для правильного шифрования и расшифрования. Коды, состоящие из одной части, использовались, например, во время Первой Мировой Войны. Более официальное освещение понятия шифрования, сохраняющие порядок зашифрованных данных было предложено в сообществе баз данных Агравалем [AKSY04]. Причиной нового интереса к таким схемам является то, что они позволяют эффективный спектр запросов к зашифрованным данным. То есть удаленный ненадежный сервер баз данных способен индексировать (конфиденциальные) данные, которые он получает в зашифрованном виде, в структуре данных, что позволяет использовать эффективный диапазон запросов (запрос серверу, чтобы вернуться шифртекст в базу данных, чей расшифрованный вид лежит в заданном диапазоне, скажем [a; b]). Под «эффективным»подразумевается логарифмическое время (или по крайней мере суб-линейное) от размера базы данных, так как выполнение линейные работы на каждый запрос является чрезмерно медленным на практике для большие базы данных.

Схема шифрования, основанная на OPE, (Order-preserving encryption scheme, OPES) позволяет непосредственно применять операции сравнения на зашифрованные данные, не расшифровывая операндов. Таким образом, сравнения и диапазон запросов, а также поиск максимального, минимального, и подсчет запросов могут быть обработаны непосредственно над зашифрованными данными. Аналогично, команды GROUP BY и ORDER BY могут быть применимы к нерасшифрованным данным. Только при применении команд SUM или AVG к группе значений, эти значения должны быть расшифрованы.

OPES также обладает следующими свойствами:

  • Результаты обработки запросов над данными, шифруемые с использованием OPES, являются точными. Они не содержат никаких ложных срабатываний, ни пропускают ни одного ложного ответа.
  • OPES управляет обновлениями изящно. Значение в столбце могут быть изменены или новое значение может быть вставлено в столбец, при этом не требуется изменений в шифровании других значений.
  • OPES может быть легко интегрированы с существующими системами баз данных, так как данный метод был разработан, чтобы работать с существующими индексированными структурами, такими как B-деревья. Тот факт, что база данных зашифрована, то можно сделать БД прозрачными для приложений.

Математические определения

Определение 1. Шифрование - инъективное отображение (F) из множества открытых текстов (P) в множество шифртекстов (C): F:P →C.

Определение 2. OPES - детерминированная схема шифрования с симметричным ключом, которая сохраняет порядок открытых текстов.

Определение 3. Пусть m≤n, P={i| 1≤i≤m} - множество открытых текстов, С= {i| 1≤i≤n} - множество шифртекстов. SEm,n= (Km,n, Em,n, Dm,n) - детерминированная симметричная схема шифрования, где Km,n : {0,1}*→ {0,1}* - функция генерации ключа, Em,n:P⨯{0,1}*→C - детерминированный алгоритм симметричного шифрования, Dm,n:С⨯{0,1}*→Р - алгоритм расшифрования такой, что ∀ x ∈ P и любого валидного ключа k, x < x` ⇔ Em,n(x,k)< Em,n(x`,k).

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

B-деревья

Как известно [BCO11], что любое отношение порядка на множестве можно задать в виде двоичного дерева. С другой стороны в теории сжатия информации построение дерева Хаффмана является прямым проявлением монотонности относительно порядка на символах относительно частот появления данного символа в тексте. Чаще встречающийся символ, меньше, чем реже встречающийся. Этот подход реализован в работе [PLZ11]. Модель, предложенная авторами, представляет клиент-серверную архитектуру. Клиент обладает некоторыми данными, которые ему требуется зашифровать и хранить на недоверенной стороне сервера. Зашифрованные данные хранятся в виде двоичного дерева поиска. Для двоичного дерева поиска для каждого узла v, все узлы в левом поддереве строго меньше v, а все узлы в правом поддереве строго больше v. Кроме того в реализации используются Б-деревья, так как они имеют преимущества такие, как логарифмическое время вставки, удаления, поиска, позволяют эффективно проводить обновления шифртекстов. В каждом узле такого дерева хранится зашифрованный с помощью клиентского ключа открытый текст, согласно соответствующему отношению порядка. Для шифрования значений используются детерминированные алгоритмы (DET), с криптостойкостью отвечающей криптостойкости случайной функции, к примеру AES. Дерево с такими свойствами (OPE Tree), показано на рисунке 1.

Рисунок 1 - OPE дерево и OPE таблица для данного дерева

Данный метод имеет несколько неизбежных недостатков, связанных с использованием бинарного Б-дерева. Сложность поиска в бинарном дереве в худшем случае O(n), в среднем O(logn), где n – число вершин в дереве. Однако открытый текст не может быть зашифрован, до того, как будет найдена его позиция в дереве, следовательно, на каждом шаге требуется проводить дешифрование соответствующих узлов дерева. Сложность вставки и удаления аналогична, и также на каждом шаге требуется взаимодействие клиента с сервером и проведение операций дешифрования. Таким образом, работа клиента для шифрования n записей составит в среднем O(logn). Кроме того, для того чтобы предотвратить рост шифртекстов и поддерживать примерно одинаковую длину правого и левого поддеревьев в каждом узле, в процессе работы с деревом требуется проводить операцию балансировки. Хотя авторы предлагают технику проведения балансировки, в лучшем случае требующую O(logn), при большом количестве записей на сервере эта операция потребует значительных временных затрат.

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

В общем виде алгоритм шифрования выглядит следующим образом:

  1. Клиент вычисляет DET шифртекст c и отправляет его на сервер.
  2. Если шифртекст c уже есть в OPE таблице, то дерево не изменяется.
  3. Иначе:
    1. Выполняется обход OPE дерева при взаимодействии клиента с сервером, при котором определяется позиция для вставки шифртекста c и его OPE код. OPE код сохраняется в OPE таблице.
    2. Если требуется операция балансировки дерева, то после ее проведения, происходит обновление OPE кодов в OPE таблице.
    3. Результатом операций на сервере являются измененные OPE дерево и OPE таблица.

Для определения порядка открытых текстов соответствующих шифртекстов используются OPE коды из OPE таблицы.

Схемы шифрования

Суммирование случайных чисел

Простая схема была описана в [B02], которая вычисляет зашифрованное значение с из целого числа p как OPE 9.png , где OPE 2.png это j-е значение безопасного псевдо-случайного генератора R. К сожалению, стоимость вычисления р, каждый раз вызывая R для шифрования или расшифрования с может быть непомерно высокой.

Секретный ключ вычисляется с помощью генератора псевдослучайных чисел.

Схема является OPES, так как большему х соответствует большее значение шифртекста. Схема обладает недостатками. Во-первых, чем больше значение 𝑥, тем длиннее последовательность должна быть сгенерирована, как для шифрования, так и для расшивровки. Во-вторых, распределение открытых текстов может быть выявлено по распределению шифртекстов.

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

Рисунок 2 - Суммирование случайных чисел

Строго возрастающие полиномиальные функции

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

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

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

Рисунок 3 - Строго возрастающие полиномиальные функции

Схема шифрования Р. Агравала

В [PLZ11] рассматривается следующий подход. Интервал [0; T] – множество открытых текстов (натуральные числа). Интервал случайным образом разбивается на множество отрезков, каждому отрезку сопоставляется монотонно возрастающая линейная функция. Функции выбираются таким образом, чтобы образовать строго монотонно возрастающую кусочно-линейную функцию на интервале [0; T], для обеспечения сохранения порядка.

Секретный ключ состоит из описанных функций и их соответствия интервалам.

Шифруемое число x принадлежит одному из отрезков интервала [0; T]. Число подается на вход соответствующей этому отрезку линейной функции. Результат вычисления функции - есть результат шифрования.

Объединение отрезков, образованных областями значений функций ключа определяет множество шифртекстов. Злоумышленник, имея доступ к шифртекстам может выявить границы областей значений функций ключа, определить в какой из отрезков интервала [0; T] попал его зашифрованный открытый текст. Поскольку функции линейные, то злоумышленник может угадать ключ шифрования.


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

Безопасность

Безопасность схем шифрования может быть условно оценена на основе анализа, способен ли нарушитель найти ключ, используемый для шифрования. В статьях [S96], [S02]приведена классификации различных уровней атак на криптосистемы.

При работе с важными числовыми данными, злоумышленнику не нужно определять точного значения p, соответствующего зашифрованному значению с; взлом может возникнуть, если противник преуспеет в оценке области нахождения р. Для числовой области р, если противник может оценить с уверенность с% в том, что значение p лежит в интервале [р1; р2] тогда ширина интервала (р2 - р1)/(ширина области (р) )определяет оценку воздействия C% на доверительном уровне.

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

Схемы модулярного шифрования

Схема модулярного шифрования, сохраняющего порядок зашифрованных данных (Modular order-preserving encryption. MOPE), является расширением OPE, что повышает ее безопасность. Вместо того, чтобы определять данную схему как общую модель, определим ее как расширение уже сформулированной схемы OPE.

Видоизменение. Пусть OPE = (Kg`; Enc`; Dec`) является OPE схемой. Тогда схема MOPE: MOPE[OPE] = (Kg; Enc; Dec) , где

Kg  генерирует  K←s Kg` и j←s [M];  выходные значения  (K, j) .
Enc , при входных значениях ключа K и открытого текста m, выходными значениями которого являются  Enc`(K, m+j mod M) .
Dec , при входных значениях ключа K и шифртекста c, выходными значениями которого являются  Dex`(K, c) - j mod M .

Представленное выше значение j в секретном ключе алгоритма MOPE[OPE] называется секретное смещение сдвига .


Проблема

С MOPE так же,как и в OPE, очень легко для клиента выполнить ряд запросов: сделать ряд запросов [ml;mr], для которых 1 ≤ ml ≤ mr ≤ М, клиент вычисляет пару (cl; cr) = (Enc(K;ml), Enc(K;mr))и отправляет это на сервер. Затем сервер возвращает все шифртексты базы данных, найденных в диапазоне [cl; cr]. Обратите внимание, что в схеме MOPE, этот интервал шифртекстов интервал может "обтекать" пространство, т. е., если cr < cl, то сервер возвращает шифртексты базы данных, найденных в интервалах [cl;N] и [1; cr]. Для простоты, будем использовать обозначение [cl; cr] независимо от интервала обтекания.


Однако, как отмечено в [S96], существует уязвимость безопасности, если сделать ряд запросов с MOPE. Обратите внимание, что все допустимые значения запросов, т. е. вида [ml;mr], для которых 1 ≤ ml ≤ mr ≤ М, тогда зашифрованные значения могут "покрывать" каждое значение в шифрованном пространство [N] за исключением тех шифртекстов, лежащих в интервале между Enc(K;M) и Enc(K;1). Поэтому, исследовав достаточно запросов, противник может получить более полное представление о том, где лежит этот интервал, что увеличивает вероятность определения j. На рис. 3 показаны гистограммы начального значения из набора спектра запросов для небольшой области и значении смещения j= 20. В частности, предполагается, что область (и диапазон) является [0; 100] и, что все возможные допустимые диапазоны запросов длиной 10 (к = 10) генерируются и исполняются. В этом случае противник будет наблюдать, что нет запросов, которые начинаются между значениями 10 и 20, что соответствует окончанию области перед смещением. Следовательно, злоумышленник может легко прийти к выводу, что смещение равно 20.


Естественным действием, чтобы избежать такую атаку, является внедрение "обтекание вокруг" запросов [GS03]. Ряд таких запросов соответствует паре (ml, mr), для которого mr < ml. Желаемый интервал значений обтекает пространство, и [mr;M] и [1; ml]. MOPE схемы естественно поддерживают диапазоны таких запросов таким же образом, как стандартные ряды запросов. Эти запросы не являются практически полезными, но могут быть использованы в качестве "'эмуляторов запросов" для устранения атак.

Рисунок 3 - Гистограммы начальных значений

Единый алгоритм запросов

Идея данного алгоритма запросов заключается в следующем. Предположим, что запросы приходят от некоторых дистрибутива Q. Каждый раз необходимо сделать запрос, подкидывая α-несимметричную монету, которая возвращает решка с вероятностью α, чтобы решить, сделать ли запрос Q или от некоторого другого дистрибутива Q`. Мы выберем α и Q`, что выпуклая комбинация Q + (1- α) Q `= U, где U является равномерным распределением на все рассматриваемое пространство запросов, в том числе запросы типа "обтекание вокруг" в случае MOPE). Это решает две проблемы: (1) Q может быть неоднородным, даже на стандартных (не "обтекание вокруг") запросов, что нарушает техники анализа безопасности, разработанной в [BCO11], и (2) Q зависит от секретного смещения сдвига, в то время как U не зависит, и поэтому скрывает всю информацию о нем.

Определение Пусть D вероятностное распределение конечного набора S. Определим µd=max D(i), i∈S, и определим завершение D, как D`, равное : OPE 6.png, для всех i∈S.

Представление распределения запросов

Чтобы представить распределение запросов, воспользуемся гистограммой области запросов. Но поскольку каждый запрос может иметь различное начальное местоположение и длину, чтобы представить все возможные запросы, мы должны хранить О(M2) значений. В целях решения этой проблемы, выберем запросы фиксированной длины k≥1 и разложим каждый запрос в набор запросов с длиной k. Так, если оригинальный запрос пользователя имеет длину меньшую, чем k, то использовать единый фиксированный запрос, который начинается в том же месте, как и в исходном запросе. С другой стороны, если исходный запрос пользователя длиннее, чем k, то разделение запроса в набор запросов в диапазоне длины K, где снова первый фиксированный запрос начинается со старта местоположение исходного запроса. Такой подход гарантирует, что необходимо только О(M) значений для представления запроса гистограммы. Если запрос пользователя Q не раскладывается на несколько запросов фиксированной длины, то результаты всех запросов должны быть возвращены пользователю.

Распределение запросов

Рассмотрим сам алгоритм, назовем его QueryU, который обрабатывает новые запросы q. Алгоритм инициализируется с завершением распределения Q`, максимальная вероятность запроса µq и фиксированная длина запроса k. Обозначим через Bern( α) распределения Бернулли с параметром α, т. е., Bern(α) = 1 с вероятностью α. Входные данные для алгоритма-это только начало расположения запроса, поскольку запрос фиксированной длины. Алгоритм представлен на рисунке 4.

Рисунок 4 - Единый алгоритм запросов

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

Глоссарий


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

Перейти к списку литературы по разделу "Схемы шифрования, сохраняющие порядок зашифрованных данных ".

Вернуться к оглавлению

Исупова О.Е., 2015