Indistinguibilidade de Textos Cifrados

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Indistinguibilidade de Textos Cifrados, também chamados de Cifrotextos, é 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_purotexto_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 cifrotexto escolhido e Ataque de cifrotexto escolhido adaptativo. indistinguibilidade sob ataque de purotexto 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 (12). Se um adversário qualquer pode ser bem sucedido em distinguir o cifrotexto escolhido com uma probabilidade significativamente maior que 1⁄2, então esse adversário é considerado como tendo uma "vantagem" em distinguir o cifrotexto, 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 cifrotexto. Portanto, o adversário não deveria ser capaz de fazer melhor do que se tivesse estipulado aleatoriamente.

Definições formais[editar | editar código-fonte]

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 purotexto escolhido (abreviação em inglês: IND-CPA), indistinguibilidade sob ataque (não-adaptativo) de cifrotexto escolhido (IND-CCA), e indistinguibilidade sob ataque adaptativo de cifrotexto 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 de purotexto escolhido (IND-CPA)[editar | editar código-fonte]

Para um algoritmo de encriptação probabilística assimétrica de chave pública, indistinguibilidade sob ataque de purotexto 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:

  1. 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.
  2. O adversário pode realizar um número polinomialmente limitado de encriptações ou outras operações.
  3. Posteriormente, o adversário submete dois purotextos distintos \scriptstyle M_0, M_1 ao desafiador.
  4. O desafiador seleciona um b \in {0, 1} uniforme e aleatoriamente, e envia o cifrotexto desafio C = E(PK, \scriptstyle M_b) de volta ao adversário.
  5. 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 purotexto 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 cifrotextos válidos, e portanto encriptar \scriptstyle M_0, \scriptstyle M_1, e comparar os cifrotextos 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 purotextos arbitrários à medida em que o adversário solicita.

indistinguibilidade sob ataque de cifrotexto escolhido (IND-CCA, IND-CCA2)[editar | editar código-fonte]

Indistinguibilidade sob Ataque de Cifrotexto 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 cifrotextos arbitrários sob solicitação do adversário, retornando o purotexto. Na definição não-adaptativa, o adversário pode consultar esse oráculo somente até que ele receba o cifrotexto 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 cifrotexto desafio, com a restrição de que ele não pode passar o cifrotexto desafio para decriptação (pois, do contrário, a definição seria trivial).

  1. 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".
  2. O adversário pode realizar qualquer quantidade de encriptações, chamadas ao oráculo de decriptação baseadas em cifrotextos arbitrários, ou outras operações.
  3. Posteriormente, o adversário submete dois purotextos escolhidos distintos \scriptstyle M_0, M_1 ao desafiador.
  4. 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 cifrotexto desafio C = E(PK, \scriptstyle M_b) de volta para o adversário.
  5. 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 cifrotexto desafio C.
  6. 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[editar | editar código-fonte]

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.

Literatura[editar | editar código-fonte]

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

Veja Também[editar | editar código-fonte]

Predefinição:Cryptography navbox