Угроза утечки шаблонов доступа

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

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

CryptDB (MIT, 2011) была влиятельной системой для выполнения запросов к зашифрованным базам данных. Последующие исследования Груббса, McPherson, Навида, Ристенпарта и Спунера (2016) показали, что CryptDB и аналогичные схемы шифрования с сохранением порядка раскрывают шаблоны доступа, позволяя проводить атаки вывода. Имея вспомогательный набор данных о распределении обращений, противник может восстановить значения в открытом виде только по частоте и порядку обращений, даже не взламывая шифрование.

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

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

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

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

Простейшее решение ORAM очевидно: чтобы обратиться к одному блоку, нужно прочитать и перезаписать каждый блок во всём хранилище. Это скрывает, к какому блоку обращались (каждое обращение выглядит одинаково), но создаёт накладные расходы на обмен данными O(n) для каждого логического обращения, что делает такой подход полностью непригодным для больших наборов данных. Реальные схемы ORAM стремятся уменьшить эти расходы до O(polylog n), сохраняя при этом полное или статистическое сокрытие шаблонов доступа.

Голдрайх и Островский доказали нижнюю границу: любая схема ORAM с O(1) накладными расходами на хранение на сервере должна иметь как минимум Omega(log n) накладных расходов на обмен данными для каждого обращения. Эта логарифмическая нижняя граница относится к детерминированным схемам ORAM. Практические конструкции стремятся достичь накладных расходов O(log^2 n) или O(log n), приближаясь к этому теоретическому минимуму. Нижняя граница показывает, что полное скрытие шаблонов доступа неизбежно связано с определёнными затратами.

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

ORAM нужен не всегда. Решение зависит от модели угроз: наблюдает ли противник шаблоны доступа? Для локального хранилища с полнодисковым шифрованием и удалённым противником ORAM может быть не нужен. Для облачного хранилища, где поставщику облачных услуг нельзя доверять, ORAM уместен. Накладные расходы (обычно увеличение трафика в 20–50 раз) оправданы, когда утечка шаблонов доступа действительно представляет угрозу, а важность данных оправдывает такие затраты.

Шифрование содержимого данных не скрывает шаблоны доступа, которые могут раскрывать конфиденциальную информацию с помощью частотного анализа и анализа времени. Поставщики облачных услуг в моделях «честный, но любопытный» наблюдают, к каким блокам шифротекста обращаются клиенты. Атаки на CryptDB показали возможность практического вывода информации из шаблонов доступа в зашифрованных базах данных. ORAM решает эту проблему, делая все обращения одинаковыми с точки зрения сервера. Простейшее решение (читать всё при каждом обращении) непригодно на практике из-за O(n); реальные схемы ORAM обеспечивают накладные расходы O(log^2 n).