Quanto tempo levaria para quebrar um e-mail criptografado em OpenPGP de 1024 bits?

9

Para o WPA, existem calculadoras para determinar o tempo necessário para decifrar uma senha, mas não encontrei nada para o OpenPGP.

Quanto tempo levaria para quebrar um e-mail criptografado em OpenPGP de 1024 bits (dependendo da energia da CPU)?

Também estou interessado em outros tamanhos de chave como 2048 e 4096.

Kelmat
fonte

Respostas:

7

Embora a resposta de @Jens Erat tenha sido bastante abrangente, eu pesquisei sobre a quebra do RSA (o algoritmo por trás do OpenPGP), então eu queria opinar:

Vou quebrar a norma e dar o TL; DR primeiro: é impossível para você quebrar essa chave. Se estivermos analisando isso de forma realista, não há como você fatorar um número inteiro de 1024 bits. Sua melhor aposta possível seria tentar quebrar alguma outra parte da cadeia de segurança (por exemplo, a área de trabalho onde o destinatário verifica seu e-mail).

Com o realismo fora do caminho, vamos considerar possíveis estratégias:

  • Adivinhar às cegas / forçar bruto. Com um semiprime de 1024 bits, há poucas chances de que isso funcione. Seria melhor usar seu tempo aleatoriamente tentando adivinhar os números da loteria.

  • Gerando uma tabela de arco-íris. Elimine a adivinhação de fatoração, tomando cada primo abaixo de 2 ^ 1024 e multiplicando-o por qualquer outro primo, armazenando o resultado em uma tabela. Então tudo o que você precisa fazer é procurar o par correto. Como você pode imaginar, isso também é impossível. Isso envolveria x! pares para x número de primos. Pela função de contagem primária , você está vendo cerca de 2,95 * 10 ^ 307 primos - para comparação, estima-se que o número de átomos no universo obserável esteja na magnitude de 10 ^ 83, portanto, mesmo que pudéssemos fazer com que cada átomo armazene dois números primos e seu produto de uma maneira que nosso computador possa indexar, seria impossível.

  • Use a peneira de campo de número geral . O GNFS é sua melhor aposta para fatorar um grande semiprime. Foi usado por Kleinjung e sua equipe para o fator RSA-768, um semiprime de 768 bits. Infelizmente, isso levou sua equipe ao longo de três anos para ser concluída, e são ordens de magnitude menores que os números que você deseja levar em consideração. Mesmo se você gastasse milhões de dólares (por dia) alugando os melhores supercomputadores em plena capacidade, seria quase impossível calcular o número. O primeiro passo do GNFS é encontrar "relações" suficientes que permitam resolver os subproblemas, e isso pode levar muito tempo.

Seu último recurso é usar um computador quântico, o que permitiria fatorar os números em um período de tempo possível. Infelizmente, esses ainda precisam ser desenvolvidos a um ponto de qualquer utilidade. Portanto, por enquanto, não podemos fatorar semiprimes de 1024 bits ou mais (e, portanto, os algoritmos que dependem deles).

ahjohnston25
fonte
20

Primeiro, suponho que você esteja falando da criptografia RSA 1024 bits.

Geralmente, o tópico é muito complicado para fornecer um número simples.

tl; dr : Quebrar uma mensagem criptografada do OpenPGP em uma única CPU não é viável e provavelmente leva anos, mesmo com grandes clusters de computação. No entanto, falhas matemáticas desconhecidas (para o público) podem mudar isso por ordem de magnitude, como os computadores quânticos podem fazer em algum momento no futuro (longe do ponto de vista da "era da Internet").

A versão um pouco mais longa:

Quebrando a criptografia assimétrica (chave RSA 1024 bits)

Além das chaves RSA 1024 bits, isso também se aplica a tamanhos de chave maiores. Chaves maiores fornecem mais segurança (na forma de poder de computação para quebrá-las), mas lembre-se de que a segurança não aumenta linearmente com o tamanho da chave.

Há uma boa postagem no Information Security Stack Exchange, "Como estimar o tempo necessário para quebrar a criptografia RSA?" , que não é concluído com uma estimativa como "Usando um modelo Core i7 xy, você poderá decifrar uma chave RSA 1024 bits em z horas estimadas", mas as respostas concordam em "As chaves RSA 1024 bits não podem ser decifradas por indivíduos com poder de computação geralmente disponível (por exemplo, um punhado de máquinas de última geração) em um tempo razoável.

A discussão de quebrar chaves de 1024 bits com muito mais poder computacional foi considerada apenas do ponto de vista acadêmico:

Eu aprendi recentemente que a seleção dos parâmetros para uma fatoração de 1024 bits começou (essa é a parte "inteligente"); a peneiração é tecnicamente viável (será cara e envolverá anos de tempo de computação em muitos clusters de universidades), mas, no momento, ninguém sabe como fazer a parte de redução linear para um número inteiro de 1024 bits. Portanto, não espere uma quebra de 1024 bits em breve.

Isso provavelmente também se aplica a instituições grandes e bem financiadas, com muito poder de computação como a NSA.

As coisas podem mudar rapidamente se

  • alguém encontra uma falha matemática, que reduz a complexidade da RSA em ordens de magnitude (algumas instituições como a NSA empregam um grande número de grandes matemáticos), ou
  • os computadores quânticos finalmente funcionam e se tornam poderosos o suficiente e capazes de executar certos algoritmos. Não se espera que ocorra nos próximos anos.

Para DSA / ElGamal, as coisas são um pouco diferentes. Uma chave DSA do mesmo tamanho de uma chave RSA fornece mais segurança, mas, ao mesmo tempo, o DSA é mais vulnerável a números aleatórios ruins (compare com a falha do gerador de números aleatórios Debian ). A criptografia de curva elíptica que está disponível para o OpenPGP no momento não possui ataques conhecidos para os algoritmos suportados ainda e geralmente considerados seguros, mas ainda há algumas dúvidas, especialmente nas curvas recomendadas pelo NIST (o NIST perdeu bastante reputação por criar um aleatório quebrado gerador de números um padrão) e alguns exemplos de implementação.

Quebrando a criptografia simétrica

Para rasons de desempenho, o OpenPGP usa criptografia híbrida, portanto, a mensagem é criptografada com criptografia simétrica e uma chave simétrica aleatória (no OpenPGP, geralmente chamado de "chave de sessão"). Esta chave de sessão novamente é criptografada usando o algoritmo de criptografia assimétrica, por exemplo. RSA.

Se você conseguir quebrar a chave de criptografia simétrica de uma mensagem, também poderá ler a mensagem (diferente da quebra da chave assimétrica, onde você poderá ler todas as mensagens criptografadas nessa chave).

Diferentemente das versões muito antigas do PGP (que usavam um algoritmo de criptografia simétrica projetado pelo próprio Zimmermann chamado BassOmatic , considerado quebrado), todos os algoritmos simétricos definidos para o OpenPGP não possuem ataques conhecidos relevantes.

A menos que alguém tenha escolhido não usar criptografia simétrica (o que é realmente possível!), A quebra de uma mensagem usando o algoritmo de criptografia simétrica não deve ser considerada viável no momento.

Jens Erat
fonte
Eu tenho que perguntar ... o erro ortográfico de "assimétrico" é intencional?
David Z
Não, claro que não; nem foi "copmuting". Obrigado por me notificar.
Jens Erat 22/02
Não existe "uma chave DES do mesmo tamanho que uma chave RSA". O DES usa chaves de 56 bits, ponto final . É definido apenas com chaves de 56 bits; você não pode executar o DES com nenhum outro tamanho de chave. Também não é vulnerável a números aleatórios ruins, porque o DES não usa números aleatórios em nenhum momento do algoritmo (nem qualquer outro código primitivo de bloco); usos particulares dele podem incluir um aspecto aleatório (por exemplo, um IV para o modo CBC deve ser aleatório), mas o próprio DES é totalmente determinístico. O DES também não é mais usado (o DES triplo é ocasionalmente, mas o próprio DES nunca). Tem certeza de que pretendia falar sobre DES?
cpast
Claro que não queria. O DES confuso com o DSA não deveria ter acontecido. DES, PGP, RSA, NSA, DSA: Precisamos de menos siglas de três letras!
precisa
A maioria das chaves openpgp de 1024 bits (diferentemente das chaves ssl / tls) são DSA e não RSA. Encontro muitas discussões on-line sobre o cracking RSA de 1024 bits, mas pouco sobre o cracking DSA de 1024 bits.
plugwash