Essa comunicação criptografada em XOR simples é absolutamente segura?

23

Digamos que Alice e Peter tenham um cartão de memória flash USB de 4 GB. Eles encontram e salvam nos dois bastões dois arquivos nomeados alice_to_peter.key(2GB) e peter_to_alice.key(2GB) que contêm bits gerados aleatoriamente. Eles nunca se reencontram, mas se comunicam eletronicamente. Alice também mantém uma variável chamada alice_pointere Peter mantém a variável chamada peter_pointer, ambas inicialmente definidas como zero.

Quando Alice precisa enviar uma mensagem para Peter, ela envia (onde né o enésimo byte da mensagem):

encrypted_message_to_peter[n] = message_to_peter[n] XOR alice_to_peter.key[alice_pointer + n]
encrypted_payload_to_peter = alice_pointer + encrypted_message_to_peter
alice_pointer += length(encrypted_message_to_peter)

(e para segurança máxima, a parte usada da chave pode ser apagada)

Peter recebe encrypted_payload_to_peter, lê alice_pointerarmazenado no início da mensagem e faz:

message_to_peter[n] = encrypted_message_to_peter[n] XOR alice_to_peter.key[alice_pointer + n]

E para segurança máxima, após a leitura da mensagem, apague também a parte usada da chave. - EDIT: De fato, este passo com este algoritmo simples (sem verificação de integridade e autenticação) diminui a segurança, veja a publicação de Paŭlo Ebermann abaixo.

Quando Peter precisa enviar uma mensagem para Alice, eles fazem o inverso, desta vez com peter_to_alice.keye peter_pointer.

Com esse esquema trivial, eles podem enviar todos os dias pelos próximos 50 anos 2 GB / (50 * 365) = ~ 115 kB de dados criptografados nas duas direções. Se eles precisarem de mais dados para enviar, poderão usar chaves maiores, por exemplo, com os HDs de 2 TB de hoje (chaves de 1 TB), seria possível trocar 60 MB / dia pelos próximos 50 anos! São muitos dados na prática; por exemplo, usando compressão, são mais de uma hora de comunicação de voz de alta qualidade.

Parece-me que não há como um invasor ler as mensagens criptografadas sem as chaves, porque mesmo que possuam um computador infinitamente rápido, com força bruta podem obter todas as mensagens possíveis abaixo do limite, mas esse é um número astronômico de mensagens e o atacante não sabe qual delas é a mensagem real.

Estou certo? Esse esquema de comunicação é realmente absolutamente seguro? E se for seguro, ele tem seu próprio nome? A criptografia XOR é bem conhecida, mas estou procurando o nome desse aplicativo prático concreto usando chaves grandes em ambos os lados? Estou humildemente esperando que este aplicativo tenha sido inventado por alguém antes de mim. :-)

Nota: Se é absolutamente seguro, é incrível, porque com os atuais dispositivos de armazenamento grandes e de baixo custo, seria muito mais barato fazer comunicação segura do que com criptografia quântica cara, e isso tem segurança equivalente!

EDIT: Eu acho que isso será mais prático no futuro, pois os custos de armazenamento diminuem.Pode resolver a comunicação segura para sempre.Hoje, você não tem certeza se alguém ataca com sucesso as cifras existentes, mesmo um ano depois, e torna inseguras as implementações muitas vezes caras. Em muitos casos, antes que a comunicação ocorra, quando os dois lados se encontram pessoalmente, é a hora de gerar as chaves. Eu acho que é perfeito para comunicação militar, por exemplo, entre submarinos que podem ter HDs com teclas grandes e a central militar pode ter um HD para cada submarino. Também pode ser prático na vida cotidiana, por exemplo, controlar sua conta bancária, porque quando você cria sua conta, encontra-se com o banco etc.

user3123061
fonte
4
Além do esquema específico para coordenar qual parte da chave usar, este é apenas um bloco de uso único . Porém, sob uma inspeção mais detalhada, não é realmente útil para 99% dos casos de uso.
10
Como essa pergunta é sobre a força de um algoritmo criptográfico específico, pode ser mais adequado para o crypto.stackexchange.com . Para mover sua pergunta para lá, você pode sinalizar para atenção do moderador e solicitar migração.
Bart van Ingen Schenau
12
Os OTPs foram inventados há mais de um século e foram usados ​​como blocos físicos reais de papel nas duas Guerras Mundiais. ( en.wikipedia.org/wiki/One-time_pad ) O problema na criptografia, então como agora é a troca de chaves.
Gort the Robot
6
Observe que isso ainda permite resolver o problema de gerar chaves únicas suficientes para todos os dados esperados até que as duas partes se reencontrem e que as chaves devem ser geradas por um processo aleatório GENUINAMENTE - geradores de números pseudoaleatórios são vulneráveis ​​à análise, cada vez mais à medida que mais amostras usando o mesmo PRNG se tornam disponíveis.
keshlam
1
@keshlam. Gerar números aleatórios quânticos verdadeiros está se tornando muito barato. Interessante artigo no arXiv: Quantum geração de números aleatórios sobre um telefone móvel: arxiv.org/abs/1405.0435
user3123061

Respostas:

50

Sim, este é um bloco único . Se o material principal nunca for reutilizado, é teoricamente seguro.

As desvantagens são que você precisaria de uma chave por par de principais de comunicação e de uma maneira segura de trocar o material da chave antes da comunicação.

Vatine
fonte
52
Acho que vale ressaltar que "teoricamente seguro" significa que é matematicamente comprovado como inquebrável , desde que as chaves sejam realmente aleatórias e não sejam reutilizadas. Essa é a garantia mais forte que você pode obter em qualquer lugar na criptografia.
Michael Borgwardt
1
@MichaelBorgwardt enorme ponto lá. Nesse caso, "teoricamente seguro" é realmente melhor do que "praticamente seguro".
Mark
2
Caso em questão: Eu tenho uma chave aleatória de 2 GB, que passa a ter 16 bytes sequenciais de 0.
Michael
@ Michael As chances de isso acontecer são de cerca de 1 em 10 ^ 27.
este
1
@Floris Meu "cálculo": um byte tem 256 valores possíveis. Esse é um em 256 que todos serão zero. 256 ^ 16 para obter a chance de 16 bytes. E depois divida o número de bytes em 2 GB por essa chance. Acho que perdi uma divisão por 16, de qualquer maneira aqui (1024 * 1024 * 1024 * 1024 * 2 * (1/16)) / (256 ^ 16) Seu último ponto torna esse cálculo irrelevante de qualquer maneira.
este
32

Como a resposta de Vatine indica, seu algoritmo é basicamente um bloco único.

No entanto, para comentar uma de suas anotações:

Nota: Se é absolutamente seguro, então é incrível, porque hoje em dia com grandes memórias de baixo custo, é praticamente uma maneira mais barata de comunicação segura do que a criptografia quântica cara e com segurança equivalente!

Minha resposta é não, não é incrível. O diabo está sempre nos detalhes, e o diabo aqui está na troca de chaves. Seu método depende de uma troca de chaves cara a cara sem falhas. Não posso me dar ao luxo de enviar James Bond carregando um disco flash de 4 GB para todos os comerciantes da Internet toda vez que quiser comprar algo ou ter outras conexões seguras.

E, por último, o aspecto XOR do seu algoritmo não é importante. Uma cifra de substituição simples é adequada para um OTP. O ponto forte do OTP é que a chave nunca é reutilizada e supõe que James Bond esteja trocando as chaves na perfeição por ambas as partes (ou seja, troca segura de chaves anterior)

whatsisname
fonte
13
A outra coisa sobre um OTP é que a chave é (pelo menos), enquanto a mensagem para criptografar e precisa de uma muito fonte de números aleatórios de alta qualidade.
Donal Fellows
Muitos algoritmos de criptografia funcionam de alguma forma convertendo uma chave em um fluxo de dados que é indistinguível de dados aleatórios e, em seguida, usando esses dados como um bloco único. Do ponto de vista de um invasor, não há diferença entre dados verdadeiramente aleatórios e dados que são indistinguíveis de dados aleatórios (por definição; se você encontrou uma diferença, não era indistinguível), portanto, em teoria, isso é tão seguro quanto o OTP . Obviamente, quando dizemos que os dados são indistinguíveis dos verdadeiros dados aleatórios, geralmente há um monte de advertências. Esta explicação é obviamente uma simplificação grosseira.
Brian
21

Embora o one-time-pad tenha uma garantia de privacidade incondicional (matematicamente comprovada) contra um invasor que só pode ler mensagens, ele tem alguns pontos fracos.

  • Um invasor interceptador que adivinha corretamente o texto sem formatação pode manipular o texto cifrado para o que quiser (com o mesmo comprimento).

  • Se um invasor inserir ou excluir alguma mensagem (ou parte dela), os ponteiros de Alice e Bob ficarão fora de sincronia e toda comunicação futura será interrompida.

    Atualização: Isso pressupõe que ambas as partes controlem os dois ponteiros. Se você enviar o valor atual do ponteiro, estará vulnerável a ataques de duas vezes (se você permitir que o mesmo intervalo de chaves seja usado mais de uma vez) ou ataques do DOS (se você não permitir o mesmo intervalo de teclas) para ser usado mais de uma vez, por exemplo, excluindo-os).

Esses dois problemas são causados ​​por falta de integridade e proteção de autenticação - você tem uma cifra perfeita, mas não possui MAC.

Adicione um MAC ao seu protocolo one-time-pad para torná-lo realmente seguro. Cada mensagem deve receber uma "soma de verificação" que garante que ela foi realmente enviada pelo suposto remetente e não foi modificada no meio. Além disso, você deve enviar algum número de sequência para que o destinatário saiba qual parte da chave usar quando uma mensagem anterior foi perdida (ou para rejeitar a mensagem se ela estiver duplicada) - inclua isso no cálculo da soma de verificação.

Um algoritmo MAC comum faria aqui, mas suponho que você queira usar algum MAC polinomial único para ter segurança correspondente ao seu teclado único. (Pegue a chave MAC dos bits antes ou depois da sua chave de criptografia, ou seja, não reutilize uma chave para os dois objetivos.)

Paŭlo Ebermann
fonte
Se um invasor inserir ou excluir alguma mensagem (ou parte dela), os ponteiros de Alice e Bob ficarão fora de sincronia e toda comunicação futura será interrompida. Os ponteiros são independentes e não precisam estar sincronizados; portanto, nenhuma comunicação futura será interrompida se a mensagem for perdida (o deslocamento real da chave usada para criptografar a mensagem é enviado com essa mensagem). Mas você está parcialmente certo: Fora de sincronia é usada parte da chave no lado do recebimento que não é apagada porque a mensagem excluída não é recebida (a parte usada será apagada na próxima mensagem recebida).
precisa saber é o seguinte
Mas você está certo. Apresentou algoritmo simples, sem integridade e autenticação. A implementação prática precisará ser mais robusta.
precisa saber é o seguinte
@ user3123061 Eu não descartaria a integridade e a autenticação se fosse você. A técnica do ataque de texto cifrado adaptativo escolhido explora a falta de proteção à integridade para quebrar a confidencialidade . Eu chegaria ao ponto de dizer que a clássica almofada de uso único (que é o que você reinventou) é totalmente insegura , apesar de sua aparente solidez matemática, apenas por causa desse ataque.
Zwol
2
O ataque cipertexto adaptativo escolhido é uma escolha muito ruim de ataque contra um OTP verificado por humanos. OOS será notado e seu atacante será puncionado rapidamente. Somente se o receptor for processado na máquina e fornecer uma resposta, esse ataque será bom.
Joshua
@ Zack Existem muitos problemas com os OTPs, mas nenhum ameaça a confidencialidade. Observe que, mesmo que você adivinhe perfeitamente a chave plantext + da mensagem anterior, a próxima mensagem será criptografada com uma chave totalmente nova e independente (também de tamanho considerável). Não há nada para se adaptar a várias interações.
4

Na verdade, não é totalmente seguro. O que o seu protocolo vaza é o COMPRIMENTO da mensagem comunicada.

Por exemplo, se o espião sabe que você responderá com "sim" ou "não" e vê o comprimento = 2, ele pode deduzir que é "não".

Na verdade, é incrível o quanto pode ser deduzido apenas de comprimentos conhecidos, se alguém puder adivinhar o contexto.

w.pasman
fonte
3
Isso é bastante fácil de corrigir, com um nível razoável de segurança, pois você pode preencher a mensagem com lixo aleatório, para que o comprimento da mensagem seja múltiplo de um tamanho fixo de bloco - digamos 256 caracteres. Isso anularia uma análise simples do tipo sim v não, a um custo de usar o OTP mais rapidamente.
precisa
De fato - como você pode enviar ~ 115kB todos os dias pelos próximos 50 anos, você pode esperar que cada bloco tenha pelo menos 20kb, o que significa que o comprimento não é tão importante.
apnorton