Saltar para o conteúdo

Indistinguibilidade de textos cifrados

Origem: Wikipédia, a enciclopédia livre.

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 (12). 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

[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 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)

[editar | editar código-fonte]

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:

  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 textos claros distintos ao desafiador.
  4. O desafiador seleciona um b {0, 1} uniforme e aleatoriamente, e envia o texto cifrado desafio C = E(PK, ) 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 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 , onde é uma função desprezível no parâmetro de segurança k, isto é, para toda função polinomial (não-nula) existe tal que para todo .

Embora o adversário conheça , e PK, a natureza probabilística de E significa que a encriptação de será apenas um de muitos textos cifrados válidos, e portanto encriptar , , 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)

[editar | editar código-fonte]

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).

  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 textos cifrados arbitrários, ou outras operações.
  3. Posteriormente, o adversário submete dois textos claros escolhidos distintos 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 {0, 1} uniforme e aleatoriamente por e envia o texto cifrado desafio C = E(PK, ) 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 texto cifrado 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 significa que a propriedade A implica na propriedade B. siginfica que a propriedade A e B são equivalentes. significa que a propriedade A não necessariamente implica na propriedade B.

  • IND-CPA semântica segura sobre CPA.
  • NM-CPA (não maleável sob ataque de purotexto escolhido) IND-CPA.
  • NM-CPA (não maleável sob ataque de purotexto escolhido) IND-CCA2.
  • NM-CCA2 (não maleável sob ataque de cifrotexto escolhido) IND-CCA2.
  • Jonathan Katz, Yehuda Lindell, "Introduction to Modern Cryptography: Principles and Protocols," Chapman & Hall/CRC, 2007