ULBT: Buscando e Ordenando Dados Criptografados Sem Escaneamento Completo

Em sistemas onde dados sensíveis precisam ser protegidos, mas a maior parte da informação permanece em um ambiente de acesso aberto e menos controlado, surge o desafio de gerenciar e consultar esses dados confidenciais de forma eficiente e segura. Uma abordagem comum é isolar os dados sensíveis em um "contorno" seguro com acesso restrito. Embora a descriptografia e o acesso direto a esses dados com chaves conhecidas sejam tarefas triviais, a complexidade aumenta significativamente quando grandes volumes de dados confidenciais precisam ser filtrados ou utilizados para fins de ordenação. Essencialmente, a necessidade é buscar e ordenar strings confidenciais rapidamente, minimizando as interações com a zona segura e, crucialmente, sem expor seu conteúdo. Uma solução aparente seria o uso de índices sobre os dados criptografados na zona aberta. No entanto, as abordagens clássicas frequentemente falham em escalar adequadamente ou vazam informações excessivas através do próprio índice.

Este artigo propõe uma abordagem prática para resolver esse problema utilizando a estrutura ULBT (Unbalanced Lexicographic Bucket Tree). A metodologia apresentada visa solucionar as seguintes tarefas: busca por substring, busca por prefixo e paginação com ordenação. A principal limitação imposta é a estaticidade do índice, o que significa que um índice atribuído a uma string única é fixo e imutável. A necessidade dessa abordagem se torna evidente em sistemas com zonas de segurança divididas (confiável/não confiável). Enquanto o acesso por chave primária funciona bem, operações de produto mais complexas como contains (busca por substring), startsWith (busca por prefixo) e order by com paginação em campos protegidos se tornam problemáticas. O caminho ingênuo de transferir grandes volumes de dados candidatos para a zona segura para processamento (filtragem ou ordenação) rapidamente esbarra em gargalos de rede quando se lida com dezenas ou centenas de milhões de registros. Portanto, um índice na zona aberta é necessário, mas qualquer índice inevitavelmente revela alguma informação. A tarefa se resume a um compromisso de engenharia: garantir a completude da busca (sem falsos negativos), reduzir previsivelmente o número de candidatos antes de enviá-los à zona segura, evitar a reindexação completa a cada inserção e limitar o vazamento de informações através da estrutura do índice.

A arquitetura de segurança considerada para esta implementação foca em mitigar vazamentos de tabelas e índices da zona aberta, a descriptografia parcial de registros individuais através de canais acessíveis e cenários ativos onde um atacante tenta obter material de chave para registros especificamente selecionados. O objetivo do design é impedir a recuperação barata do restante do conjunto de dados e seu significado exato, mesmo sob essas condições. A ideia central do ULBT é que ele é uma árvore lexicográfica de buckets de capacidade fixa N. Ao dividir um nó, a estabilidade das referências para registros já publicados é mantida. No contorno externo, para operações com dados criptografados, não se opera com as strings originais, mas sim com identificadores de bucket (bucket_id). A propriedade chave é que a estrutura suporta filtragem seletiva e operações de intervalo sem a necessidade de reescrever o índice externo "do zero" a cada vez. Simplificadamente, imagine uma árvore onde cada nó pode conter no máximo N chaves (por exemplo, N=5). Ao adicionar a sexta chave, o nó é dividido: seis nós filhos são criados, e o nó pai se torna um nó interno com delimitadores. Se o limite de um nó filho for excedido, ele, por sua vez, se torna um nó interno e cria nós filhos. O detalhe crucial é que o identificador do nó (bucket_id) nunca muda após sua criação. Quando um nó é dividido, o nó original permanece no lugar, mas se transforma de uma folha em um nó interno. Todas as referências externas a ele continuam funcionando, e a zona segura sabe como redirecionar transparentemente a consulta para o nó filho apropriado.

Na zona segura, reside o dicionário que mapeia chaves únicas para os valores originais das strings, as estruturas ULBT para a formação de índices da zona aberta e a base de armazenamento para a recuperação das estruturas após reinicializações do serviço. Na zona aberta, encontram-se os índices para filtragem e ordenação derivados da árvore ULBT da zona segura, juntamente com a chave única do registro da zona segura. É importante notar que a zona externa não contém as strings originais em texto claro. Para a busca por substring, a árvore ULBT é utilizada para armazenar trigramas. A construção de um índice de trigramas na zona segura envolve os seguintes passos: a string de entrada é decomposta em trigramas; cada trigrama recebe um índice de bucket na árvore ULBT na forma de uma sequência de caracteres; e o índice externo é formado "colando" as sequentes obtidas em uma única string. Durante a busca na zona aberta, a sequência de busca é enviada à zona segura, e a chave resultante é usada para a busca. Por exemplo, para a string "azbuka", decompomos em trigramas e buscamos/adicionamos na ULBT. O resultado é um conjunto de índices como "аз"(an), "азб"(c), "збу"(cf), "бук"(cd), "ука"(fee). A variação no comprimento do índice é determinada pela profundidade na árvore do bucket onde o trigrama foi encontrado. O índice final na zona aberta seria anccfcdfee. Uma consulta de busca pela substring "збук" seria transformada em cfcd, permitindo encontrar facilmente a string desejada pelo índice. É importante notar que os códigos são concatenados sem delimitadores, o que impede a recuperação inequívoca dos trigramas originais a partir do índice, mesmo em caso de comprometimento. Claramente, essa filtragem resultará em um certo número de falsos positivos, pois cfcd pode ser formado por outros índices (como c fcd, c f c d ou até mesmo c f c d), mas isso é uma vantagem do ponto de vista de segurança, pois complica ainda mais a análise. A ideia é simples: não provamos a correspondência definitivamente, mas obtemos rapidamente uma lista restrita de candidatos para verificação final na zona confiável.

Para busca por prefixo, a operação é direta. Adiciona-se um espaço inicial à substring de busca e procuram-se correspondências no início do índice para o início da string, ou como substring para buscar o início de um token. Para paginação e ordenação em campos protegidos, um ULBT separado é construído na zona segura, onde as strings completas servem como valores. Os índices de buckets são usados como índice de ordenação na zona aberta. Este índice não permite acesso direto sem processamento. Portanto, para encontrar os candidatos da página desejada na zona aberta, é necessário um processamento adicional. O algoritmo neste caso é o seguinte: na zona aberta, com base no índice, é construída uma árvore de frequência que determina a quantidade real de registros da tabela ou de um conjunto pré-filtrado em um bucket, considerando toda a subárvore. Com base nos dados skip-take, ocorre o corte das subárvores na árvore de frequência à esquerda e à direita. Uma filtragem adicional é realizada em profundidade na árvore usando um algoritmo pessimista para evitar cortes falsos negativos. O efeito prático é que para a zona segura é enviada "a página + um pequeno rabo", em vez do conjunto completo. As regras de operação (as mais importantes em produção) incluem a gestão da concorrência: a inserção de registros na árvore é rápida, mas se não for suficiente, a restrição de inserção paralela pode ser parcialmente relaxada. Uma situação sensível pode ocorrer quando, durante a inserção em uma folha, ocorre uma nova divisão do bucket. Dependendo da ordem de inserção, os registros receberão índices diferentes. Como os nós não folha são estáticos, um bloqueio de inserção paralela no nível da folha é suficiente (modelo de bloqueio: lock per leaf; inserções independentes em folhas diferentes ocorrem em paralelo). Quanto à exclusão, os valores nos nós são usados para determinar os limites dos buckets subjacentes, o que é crítico para buckets com nós folha diretos. Do ponto de vista da ideologia da zona segura, a exclusão de dados nela já é indesejável. Portanto, podem ser adotadas as seguintes regras: exclusão arbitrária é proibida; apenas o rollback sequencial dos últimos registros é permitido (LIFO-rollback). LIFO-rollback significa que apenas a última transação adicionada pode ser removida com segurança se ainda não foi confirmada na zona externa. Atualizações (UPDATE) são implementadas como uma nova versão do valor; os índices antigos não são reescritos. A consistência da publicação garante que os dados e o índice só são publicados externamente após um COMMIT bem-sucedido na zona segura; se ocorrer uma falha antes do COMMIT, nem a chave nem o índice são expostos externamente. Os invariantes de implementação incluem um identificador unificado (bucket_id) usado em toda a zona externa, a fixidez das referências (para registros já publicados, bucket_id não é reescrito), o modo de exclusão (apenas LIFO-rollback, sem exclusões arbitrárias), publicação atômica (o contorno externo vê o registro apenas após o COMMIT) e recuperação (a árvore é levantada a partir dos índices no banco de dados da zona segura). O modelo de atualizações cria um novo índice para uma nova versão, sem alterar o antigo.

Por que não Bloom Filter ou OPE? Bloom Filters são muito compactos e rápidos, mas não suportam busca por prefixo, requerem conhecimento das funções hash no cliente e podem ser vulneráveis a ataques de recuperação se os hashes forem conhecidos. Crucialmente, Bloom Filters não suportam condições posicionais, enquanto o ULBT, ao armazenar posições de trigramas, reduz drasticamente a taxa de falsos positivos. Order-Preserving Encryption (OPE) oferece ordenação "out-of-the-box" e é rápido, mas apresenta uma fuga crítica: revela a ordem exata de todos os registros, sendo vulnerável a ataques de inferência e análise de frequência. O ULBT, por outro lado, oferece vazamento mínimo, fixidez de referências, suporte a prefixos e substrings, mas é mais complexo de implementar, requer busca em duas etapas e resulta em um pequeno excesso de candidatos. Em experimentos, o algoritmo descrito foi implementado e testado em um ambiente com 1,8 milhão de linhas simulando dados confidenciais, onde a zona segura era um serviço WebAPI e a zona aberta um cliente de console em C# (.NET 9). Uma tabela com 200.000 registros (subconjunto de chaves e índices de dados com chaves duplicadas da zona segura) foi utilizada para verificação, armazenando uma coluna separada com dados criptografados para validar o funcionamento dos índices. As observações incluíram: a construção de um ULBT de string com 1,8 milhão de linhas (N=26) levou cerca de 9 segundos; a profundidade da árvore em construções para 100 execuções com ordem de entrada embaralhada foi próxima ao mínimo teórico (não mais que 6 níveis para um ótimo de 5); testes de paginação em 100 páginas aleatórias de tamanhos variados enviaram para a zona segura "tamanho da página + 5 a 30 registros" (por exemplo, para uma página de 50, de 55 a 80 candidatos); não foram observados falsos negativos, e após o processamento na zona segura, o resultado da página correspondeu exatamente ao conjunto de controle de dados abertos; a busca pelo índice aberto levou de 300 a 900 microssegundos para paginação e de 1 a 5 milissegundos para busca por substring. Os limites de aplicabilidade do ULBT são claros: é adequado quando os registros não são excluídos, quando contains/prefix/sort + page práticos são necessários, quando é crítico não recalcular todo o índice em inserções, e quando há uma separação estrita entre zonas confiáveis e não confiáveis. O ULBT não é uma solução universal se um modelo flexível de exclusão/reconstrução for necessário, se for exigida proteção formalmente comprovada do perfil de vazamento de esquemas SSE acadêmicos, ou se mesmo vazamentos estruturais de ordem forem inaceitáveis. Em conclusão, o ULBT representa um compromisso com limitações claras. Em cenários práticos com zonas separadas, ele oferece o que geralmente falta: segurança aceitável, alta seletividade, exploração previsível e velocidade suficiente para cargas de trabalho de produto reais. O artigo convida os leitores a compartilhar suas abordagens para busca em dados criptografados e suas experiências com as limitações de OPE ou esquemas SSE em produção.