Selecionar idioma

Um Servidor de Quebra de Senhas Oblívio: Combinando Tabelas de Hellman e Protocolos PIR

Análise de um servidor de quebra de senhas que preserva a privacidade, utilizando tabelas de Hellman e protocolos de Recuperação de Informação Privada (PIR) para proteger a confidencialidade das consultas.
strongpassword.org | PDF Size: 0.2 MB
Avaliação: 4.5/5
★ ★ ★ ★ ★
Sua avaliação
Você já avaliou este documento
Capa do documento PDF - Um Servidor de Quebra de Senhas Oblívio: Combinando Tabelas de Hellman e Protocolos PIR
Ver documento PDF Baixar PDF Traduzir PDF
Início » Documentação » Um Servidor de Quebra de Senhas Oblívio: Combinando Tabelas de Hellman e Protocolos PIR

Índice

1. Introdução

Este artigo aborda um desafio crítico de privacidade em operações de segurança ofensiva: realizar a quebra de senhas através de um servidor de terceiros sem revelar os hashes alvo. O cenário envolve um pentester com recursos locais limitados (por exemplo, um smartphone) que precisa consultar grandes tabelas de hash pré-computadas (como tabelas Rainbow ou Hellman) hospedadas remotamente. O problema central é construir um servidor de quebra de senhas oblívio onde o servidor não pode descobrir quais pares de senha-hash o cliente está tentando quebrar, preservando assim o sigilo operacional.

2. Preliminares

2.1 Tabelas de Reversão de Hash

Sistemas de senha frequentemente armazenam hashes criptográficos. Atacantes usam tabelas pré-computadas para reverter esses hashes. Os principais métodos incluem:

  • Tabelas de Hellman (1980): Um compromisso tempo-memória usando cadeias de hashes e senhas, armazenando apenas os pontos inicial e final da cadeia.
  • Pontos Distintos de Rivest (1982): Uma otimização que usa valores de hash "distintos" especiais como pontos finais da cadeia para reduzir as buscas.
  • Tabelas Rainbow (Oeschlin, 2003): Usa uma função de redução diferente em cada passo da cadeia, geralmente mais rápida, mas menos adequada para o modelo de consulta baseado em PIR proposto.

O artigo argumenta que as tabelas de Hellman (ou variantes com pontos distintos) são mais compatíveis com protocolos PIR do que as tabelas Rainbow para esta aplicação específica.

2.2 Recuperação de Informação Privada

A Recuperação de Informação Privada (PIR) permite que um cliente recupere um item de um banco de dados sem que o servidor descubra qual item foi acessado. Para um único banco de dados que contém uma string de n bits, um esquema PIR envolve:

  1. Geração da Consulta (Cliente)
  2. Transmissão da Consulta
  3. Processamento da Consulta (Servidor)
  4. Transmissão da Resposta
  5. Decodificação da Resposta (Cliente)

A complexidade é medida como $O_C$ (processamento do cliente), $O_S$ (processamento do servidor) e $O_T$ (transferência). Um limite inferior fundamental é que $O_S$ deve ser pelo menos $O(n)$ para garantir a privacidade, o que significa que o servidor deve realizar um trabalho proporcional ao tamanho do banco de dados.

3. Visão Geral da Solução

A solução proposta combina de forma engenhosa tabelas de Hellman (ou tabelas de pontos distintos) com um protocolo PIR de banco de dados único. O servidor armazena as tabelas de quebra pré-computadas. Quando um cliente deseja quebrar um hash, ele usa uma consulta PIR para recuperar de forma privada as informações necessárias das localizações específicas nas tabelas de Hellman que correspondem a possíveis correspondências de cadeia, sem revelar os índices de busca.

4. Detalhes Técnicos & Construção do Algoritmo

A construção foca em adaptar as tabelas de Hellman para PIR. Uma tabela de Hellman é definida por uma função de hash criptográfica $H$ e uma função de redução $R$. Uma cadeia começa com um texto simples $SP_i$ e calcula iterativamente: $X_0 = SP_i$, $X_{j+1} = H(R(X_j))$, armazenando apenas $(SP_i, EP_i)$ onde $EP_i$ é o valor final após $t$ passos. Para verificar um hash $h$, o cliente calcula uma cadeia de comprimento $t$ começando em $h$, verificando a cada passo se o valor intermediário corresponde a um ponto final armazenado. O protocolo PIR é usado para buscar de forma privada essas comparações de pontos finais da tabela do servidor.

5. Protocolos PIR & Análise de Complexidade

O artigo analisa a sobrecarga computacional e de comunicação. Usando um protocolo PIR computacional padrão (por exemplo, baseado na suposição de residuosidade quadrática), o custo de processamento do lado do servidor $O_S$ escala com o tamanho da tabela. O custo do cliente $O_C$ e a comunicação $O_T$ são significativamente menores, mas não triviais. A análise mostra que, embora o PIR introduza sobrecarga em comparação com uma consulta em texto simples, este é o preço necessário para uma forte privacidade da consulta. A escolha das tabelas de Hellman em vez das Rainbow é justificada aqui porque as tabelas Rainbow exigem a verificação de múltiplas colunas com diferentes funções de redução, levando a mais consultas PIR e a um custo geral maior.

6. Resultados Experimentais

Um protótipo foi implementado em Python. Os experimentos demonstraram a viabilidade da abordagem. As principais métricas incluíram:

  • Tempo de Consulta: O tempo total para uma tentativa de quebra oblívia, considerando a computação PIR e a latência de comunicação.
  • Carga do Servidor: A carga computacional no servidor por consulta, confirmando o limite teórico $O(n)$.
  • Taxa de Sucesso: A probabilidade de quebrar um hash com sucesso dada a cobertura da tabela, que se alinha com as probabilidades de sucesso padrão das tabelas de Hellman.

Os resultados validaram que o sistema funciona, mas destacaram o compromisso de desempenho: a privacidade vem ao custo de um aumento na computação do servidor por consulta em comparação com um serviço não privado.

7. Conclusão & Trabalho Futuro

O artigo demonstra com sucesso uma nova arquitetura para um servidor de quebra de senhas oblívio. As direções para trabalho futuro incluem:

  • Explorar protocolos PIR mais eficientes para reduzir $O_S$ e $O_T$.
  • Investigar o uso de Ambientes de Execução Confiáveis (TEEs) como Intel SGX como uma alternativa ou complemento ao PIR criptográfico.
  • Estender o modelo para configurações PIR distribuídas ou multi-servidor para potencialmente melhorar o desempenho.

8. Análise Original & Comentário de Especialista

Insight Central: Este artigo não trata de quebrar senhas mais rápido; trata de quebrá-las de forma mais silenciosa. Os autores identificaram uma lacuna operacional gritante na segurança ofensiva: a pegada digital. Quando um membro de uma equipe vermelha consulta um serviço de quebra baseado em nuvem, esses metadados da consulta são um passivo. Este trabalho propõe criptografar a própria intenção usando PIR, tornando o servidor "oblívio". É um exemplo clássico de aplicar teoria criptográfica avançada (PIR) a um problema prático e complexo de segurança da informação. A importância é semelhante às considerações de privacidade em ataques de inversão de modelo ou ataques de inferência de associação contra APIs de aprendizado de máquina, onde a própria consulta pode vazar informações sensíveis.

Fluxo Lógico: O argumento é logicamente sólido. 1) Definir o modelo de ameaça: um servidor de terceiros não confiável. 2) Selecionar a primitiva criptográfica apropriada: PIR computacional de banco de dados único, que é a única opção viável para este cenário de servidor único sem conluio. 3) Adaptar a primitiva de quebra: Escolher tabelas de Hellman em vez de tabelas Rainbow porque sua estrutura requer menos consultas PIR, mais determinísticas, por tentativa de quebra. Esta é uma decisão de engenharia crucial que mostra um profundo conhecimento de domínio. O fluxo do problema para a ferramenta criptográfica e para a integração de sistemas é coerente.

Pontos Fortes & Fraquezas: O principal ponto forte é a novidade e a aplicabilidade direta. O protótipo prova a viabilidade do conceito. No entanto, as fraquezas são práticas. A sobrecarga de desempenho do PIR é massiva. Como os autores observam, o trabalho do servidor é $O(n)$. Para tabelas grandes (terabytes), isso é proibitivo para um serviço comercial. É uma solução que prioriza a privacidade perfeita sobre qualquer semelhança de eficiência. Além disso, ela protege apenas a consulta. O servidor ainda sabe que o cliente está realizando uma operação de quebra, o que pode ser suficiente para acionar alarmes em algumas jurisdições. Em comparação com abordagens de criptografia totalmente homomórfica (FHE) que estão surgindo, este método baseado em PIR é mais simples, mas muito menos flexível.

Insights Acionáveis: Para profissionais de segurança, este é um modelo para ferramentas ofensivas de alta garantia e que preservam a privacidade. Para pesquisadores, abre uma linha de trabalho em PIR eficiente e utilizável. O próximo passo imediato é comparar este método com uma abordagem baseada em TEE (por exemplo, executando a lógica de quebra dentro de um enclave SGX). O TEE lidaria com a computação de forma privada com potencialmente menos sobrecarga do que o PIR criptográfico, embora introduza confiança no fabricante do hardware. A visão de longo prazo deve ser um modelo híbrido: usar PIR para a busca inicial de índice mais sensível e, talvez, hardware confiável para as etapas subsequentes, equilibrando suposições de confiança e desempenho. Este trabalho, como o artigo fundamental do CycleGAN que combinou criativamente redes para tradução de imagens não pareadas, mostra como combinar duas tecnologias maduras (tabelas de Hellman e PIR) pode criar uma solução nova para um problema de nicho, mas importante.

9. Detalhes Técnicos & Formulação Matemática

O núcleo de uma cadeia de Hellman para uma função de hash $H$ e função de redução $R$ é definido iterativamente. Dado um texto simples inicial $P_0$: $$X_0 = P_0$$ $$X_{k+1} = H(R(X_k)) \quad \text{para } k = 0, 1, ..., t-1$$ O ponto final da cadeia é $X_t$. A tabela armazena pares $(P_0, X_t)$. Para inverter um hash $h$, calcula-se uma cadeia de teste a partir de $h$: $Y_0 = h$, $Y_1 = H(R(Y_0))$, ..., $Y_t = H(R(Y_{t-1}))$. A cada passo $j$, verifica-se se $R(Y_j)$ é um ponto distinto ou se $Y_j$ corresponde a um ponto final armazenado $X_t$, acionando uma regeneração da cadeia para encontrar a pré-imagem. Na versão adaptada para PIR, a verificação contra a lista de pontos finais armazenados no servidor é realizada por meio de uma consulta PIR no índice correspondente a $R(Y_j)$ ou $Y_j$.

10. Estrutura de Análise & Estudo de Caso

Estudo de Caso: Teste de Penetração Seguro como Serviço (PTaaS)
Imagine uma plataforma de PTaaS baseada em nuvem que oferece auditoria de senhas. Uma empresa cliente carrega uma lista de hashes de senha de seu próprio sistema para uma auditoria de segurança. Usando um serviço padrão, o provedor de nuvem descobre quais hashes específicos correspondem às senhas da empresa, uma potencial violação. Usando a estrutura do servidor oblívio:

  1. A ferramenta de auditoria do cliente pré-processa cada hash alvo $h$.
  2. Para cada $h$, ela calcula localmente os índices necessários $i_1, i_2, ... i_k$ nas tabelas de Hellman do provedor.
  3. Ela usa um protocolo PIR para gerar consultas criptografadas para esses índices e as envia para o servidor PTaaS.
  4. O servidor processa todas as consultas (realizando trabalho em todo o seu banco de dados) e retorna blocos de dados criptografados.
  5. O cliente descriptografa as respostas e as processa localmente para ver se alguma correspondência de cadeia foi encontrada, recuperando as senhas em texto simples.

Durante todo este processo, o provedor PTaaS vê apenas consultas criptografadas, de aparência aleatória, e não descobre nada sobre quais hashes o cliente estava testando, preservando assim a confidencialidade do conjunto interno de senhas do cliente.

11. Aplicações Futuras & Direções

Os princípios desta pesquisa se estendem além da quebra de senhas:

  • Consultas de Inteligência de Ameaças que Preservam a Privacidade: Consultar indicadores de comprometimento (IOCs) de um banco de dados compartilhado sem revelar seus próprios ativos.
  • Correspondência Confidencial de Sequências de DNA: Um hospital poderia consultar um banco de dados genômico em busca de marcadores de doença sem expor o genoma completo do paciente.
  • Filtragem Privada em Análise de Logs: Pesquisar logs de segurança compartilhados em busca de padrões de ataque sem revelar os padrões específicos aos quais sua organização é vulnerável.
  • A convergência com a Criptografia Totalmente Homomórfica (FHE) é uma direção chave. Enquanto o PIR oculta o padrão de acesso, a FHE poderia permitir que o servidor realizasse toda a computação de quebra em dados criptografados, retornando apenas um resultado criptografado. Projetos como o SEAL da Microsoft e o OpenFHE estão tornando isso mais prático.
  • A integração com a privacidade diferencial poderia adicionar uma camada de privacidade estatística, garantindo que mesmo o sucesso ou fracasso de uma consulta não vaze muitas informações.

12. Referências

  1. Calvo, A., Futoransky, A., & Sarraute, C. (2013). An Oblivious Password Cracking Server. arXiv preprint arXiv:1307.8186.
  2. Hellman, M. (1980). A cryptanalytic time-memory trade-off. IEEE Transactions on Information Theory, 26(4), 401-406.
  3. Rivest, R. L. (1982). How to reuse a "write-once" memory. (MIT Laboratory for Computer Science Technical Report).
  4. Oechslin, P. (2003). Making a faster cryptanalytic time-memory trade-off. Advances in Cryptology - CRYPTO 2003 (pp. 617-630). Springer.
  5. Chor, B., Goldreich, O., Kushilevitz, E., & Sudan, M. (1995). Private information retrieval. Proceedings of IEEE 36th Annual Symposium on Foundations of Computer Science (pp. 41-50). IEEE.
  6. Zhu, J. Y., Park, T., Isola, P., & Efros, A. A. (2017). Unpaired image-to-image translation using cycle-consistent adversarial networks. Proceedings of the IEEE international conference on computer vision (pp. 2223-2232). (Citado como um exemplo análogo de combinação criativa de tecnologias).
  7. Microsoft Research. (n.d.). Microsoft SEAL (Simple Encrypted Arithmetic Library). Recuperado de https://www.microsoft.com/en-us/research/project/microsoft-seal/