A Ameaça do Vazamento de Padrões de Acesso

Criptografar dados protege seu conteúdo contra pessoas não autorizadas, mas a criptografia, por si só, não oculta os metadados sobre como os dados são acessados. Os padrões de acesso — quais registros são lidos ou gravados, quando e com que frequência — podem revelar informações sensíveis mesmo quando os próprios dados estão completamente criptografados. Essa lacuna entre a privacidade do conteúdo e a privacidade do acesso é a principal motivação para a RAM de Acesso Oculto.

A análise dos padrões de acesso pode revelar: quais registros de um banco de dados um usuário consulta (permitindo inferir condições médicas a partir dos registros acessados), padrões de comunicação (quem entra em contato com quem, mesmo quando o conteúdo das mensagens está criptografado), atividade financeira (permitindo inferir estratégias de negociação a partir dos preços solicitados por um usuário) e padrões comportamentais (rotinas diárias a partir dos horários e da frequência dos acessos). Essas inferências podem ser tão sensíveis quanto o próprio conteúdo dos dados.

CryptDB (MIT, 2011) foi um sistema influente para consultar bancos de dados criptografados. Trabalhos posteriores de Grubbs, McPherson, Naveed, Ristenpart e Spooner (2016) mostraram que o CryptDB e esquemas semelhantes de criptografia com preservação de ordem vazam padrões de acesso que possibilitam ataques de inferência. Um atacante com um conjunto de dados auxiliar sobre as distribuições de acesso pode inferir valores em texto simples apenas pela frequência e pela ordem dos acessos, mesmo sem quebrar a criptografia.

Se um serviço de armazenamento em nuvem criptografado registra quais blocos de texto cifrado são acessados, um adversário pode realizar uma análise de frequência. Como os usuários tendem a acessar arquivos populares com mais frequência, o histograma de frequência de acesso dos blocos de texto cifrado reproduz a distribuição de acesso ao texto claro. Comparar o histograma de frequência criptografado com padrões de acesso conhecidos pode identificar quais arquivos criptografados correspondem a categorias populares de conteúdo.

No modelo de ameaça honesto, porém curioso (semi-honesto), o provedor de nuvem segue o protocolo corretamente, mas observa todos os padrões de acesso aos dados do cliente. Muitos provedores de nuvem registram legitimamente os padrões de acesso para faturamento, depuração e otimização de desempenho. Mesmo sem intenção maliciosa, esses registros criam um risco: um provedor de nuvem comprometido, um funcionário mal-intencionado ou uma intimação judicial do governo poderia expor padrões de acesso confidenciais.

A RAM Oblívia (ORAM), introduzida por Goldreich e Ostrovsky (1996), é uma primitiva criptográfica que oculta os padrões de acesso do servidor. Em um esquema de ORAM, cada acesso (leitura ou gravação) a qualquer posição de memória gera a mesma distribuição de operações visíveis ao servidor, independentemente da posição que está sendo acessada. Um adversário que observa o servidor vê apenas padrões de acesso uniformemente aleatórios.

ORAM tem uma ampla variedade de aplicações sempre que a privacidade dos padrões de acesso é necessária: armazenamento seguro em nuvem (ocultando quais arquivos um usuário acessa), consultas obliviosas a bancos de dados (ocultando quais linhas são retornadas por uma consulta), enclaves SGX (impedindo canais laterais de padrões de acesso à memória do enclave), recuperação privada de informações (ocultando qual entrada do banco de dados um usuário recupera) e computação segura multipartidária (ocultando padrões de acesso ao estado intermediário).

A solução de ORAM mais simples é trivialmente óbvia: para acessar qualquer bloco, leia e regrave todos os blocos de todo o armazenamento. Isso oculta qual bloco foi acessado (todo acesso parece idêntico), mas gera uma sobrecarga de comunicação O(n) por acesso lógico, tornando a solução completamente impraticável para conjuntos de dados grandes. Os esquemas reais de ORAM buscam reduzir essa sobrecarga para O(polylog n), mantendo a obliviedade perfeita ou estatística.

Goldreich e Ostrovsky provaram um limite inferior: qualquer ORAM com sobrecarga de armazenamento no servidor O(1) deve incorrer em uma sobrecarga de comunicação de pelo menos Omega(log n) por acesso. Esse limite inferior logarítmico se aplica a ORAMs determinísticas. As construções práticas buscam alcançar uma sobrecarga O(log^2 n) ou O(log n), próxima desse mínimo teórico. O limite inferior mostra que ocultar perfeitamente os padrões de acesso tem um custo inevitável.

A criptografia simétrica pesquisável (SSE) permite fazer pesquisas em dados criptografados. Os esquemas básicos de SSE revelam os padrões de pesquisa (quais palavras-chave são pesquisadas) e os padrões de acesso (quais documentos são retornados). A SSE com privacidade futura oculta o padrão de pesquisa de documentos novos, mas também é necessário usar ORAM para ocultar quais documentos são acessados. Combinar SSE com ORAM oferece a mais forte garantia de privacidade, mas a um custo significativo de desempenho.

ORAM nem sempre é necessária. A decisão depende do modelo de ameaça: o adversário observa os padrões de acesso? Para armazenamento local com criptografia de disco completo e um adversário remoto, talvez não seja necessário usar ORAM. Para armazenamento em nuvem em que o provedor de nuvem não é confiável, ORAM é apropriada. A sobrecarga (normalmente de 20 a 50 vezes a largura de banda) vale a pena quando o vazamento de padrões de acesso é uma ameaça real e a sensibilidade dos dados justifica o custo.

Qual das opções a seguir descreve corretamente por que os padrões de acesso são confidenciais mesmo quando os dados estão criptografados?

Criptografar o conteúdo dos dados não oculta os padrões de acesso, que podem revelar informações confidenciais por meio de análise de frequência e de tempo. Provedores de nuvem em modelos honestos, porém curiosos, observam quais blocos de texto cifrado os clientes acessam. Os ataques contra CryptDB demonstraram inferências práticas a partir de padrões de acesso em bancos de dados criptografados. ORAM resolve esse problema fazendo com que todos os acessos pareçam idênticos ao servidor. A solução trivial (ler tudo a cada acesso) é impraticável com O(n); a ORAM real alcança uma sobrecarga O(log^2 n).