One-time pad

Excerto de uma cifra de uso único

One-time pad (OTP), em português cifra de uso único ou chave de uso único, é uma técnica de criptografia que não pode ser quebrada se utilizada corretamente.

Visão geral

Consiste num algoritmo em que o purotexto é combinado, caractere por caractere, a uma chave secreta aleatória que para isso deve ter, no mínimo, o mesmo número de caracteres do purotexto. Para garantir que a criptografia seja imperscrutável, a chave só deve ser usada uma única vez, sendo imediatamente destruída após o uso. Foi primeiramente descrita pelo banqueiro e criptografista Frank Miller em 1882. Em 1917 foi re-inventada e, poucos anos depois, registrada.

A chave de uso único deriva da cifra de Vernam, cujo nome se deve a Gilbert Vernam, um de seus inventores. O sistema de Vernam consistia numa cifra que combinava uma mensagem com uma chave lida numa fita perfurada. Em sua forma original, o sistema de Vernam era vulnerável porque a fita com as chaves era reutilizada ao chegar ao fim. O uso único veio apenas posteriormente, quando Hoseph Maugorgne percebeu que se a fita fosse totalmente aleatória, a criptoanálise poderia ser impossível.

Se a chave for verdadeiramente aleatória, nunca reutilizada, e mantida em segredo, a cifra de uso único é imperscrutável. Também provou-se que toda a cifra teórica inquebrável deve usar chaves com as mesmas exigências que chaves de OTP.

A expressão "pad" do nome em inglês deve-se ao fato de que cifras de uso único comumente são utilizadas sob a forma de cadernetas, de modo que a folha superior possa ser arrancada e destruída após a utilização. Para facilitar sua ocultação, o bloco era às vezes muito pequeno, sendo quase impossível de ser utilizado sem uma lupa. Imagens acessíveis na Internet mostram cadernetas da KGB, capturadas por agentes oponentes, que cabem na palma da mão ou em uma casca de noz.

Existe muita ambiguidade na terminologia referente a esse tipo de cifra, já que alguns autores usam indistintamente os termos “cifra de Vernam” e “cifra de uso único”, enquanto outros utilizam a expressão "cifra de Vernam" para qualquer cifra de fluxo, inclusive as baseadas em CSPRNG.

História

O banqueiro Frank Miller, em 1882, foi o primeiro a descrever o funcionamento de chaves de uso único para uso em mensagens telegráficas.

Já no século XX, em 1917, foi criado para a AT&T o sistema eléctrico de Gilbert Vernam, patenteado em 1919, que se baseava na tecnologia utilizada no teletipo. Cada caractere na mensagem era electricamente combinado com uma chave contida numa fita perfurada. Joseph Mauborgne, então capitão das forças armadas dos Estados Unidos, percebeu que caso a sequência de caracteres na fita fosse totalmente aleatória, a criptoanálise seria mais difícil. Foi então introduzido o primeiro sistema de fita de uso único.

O próximo passo foi o desenvolvimento do sistema que utilizava a caderneta de papel. Durante muito tempo, os diplomatas usaram códigos e cifras para receber informações confidenciais e também reduzir os custos com telégrafo. Utilizando os códigos, as palavras e as frases eram convertidas em grupos de números (geralmente 4 ou 5 dígitos) usando um livro de códigos que funcionava como uma espécie de dicionário. Para aumentar a segurança, números secretos podiam ser combinados (geralmente por meio de adição modular) com cada grupo de números antes da transmissão, com os números secretos sendo trocados periodicamente. Esse sistema era chamado de superencryption. No início dos anos 1920, três criptografistas alemães — Werner Kunze, Rudolf Schauffler e Erich Langlotz -— que estavam envolvidos em descodificar esses sistemas, perceberam que eles poderiam ser indecifráveis se um número escolhido aleatoriamente fosse usado para codificar cada grupo. Eles possuíam cadernetas de papel idênticas, com grupos de números aleatórios. Cada página tinha um número de série e oito linhas; por conseguinte cada linha tinha seis números de cinco dígitos cada um. Uma página seria usada para codificar uma mensagem e imediatamente destruída. O número serial da página seria enviado com a mensagem codificada, para que o receptor soubesse qual a página a usar. Para descodificar, o destinatário deveria apenas realizar o processo inverso ao de codificação, destruindo a página após terminar. O ministério das relações exteriores alemão pôs o sistema em operação em 1923.

A última descoberta relacionada à cifra de uso único deveu-se a Claude Shannon que, nos anos 1940, comprovou cientificamente a segurança desse sistema. Shannon relatou seus resultados em um relatório confidencial em 1945 e publicou-os abertamente em 1949. Na mesma época, Vladimir Kotelnikov havia provado independentemente a segurança das chaves de uso único. Seus resultados foram registrados em um relatório que aparentemente permanece confidencial.

Exemplo

Suponhamos que Alice deseje emitir a mensagem HELLO ("olá") a Bob. Suponha que ambos estejam de posse de cadernetas que contenham sequências aleatórias idênticas previamente produzidas. Alice escolhe a página apropriada (ainda não-utilizada) da caderneta. O critério de escolha deve ser combinada previamente entre as partes. Geralmente usa-se regras como "usar a primeira folha disponível" ou "usar a folha X para o dia tal".

O material na folha selecionada é a chave para codificação e decodificação da mensagem. Cada letra da cifra será combinada de uma forma padrão a uma letra da mensagem. Geralmente, atribui-se a cada letra um valor numérico: por exemplo, A=0, B=1, e assim por diante, até Z=25. Neste exemplo, a técnica é combinar a chave e a mensagem usando a adição modular. Assim, somam-se os numéricos de cada letra da mensagem ao seu correspondente na cifra. Deve-se lembrar de considerar o módulo 26, de modo que, se uma soma ultrapassa 26, o número deve ser dividido por 26, tomando-se, no lugar dele, apenas o resto da divisão inteira.

No exemplo em questão, portanto, se o material chave começar com XMCKL e a mensagem for HELLO, opera-se do do seguinte modo:

  +  7 (H)   4 (E)  11 (L)  11 (L)  14 (O)  mensagem
    23 (X)  12 (M)   2 (C)  10 (K)  11 (L)  chave
  = 30      16      13      21      25      soma (mensagem + chave)
  =  4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z)  soma ao módulo 26 e letras correspondentes

A mensagem cifrada a ser enviada a Bob é, assim, EQNVZ. Bob usa a mesma chave, fazendo o processo inverso para obter o purotexto. Aqui, a chave é subtraída da mensagem cifrada, usando outra vez a aritmética modular:

     4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) mensagem cifrada
 -  23 (X)  12 (M)   2 (C)  10 (K)  11 (L) chave
 = -19       4      11      11      14     subtração (mensagem cifrada - chave)
 =   7 (H)   4 (E)  11 (L)  11 (L)  14 (O) subtração ao módulo 26 e mensagem decifrada

Por ser utilizada a aritmética modular, se o resultado de uma subtração é um número negativo, deve-se somar 26 a ele para transformá-lo em não-negativo. Desta forma, Bob recupera o texto original de Alice - a mensagem HELLO. Imediatamente após a transmissão, Alice e Bob devem ambos destruir a página em que se encontra a chave, impedindo sua reutilização e evitando um eventual ataque à cifra.

A KGB emite frequentemente sua cifra de uso único dos agentes impressas em folhas minúsculas “de papel do papel flash” - convertido quimicamente a nitrocelulose, que se queima quase imediatamente e não deixa nenhuma cinza. A cifra de uso único clássica de espionagem pode ser executada como um programa do software usando arquivos de dados como a entrada (plaintext) e a saída (mensagem cifrada) e o material chave (a sequência aleatória requerida). A operação de XOR é usada frequentemente para combinar o plaintext e os elementos chaves, e é especialmente atrativa em computadores desde que seja geralmente uma instrução de máquina nativa e é consequentemente muito rápida.

Entretanto, assegurar-se de que o material chave seja realmente aleatório, seja usado somente uma vez, nunca seja conhecido pela oposição, e que seja completamente destruído após o uso, realmente é muito difícil. As partes auxiliares de um software cifra de uso único apresentam desafios reais: fixar a manipulação/transmissão do plaintext, chaves verdadeiramente aleatórias, e um único uso de uma chave.

Tentativa de interceptação

Continuando no mesmo exemplo acima, suponhamos que Eve intercepte a mensagem cifrada de Alice: “EQNVZ.” Se Eve tivesse capacidade infinita de computação, descobriria que a chave “XMCKL” pode produzir o texto “HELLO”, mas descobriria também que a chave “TQURI” produziria a mensagem igualmente plausível “LATER” ("mais tarde"):

     4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) mensagem cifrada
 −  19 (T)  16 (Q)  20 (U)  17 (R)   8 (I) possível chave
 = −15       0      −7       4      17     mensagem cifrada
 =  11 (L)   0 (A)  19 (T)   4 (E)  17 (R) chave + mensagem (mod 26)

De fato, vemos que, ao tentar decifrar, é possível chegar a qualquer mensagem com o mesmo número dos caracteres fora da mensagem cifrada usando uma chave diferente e nenhuma informação na mensagem cifrada permitirá a Eve fazer uma escolha acertada entre as várias leituras possíveis da mensagem cifrada.

Segurança

As cifras de uso único são “informações teoricamente seguras” já que as mensagens cifradas não fornecem nenhuma informação sobre a mensagem original a um criptanalista, exceto seu tamanho máximo possível. Esta é uma noção muito forte de segurança primeiramente desenvolvida e provada matematicamente durante a 2ª Guerra Mundial por Claude Shannon, cujos resultados foram publicados no Jornal Técnico dos Laboratórios Bell em 1949. As cifras de uso único, se usadas corretamente são seguras mesmo se o adversário tiver capacidade computacional infinita.

A maioria de algoritmos convencionais de criptografia, seja simétrica ou assimétrica, usa padrões de teste complexos de substituição e transposição. Para o uso melhor destes atualmente, não se sabe se pode haver um procedimento criptanalítico que possa inverter (ou inverter parcialmente) estas transformações sem saber a chave usada durante a criptografia. Em termos práticos nenhum procedimento como esse é conhecido, embora já possam existir algoritmos de computador que poderiam fazê-lo em tempo “razoável”. Um dos problemas proeminentes centrais não-solucionados da informática carrega neste problema; se P=NP então seria possível que tais algoritmos pudessem ser encontrados, e se ele fossem procurados mais vigorosamente do que são hoje. Mesmo se não, os cripto sistemas atuais do indivíduo poderiam ainda ser quebrados.

Entretanto, a cifra de uso único não seria feita menos segura por uma prova que P=NP. A maioria dos observadores informados acreditam que P≠NP e, em qualquer o caso, muitos duvidam que esta pergunta tenha qualquer relevância prática ao projeto do algoritmo de criptanalise e criptografia.

Aplicabilidade da cifra de uso único

A segurança perfeita teórica da cifra de uso único aplica-se somente em um ajuste teoricamente perfeito; nenhuma execução do mundo-real de todo o cripto-sistema pode fornecer a segurança perfeita porque as considerações práticas introduzem vulnerabilidades potenciais. Estas considerações práticas da segurança e da conveniência significam que cifra de uso único é, na prática, pouco usada.

• As cifras de uso único resolvem poucos problemas práticos atuais na criptografia. As cifras da alta qualidade que se submeteram à revisão pública rigorosa estão extensamente disponíveis e sua segurança não é considerada uma preocupação principal no presente. Tais cifras são quase sempre mais fáceis de empregar do que as cifras de uso único; a quantidade do material chave que deve ser gerada corretamente e distribuído firmemente é bem menor, e a chave pública criptográfica faz com que o problema seja mais fácil.

• Os números aleatórios da alta qualidade podem ser difíceis de gerar. As funções da geração do número aleatório na maioria das bibliotecas da língua de programação não são apropriadas para o uso criptográfico. Mesmo aqueles geradores que são apropriados para o uso criptográfico normal, incluindo /dev/random e muitos geradores do número aleatório , fazem algum uso das funções criptográficas cuja segurança não é provada.

• Distribuir as chaves cifra de uso único é inconveniente. Os meios de armazenamento tais como “thumb drivers”, “DVD-Rs” ou “digital audio players” pessoais podem ser usados para carregar uma cifra de uso único muito grande de um lugar para outro de uma maneira não-suspeita, mas nivelar assim que a necessidade de transportar a caderneta fisicamente é um muito peso comparando aos protocolos chaves da negociação de um cripto-sistema moderno de chave-pública, e estes meios não podem confiantemente serem apagados por nenhum meio brevemente de incineração. Uns 4,7 GB DVD-R completamente cheios de dados de cifra de uso único, se reduzi-los em partículas de 1 mm² no tamanho, saem com mais de 100 kilobits dos dados em cada partícula. Além disso o risco do compromisso durante o trânsito é provavelmente muito maior na prática do que a probabilidade do compromisso para uma cifra tal como AES. Finalmente, o esforço necessitou controlar as escalas cifra de uso único ruins do material chave das grandes redes (networks). O número das cifras requeridas são maiores que o quadrado do número de usuários que trocam mensagens livremente entre si. Para uma comunicação entre somente duas pessoas, ou uma topologia da “rede estrela”, este é um problema menor.

• O material chave deve ser depois de usado firmemente disposto, assegurar que o material chave nunca seja reutilizado e proteger as mensagens emitidas. Porque o material chave deve ser transportado de um ponto final a outro, e persiste até que a mensagem esteja emitida ou recebida, pode ser mais vulnerável para a recuperação forense do que o plaintext que transiente ele protege.

• Como as usadas tradicionalmente, cifras de uso único não fornecem nenhuma autenticação da mensagem, a falta de uma frequente fonte de segurança faz com que ocorra falhas em sistemas de mundo-real. A natureza aditiva direta do “keystream” faz esta vulnerabilidade especialmente simples para explorar - por exemplo, um “atacante” que saiba que a mensagem contém “Meet Jane and me tomorrow at 3:30 pm (Encontre Jane e eu amanhã às 15h30)” pode substituir esse índice por todo o outro índice do mesmo comprimento, tal como “ 3:30 meeting is cancelled, stay home (O encontro de 15h30 esta cancelado casa, fique em casa”, sem ter o acesso à cifra de uso único. O hashing universal fornece uma maneira de autenticar as mensagens até um limite arbitrário de segurança mas este usa dados aleatórios adicionais da cifra, e remove a possibilidade de executar o sistema sem um computador.

Contudo, um cifra de uso único retêm algum interesse prático limitado:

• A cifra de uso único é o único criptosistema provido de segurança. Embora a maioria dos peritos tenham confiança em criptosistemas padrões para finalidades práticas, um pode não estar certo de que uma descoberta criptanalítica futura, ou uma descoberta no hardware de um computador tal como o computador quântico, não vão quebrá-los. cifra de uso único é um dos métodos mais práticos de criptografia onde uma ou ambas as obrigações dos partidos faz todo o trabalho à mão, sem o DAE (Dispositivo Automático de Entrada) de um computador; isto foi importante na era “pré-computador”, e poderia concebivelmente ainda ser útil nas situações onde há um computador é ilegal ou em incriminação ou onde os sistemas de computador operativos de confiança, não estão disponíveis.

• Fazer e usar uma cifra de uso único tem valor educacional. Nenhum equipamento especial é requerido e serve como uma introdução boa para as diversas ideias criptográficas.

• OTP pode ser usado, junto com um criptosistema mais padrão, em um esquema de super-criptografia. Adicionar uma camada de OTP é um exemplo especial de super-criptografia em que se pode provar que, desde que você usa as chaves que são estatística independente para cada camada (por exemplo RNGs independente), a combinação seria pelo menos tão forte quanto a camada a mais forte.

Usos

Em algumas situações de espionagem, a chave de uso único pode ser útil porque pode ser computada à mão, com lápis e papel. Quase todas as outras cifras de igual qualidade são pouco práticas se não se utilizar um computador. Espiões podem receber suas cadernetas pessoalmente por meio de portadores. Entretanto, no mundo moderno os computadores e outros dispositivos capazes de realizar cálculos complexos são tão ubíquos que possuir um dispositivo capaz de executar criptografia convencional (por exemplo, um telefone que possa funcionar um software criptográfico escondido) não atrairá nenhuma suspeita.

As cifras de uso único foram usadas em circunstâncias especiais desde os anos 1900. O Serviço Diplomático da República de Weimar começou a usar o método por volta de 1920. Em 1923, era empregado para comunicações diplomáticas pelo serviço diplomático alemão. A quebra da frágil criptografia soviética pelos Ingleses, com publicação das mensagens por razões políticas em dois momentos nos anos 1920, parece ter levado a URSS a adotar chaves de uso único por volta de 1930. Os espiões da KGB são conhecidos também por terem continuado a usar lápis e papel nas cifras de uso único mais recentemente. Um exemplo é o do coronel Rudolf Abel, que foi preso e condenado em Nova York nos anos 1950, e os “Krogers” (Morris e Lona Cohen), que foram presos e condenados por espionagem no Reino Unido nos anos 60. Ambos foram encontrados em posse cifras de uso único físicas.

Um grande número de nações usou sistemas de cifras de uso único para tráfego de informação confidencial. Leo Marks relatou que as operações executivas especiais britânicas usaram cifras de uso único para codificar a troca de informações entre seus escritórios. As cifras de uso único para uso com agentes ultramarinos foram introduzidas mais tarde, na guerra. Outras máquinas one-time da cifra de fita incluem as máquinas inglesas Rockex e Noreen.

A NSA descreve os sistemas one-time de fita como SIGTOT e 5-UCO como tendo sido usados para o tráfego da inteligência até a introdução da cifra eletrônica baseada em KW-26.

O “scrambler” de voz SIGSALY, da segunda guerra mundial, era uma forma de sistema de uso único. Ele adicionava ruído ao sinal no transmissor e removia-o no receptor. O padrão de ruído era distribuído aos dois canais sob a forma de gravações em goma-laca idênticas, das quais apenas duas cópias haviam sido feitas. Aconteceram problemas de sincronização que tiveram que ser resolvidos antes que o sistema pudesse ser usado.

O conhecido Telefone vermelho entre Moscou e Washington D.C., estabelecido em 1963 após a Crise dos Mísseis de Cuba, utilizava teletipos protegidos por um sistema de fita de uso único comercial. Cada país preparou as fitas com as chaves usadas para codificar suas mensagens e entregou-as através de sua Embaixada no outro país. Uma vantagem original das cifras de uso único neste caso era que nenhum país teve que revelar métodos mais elaborados de criptografia ao outro.

Durante a Invasão de Granada, em 1983, as forças dos Estados Unidos encontraram um acervo de pares de cadernetas de cifras de uso único em um armazém Cubano.

O código de comunicação tática BATCO do exército britânico é um sistema de lápis-e-papel do sistema cifra de uso único .

O material chave é fornecido nas folhas de papel que são mantidas em uma carteira plástica especial com um ponteiro de deslizamento que indica a última chave usada. As folhas novas são fornecidas diariamente e as velhas são destruídas. BATCO é usado em redes da voz do campo de batalha; as parcelas mais sensíveis de uma mensagem são codificadas e a mensagem cifrada são lidas para fora, letra por letra.

Uma noção relacionada é o código one-time, um sinal, usado somente uma vez, por exemplo o “alfa” para a “missão terminada” e o “Bravo” para a “missão falhada” não pode ser decifrado em nenhum sentido razoável da palavra. Compreender a mensagem requererá a informação adicional, frequentemente “profundidade” da repetição, ou alguma análise de tráfego. Entretanto, tais estratégias .Embora tais estratégias não sejam um “cifra de uso único” criptográficos em qualquer senso significativo.

Façanhas

Cifras de uso único são seguras se geradas e usadas corretamente, mas erros pequenos podem fazer com que a criptoanálise seja bem sucedida.

Em 1944-1945, a agência da segurança do exército dos Estados Unidos conseguiu decifrar o sistema de cifras de uso único usado alemão GEE (Erskine, 2001). O GEE era inseguro porque as chaves não eram completamente aleatórias - a máquina usada gerar as cifras produziu saídas previsíveis.

Em 1945, os Estados Unidos descobriram que mensagens enviadas de Camberra a Moscou eram cifradas primeiramente usando um livro de códigos e depois uma cifra de uso único. Entretanto, a cifra de uso único usada era mesma usada por Moscou para mensagens de Washington, D.C.. Isso, somado ao facto de que algumas das mensagens de Camberra a Moscou incluíram documentos originais britânicos conhecidos pelo governo estadunidense, permitiu que algumas das mensagens cifradas fossem quebradas.

Agências de espionagem Soviéticas empregaram cifras de uso único para comunicações secretas com seus agentes. A análise mostrou que as cifras usadas foram geradas por datilógrafos usando máquinas de escrever reais, o que não é um método realmente aleatório, já que determinadas sequências de teclas mais confortáveis acabam por ser mais prováveis do que outras. Mesmo assim, esse sistema provou-se eficaz na prática. Sem cópias do material chave usado, somente algum defeito no método da geração ou reutilização das chaves davam alguma esperança aos criptoanalistas. A partir dos anos 1940, as agências de inteligência dos Estados Unidos e do Reino Unido conseguiram decodificar mensagens cifradas soviéticas para Moscou durante a segunda guerra graças a erros cometidos na geração e na distribuição do material chave. Uma hipótese é que o centro pessoal de Moscou, agindo às pressas devido à presença de tropas alemãs nos arredores da cidade entre o fim de 1941 e o início de 1942, acabou por produzir mais de uma cópia do mesmo material chave durante esse período. Essa operação, que durou mais de uma década e recebeu o nome de VENONA, produziu uma considerável quantidade de informação, incluindo informações sobre espiões atômicos soviéticos. Mesmo assim, somente uma pequena percentagem das mensagens interceptadas foi decifrada inteira ou parcialmente (cerca de mil de um total de cem mil).