Pad de uso único

Um formato de um pad usado pela Agência Nacional de Segurança dos EUA, código chamado DIANA. A tabela à direita é uma ajuda para converter entre texto simples e cifratexto usando os caracteres à esquerda como a chave.

Na criptografia, o one-time pad (OTP) é uma técnica de criptografia que não pode ser violada, mas requer o uso de uma chave pré-compartilhada de uso único que é maior ou igual ao tamanho da mensagem que está sendo enviada. Nesta técnica, um texto sem formatação é emparelhado com uma chave secreta aleatória (também chamada de one-time pad). Em seguida, cada bit ou caractere do texto simples é criptografado combinando-o com o bit ou caractere correspondente do bloco usando adição modular.

O texto cifrado resultante será impossível de descriptografar ou quebrar se as quatro condições a seguir forem atendidas:

1. A chave deve ser pelo menos enquanto o texto simples.
2. A chave deve ser aleatória (uniformamente distribuída no conjunto de todas as chaves possíveis e independente do texto liso), totalmente amostrada de uma fonte não-algoritmética, caótica, como um gerador de números aleatórios de hardware; padrão, de acordo com a definição de Gregory Chaitin. Não é suficiente para as chaves OTP passarem testes de aleatoriedade estatística, pois tais testes não podem medir a entropia, e o número de bits de entropia deve ser pelo menos igual ao número de bits no texto simples. Por exemplo, usar hashes criptográficos ou funções matemáticas (como logaritmo ou raiz quadrada) para gerar chaves de menos bits de entropia quebraria o requisito de distribuição uniforme, e, portanto, não forneceria segredo perfeito.
3. A chave nunca deve ser reutilizada no todo ou em parte.
4. A chave deve ser mantida completamente secreta pelas partes comunicantes.

Também foi provado matematicamente que qualquer cifra com a propriedade de sigilo perfeito deve usar chaves com efetivamente os mesmos requisitos que as chaves OTP. Versões digitais de cifras de uso único têm sido usadas por nações para comunicações diplomáticas e militares críticas, mas os problemas de distribuição segura de chaves as tornam impraticáveis para a maioria das aplicações.

Descrito pela primeira vez por Frank Miller em 1882, o one-time pad foi reinventado em 1917. Em 22 de julho de 1919, a Patente dos EUA 1.310.719 foi emitida para Gilbert Vernam para a operação XOR usada para a criptografia de uma única vez almofada. Derivado de sua cifra de Vernam, o sistema era uma cifra que combinava uma mensagem com uma chave lida de uma fita perfurada. Em sua forma original, o sistema de Vernam era vulnerável porque a fita chave era um loop, que era reutilizado sempre que o loop fazia um ciclo completo. O uso único veio mais tarde, quando Joseph Mauborgne reconheceu que, se a fita da chave fosse totalmente aleatória, a criptoanálise seria impossível.

O "pad" parte do nome vem de implementações iniciais em que o material principal era distribuído como um bloco de papel, permitindo que a folha superior atual fosse arrancada e destruída após o uso. Para ocultação, a almofada às vezes era tão pequena que era necessária uma lupa poderosa para usá-la. A KGB usava absorventes de tal tamanho que cabiam na palma da mão ou na casca de uma noz. Para aumentar a segurança, os absorventes de uso único às vezes eram impressos em folhas de nitrocelulose altamente inflamável, para que pudessem ser facilmente queimados após o uso.

Existe alguma ambigüidade no termo "cifra de Vernam" porque algumas fontes usam "cifra de Vernam" e "one-time pad" como sinônimos, enquanto outros se referem a qualquer cifra de fluxo aditivo como uma "cifra de Vernam", incluindo aquelas baseadas em um gerador de números pseudo-aleatórios criptograficamente seguro (CSPRNG).

História

Frank Miller em 1882 foi o primeiro a descrever o sistema one-time pad para proteger a telegrafia.

O próximo sistema de uso único era elétrico. Em 1917, Gilbert Vernam (da AT&T Corporation) inventou e posteriormente patenteou em 1919 (Patente dos EUA 1.310.719) uma cifra baseada na tecnologia de teleimpressão. Cada caractere em uma mensagem foi eletricamente combinado com um caractere em uma chave de fita de papel perfurada. Joseph Mauborgne (então capitão do Exército dos EUA e mais tarde chefe do Signal Corps) reconheceu que a sequência de caracteres na fita da chave poderia ser completamente aleatória e que, se assim fosse, a criptoanálise seria mais difícil. Juntos, eles inventaram o primeiro sistema de fita única.

O próximo desenvolvimento foi o sistema de bloco de papel. Os diplomatas há muito usam códigos e cifras para manter a confidencialidade e minimizar os custos do telégrafo. Para os códigos, palavras e frases foram convertidas em grupos de números (normalmente 4 ou 5 dígitos) usando um livro de códigos semelhante a um dicionário. Para aumentar a segurança, os números secretos podiam ser combinados com (geralmente adição modular) cada grupo de código antes da transmissão, com os números secretos sendo alterados periodicamente (isso era chamado de supercriptografia). No início da década de 1920, três criptógrafos alemães (Werner Kunze, Rudolf Schauffler e Erich Langlotz), que estavam envolvidos na quebra de tais sistemas, perceberam que eles nunca poderiam ser quebrados se um número aditivo escolhido aleatoriamente fosse usado para cada grupo de código. Eles tinham blocos de papel duplicados impressos com linhas de grupos de números aleatórios. Cada página tinha um número de série e oito linhas. Cada linha tinha seis números de 5 dígitos. Uma página seria usada como uma folha de trabalho para codificar uma mensagem e depois destruída. O número de série da página seria enviado com a mensagem codificada. O destinatário reverteria o procedimento e então destruiria sua cópia da página. O Ministério das Relações Exteriores da Alemanha colocou esse sistema em operação em 1923.

Uma noção separada era o uso de um único bloco de letras para codificar o texto sem formatação diretamente, como no exemplo abaixo. Leo Marks descreve a invenção de tal sistema para o Executivo Britânico de Operações Especiais durante a Segunda Guerra Mundial, embora suspeitasse na época que já era conhecido no mundo altamente compartimentalizado da criptografia, como por exemplo em Bletchley Park.

A descoberta final foi feita pelo teórico da informação Claude Shannon na década de 1940, que reconheceu e comprovou o significado teórico do sistema one-time pad. Shannon apresentou seus resultados em um relatório classificado em 1945 e os publicou abertamente em 1949. Ao mesmo tempo, o teórico da informação soviético Vladimir Kotelnikov provou independentemente a segurança absoluta do bloco de uso único; seus resultados foram entregues em 1941 em um relatório que aparentemente permanece confidencial.

Exemplo

Suponha que Alice deseja enviar a mensagem hello para Bob. Suponha que dois blocos de papel contendo sequências aleatórias idênticas de letras foram de alguma forma produzidos anteriormente e emitidos com segurança para ambos. Alice escolhe a página não utilizada apropriada do bloco. A forma de o fazer é normalmente combinada com antecedência, como por exemplo "utilize a 12ª folha no dia 1 de maio", ou "utilize a próxima folha disponível para a próxima mensagem".

O material na folha selecionada é a chave para esta mensagem. Cada letra do bloco será combinada de forma predeterminada com uma letra da mensagem. (É comum, mas não obrigatório, atribuir a cada letra um valor numérico, por exemplo, a é 0, b é 1 e assim por diante.)

Neste exemplo, a técnica é combinar a chave e a mensagem usando adição modular, não muito diferente da cifra de Vigenère. Os valores numéricos da mensagem correspondente e as letras-chave são somados, módulo 26. Portanto, se o material da chave começar com XMCKL e a mensagem for hello, a codificação será feita do seguinte modo:

 h e l l o mensagem
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 mensagem + chave
= 4 (E) 16 (Q) 13 (N) 21 (V) 25 (Z) (mensagem + chave) mod 26
E Q N V Z → cifratexto

Se um número for maior que 25, então o resto após a subtração de 26 é calculado de forma aritmética modular. Isso significa simplesmente que se os cálculos "passarem" Z, a sequência recomeça em A.

O texto cifrado a ser enviado para Bob é, portanto, EQNVZ. Bob usa a página-chave correspondente e o mesmo processo, mas ao contrário, para obter o texto simples. Aqui a chave é subtraída do texto cifrado, novamente usando aritmética modular:

 E Q N V Z cifrado
4 (E) 16 (Q) 13 (N) 21 (V) 25 (Z) cifratexto
- 23 (X) 12 (M) 2 (C) 10 (K) 11 (L) chave
= −19 4 11 11 14 cifratexto – chave
= 7 (h) 4 (e) 11 (l) 11 (l) 14 (o) cifratexto – chave (mod 26)
h e l o → mensagem

Semelhante ao acima, se um número for negativo, 26 será adicionado para tornar o número zero ou superior.

Assim, Bob recupera o texto simples de Alice, a mensagem Olá . Alice e Bob destroem a folha -chave imediatamente após o uso, impedindo a reutilização e um ataque contra a cifra. A KGB costumava emitir seus agentes, impressos em pequenas folhas de papel flash, papel quimicamente convertido em nitrocelulose, que queima quase instantaneamente e não deixa cinzas.

A almofada clássica única da espionagem usava almofadas reais de minúsculo, papel facilmente escondido, um lápis afiado e alguma aritmética mental. O método pode ser implementado agora como um programa de software, usando arquivos de dados como entrada (texto simples), saída (CipherText) e material -chave (a sequência aleatória necessária). A operação exclusiva ou (XOR) é frequentemente usada para combinar o texto simples e os elementos -chave e é especialmente atraente nos computadores, pois geralmente é uma instrução de máquina nativa e, portanto, é muito rápida. No entanto, é difícil garantir que o material chave seja aleatório, seja usado apenas uma vez, nunca se torne conhecido pela oposição e seja completamente destruído após o uso. As partes auxiliares de um software implementação única apresentam desafios reais: manuseio/transmissão segura de texto simples, teclas verdadeiramente aleatórias e uso único da chave.

Tentativa de criptonálise

Para continuar o exemplo acima, suponha que Eve intercepte o CipherText: eqnvz . Se Eve tentasse todas as teclas possíveis, ela descobriria que a chave xmckl produziria o texto simples hello , mas ela também descobriria que a chave tquri produziria o texto simples mais tarde , uma mensagem igualmente plausível:

 4 (E) 16 (Q) 13 (N) 21 (V) 25 (Z) cifratexto
− 19 (T) 16 (Q) 20 (U) 17 (R) 8 (I) possível chave
= −15 0 −7 4 17 cifratexto-chave
= 11 (l) 0 (a) 19 (t) 4 (e) 17 (r) cifratexto-chave (mod 26)

Na verdade, é possível "descriptografar" do texto cifrado qualquer mensagem com o mesmo número de caracteres, simplesmente usando uma chave diferente, e não há nenhuma informação no texto cifrado que permita a Eve escolher entre as várias leituras possíveis do texto cifrado.

Se a chave não for verdadeiramente aleatória, é possível usar a análise estatística para determinar qual das chaves plausíveis é a "menos" aleatório e, portanto, mais provável de ser o correto. Se uma chave for reutilizada, ela será visivelmente a única chave que produz textos simples sensatos de ambos os textos cifrados (as chances de alguma chave incorreta aleatória também produzir dois textos simples sensatos são muito pequenas).

Sigilo perfeito

Os blocos de uso único são "informações teoricamente seguras" em que a mensagem criptografada (ou seja, o texto cifrado) não fornece nenhuma informação sobre a mensagem original para um criptoanalista (exceto o comprimento máximo possível da mensagem). Esta é uma noção muito forte de segurança desenvolvida pela primeira vez durante a Segunda Guerra Mundial por Claude Shannon e provou, matematicamente, ser verdadeira para o bloco de uso único de Shannon mais ou menos na mesma época. Seu resultado foi publicado no Bell System Technical Journal em 1949. Usados corretamente, os one-time pads são seguros nesse sentido, mesmo contra adversários com poder computacional infinito.

Shannon provou, usando considerações teóricas da informação, que o one-time pad tem uma propriedade que ele chamou de perfeito sigilo; ou seja, o texto cifrado C não fornece absolutamente nenhuma informação adicional sobre o texto simples. Isso ocorre porque (intuitivamente), dada uma chave aleatória verdadeiramente uniforme que é usada apenas uma vez, um texto cifrado pode ser traduzido em qualquer texto simples do mesmo tamanho, e todos são igualmente prováveis. Assim, a probabilidade a priori de uma mensagem de texto plano M é a mesma que a probabilidade a posteriori de uma mensagem de texto simples M dado o texto cifrado correspondente.

Matematicamente, isso é expresso como H. H. H.(M)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =H. H. H.(M|C)- Sim. {H} (M)=mathrm {H} (M|C)}, onde H. H. H.(M)(M)} é a entropia da informação do texto liso e H. H. H.(M|C)(M|C)} é a entropia condicional do texto liso dado o cifratexto C. (Aqui, Olá. é a capital grega letra eta.) Isso implica que para cada mensagem M e cifratexto correspondente C, deve haver pelo menos uma chave KK que os liga como uma almofada única. Matemáticamente falando, isso significa KK≥ ≥ C≥ ≥ MNão. Kgeq Cgeq M} deve segurar, onde KK,C,M- Sim. denota as quantidades de possíveis chaves, cifras e mensagens, respectivamente. Em outras palavras, para ser capaz de ir de qualquer texto simples no espaço da mensagem M para qualquer cifra no espaço cifra C (via criptografia) e de qualquer cifra no cifra-espaço C para um texto simples no espaço da mensagem M (decodificação), ele exigiria pelo menos |M|= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =|C||M|=|C|} chaves (com todas as chaves usadas com igual probabilidade de 1/|KK|{displaystyle 1/|K|} para garantir o segredo perfeito).

Outra maneira de afirmar o segredo perfeito é que para todas as mensagens m1,m2Não. m_{1},m_{2}} em espaço de mensagem Me para todas as cifras c em espaço de cifra Cnós temos Prk⇐ ⇐ KKNão.Ek(m1)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =c]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =Prk⇐ ⇐ KKNão.Ek(m2)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =c]{displaystyle {underset {k Leftarrow mathrm Nome do operador {Pr} }}[E_{k}(m_{1})=c]={underset {k Leftarrow mathrm Nome do operador {Pr} }}[E_{k}(m_{2})=c]}, onde PrNome do operador Não. representa as probabilidades, tomadas sobre uma escolha de kNão. em espaço chave KK{displaystyle mathrm {K} } sobre os tosses de moeda de um algoritmo probabilístico, ENão.. O segredo perfeito é uma forte noção de dificuldade criptoanalítica.

algoritmos de criptografia simétrica convencionais usam padrões complexos de substituição e transposições. Para o melhor deles atualmente em uso, não se sabe se pode haver um procedimento criptanalítico que possa reverter com eficiência (ou até parcialmente reverter) essas transformações sem conhecer a chave usada durante a criptografia. Os algoritmos de criptografia assimétricos dependem de problemas matemáticos que se consideram difíceis de resolver, como fatoração inteira ou logaritmo discreto. No entanto, não há provas de que esses problemas sejam difíceis e um avanço matemático possa tornar os sistemas existentes vulneráveis ao ataque.

Dado o sigilo perfeito, em contraste com a criptografia simétrica convencional, o bloco único é imune até a ataques de força bruta. Tentar todas as teclas simplesmente produz todos os textos simples, todos igualmente prováveis de ser o texto simples. Mesmo com um texto simples parcialmente conhecido, ataques de força bruta não podem ser usados, pois um invasor não pode obter nenhuma informação sobre as partes da chave necessária para descriptografar o restante da mensagem. As partes do texto simples que são conhecidas revelarão apenas as partes da chave correspondentes a elas, e elas correspondem a uma base estritamente individual; Uma chave uniformemente aleatória é independente.

Os computadores quânticos foram demonstrados por Peter Shor e outros como muito mais rápido em resolver alguns problemas dos quais a segurança dos algoritmos de criptografia assimétrica tradicional depende. Os algoritmos criptográficos que dependem desses problemas ' A dificuldade seria tornada obsoleta com um computador quântico poderoso o suficiente. Pads únicas, no entanto, permaneceriam seguras, pois o sigilo perfeito não depende de suposições sobre os recursos computacionais de um invasor. A criptografia quântica e a criptografia pós-cantum envolvem o estudo do impacto dos computadores quânticos na segurança da informação.

Problemas

Apesar da prova de sua segurança, o bloco de Shannon tem desvantagens graves na prática porque exige:

• Verdadeiramente aleatório, em oposição ao pseudoaleatório, valores de pad de uma vez, que é um requisito não trivial. A geração de números aleatórios em computadores é muitas vezes difícil, e geradores de números pseudoaleatórios são frequentemente usados para sua velocidade e utilidade para a maioria das aplicações. Os geradores de números aleatórios verdadeiros existem, mas são tipicamente mais lentos e mais especializados.
• Geração segura e troca dos valores de uma vez pad, que deve ser pelo menos enquanto a mensagem. Isso é importante porque a segurança da almofada de uma vez depende da segurança da troca de um pad. Se um atacante é capaz de interceptar o valor do pad de uma vez, eles podem descriptografar mensagens enviadas usando o pad de uma vez.
• Cuidados de tratamento para garantir que os valores de um pad único continuam a permanecer secretos e são descartados corretamente, impedindo qualquer reutilização (parcial ou inteiramente) —daí "uma vez". Problemas com a remanência de dados podem tornar difícil apagar completamente a mídia do computador.

Pads de uso único resolvem alguns problemas práticos atuais em criptografia. Cifras de alta qualidade estão amplamente disponíveis e sua segurança não é atualmente considerada uma grande preocupação. Essas cifras são quase sempre mais fáceis de empregar do que os blocos de uso único, porque a quantidade de material de chave que deve ser gerada, distribuída e armazenada de maneira adequada e segura é muito menor. Além disso, a criptografia de chave pública supera o problema da distribuição de chaves.

Verdadeira aleatoriedade

Os números aleatórios de alta qualidade são difíceis de gerar. As funções de geração de números aleatórios na maioria das bibliotecas de linguagem de programação não são adequadas para uso criptográfico. Mesmo aqueles geradores que são adequados para uso criptográfico normal, incluindo /dev/random e muitos geradores de números aleatórios de hardware, podem fazer uso de funções criptográficas cuja segurança não foi comprovada. Um exemplo de técnica para gerar aleatoriedade pura é a medição de emissões radioativas.

Em particular, o uso de uma vez é absolutamente necessário. Se um pad de uma vez for usado apenas duas vezes, operações matemáticas simples podem reduzi-lo a uma cifra chave em execução. Por exemplo, se p1Não. p_{1}} e p2{displaystyle p_{2}} representam duas mensagens de texto simples distintas e eles são cada criptografado por uma chave comum kNão., então os respectivos cifratextos são dados por:

c1= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =p1⊕ ⊕ kNão. c_{1}=p_{1}oplus k}

c2= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =p2⊕ ⊕ kNão. c_{2}=p_{2}oplus k}

Onde? ⊕ ⊕ - Sim. significa XOR. Se um atacante tivesse ambos os cifratextos c1Não. c_{1}} e c2{displaystyle c_{2}}, então simplesmente tomando o XOR de c1Não. c_{1}} e c2{displaystyle c_{2}} produz o XOR dos dois textos simples p1⊕ ⊕ p2Não. p_{1}oplus p_{2}}. (Isto é porque tomar o XOR da chave comum kNão. com si mesmo produz um bitstream constante de zeros.) p1⊕ ⊕ p2Não. p_{1}oplus p_{2}} é então o equivalente a uma cifra chave em execução.

Se ambos os textos simples estiverem em um idioma natural (por exemplo, inglês ou russo), cada um tem uma chance muito alta de ser recuperado por criptoanálise heurística, possivelmente com algumas ambiguidades. É claro que uma mensagem mais longa só pode ser quebrada na parte que se sobrepõe a uma mensagem mais curta, e talvez um pouco mais ao completar uma palavra ou frase. A exploração mais famosa dessa vulnerabilidade ocorreu com o projeto Venona.

Distribuição de chaves

Como o bloco, como todos os segredos compartilhados, deve ser passado e mantido em segurança, e o bloco deve ser pelo menos tão longo quanto a mensagem, muitas vezes não faz sentido usar preenchimento único, pois pode-se simplesmente enviar o texto simples em vez do bloco (já que ambos podem ter o mesmo tamanho e devem ser enviados com segurança). No entanto, uma vez que um bloco muito longo foi enviado com segurança (por exemplo, um disco de computador cheio de dados aleatórios), ele pode ser usado para várias mensagens futuras, até que a soma dos tamanhos da mensagem seja igual ao tamanho do bloco. A distribuição de chaves quânticas também propõe uma solução para esse problema, assumindo computadores quânticos tolerantes a falhas.

A distribuição de teclas de uso único muito longas é inconveniente e geralmente representa um risco de segurança significativo. O bloco é essencialmente a chave de criptografia, mas ao contrário das chaves para cifras modernas, deve ser extremamente longo e é muito difícil para os humanos se lembrarem. Mídias de armazenamento como pen drives, DVD-Rs ou reprodutores de áudio digital pessoais podem ser usados para transportar um one-time-pad muito grande de um lugar para outro de maneira não suspeita, mas a necessidade de transportar o pad fisicamente é um fardo em comparação com os protocolos de negociação de chave de um sistema criptográfico moderno de chave pública. Essa mídia não pode ser apagada com segurança por qualquer meio que não seja a destruição física (por exemplo, incineração). Um DVD-R de 4,7 GB cheio de dados one-time-pad, se fragmentado em partículas de 1 mm² (0,0016 sq in) de tamanho, deixa mais de 4 megabits de dados em cada partícula. Além disso, o risco de comprometimento durante o trânsito (por exemplo, um batedor de carteira roubando, copiando e substituindo o bloco) provavelmente será muito maior na prática do que a probabilidade de comprometimento de uma cifra como AES. Finalmente, o esforço necessário para gerenciar o material de teclas de uso único aumenta muito mal para grandes redes de comunicantes - o número de blocos necessários aumenta com o quadrado do número de usuários que trocam mensagens livremente. Para comunicação entre apenas duas pessoas, ou uma topologia de rede em estrela, isso é menos problemático.

O material da chave deve ser descartado com segurança após o uso, para garantir que o material da chave nunca seja reutilizado e para proteger as mensagens enviadas. Como o material da chave deve ser transportado de um terminal para outro e persistir até que a mensagem seja enviada ou recebida, ele pode ser mais vulnerável à recuperação forense do que o texto simples transitório que ele protege (devido à possível remanência de dados).

Autenticação

Conforme usado tradicionalmente, os one-time pads não fornecem autenticação de mensagem, cuja falta pode representar uma ameaça à segurança em sistemas do mundo real. Por exemplo, um invasor que sabe que a mensagem contém "me encontre com Jane amanhã às três e meia da tarde" pode derivar os códigos correspondentes do bloco diretamente dos dois elementos conhecidos (o texto criptografado e o texto simples conhecido). O invasor pode então substituir esse texto por qualquer outro texto exatamente do mesmo tamanho, como "a reunião das três e meia foi cancelada, fique em casa". O conhecimento do invasor sobre o one-time pad é limitado a esse comprimento de byte, que deve ser mantido para que qualquer outro conteúdo da mensagem permaneça válido. Isso é diferente da maleabilidade, onde o texto simples não é necessariamente conhecido. Sem conhecer a mensagem, o invasor também pode inverter bits em uma mensagem enviada com um one-time pad, sem que o destinatário seja capaz de detectá-la. Por causa de suas semelhanças, os ataques em blocos de uso único são semelhantes aos ataques em cifras de fluxo.

Técnicas padrão para evitar isso, como o uso de um código de autenticação de mensagem, podem ser usadas junto com um sistema de preenchimento único para evitar tais ataques, assim como métodos clássicos como preenchimento de comprimento variável e cópula russa, mas todos eles carecem da segurança perfeita que o próprio OTP possui. O hashing universal fornece uma maneira de autenticar mensagens até um limite de segurança arbitrário (ou seja, para qualquer p > 0, um hash grande o suficiente garante que mesmo a probabilidade de um invasor computacionalmente ilimitado de falsificação bem-sucedida é menor que p), mas isso usa dados aleatórios adicionais do bloco e algumas dessas técnicas removem a possibilidade de implementar o sistema sem um computador.

Erros comuns de implementação

Devido à sua relativa simplicidade de implementação e à promessa de sigilo perfeito, o one-time-pad goza de grande popularidade entre os alunos que estão aprendendo sobre criptografia, especialmente porque geralmente é o primeiro algoritmo a ser apresentado e implementado durante um curso. Tal "primeiro" As implementações geralmente quebram os requisitos de segurança teórica da informação de uma ou mais maneiras:

• O pad é gerado através de algum algoritmo, que expande um ou mais valores pequenos em um "pad de tempo único". Isso se aplica igualmente a todos os algoritmos, de operações matemáticas básicas inseguras, como expansões decimais de raiz quadrada, a geradores de números aleatórios pseudo-aleatórios criptograficamente seguros (CSPRNGs). Nenhuma dessas implementações são um-pads de tempo, mas fluxo cifras por definição. Todos os pads de uma só vez devem ser gerados por um processo não-algoritmic, por exemplo, por um gerador de números aleatórios de hardware.
• A almofada é trocada usando métodos não-teoricamente seguros. Se o one-time-pad é criptografado com um algoritmo não-informação teoricamente seguro para a entrega, a segurança do criptosistema é apenas tão seguro como o mecanismo de entrega inseguro. Um mecanismo de entrega de falha comum para um-pad é um criptografia híbrido padrão que depende da criptografia de chave simétrica para criptografia de almofadas e criptografia assimétrica para entrega de chaves simétricas. Os métodos seguros comuns para a entrega de um pad são a distribuição de chaves quânticas, um serviço de sneakernet ou correio, ou uma gota morta.
• A implementação não possui um mecanismo de autenticação incondicionalmente seguro, como um MAC de uma só vez.
• A almofada é reutilizada (explorada durante o projeto Venona, por exemplo).
• A almofada não é destruída imediatamente após o uso.

Usos

Aplicabilidade

Apesar de seus problemas, o one-time-pad mantém algum interesse prático. Em algumas situações hipotéticas de espionagem, o bloco de uso único pode ser útil porque a criptografia e a descriptografia podem ser calculadas manualmente, apenas com lápis e papel. Quase todas as outras cifras de alta qualidade são totalmente impraticáveis sem computadores. No mundo moderno, no entanto, os computadores (como os embutidos em telefones celulares) são tão onipresentes que possuir um computador adequado para executar criptografia convencional (por exemplo, um telefone que pode executar software criptográfico oculto) geralmente não atrai suspeitas.

• O one-time-pad é o criptosistema ideal com teoricamente perfeito sigilo.
• O one-time-pad é um dos métodos mais práticos de criptografia onde uma ou ambas as partes devem fazer todo o trabalho à mão, sem a ajuda de um computador. Isso tornou importante na era pré-computador, e poderia concebível ainda ser útil em situações em que a posse de um computador é ilegal ou incriminante ou onde computadores confiáveis não estão disponíveis.
• Uma vez pads são práticos em situações em que duas partes em um ambiente seguro devem ser capazes de partir um do outro e se comunicar de dois ambientes seguros separados com perfeito sigilo.
• O one-time-pad pode ser usado em superencryption.
• O algoritmo mais comumente associado com a distribuição de chaves quânticas é a única vez pad.
• A almofada de uma vez é imitada por cifras de fluxo.
• Estações de números muitas vezes enviam mensagens criptografadas com um pad de uma vez.

Criptografia quântica e pós-quântica

Um uso comum do one-time pad na criptografia quântica está sendo usado em associação com a distribuição de chaves quânticas (QKD). O QKD é normalmente associado ao one-time pad porque fornece uma maneira de distribuir uma longa chave secreta compartilhada com segurança e eficiência (assumindo a existência de hardware de rede quântica prático). Um algoritmo QKD usa propriedades de sistemas mecânicos quânticos para permitir que duas partes concordem em uma string compartilhada e uniformemente aleatória. Algoritmos para QKD, como BB84, também são capazes de determinar se uma parte adversária está tentando interceptar o material da chave e permite que uma chave secreta compartilhada seja acordada com relativamente poucas mensagens trocadas e sobrecarga computacional relativamente baixa. Em um nível alto, os esquemas funcionam aproveitando a maneira destrutiva como os estados quânticos são medidos para trocar um segredo e detectar adulteração. No artigo original do BB84, foi comprovado que o one-time pad, com chaves distribuídas via QKD, é um esquema de criptografia perfeitamente seguro. No entanto, esse resultado depende do esquema QKD ser implementado corretamente na prática. Existem ataques em sistemas QKD do mundo real. Por exemplo, muitos sistemas não enviam um único fóton (ou outro objeto no estado quântico desejado) por bit da chave devido a limitações práticas, e um invasor pode interceptar e medir alguns dos fótons associados a uma mensagem, obtendo informações sobre a chave (ou seja, vazando informações sobre a almofada), enquanto passa ao longo de fótons não medidos correspondentes ao mesmo bit da chave. A combinação de QKD com um one-time pad também pode afrouxar os requisitos para a reutilização de chaves. Em 1982, Bennett e Brassard mostraram que, se um protocolo QKD não detectar que um adversário estava tentando interceptar uma chave trocada, a chave pode ser reutilizada com segurança, preservando o sigilo perfeito.

Também existe um análogo quântico do bloco de tempo único, que pode ser usado para trocar estados quânticos ao longo de um canal quântico unidirecional com sigilo perfeito, que às vezes é usado na computação quântica. Pode ser mostrado que um segredo compartilhado de pelo menos 2n bits clássicos é necessário para trocar um estado quântico de n-qubits ao longo de um canal quântico unidirecional (por analogia com o resultado de que uma chave de n bits é necessária para trocar um bit n mensagem com perfeito sigilo). Um esquema proposto em 2000 atinge esse limite. Uma maneira de implementar esse bloco único quântico é dividindo a chave de 2n bits em n pares de bits. Para criptografar o estado, para cada par de bits i na chave, deve-se aplicar uma porta X ao qubit i do estado se e somente se o primeiro bit do par for 1 e aplicar uma porta Z ao qubit i do declare se e somente se o segundo bit do par for 1. A descriptografia envolve a aplicação dessa transformação novamente, pois X e Z são seus próprios inversos. Pode-se mostrar que isso é perfeitamente secreto em um cenário quântico.

O one-time pad é um exemplo de criptografia pós-quântica, porque sigilo perfeito é uma definição de segurança que não depende dos recursos computacionais do adversário. Conseqüentemente, um adversário com um computador quântico ainda não seria capaz de obter mais informações sobre uma mensagem criptografada com um único bloco de tempo do que um adversário com apenas um computador clássico.

Usos históricos

Os absorventes descartáveis têm sido usados em circunstâncias especiais desde o início do século XX. Em 1923, eles foram contratados para comunicações diplomáticas pelo estabelecimento diplomático alemão. O Serviço Diplomático da República de Weimar começou a usar o método por volta de 1920. A quebra da pobre criptografia soviética pelos britânicos, com mensagens tornadas públicas por razões políticas em duas instâncias na década de 1920 (caso ARCOS), parece ter levado a União Soviética a adotar blocos de uso único para alguns propósitos por volta de 1930. Os espiões da KGB também são conhecidos por terem usado blocos de uso único a lápis e papel mais recentemente. Os exemplos incluem o coronel Rudolf Abel, que foi preso e condenado na cidade de Nova York na década de 1950, e os 'Krogers' (ou seja, Morris e Lona Cohen), que foram presos e condenados por espionagem no Reino Unido no início dos anos 1960. Ambos foram encontrados com blocos descartáveis físicos em sua posse.

Várias nações têm usado sistemas one-time pad para seu tráfego sensível. Leo Marks relata que o Executivo Britânico de Operações Especiais usou blocos de uso único na Segunda Guerra Mundial para codificar o tráfego entre seus escritórios. Pads de uso único para uso com seus agentes no exterior foram introduzidos no final da guerra. Algumas máquinas de codificação de fita únicas britânicas incluem Rockex e Noreen. A Stasi Sprach Machine alemã também era capaz de usar uma fita de tempo que a Alemanha Oriental, a Rússia e até Cuba usavam para enviar mensagens criptografadas a seus agentes.

O misturador de voz SIGSALY da Segunda Guerra Mundial também era uma forma de sistema único. Acrescentou ruído ao sinal em uma extremidade e o removeu na outra extremidade. O ruído foi distribuído para as extremidades do canal na forma de grandes discos de goma-laca que foram fabricados em pares únicos. Surgiram problemas de sincronização inicial e desvio de fase de longo prazo que tiveram que ser resolvidos antes que o sistema pudesse ser usado.

A linha direta entre Moscou e Washington D.C., estabelecida em 1963 após a Crise dos Mísseis de Cuba em 1962, usava teleimpressores protegidos por um sistema comercial de fita única. Cada país preparou as fitas de codificação usadas para codificar suas mensagens e as entregou por meio de sua embaixada no outro país. Uma vantagem única do OTP neste caso foi que nenhum dos países teve que revelar métodos de criptografia mais sensíveis para o outro.

EUA As Forças Especiais do Exército usaram almofadas descartáveis no Vietnã. Ao usar o código Morse com blocos de uso único e transmissão de rádio de onda contínua (a portadora do código Morse), eles alcançaram sigilo e comunicações confiáveis.

A partir de 1988, o Congresso Nacional Africano (ANC) usou blocos de uso único baseados em disco como parte de um sistema de comunicação seguro entre os líderes do ANC fora da África do Sul e os agentes do país como parte da Operação Vula, um esforço bem-sucedido para construir uma rede de resistência dentro da África do Sul. Números aleatórios no disco foram apagados após o uso. Um comissário de bordo belga atuou como mensageiro para trazer os pad disks. Era necessário um reabastecimento regular de novos discos, pois eles se esgotavam rapidamente. Um problema com o sistema era que ele não podia ser usado para armazenamento seguro de dados. Mais tarde, Vula adicionou uma cifra de fluxo codificada por códigos de livro para resolver esse problema.

Uma noção relacionada é o código de uso único—um sinal, usado apenas uma vez; por exemplo, "Alfa" para "missão concluída", "Bravo" para "missão falhou" ou mesmo "Tocha" para "invasão aliada da África do Norte francesa" não pode ser "descriptografado" em qualquer sentido razoável da palavra. Compreender a mensagem exigirá informações adicionais, geralmente 'profundidade' de repetição, ou alguma análise de tráfego. No entanto, essas estratégias (embora frequentemente usadas por agentes reais e treinadores de beisebol) não são um bloco de uso único criptográfico em nenhum sentido significativo.

NSA

Pelo menos na década de 1970, a Agência de Segurança Nacional dos EUA (NSA) produziu uma variedade de almofadas manuais de uso único, tanto de uso geral quanto especializadas, com 86.000 almofadas de uso único produzidas no ano fiscal de 1972. As almofadas de uso especial foram produzidas para o que a NSA chamou de "pro forma" sistemas, onde “a estrutura básica, forma ou formato de cada texto de mensagem é idêntico ou quase idêntico; o mesmo tipo de informação, mensagem após mensagem, deve ser apresentada na mesma ordem, e apenas valores específicos, como números, mudam a cada mensagem”. Os exemplos incluem mensagens de lançamento nuclear e relatórios de localização de rádio (COMUS).

Os pads de uso geral foram produzidos em vários formatos, uma lista simples de letras aleatórias (DIANA) ou apenas números (CALYPSO), pads minúsculos para agentes secretos (MICKEY MOUSE) e pads projetados para codificação mais rápida de mensagens curtas, em o custo de menor densidade. Um exemplo, ORION, tinha 50 linhas de alfabetos de texto simples de um lado e as letras de texto cifradas aleatórias correspondentes do outro lado. Ao colocar uma folha em cima de um pedaço de papel carbono com a face carbono para cima, pode-se circular uma letra em cada linha de um lado e a letra correspondente no outro lado seria circulada pelo papel carbono. Assim, uma folha ORION poderia codificar ou decodificar rapidamente uma mensagem de até 50 caracteres. A produção de blocos ORION exigia a impressão de ambos os lados em registro exato, um processo difícil, então a NSA mudou para outro formato de bloco, MEDEA, com 25 linhas de alfabetos pareados e caracteres aleatórios. (Consulte Commons:Category:NSA one-time pads para obter ilustrações.)

A NSA também construiu sistemas automatizados para o "quartel-general centralizado da CIA e das unidades das Forças Especiais, para que possam processar com eficiência as muitas mensagens separadas de uso único de e para os detentores de bloquinhos individuais no campo".

Durante a Segunda Guerra Mundial e na década de 1950, os EUA fizeram uso extensivo de sistemas de fita única. Além de fornecer confidencialidade, os circuitos protegidos por uma fita única rodavam continuamente, mesmo quando não havia tráfego, protegendo assim contra a análise de tráfego. Em 1955, a NSA produziu cerca de 1.660.000 rolos de fita de uso único. Cada rolo tinha 20 centímetros de diâmetro, continha 100.000 caracteres, durava 166 minutos e custava US$ 4,55 para ser produzido. Em 1972, apenas 55.000 rolos foram produzidos, já que as fitas de uso único foram substituídas por máquinas de rotor como SIGTOT e, posteriormente, por dispositivos eletrônicos baseados em registradores de deslocamento. A NSA descreve sistemas de fita única como 5-UCO e SIGTOT como sendo usados para tráfego de inteligência até a introdução do KW-26 baseado em cifra eletrônica em 1957.

Explorações

Embora os blocos únicos forneçam sigilo perfeito se gerados e usados corretamente, pequenos erros podem levar a criptoanálises bem-sucedidas:

• Em 1944-1945, o Serviço de Inteligência de Sinais do Exército dos EUA foi capaz de resolver um sistema de pad único usado pelo Ministério das Relações Exteriores da Alemanha por seu tráfego de alto nível, codinome GEE. A GEE foi insegura porque as almofadas não eram suficientemente aleatórias - a máquina usada para gerar as almofadas produziu saída previsível.
• Em 1945, os EUA descobriram que as mensagens Canberra-Moscow estavam sendo criptografadas primeiro usando um livro de código e, em seguida, usando uma almofada única. No entanto, o pad usado foi o mesmo usado por Moscou para Washington, D.C.-Moscow mensagens. Combinado com o fato de que algumas das mensagens Canberra-Moscow incluídas documentos do governo britânico conhecidos, isso permitiu que algumas das mensagens criptografadas fossem quebradas.
• Uma vez pads foram empregados por agências de espionagem soviéticas para comunicações secretas com agentes e controladores de agentes. A análise mostrou que essas almofadas foram geradas por digitadores usando máquinas de escrever reais. Este método não é verdadeiramente aleatório, pois torna as almofadas mais propensas a conter certas sequências de chaves convenientes com mais frequência. Isso provou ser geralmente eficaz porque as almofadas ainda eram um tanto imprevisível porque os tipógrafos não estavam seguindo regras, e diferentes tipógrafos produziram diferentes padrões de almofadas. Sem cópias do material chave usado, apenas algum defeito no método de geração ou reutilização de chaves ofereceu muita esperança de criptoanálise. Começando no final da década de 1940, as agências de inteligência dos EUA e do Reino Unido foram capazes de quebrar alguns do tráfego de pads soviéticos uma vez para Moscou durante a Segunda Guerra Mundial como resultado de erros feitos na geração e distribuição do material chave. Uma sugestão é que o pessoal do Centro de Moscou foi um tanto apressado pela presença de tropas alemãs fora de Moscou no final de 1941 e início de 1942, e eles produziram mais de uma cópia do mesmo material chave durante esse período. Este esforço de décadas foi finalmente codificado VENONA (BRIDE tinha sido um nome anterior); produziu uma quantidade considerável de informação. Mesmo assim, apenas uma pequena porcentagem das mensagens interceptadas foi totalmente ou parcialmente descriptografada (algumas mil de várias centenas de mil).
• Os sistemas de fita única usados pelos misturadores eletromecânicos empregados dos EUA para combinar pedaços da mensagem e da fita única. Estes misturadores irradiaram energia eletromagnética considerável que poderia ser captado por um adversário a alguma distância do equipamento de criptografia. Este efeito, notado pela primeira vez por Bell Labs durante a Segunda Guerra Mundial, poderia permitir a interceptação e a recuperação do texto de mensagens sendo transmitido, um código de vulnerabilidade chamado Tempest.