Dizemos que um sistema criptográfico é possui indistinguibilidade (indistinguishability) se dois textos ilegíveis gerados por textos legíveis diferentes tem propriedades indistinguíveis.
Na prática, isso significa que informação nenhuma sobre os legíveis pode ser obtida através da análise de diferentes ilegíveis (isso também é chamado de indistinguibilidade semântica, que pode-se provar que é equivalente a IND-CPA).
A indistinguibilidade envolve todas as peças do esquema: a criptografia, o padding e quaisquer outros mecanismos adicionais. A inviabilidade de se obter a chave, a indistinguibilidade e a unidirecionalidade são as três principais formas de segurança de um esquema criptográfico.
Um sistema possui indistinguibilidade sobre ataques de legível escolhido (indistinguishability under chosen-plaintext attack, IND-CPA) se no jogo abaixo o adversário possui uma vantagem negligente em relação ao chute aleatório: - O desafiante gera um par de chaves pública e privada e concede a pública para o adversário, mantendo a secreta para si. - O adversário pode utilizar a chave pública para encriptar legíveis escolhidos quaisquer e fazer quaisquer computações. - Quando satisfeito, o adversário deve submeter dois textos legíveis escolhidos ao desafiante. - O desafiante encripta um deles, escolhido aleatoriamente, e mostra esse texto-desafio para o adversário. - O adversário pode fazer quaisquer computações - Quando satisfeito, o adversário deve palpitar qual legível foi encriptado pelo desafiante, dentre os dois que ele entregou.
Note que se o sistema é determinístico (como o RSA cru), ele automaticamente não é IND-CPA, pois basta o adversário encriptar previamente os legíveis que ele escolheu e verificar com qual ilegível o desafio bate.
Um sistema possui indistinguibilidade sobre ataques de ilegível escolhido (indistinguishability under chosen-plaintext attack, IND-CCA1) se no jogo abaixo o adversário possui uma vantagem negligente em relação ao chute aleatório (mudanças em relação ao primeiro jogo em negrito): - O desafiante gera um par de chaves pública e privada e concede a pública para o adversário, mantendo a secreta para si. - Um oráculo de decriptação é entregue ao adversário. - O adversário pode utilizar a chave pública e o oráculo para encriptar e decriptar textos escolhidos quaisquer e fazer quaisquer computações. - Quando satisfeito, o adversário deve submeter dois textos legíveis escolhidos ao desafiante. - O desafiante encripta um deles, escolhido aleatoriamente, e mostra esse texto-desafio para o adversário. - O adversário pode fazer quaisquer computações exceto decriptar mais textos. - Quando satisfeito, o adversário deve palpitar qual legível foi encriptado pelo desafiante, dentre os dois que ele entregou.
O ElGamal é IND-CPA, mas não é IND-CCA1
Um sistema possui indistinguibilidade sobre ataques de ilegível escolhido adaptativamente (indistinguishability under adaptive chosen-plaintext attack, IND-CCA2) se no jogo abaixo o adversário possui uma vantagem negligente em relação ao chute aleatório (mudanças em relação ao primeiro jogo em negrito e em relação ao segundo em itálico): - O desafiante gera um par de chaves pública e privada e concede a pública para o adversário, mantendo a secreta para si. - Um oráculo de decriptação é entregue ao adversário. - O adversário pode utilizar a chave pública e o oráculo para encriptar e decriptar textos escolhidos quaisquer e fazer quaisquer computações. - Quando satisfeito, o adversário deve submeter dois textos legíveis escolhidos ao desafiante. - O desafiante encripta um deles, escolhido aleatoriamente, e mostra esse texto-desafio para o adversário. - O adversário pode fazer quaisquer computações podendo inclusive decriptar textos quaisquer, exceto o texto-desafio. - Quando satisfeito, o adversário deve palpitar qual legível foi encriptado pelo desafiante, dentre os dois que ele entregou.
Geralmente apenas “IND-CCA” significa “IND-CCA2”.
Indistinguibilidade não significa que o texto ilegível é indistinguível de texto aleatório, i.e., ruído: pode ser que o sistema seja IND-CCA2 mas que ainda sim seja estatisticamente perceptível que existe uma mensagem encriptada no texto ilegível.
Apesar disso, é muito comum que sistemas IND-CPA tenham também texto ilegível indistinguível de ruído, e essa é uma propriedade desejável em algumas aplicações, como na encriptação de disco e na esteganografia.
As três formar se indistinguibilidade acima estão em ordem de força, ou seja: - IND-CCA1 implica IND-CPA - IND-CCA2 implica ambos IND-CCA1 e IND-CPA