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

Question

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 OpenPGP de 1024 bits (dependendo da potência da CPU)?

Também estou interessado em outras chaves como 2048 e 4096.

    

Answer 1

Embora a resposta do @Jens Erat fosse bastante abrangente, eu fiz uma pesquisa sobre a quebra do RSA (o algoritmo por trás do OpenPGP), então eu queria opinar:

Eu vou quebrar a norma e dar o TL; DR primeiro: É impossível você quebrar essa chave. Se estamos olhando para isso de forma realista, não há como você fatorar um 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 em que o destinatário verifica seu e-mail).

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

• Adivinhação cega / Força bruta. Com um semprime de 1024 bits, há poucas chances de que isso funcione. Seria melhor usar seu tempo tentando adivinhar números de loteria aleatoriamente.

• Gerando uma tabela do arco-íris. Tire o trabalho de adivinhação de fatoração tomando cada primo abaixo de 2 ^ 1024 e multiplicando-o por todos os outros primos, armazenando o resultado em uma tabela. Então tudo que você teria que 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 de primos , você está vendo cerca de 2,95 * 10 ^ 307 primos - para comparação, estima-se que o número de átomos no universo observável esteja na magnitude de 10 ^ 83, portanto, mesmo que pudéssemos fazer cada átomo armazenar dois primos e seu produto de uma maneira que nosso computador pudesse indexar, seria impossível.

• Use a peneira de campo de número geral . O GNFS é sua melhor aposta para fatorar um grande semiprime. Ele foi usado por Kleinjung e sua equipe para fatorar o RSA-768, um semiprimo de 768 bits. Infelizmente, isso levou sua equipe ao longo de três anos, e é uma ordem de grandeza menor do que os números que você deseja calcular. Mesmo se você gastasse milhões de dólares (por dia) alugando os melhores supercomputadores a plena capacidade, seria quase impossível calcular o número. O primeiro passo do GNFS é encontrar "relações" suficientes que permitam resolver os subproblemas, o que 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 viável. Infelizmente, estes ainda precisam ser desenvolvidos a um ponto de qualquer utilidade. Portanto, por enquanto, não podemos fatorar semprimes de 1024 bits e maiores (e, portanto, os algoritmos que dependem deles).

    

Answer 2

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

Geralmente, o tópico é complicado demais 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, as falhas matemáticas desconhecidas (para o público) poderiam mudar isso por ordem de grandeza, como os computadores quânticos podem fazer em algum momento no futuro (longe, do ponto de vista da "era da internet").

A versão ligeiramente mais longa:

Cracking the Asymmetric Encryption (chave RSA 1024 bit)

Além das chaves RSA 1024 bits, isso também se aplica a tamanhos de chave maiores. Chaves maiores fornecem mais segurança (em 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á um post interessante no Stack Stack do Information Security, "Como estimar o tempo necessário para quebrar a criptografia RSA ? " , que não se completa com uma estimativa como" Usando um modelo xy do Core i7, você será capaz de quebrar uma chave RSA 1024 bit em z horas estimadas ", mas as respostas estão de acordo "Chaves RSA de 1024 bits não podem ser quebradas por pessoas com capacidade de computação normalmente disponível (ou seja, um punhado de máquinas de última geração) em um tempo razoável.

A discussão sobre a quebra de chaves de 1024 bits com muito mais poder de computação foi considerada apenas do ponto de vista acadêmico:

I recently learned that the selection of the parameters for a 1024-bit number factorization has begun (that's the "brainy" part); the sieving is technically feasible (it will be expensive and involve years of computation time on many university clusters) but, for the moment, nobody knows how to do the linear reduction part for a 1024-bit integer. So do not expect a 1024-bit break any time soon.

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 por ordem de magnitude (algumas instituições como a NSA empregam um grande número de grandes matemáticos), ou
• computadores quânticos finalmente funcionam e são poderosos o suficiente e capazes de executar certos algoritmos. Não esperado para ocorrer nos próximos anos.

Para o 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, a DSA é mais vulnerável a números aleatórios ruins (compare com os Falha no gerador de números aleatórios da Debian . A criptografia de curva elíptica que está chegando para o OpenPGP agora não possui ataques conhecidos para os algoritmos suportados e geralmente considerados seguros, mas há algumas dúvidas sobrando especialmente nas curvas recomendadas pelo NIST (o NIST perdeu uma boa reputação por fazer uma quebra aleatória). gerador de números, um padrão), e alguns detalhes de implementação.

Cracking da criptografia simétrica

Para o 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 chamada 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 decifrar a chave de criptografia simétrica de uma mensagem, também poderá ler a mensagem (ao contrário da quebra da chave assimétrica, onde você pode ler todas as mensagens criptografadas para essa chave).

Ao contrário das versões muito antigas do PGP (que usavam um algoritmo de criptografia simétrica projetado pelo próprio Zimmermann chamado BassOmatic , que é considerado inválido, todos os algoritmos simétricos definidos para o OpenPGP não têm relevância relevante ataques.

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