O HMAC comeu o meu autocomplete: pesquisa type-ahead sobre e-mails encriptados

Encriptamos os PII dos utilizadores em repouso com chaves por tenant, para que um dump de base de dados divulgado não exponha nada de útil. A coluna de e-mail é texto cifrado. Números de telefone, nomes, atributos personalizados: texto cifrado. Temos orgulho nisto. É um argumento de venda.

E no dia em que entrou em produção, a caixa de pesquisa do admin deixou silenciosamente de autocompletar.

Sem erro. Sem linha de log. Ao escrever ali na pesquisa de utilizadores, o administrador do tenant que costumava ver [email protected] aparecer após três teclas passava a ver... nada, a menos que escrevesse o endereço de e-mail inteiro, exatamente. A pesquisa não tinha quebrado: tinha-se degradado em silêncio de "começa por" para "é igual a", e nada no sistema considerou que isso merecia uma menção.

Esta é a história de como recuperámos o type-ahead sobre dados que nos recusamos a armazenar em texto claro, e das três armadilhas em que caímos pelo caminho. A criptografia acabou por ser a parte fácil.

Porque é que a encriptação come o autocomplete

Com texto claro, a pesquisa por prefixo é aquilo para que as bases de dados servem. Mantenha um índice ordenado por e-mail e starts with "ali" é um range scan: tudo o que é >= "ali" e < "alj". Barato, óbvio, resolvido.

Encripte a coluna e o índice ordenado desaparece. O substituto padrão é um blind index (índice cego): ao lado do texto cifrado, armazena-se um HMAC com chave do valor, e os utilizadores procuram-se recalculando o HMAC do termo de pesquisa. HMAC(key, "[email protected]") é determinístico, por isso a procura por correspondência exata funciona na perfeição. E o índice não divulga nada legível, porque sem a chave por tenant não é possível calcular um digest para comparar.

Mas repare para que serve o HMAC. Todo o seu objetivo de design é que entradas semelhantes produzam saídas sem qualquer relação entre si: inverta um bit e obtém um digest completamente diferente. HMAC("ali") e HMAC("alistair") não têm nada a ver um com o outro. A propriedade que torna o blind index seguro de expor é precisamente a propriedade que o impede de responder a "começa por". A ordenação é fuga de informação. Um blind index não quebra a pesquisa por prefixo por acidente; quebra-a por princípio.

Foi assim que a caixa de pesquisa se degradou para correspondência exata, silenciosamente: correspondência exata era a única pergunta a que o índice ainda conseguia responder.

O design: indexar cada prefixo como um valor próprio

Se o índice só consegue responder a "é igual a", então transforme "começa por" em "é igual a".

Cada prefixo da parte local normalizada do e-mail (a parte antes do @) ganha a sua própria linha no blind index. Para [email protected], isso significa linhas para al, ali, alis, alist, e assim por diante: PartitionKey = HMAC(prefix), RowKey = o id do utilizador. Agora "começa por ali" é uma procura por correspondência exata sobre HMAC("ali"): uma única point query, sem necessidade de ordenação. A nossa pesquisa por nome já funcionava assim, pela mesma razão; o e-mail apenas se juntou a ela.

Duas constantes mantêm isto sob controlo. Os prefixos começam nos 2 caracteres (procuras de um carácter nunca foram úteis e duplicam as linhas) e têm um teto de 16 (limita o fan-out por e-mail; uma consulta mais longa simplesmente corresponde pelos seus primeiros 16 caracteres, e o punhado de candidatos é filtrado após a desencriptação). Assim, cada e-mail custa no máximo 15 linhas de índice: escritas na criação, movidas na alteração do e-mail, removidas na eliminação.

Este é o negócio numa frase: compra de volta a ordenação que se recusou a expor, e paga por ela em fan-out de escrita. Armazenamento e escritas são baratos; estrutura exposta não é. É um bom negócio.

Uma subtileza no caminho de mover-na-alteração mereceu o seu próprio comentário no código: as linhas de prefixo são chaveadas pela parte local, por isso a reescrita tem de ser despoletada quando a parte local muda, independentemente do domínio. Uma renomeação dentro do mesmo domínio, [email protected] → [email protected], parece "domínio inalterado, saltar o trabalho de índice" a uma guarda escrita a pensar no índice de domínio, e deixaria as antigas linhas de prefixo a apontar para o utilizador renomeado para sempre.

E, para sermos honestos sobre o que construímos: este índice divulga deliberadamente igualdade de prefixo. Um atacante com a tabela consegue ver que dois utilizadores partilham um prefixo de e-mail de 3 caracteres, embora não qual é. A encriptação pesquisável nunca elimina a fuga de informação; permite escolhê-la, conscientemente, por forma de consulta. Igualdade e igualdade de prefixo são a fuga que escolhemos. Esse enquadramento (escolher a fuga e depois fazer a engenharia de todo o resto à volta dela) é toda a disciplina.

O design funcionou. Depois começaram os problemas de sistemas.

Armadilha um: a chave que não podia ser criada

Os blind indexes precisam de uma chave HMAC por tenant, provisionada no transit engine do Vault tal como as nossas chaves de encriptação. Criar uma devolvia um 500: invalid key size for HMAC key.

O Vault exige um key_size explícito para chaves do tipo hmac (32 a 512 bytes), enquanto os tipos de tamanho fixo (aes256-gcm96, ecdsa-p256) o proíbem. A nossa chamada de criação de chave enviava apenas {"type":"hmac"}. Um campo em falta.

Eis porque isto foi uma armadilha e não um mero bug report: todas as operações de tokenização lançavam exceção. E o caminho de login tokeniza, porque encontrar um utilizador pelo e-mail no início de sessão passa pelo mesmo blind index que a pesquisa de admin. Ativar a encriptação não quebrou a pesquisa. Quebrou o login. A funcionalidade cujo argumento de venda é "os seus utilizadores estão mais seguros" derrubou o início de sessão logo na primeira ativação em dev. A correção é key_size=32 (HMAC-SHA256) para chaves hmac, omitido para os tipos de tamanho fixo. E uma regra permanente: fazer smoke-test ao caminho de tokenização contra um Vault real antes de ligar a encriptação em qualquer lado. Mocks não validam payloads de criação de chaves.

Armadilha dois: a atualização que podia deixar um utilizador perdido

Alterar um e-mail implica manutenção do índice: remover as linhas antigas, escrever as novas. A nossa primeira implementação fazia-o por essa ordem: apagar, depois escrever. Natural, arrumado, errado.

Cada escrita de linhas novas envolve agora o Vault (para calcular as PartitionKeys HMAC). Apague primeiro as linhas antigas, e um soluço do Vault durante a escrita deixa o utilizador nem com as linhas de lookup antigas nem com as novas. Ele existe, encriptado, na tabela, e nada consegue encontrá-lo. Incluindo o login. Isso não é uma pesquisa degradada; é um utilizador trancado fora da conta, até que algum reindex futuro passe por lá.

A correção é ordem, não tratamento de erros: escrever antes de apagar, em todos os sítios onde o índice é mantido. Um crash entre os dois passos deixa agora uma linha obsoleta a mais (inofensiva, limpa de forma preguiçosa) em vez de uma linha em falta. O modo de falha passou de "utilizador inalcançável" para "uma linha redundante", de graça. Quando um caminho de escrita envolve uma dependência remota, escolha a ordem de passos cujo estado meio-terminado consegue tolerar.

Armadilha três: a partição que comeu uma importação

Também mantemos um blind index de domínio (HMAC(domain) → membros) para que "toda a gente em acme.com" seja uma única consulta. O hashing determinístico tem uma consequência que ninguém orça até chegar uma importação: todos os utilizadores de um domínio caem numa única partição. Uma partição do Azure Table aguenta cerca de 2.000 operações por segundo. Uma importação de 50 mil utilizadores de um único domínio a partir do Auth0 afunilou todas as escritas do índice de domínio exatamente nesse gargalo.

A correção é bucketing: os membros espalham-se por 16 partições através de um hash do id do utilizador, e as leituras de domínio fazem fan-out pelos buckets (limitado, e raro o suficiente para não ter importância). Dois detalhes carregam a lição. O hash de bucket é um FNV-1a feito à mão, porque o string.GetHashCode do .NET é deliberadamente instável entre processos: faça bucketing com ele e o processo de amanhã calcula um bucket diferente para o mesmo utilizador e não consegue encontrar a linha que devia apagar. E o caminho de leitura continua a varrer as partições legadas sem bucketing, por isso as linhas existentes continuaram encontráveis sem backfill forçado: as escritas novas distribuem-se imediatamente, as linhas antigas migram quando o utilizador for tocado da próxima vez.

A lição

Nada nesta história é criptografia nova. O HMAC tem décadas; "faça hash do valor, indexe o hash" cabe numa frase. Tudo o que realmente nos custou foi trabalho de sistemas: que formas de consulta o produto precisa genuinamente (igualdade, prefixo, domínio: cada uma ganhou o seu próprio índice, porque um blind index responde exatamente a uma pergunta); como as chaves são provisionadas e o que acontece no caminho de login quando não são; em que ordem acontecem as escritas do índice quando um KMS remoto está no meio; e onde o hashing determinístico concentra carga que o texto claro nunca concentrou.

A encriptação pesquisável é vendida como uma funcionalidade de criptografia. Construa-a e vai descobrir que é uma funcionalidade de sistemas distribuídos vestida com um fato de criptografia. A caixa de pesquisa volta a autocompletar (ali encontra o Alistair após três teclas) e um dump roubado da mesma tabela mostra digests HMAC espalhados por dezasseis buckets, ou seja: nada. Ter as duas coisas ao mesmo tempo foi sempre o objetivo.