Diferença entre teoria e prática de segurança e criptografia?

21

Que diferenças interessantes existem entre teoria e prática de segurança e criptografia?

O mais interessante será, obviamente, exemplos que sugerem novos caminhos para a pesquisa teórica com base na experiência prática :).

As respostas podem incluir (mas não estão limitadas a):

  • Exemplos em que a teoria sugere que algo é possível, mas nunca é usado na prática
  • Exemplos em que a teoria sugere que algo é seguro e não é seguro na prática
  • Exemplos de algo amplamente utilizado na prática tem pouca teoria por trás disso.

...

Embargo

Se sua resposta for essencialmente da forma "A teoria é sobre assintóticos, mas a prática não é", então a teoria deve ser realmente central ou a resposta deve incluir exemplos específicos em que a experiência prática em instâncias do mundo real difere das expectativas baseadas na teoria.


Um exemplo que conheço: avaliação segura de circuitos. Muito poderoso em teoria, mas muito complicado para ser usado na prática, porque envolveria levar seu código, desenrolá-lo em um circuito e, em seguida, fazer uma avaliação segura de cada porta, uma de cada vez.

Joshua Grochow
fonte
FYI, esta questão foi inspirado por alguns dos retórica / discussão sobre esta outra pergunta: cstheory.stackexchange.com/questions/453/...
Joshua Grochow

Respostas:

23

Oh garoto, por onde começar.

O grande é definitivamente caixas pretas. Pesquisadores de criptografia se preocupam com coisas como o problema da instabilidade do Random Oracle Model. Os pesquisadores de segurança estão no outro extremo e desejam que tudo seja utilizável como uma caixa preta, não apenas funções de hash. Esta é uma fonte constante de tensão.

Para ilustrar, se você examinar a análise formal dos protocolos de segurança, por exemplo , a lógica BAN , verá que a criptografia simétrica é tratada como uma "cifra de bloco ideal". Há uma distinção sutil aqui - a lógica BAN (e outras técnicas de análise de protocolo) não afirmam ser provas de segurança; pelo contrário, são técnicas para encontrar falhas. Portanto, não é estritamente verdade que o modelo de cifra ideal esteja envolvido aqui. No entanto, é empiricamente verdade que a maior parte da análise de segurança tende a ser limitada ao modelo formal; portanto, o efeito é o mesmo.

Ainda nem falamos sobre praticantes. Esses caras geralmente nem têm idéia de que as primitivas de criptografia não são caixas pretas, e duvido que isso mude - décadas de tentativas de colocar isso em suas cabeças não fizeram diferença.

Para ver o quão ruim é o problema, considere este aviso de segurança relacionado à capacidade de perdoabilidade da assinatura da API. O bug se deve em parte ao ataque de extensão de comprimento na construção Merkle-Damgard (que é realmente muito básico) e afeta o Flickr, DivShare, iContact, Mindmeister, Myxer, RememberTheMilk, Scribd, Vimeo, Voxel, Wizehhive e Zoomr. Os autores observam que esta não é uma lista completa.

Eu acho que os profissionais merecem a maior parte da culpa por esse triste estado de coisas. Por outro lado, talvez os teóricos da criptografia precisem repensar sua posição também. A linha deles era: "caixas-pretas são impossíveis de construir; nós nem vamos tentar". Pelo que digo, já que é claro que suas construções serão (des) usadas como caixas-pretas de qualquer maneira, por que não tentar ao menos torná-las o mais próximo possível das caixas-pretas?

O artigo Merkle-Damgard Revisited é um ótimo exemplo do que estou falando. Eles estudam a noção de segurança de que "a função arbitrária de hash de comprimento H deve se comportar como um oráculo aleatório quando o bloco de construção de comprimento fixo é visto como um oráculo aleatório ou uma cifra de bloco ideal". Esse tipo de pesquisa teórica tem o potencial de ser extremamente útil na prática.

Agora vamos ao seu exemplo de avaliação de circuitos. Eu imploro para discordar do seu raciocínio. Não é como se você pegasse um binário compilado e o transformasse cegamente em um circuito. Em vez disso, você aplicaria a avaliação de circuito apenas à função de comparação subjacente, que geralmente é bastante simples. Fairplay é uma implementação de avaliação de circuitos. Um colega meu que trabalhou com ele me diz que é surpreendentemente rápido. Embora seja verdade que a eficiência seja um problema com a avaliação de circuitos (e eu conheço casos do mundo real em que ela foi rejeitada por esse motivo), está longe de ser um empecilho.

A segunda razão pela qual discordo de você é que, se você pensar em alguns dos cenários típicos da vida real, nos quais é possível que você deseje realizar uma avaliação de circuito inconsciente - por exemplo, quando duas empresas estão pensando em mesclar - os custos computacionais envolvidos são triviais em comparação com o esforço e orçamento humanos em geral.

Então, por que ninguém usa a avaliação de funções seguras genérica na prática? Ótima pergunta. Isso me leva à minha segunda diferença entre teoria e prática: a confiança realmente existe na prática! Nem tudo precisa ser feito no modelo paranóico. O conjunto de problemas que as pessoas realmente querem resolver usando criptografia é muito, muito menor do que o que os criptógrafos imaginam.

Conheço alguém que iniciou uma empresa tentando vender serviços de computação multipartidários seguros para clientes corporativos. Adivinha o quê - ninguém queria. A maneira como eles abordam esses problemas é assinar um contrato especificando o que você pode ou não fazer com os dados, e que você os destruirá após terminar de usá-los para a finalidade pretendida. Na maioria das vezes, isso funciona muito bem.

Meu último ponto de diferença entre teoria e prática é sobre PKI. Os papéis criptográficos freqüentemente colocam uma frase em algum lugar dizendo "assumimos uma PKI". Infelizmente, os certificados digitais para usuários finais (ao contrário de sites ou funcionários em um contexto corporativo, onde existe uma hierarquia natural) nunca se materializaram. Este artigo clássico descreve a alegria que ocorre quando você pede que pessoas normais usem PGP. Disseram-me que o software melhorou muito desde então, mas os problemas subjacentes de design e arquitetura e as limitações humanas não são muito diferentes hoje.

Eu não acho que os criptografadores devam estar fazendo algo diferente como consequência dessa falta de PKI do mundo real, exceto para estar ciente do fato de que isso limita a aplicabilidade do mundo real de protocolos criptográficos. Eu o joguei porque é algo que estou tentando consertar.

randomwalker
fonte
Ótima resposta! (Embora eu admita que não segui tudo isso - vou ter que seguir alguns dos seus links e lê-los, mas em outra ocasião.) Quanto à avaliação de circuito segura: adoro ouvi-la. A opinião que afirmei foi basicamente o que senti depois de fazer um curso introdutório de teoria da criptografia e perguntar ao meu professor sobre se algum dia ele é usado na prática.
Joshua Grochow
Obrigado. BTW, eu sou novo no StackExchange e não sei se o wiki da comunidade significa que a escrita em primeira pessoa não é aceitável. Se for esse o caso, sinta-se à vontade para fazer alterações.
randomwalker
Eu gostaria de poder votar esta resposta mais de uma vez.
Jeffε
O FairPlay é inseguro sob modelos de ameaças realistas (não é seguro contra invasores mal-intencionados; só é seguro se confiarmos que o adversário não se comportará de maneira adversa / maliciosa). A eficiência é fácil se a segurança não é importante, e a segurança é fácil se a eficiência não é importante, mas atualmente não se sabe como alcançar os dois simultaneamente.
DW
Seu comentário sobre os profissionais é realmente generoso. Encontrei uma empresa cujo único produto era o processamento de pagamentos de cartões de crédito que usavam a codificação Vigenère com uma chave mais curta do que alguns fragmentos de texto simples conhecido. E então eles não acreditaram em mim que era inseguro até eu lhes enviar um código de ataque.
Peter Taylor
12

A resposta do Randomwalker é muito boa. Minha lacuna favorita entre teoria e prática é o modelo de oráculo aleatório. Isso parece uma heurística muito segura na prática (supondo que as pessoas não façam algo estúpido e, pelo menos, façam extensão propriamente, veja também a resposta do randomwalker), mas não temos resultados teóricos positivos. De fato, todos os resultados teóricos sobre essa heurística são negativos. Eu acho que essa é uma ótima pergunta de pesquisa e espero que algum dia alguns resultados positivos interessantes sobre esse modelo sejam provados.

Quanto à ofuscação, tanto quanto eu sei, na prática, embora seja amplamente utilizada, a ofuscação não é considerada tão segura quanto a criptografia, e não é prudente usar a ofuscação para ocultar um segredo muito sensível e a longo prazo. (Em oposição à criptografia usando o oracle aleatório, com o qual as pessoas se sentem completamente à vontade para usar isso.) Portanto, nesse sentido, a diferença existente entre teoria e prática não é tão grande. (ou seja, ofuscação é uma área extremamente interessante que estamos longe de entender tanto na teoria quanto na prática.)

Boaz Barak
fonte
10

A criptografia homomórfica e a comunicação multipartidária segura são duas das grandes e recentes descobertas em criptografia que ainda não foram suficientemente estudadas para serem práticas: esforços de pesquisa como o PROCEED estão avançando nessa direção para identificar que tipo de modelo de programação podemos usar para escrever isso. tipo de cálculo, bem como encontrar otimizações para os principais algoritmos criptográficos que os executam em tempo razoável. Essa é uma ocorrência bastante comum em criptografia: começamos com (comparativamente) algoritmos simples que levam muito tempo para serem executados e, em seguida, os criptografadores passam anos usando a matemática para otimizar cada vez mais os algoritmos.

Edward Z. Yang
fonte
10

Exemplos em que a teoria sugere que algo é possível, mas nunca é usado na prática:

É muito fácil encontrar exemplos de coisas resolvidas na teoria, mas (1) são ineficientes demais para serem usadas na prática ou (2) ninguém se importa. Exemplos: (1) provas (genéricas) de conhecimento zero, (2) assinaturas inegáveis. De fato, olhe para qualquer conferência de criptografia e pelo menos metade dos papéis provavelmente se enquadram em uma dessas categorias.

Exemplos em que a teoria sugere que algo é seguro e não é seguro na prática:

Essa pergunta é um pouco vaga, então não tenho certeza se isso responde a ela - mas há muitos exemplos de esquemas 'comprovadamente seguros' que são quebrados na prática porque a definição de segurança não corresponde ao cenário de implantação. Somente nos últimos anos, houve ataques a (variantes prováveis ​​de) SSH e IPSec, entre outros.

Exemplos de algo amplamente utilizado na prática tem pouca teoria por trás disso:

Suponho que você queira dizer no mundo das criptografia, não no mundo da segurança geral. Um bom exemplo são as assinaturas DSS, que não têm prova de segurança.

user686
fonte
9

MMMWMWMWMWMMMM

Existem muitas empresas comerciais que oferecem soluções binárias de ofuscação e também várias soluções de código aberto. Métodos exatos de ofuscação, é claro, são mantidos em segredo; o paradigma de ofuscação predominante na indústria é heurístico; portanto, conhecer os algoritmos usados ​​para ofuscar um binário nesse contexto geralmente garante alguma vantagem na desofuscação. O ofuscamento na indústria é conhecido como "segurança através da obscuridade".

Existem abordagens teóricas para o problema de ofuscação que formalizam os desejos da indústria, mas contam com uma noção estritamente mais forte de segurança baseada na intratabilidade computacional (imagine substituir testes de equivalência de números inteiros e de string por testes de equivalência de função unidirecional). Em particular, o estudo da ofuscação de pontos compostáveis foi avançado para tentar resolver o problema de ofuscação interessante para a indústria. Infelizmente, o modelo teórico mais difundido para ofuscação baseado em um modelo inspirado em hardware à prova de violações recebeu um resultado impossível em 2001 por Barak et al. No artigo " Sobre a (im) possibilidade de programas de ofuscação ". (Vários outros modelos também receberam resultados impossíveis).

No momento, a teoria da ofuscação do programa está em um estado de fluxo, exigindo um novo modelo (provavelmente menos restritivo). De fato, o principal problema com a teoria é a falta de um modelo acordado (e, portanto, funcionários formais). O recente advento da Criptografia Totalmente Homomórfica pode fornecer tal base (isso é pura especulação por parte deste autor).

Para esclarecer, a ofuscação corresponde ao seu terceiro exemplo: "Exemplos de algo amplamente utilizado na prática têm pouca teoria por trás disso". Hoje, a ofuscação é amplamente usada tanto pela indústria quanto por aqueles com propósitos mais nefastos. Atualmente, a ofuscação na indústria não se baseia em nenhuma teoria rigorosa, apesar das tentativas.

Ross Snider
fonte
8

Existe uma lacuna significativa mesmo quando se trata de primitivos básicos, como geradores pseudo-aleatórios. Considere, por exemplo, funções pseudo-aleatórias. Na prática, as pessoas usam coisas como AES , que diferem dos candidatos teóricos (Goldreich, Goldwasser, Micali; Naor, Reingold; etc.) em várias dimensões: Primeiro, os parâmetros são completamente diferentes, por exemplo, o AES pode ter um comprimento de chave que é igual ao tamanho da entrada , o que é inédito em construções teóricas. Talvez o mais importante seja que a AES (e muitas outras cifras de bloco) segue o chamado paradigma da rede de permutação de substituição, que é bem diferente da maneira como as construções teóricas seguem (por exemplo, as mencionadas acima).

O mais interessante será, obviamente, exemplos que sugerem novos caminhos para a pesquisa teórica com base na experiência prática :).

Eu acho que o exemplo acima é um exemplo. Veja, por exemplo, este artigo com Eric Miles (do qual essencialmente essa resposta é retirada).

Manu
fonte