Indistinguibilidade de textos cifrados

Indistinguibilidade de textos cifrados é uma propriedade de alguns esquemas de encriptação. Intuitivamente, se um criptossistema possui a propriedade de indistinguibilidade, então um adversário será incapaz de distinguir pares de textos cifrados baseados em mensagens encriptadas por eles. A propriedade de indistinguibilidade sob ataque de texto claro escolhido é considerado um requisito básico por grande parte dos criptossistemas de chave pública demonstravelmente seguros, embora alguns esquemas também proveem indistinguibilidade sob ataque de texto cifrado escolhido e ataque de texto cifrado escolhido adaptativo. indistinguibilidade sob ataque de texto claro escolhido é equivalente à propriedade de segurança semântica, e muitas provas criptográficas usam essas definições indistintamente.

Um criptossistema é considerado seguro em termos de indistinguibilidade se nenhum adversário, dado uma encriptação de uma mensagem aleatoriamente escolhida de um espaço contendo duas mensagens determinado pelo adversário, pode identificar a escolha da mensagem com uma probabilidade significativamente melhor que a adivinhação aleatória (1⁄2). Se um adversário qualquer pode ser bem sucedido em distinguir o texto cifrado escolhido com uma probabilidade significativamente maior que 1⁄2, então esse adversário é considerado como tendo uma "vantagem" em distinguir o texto cifrado, e o esquema não é considerado seguro em termos de indistinguibilidade. Essa definição engloba a noção de que em um esquema seguro, o adversão não deveria ser capaz de obter nenhuma informação somente observando o texto cifrado. Portanto, o adversário não deveria ser capaz de fazer melhor do que se tivesse estipulado aleatoriamente.

Definições formais

Segurança em termos de indistinguibilidade tem muitas definições, dependendo das suposições feitas sobre as capacidades do atacante. A definição de segurança é normalmente apresentada como um jogo, onde o criptossistema é considerado seguro se nenhum adversário pode ganhar o jogo com probabilidade significativamente maior que um adversário que estipula aleatoriamente. As definições mais comuns usadas em criptografia são indistinguibilidade sob ataque de texto claro escolhido (abreviação em inglês: IND-CPA), indistinguibilidade sob ataque (não-adaptativo) com texto cifrado escolhido (IND-CCA), e indistinguibilidade sob ataque adaptativo com texto cifrado escolhido (IND-CCA2). Segurança sob qualquer dessas definições implica segurança sob as anteriores: um esquema que é seguro sob IND-CCA também é seguro sob IND-CPA, e um esquema que é seguro sob IND-CCA2 também é seguro sob IND-CCA e sob IND-CPA. Portanto, IND-CCA2 é a mais forte das três definições de segurança.

indistinguibilidade sob ataque com texto claro escolhido (IND-CPA)

Para um algoritmo de encriptação probabilística assimétrica de chave pública, indistinguibilidade sob ataque de texto claro escolhido (IND-CPA) é definida pelo seguinte jogo entre um adversário e um desafiador. Para esquemas baseados em segurança computacional, o adversário é modelado por uma máquina de Turing de tempo polinomial probabilístico, o que significa que ela deve completar o jogo e dar como saída uma estipulação dentro de um número polinomial de unidades de tempo. Sob essa definição, E(PK, M) representa a encriptação de uma mensagem M sob a chave PK:

O desafiador gera um par de chaves PK, SK baseado em algum parâmetro de segurança k (e.g., um tamanho de chave em bits), e publica PK para o adversário. O desafiador guarda SK.
O adversário pode realizar um número polinomialmente limitado de encriptações ou outras operações.
Posteriormente, o adversário submete dois textos claros distintos $\scriptstyle M_{0},M_{1}$ ao desafiador.
O desafiador seleciona um b $\in$ {0, 1} uniforme e aleatoriamente, e envia o texto cifrado desafio C = E(PK, $\scriptstyle M_{b}$ ) de volta ao adversário.
O adversário é livre para realizar qualquer número de computações ou encriptações adicionais. Finalmente, ele dá como saída uma estipulação para o valor de b.

Um criptossistema é indistinguível sob ataque de texto claro escolhido se todo adversário de tempo polinomial probabilístico tem apenas uma "vantagem" desprezível sob estipulação aleatória. Um adversário é dito ter uma "vantagem" desprezível se ele vence o jogo acima com probabilidade $\scriptstyle \left({\frac {1}{2}}\right)\,+\,\epsilon (k)$ , onde $\epsilon (k)$ é uma função desprezível no parâmetro de segurança k, isto é, para toda função polinomial (não-nula) $poly()$ existe $k_{0}$ tal que $\scriptstyle |\epsilon (k)|\;<\;\left|{\frac {1}{poly(k)}}\right|$ para todo $\scriptstyle k\;>\;k_{0}$ .

Embora o adversário conheça $\scriptstyle M_{0}$ , $\scriptstyle M_{1}$ e PK, a natureza probabilística de E significa que a encriptação de $\scriptstyle M_{b}$ será apenas um de muitos textos cifrados válidos, e portanto encriptar $\scriptstyle M_{0}$ , $\scriptstyle M_{1}$ , e comparar os textos cifrados resultantes com o cifrotexto desafio não concede qualquer vantagem não-desprezível ao adversário.

Enquanto que a definição acima é específica para um criptossistema de chave assimétrica, ela pode ser adaptada ao caso simétrico substituindo-se a função de encriptação de chave pública por um "oráculo de encriptação", que retém a chave de encriptação secreta e encripta textos claros arbitrários à medida em que o adversário solicita.

indistinguibilidade sob ataque de texto cifrado escolhido (IND-CCA, IND-CCA2)

Indistinguibilidade sob Ataque de texto cifrado Escolhido não-adaptativo (IND-CCA, IND-CCA2) usa uma definição semelhante à de IND-CPA. Entretanto, além da chave pública (ou do oráculo de encriptação, no caso simétrico), o adversário ganha acesso a um oráculo de decriptação que decripta textos cifrados arbitrários sob solicitação do adversário, retornando o texto claro. Na definição não-adaptativa, o adversário pode consultar esse oráculo somente até que ele receba o texto cifrado desafio. Na definição adaptativa, o adversário pode continuar a consultar o oráculo de decriptação mesmo após ele ter recebido o texto cifrado desafio, com a restrição de que ele não pode passar o texto cifrado desafio para decriptação (pois, do contrário, a definição seria trivial).

O desafiador gera um par de chaves "PK", "SK" baseado em algum parâmetro de segurança k (e.g. um tamanho de chave em bits), e publica "PK" para o adversário. O desafiador retém "SK".
O adversário pode realizar qualquer quantidade de encriptações, chamadas ao oráculo de decriptação baseadas em textos cifrados arbitrários, ou outras operações.
Posteriormente, o adversário submete dois textos claros escolhidos distintos $\scriptstyle M_{0},M_{1}$ ao desafiador.
The challenger selects a bit b ∈ {0, 1} uniformly at random, and sends the "challenge" ciphertext C = E(PK, ) back to the adversary. O desafiador seleciona um bit b $\scriptstyle \in$ {0, 1} uniforme e aleatoriamente por e envia o texto cifrado desafio C = E(PK, $\scriptstyle M_{b}$ ) de volta para o adversário.
O adversário é livre para realizar qualquer quantidade de computações ou encriptações adicionais.
1. No caso não adaptativo (IND-CCA), o adversário pode não fazer futuras chamadas ao oráculo de decriptação.
2. No caso adaptativo (IND-CCA2), o adversário pode fazer chamadas para o oráculo de decriptação, mas não pode submeter o texto cifrado desafio C.
Finamente, o adversário faz uma estipulação para o valor de "b e o dá como saída.

Um esquema é IND-CCA/IND-CCA2 seguro se nenhum adversário tem uma vantagem não desprezível para vencer o jogo acima.

Equivalência e implicações

Indistinguibilidade é uma importante propriedade para manutenção da confidencialidade de comunicações encriptadas. No entanto, a propriedade da indistinguibilidade tem, em alguns casos sido revelada como implicando em outras, aparentemente não-relacionadas propriedades de segurança. Às vezes essas implicações vão em ambas as direções, tornando as duas definições equivalentes; por exemplo, sabe-se que a propriedade da indisguinbilidade sob ataque de cifrotexto escolhido adaptativo (IND-CCA2) é equivalente à propriedade da não-maleabilidade sob o mesmo cenário de ataque (NM-CCA2). Essa equivalência não é imediatamente óbvia, pois não-maleabilidade é uma propriedade que trata da integridade de mensagens, ao invés de confidencialidade. Em outros casos, tem sido demonstrado que indistinguibilidade pode ser combinada com certas outras definições, de modo a levar a outras definições úteis, e vice-versa. A seguinte lista resume algumas implicações conhecidas, embora não seja de forma alguma completa.

A notação $\scriptstyle A\;\Rightarrow \;B$ significa que a propriedade A implica na propriedade B. $\scriptstyle A\;\Leftrightarrow \;B$ siginfica que a propriedade A e B são equivalentes. $\scriptstyle A\;\not \Rightarrow \;B$ significa que a propriedade A não necessariamente implica na propriedade B.

IND-CPA $\scriptstyle \Leftrightarrow$ semântica segura sobre CPA.
NM-CPA (não maleável sob ataque de purotexto escolhido) $\scriptstyle \Rightarrow$ IND-CPA.
NM-CPA (não maleável sob ataque de purotexto escolhido) $\scriptstyle \not \Rightarrow$ IND-CCA2.
NM-CCA2 (não maleável sob ataque de cifrotexto escolhido) $\scriptstyle \Leftrightarrow$ IND-CCA2.

Bibliografia

Jonathan Katz, Yehuda Lindell, "Introduction to Modern Cryptography: Principles and Protocols," Chapman & Hall/CRC, 2007