Na criptografia , uma prova de segurança é a prova de que um conjunto de algoritmos criptográficos (também chamado de esquema ) respeita as definições de segurança que lhes são exigidas. Essas definições de segurança são fornecidas em descrições de classes de esquema chamadas primitivas criptográficas . Alguns trabalhos em criptologia consistem em definir primitivas para padronizar essas definições, como as de Bellare, Micciancio e Warinschi para a assinatura do grupo em 2003, conceito que foi definido pela primeira vez por Chaum e van Heyst em 1991.
Uma primeira evidência de segurança é a segurança no sentido da teoria da informação de máscara descartável . Essa noção foi introduzida por Claude Shannon , em seu artigo Comunicação da teoria dos sistemas de sigilo publicado em 1949 , e a segurança da máscara descartável foi demonstrada neste artigo. Sendo a máscara descartável um esquema de criptografia , o conceito de segurança exigido é indistinguível do uniforme . Em outras palavras, o objetivo é que nenhum adversário possa dizer se uma mensagem criptografada é uma sequência de bits aleatórios ou se está ocultando uma mensagem. Informalmente, isso corresponde a responder a uma pergunta com um sim ou não na mensagem, então dizemos que derivamos um pouco de informação sobre a mensagem. Se isso for impossível de alcançar, então é impossível inferir qualquer coisa sobre a mensagem original.
Como é difícil obter segurança no sentido da teoria da informação, as provas criptográficas são freqüentemente baseadas em suposições computacionais , onde a noção de segurança é então reduzida à suposta complexidade dessas suposições. A criptoanálise de um conjunto de diagramas com base em uma hipótese comum é então trazida de volta ao estudo da dificuldade dessa hipótese. Às vezes falamos de redução de segurança , em referência à redução polinomial na teoria da complexidade .
A área da criptografia em que os padrões são comprovadamente seguros é chamada de segurança comprovável .
As abordagens à segurança são historicamente diferentes entre a criptografia simétrica e a criptografia assimétrica .
Mesmo que existam esquemas comprovados na criptografia de chave secreta, como o gerador pseudo-aleatório de Blum Blum Shub que é seguro sob o problema de resíduo quadrático , era frequentemente preferido em esquemas de usos práticos que resistiam às técnicas de criptanálise conhecida pela eficiência razões. O NIST recomendou SHA-1 e SHA-2 com base nisso. Mas em 2012 , o Keccak se tornou o novo padrão em termos de função hash criptográfica , provou ser seguro sob suposições sobre funções de esponja .
Na criptografia assimétrica, por outro lado, há muito consideramos os esquemas comprovados sob hipóteses computacionais. A necessidade de esquemas muito rápidos sendo cobertos por criptografia de chave privada , e o uso de criptografia assimétrica é freqüentemente feito por meio de criptografia híbrida . Por exemplo, o criptosistema ElGamal é provado sob a suposição do problema de decisão Diffie-Hellman (in) , que envolve o difícil problema do logaritmo discreto , que é um problema de aritmética modular . A prova da segurança do criptosistema ElGamal é feita por redução , ou seja, para provar que a noção de segurança resiste, provamos que essa noção no diagrama é pelo menos tão difícil quanto as suposições de segurança até um fator polinomial. Encontramo-nos, portanto, por um custo adicional considerado desprezível, para resolver um problema supostamente difícil.
Uma maneira de realizar uma redução de segurança é realizar uma redução polinomial das suposições de dificuldade para os conceitos de segurança a serem comprovados. É o caso, por exemplo, da prova do criptosistema ElGamal , ou do criptosistema Goldwasser-Micali .
A importância da sutileza das evidênciasNa segurança comprovável, medimos a qualidade de um invasor por sua vantagem , ou seja, a probabilidade de ele conseguir quebrar uma propriedade de segurança (por exemplo, produzindo uma falsificação de assinaturas digitais ). Em uma redução de segurança começamos com um atacante contra a propriedade de segurança, tendo assim uma suposta vantagem , e chegamos a um atacante contra uma hipótese de segurança , com uma vantagem polinomialmente mais fraca. É o estudo deste polinômio que é importante, uma vez que em um sistema multiusuário, a redução pode depender do número de usuários, um método genérico clássico sendo por exemplo adivinhar qual usuário será atacado pelo usuário. adversário antes de aplicar a segurança do sistema de usuário único a esse usuário-alvo. Isso dá para uma suposta vantagem ε para o sistema monousuário uma vantagem de , o que significa que para a rede de internet , há em 2016 uma perda de segurança da ordem de 2⁴¹, o que significa que para um multiusuário de segurança de 80 bits , é necessária uma segurança de usuário único de 121 bits, o que aumenta o tamanho das chaves de acordo (por exemplo, o tamanho dos números primos escolhidos para a assinatura RSA e, consequentemente, o tamanho da assinatura).
Trabalhar para obter uma estimativa melhor da perda de segurança melhora nosso conhecimento sobre a segurança dos sistemas criptográficos e, no melhor dos casos (perda de segurança constante), os criptologistas dizem que as evidências são boas .
Uma prova por jogo às vezes é usada quando a definição de segurança é dada por um jogo criptográfico a ser vencido pelo oponente . Esse é o caso, por exemplo, da segurança semântica dos esquemas de cifras. O objetivo é ir passo a passo desde o jogo original que o atacante deve vencer, transformá-lo passo a passo em um jogo que o adversário não pode vencer, por exemplo porque equivale a resolver um problema difícil ou porque não há mais informações sobre a mensagem inicial. A passagem de uma fase a outra só pode alterar a vantagem e o ponto de vista do adversário de forma insignificante em relação ao jogo anterior. De tal forma que, aplicando as diferentes transformações, terminamos com um jogo que o adversário não consegue vencer, a uma distância insignificante do conceito de segurança que queremos demonstrar.
A vantagem de tais provas é que elas são fáceis de verificar, uma vez que as passagens de uma etapa para a próxima são explicitadas, e o argumento pode, portanto, ser verificado passo a passo. A vantagem do oponente em avaliar com precisão o fator de aproximação de redução.
Podemos assim reformular a prova do criptosistema ElGamal por meio de jogos criptográficos.
A seguir, a relação " " significa que duas distribuições são estatisticamente ou computacionalmente próximas; e Adv i denota a vantagem do oponente. Para segurança semântica, trata-se de quantidade .
Finalmente, notamos que o jogo 3 não pode ser vencido por nenhum oponente com probabilidade diferente de 1/2. Além disso, a única transformação que varia essa probabilidade é o Jogo 2, onde o argumento de decisão computacional Diffie-Hellman é usado. Isso significa que, no total, a vantagem de um oponente contra este esquema é limitada pela vantagem de um oponente contra DDH; na verdade
Mas o que devemos chamar de difícil ? Uma resposta a essa pergunta é fornecida pela teoria da complexidade, da qual tomamos emprestado, entre outras coisas, o conceito de redução entre problemas. Essa teoria busca classificar os problemas de acordo com o tempo computacional necessário para resolvê-los e define classes de "dificuldade". Nesse caso, a classe que nos interessa é o chamado polinômio não determinístico (NP). Esses são os problemas para os quais uma determinada solução é "fácil" de verificar ( é verdadeira em tempo polinomial ), mas corre o risco de ser difícil (potencialmente em tempo não polinomial) de encontrar .
Pertencer a um problema da classe NP não significa que ele não seja solucionável em tempo polinomial. De fato, todos os problemas de P estão em NP, e o fato de saber se ao contrário existem problemas de NP que não estão em P chamados de Problema P = NP é uma das grandes questões em aberto na matemática.
Na criptografia teórica, outras classes de complexidades são estudadas para determinar o que é considerado difícil ou não, como AC⁰ ou NC¹ para saber o que restaria em caso de colapso da hierarquia polinomial , sabemos por exemplo que se a via unilateral existem funções , então P ≠ NP , o que invalidaria uma parte da criptografia baseada nesta hipótese de trabalho no caso de um colapso.
Os problemas usados pela criptografia estão todos em NP: é "fácil" codificar uma mensagem, ou decodificar uma mensagem quando você tem a chave. Por outro lado, no estado atual do conhecimento , todos os métodos existentes para quebrar esses códigos são exponenciais no tamanho da chave. É a desproporção prática entre o tempo de codificação ou decodificação com chave, de um lado, e de quebra, de outro, que torna os métodos úteis.
No momento, não há objeção teórica à existência de algoritmos de quebra de código polinomial em uso hoje, mas apenas a observação prática de que esses problemas resistiram aos esforços sustentados da comunidade por um longo tempo. Notemos também que os computadores quânticos, se conseguirmos construí-los de "tamanho" suficiente (número de qbits), tornariam possível quebrar sistemas como o RSA por meio do algoritmo de Shor .
Por fim, é importante observar que as evidências de segurança devem ser obtidas com cautela. Por exemplo, um sistema devido a Ajtai e Dwork, acompanhado de prova de segurança teórica assumindo algum problema difícil, foi quebrado na prática por Phong Nguyen e Jacques Stern .