Jump to content
  • Fujam para as colinas: Quebraram a criptografia RSA! #sqn


    Fernando Mercês

    O CEO da Crown Sterling, uma startup na área de criptografia, fez um anúncio em uma palestra publicada no YouTube incluindo uma demonstração de quebra da criptografia RSA em menos de um minuto. A apresentação gerou vários comentários na comunidade de segurança da informação mundial, mas acontece que na prática as coisas não são tão simples assim.

    Pedimos ao Bruno Trevizan (@trevizan), especialista em criptografia e colaborador do Mente Binária, para comentar o assunto. "Um parâmetro importante para o criptosistema RSA é o tamanho (em bits) do módulo público n, principal elemento da chave pública, sendo esse o produto de dois números inteiros primos (p e q) também utilizados no cálculo da chave privada. O ataque demonstrado lança mão da abordagem de fatoração de inteiros, que consiste em encontrar um divisor não trivial de um número composto, ou seja, encontrar um dos inteiros primos p ou q, tal que n = p x q, onde n é informado como elemento da chave pública. Obtendo sucesso na recuperação desses fatores, o atacante é capaz de calcular a chave privada. Contudo, apesar do ataque demonstrado ter sido bem-sucedido, o exemplo contido na demonstração utiliza o módulo público de 256 bits, tamanho de chave não recomendado para nenhum caso", explica.

    A notícia também foi criticada pelo criptógrafo Bruce Schneier, que lembrou que 256 bits é um tamanho de chave que nunca foi considerado seguro, ou seja, é "quebrável" mesmo. Além disso, o CEO da Crown Sterling, Robert Grant, diz na palestra que uma chave de 512 bits poderia ser quebrada em aproximadamente 5 horas, mas não demonstra. 

    "Contudo, o parâmetro em questão é reconhecidamente inseguro desde 1999, sendo que seu uso não é recomendado nem para sistemas legados. Sendo o tamanho mínimo tolerado para suportar a sobrevida de sistemas legados de 1024 bits, é recomendável o uso 2048 bits ou mais", adiciona Bruno.

    Outros nomes na área de segurança da informação acreditam se tratar mais um sales pitch do que qualquer outra coisa. No Twitter, Nicholas Weaver, PhD em Berkeley, sugeriu que a ferramenta apresentada pela Crown Sterling seja na verdade uma cópia da CADO-NFS, uma ferramenta de código aberto desenvolvida por pesquisadores na França que consiste na implementação do algoritmo de Number Field Sieve (NFS) para fatoração de números inteiros. Waver nota que a mensagem de saída apresentada no vídeo da Crown Sterling é exatamente a mesma da ferramenta CADO-NFS, o que sugere seu reuso.

    Victor Mello, Especialista em Segurança Sênior na Neoway, quando soube da notícia fez um script simples em Perl para o mesmo propósito: "para quem tiver interesse, testei aqui e levou em torno de 8 minutos usando GMP num laptop de 8 núcleos (cores). Utilizei o mesmo n que o pessoal da Crown Sterling usou na demonstração", comenta. Victor compartilhou conosco o código-fonte do seu script:

    use Math::Prime::Util::GMP ':all';
    use bigint;
    
    # Find prime factors of big numbers
    @factors = factor(shift);
     
    for my $i (@factors) {
        print $i . "\n";
    }

    Resumindo, quebraram o que já era quebrável. Não precisa fugir para as colinas ainda. 😉
     

    Edited by Fernando Mercês



    User Feedback

    Recommended Comments

    O problema não é o tamanho da chave, necessariamente, e compara a "quebra" com um script em perl é, no mínimo ingênuo, em vista de que, hoje, qualquer usuário com alguma grana sobrando consegue montar máquinas com mũltiplas placas de vídeo e usar paralelismo com MILHARES de unidades de processamento para fazer a mágica.

    Em 2018, um dos "inventores" do RSA recomendou que o algoritmo fosse gradualmente descontinuado em detrimento à curvas elípticas, já que sua força reside apenas na impossibilidade de processamento na fatoração de chaves - coisa que está ficando "fácil" de fazer, em vista do que eu disse lá em cima...

    Até mesmo RSA com 2048 estão, hoje, começando a ser substituúidos por RSA com 4096 bits por conta disso.

    Yep... a apresentação é imprecisa e usa chaves pequenas, mas o princípio é o mesmo para chaves maiores e com processamento suficiente (junte umas 3 nVidia RTX2080Ti [4352 "cores" cada] ao custo de uns US$ 4000.00) e você tem a ideia do estrago que dá pra fazer... Ainda, existem grupos de crackers que investem em máquinas com múltiplos barramentos PCI (não apenas o localbus) que permitem colocar dezenas de placas dessas num "mesmo" circuito...

    E, sim... corram para as colinas! RSA tem seus dias contados...

    Share this comment


    Link to comment
    Share on other sites

    PS: Não estou achando, agora, o artigo onde um dos 3 inventores do RSA faz a recomendação, mas o vi há alguns meses atrás (e, sorry... a recomendação foi feita - pelo que me lembro - em 2017, não 2018)...

    É interessante tentar entender como os esquemas de criptografia RSA e de EC funcionam, pelo menos em princípio e porquê são consideradas "fortes", em termos de criptografia. EC (Elliptic Curves), além do tamanho de chaves e das restrições binárias das mesas, tem ainda a complexidade em relação à curva usada para obter as chaves. É um método que exige BEM MAIS processamento para "quebrar" as chaves que o RSA e ai reside sua força (senão a prática impossibilidade matemática de quebra - até alguém descobrir como)...

    Já reparou como tá todo mundo migrando para TLS 1.2 ou superior e o keyexchange geralmente é ECDHE? O certificado digital DESTE forum, por exemplo (que é usado apenas para autenticação) continua sendo RSA, mas a preferência, hoje, é pelo ECDSA (Elliptic Curve Digital Signing Algorithm) porque:

    1. É mais seguro;
    2. As chaves são menores, em termos de bits.

    Não se trata de apenas uma "nova tecnolgia", trata-se do moribundo RSA...

    Share this comment


    Link to comment
    Share on other sites
    5 hours ago, fredericopissarra said:

    Até mesmo RSA com 2048 estão, hoje, começando a ser substituúidos por RSA com 4096 bits por conta disso.

    Pois então, não acha que ainda podemos considerar RSA com chaves grandes razoavelmente seguro? A apresentação fala em "quebrar contas bancárias". O apresentador não explica, mas se ele tá falando de online banking, cai no caso do TLS que você comentou.

    Além disso, a técnica apresentada no vídeo não é nova. O surgimento da CADO-NFS se deu nisso, não foi? O burburinho não seria exagerado? RSA pode ter seus dias contados, mas não talvez não tenhamos chegado lá ainda. 😉

    Share this comment


    Link to comment
    Share on other sites

    Sim, sim... existe, é claro, um certo exagero (típico de quem quer lucrar), mas RSA está, de fato, com os dias contados e os bancos serão os primeiros a migrarem para ECDSA. De fato, a maioria dos sites já migrou, pelo menos, para o ECDHE (key exchange), uma vez que certificados digitais só servem para autenticação (identificação) e não vale à pena gastar dimdim só para trocar um certificado que ainda é válido (certificados são caros!). Mas, pelo menos, o canal de troca de chave não usa mais o DHE (que é a base do algoritmo RSA).

    "Ahhh, mas tem o Let's Encrypt!"... Yep, mas o Let's Encrypt também oferece certificados com ECDSA - Embora exista um problema conceitual com ele (o Let's Encrypt, nao o certificado!): Qual é a utilidade de uma "Autoridade Certificadora"? Ela é uma "autoridade" porque estabelece uma cadeia de confiança entre o cliente e o fornecedor do serviço e, por isso, ambos confiam em certificados assinados por ela... Como essa confiança é estabelecida? O fornecedor (site) tem que, além de pagar uma valor pelo certificado (afugentando os pobretões!), verificar a validade dos dados do fornecedor (documentação)... Há alguns anos, autoridades como a Verisign, por exemplo, pediam CNPJ, documentação do responsável técnico, documentação autenticada em cartório, etc... Com o Let's Encrypt quaalquer pessoa pode adquirir um certificado digital assinado, bastando apenas ter um nome válido que possa ser buscado por DNS. Ou seja, a cadeia de confiança só existe no nome "chain of trust", não na prática!

    Porque estou citando o Let's Encrypt? Só porque percebi que o certificado DESTE forum é deles (e RSA), embora o key exchange seja feito por ECDHE e via TLS 1.2.

    O problema de todo esquema de criptografia assimétrica, até então, é que eles se baseiam na impossibilidade prática de fatoração. Para encontrar dois números primos relativos enormes e o módulo usado no cálculo, era estimado que um computador doméstico levaria algumas dezenas de bilhões de anos para fazer. Hoje, com alguma grana sobrando, isso tende a cair consideravelmente (alguns anos? meses? semanas? Provavelmente, daqui a uns anos levará alguns segundos!).

    As curvas elípticas adicionam alguns fatores a mais a esse esquema: A curva é parametrizada pelo lado de quem gera as chaves e, sem esses parâmetros, temos um grupo considerável de curvas disponíveis para a mesma "classe" de curvas (imagine as chaves sendo intersecções de uma linha entre dois pontos da curva. Se você não sabe como a curva se apresenta [não conhece os parâmetros da curva, mas só sua aparência geral], não dá para achar o outro ponto [o primeiro é a chave pública])... Isso, mais o esquema parecido com o Diffie-Helman (aritmética exponencial e modular) torna as EC trocentas vezes mais seguras que o RSA - mesmo para os futuros computadores quênticos...

    Share this comment


    Link to comment
    Share on other sites

    Bom, no meu entedimento o post tem a intenção de esclarecer que a apresentação em questão não demonstrou nada de novo ou desconhecido, ou seja, não mudou nada e não merece o destaque que teve, e esclarecer que não há motivos para desespero, a menos que você esteja utilizando tamanhos de chaves que não são recomendados (< 1024 bits para sistema legados e < 2048 bits para implementações novas). De forma alguma colocou-se o RSA como um criptosistema perfeito e "eternamente inquebrável", o que seria de uma ingenuidade imensa considerando o histórico observado: cifra de César e de Vigenère, Enigma ou mesmo o DES já foram seguros um dia.

     

    Visto isso, acho que os comentários levaram a discussão para uma polarização (RSA x ECC) que não existe na prática. Tanto que colocou-se o DHE como base para o RSA em oposição a ECC, mas na verdade o DHE se baseia no problema do logaritmo discreto, mesma classe de problema no qual o ECDHE e os protocolos de assinatura baseadas em curvas elípticas citados acima se apoiam. Se essa dicotomia fizesse sentido não haveria cipher suites que combinam ambas primitivas, como por exemplo a TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256.

    Concordo que  ECC pode oferecer soluções mais elegantes, eficientes e com chaves menores para o mesmo nível de segurança, mas essas são apenas características dos algoritmos, isso não a torna mais segura por definição. O mais importante é conhecer qual o nível de segurança para cada parâmetro escolhido, como mostrado na tabela abaixo:


    image.png.fe88e4201181dba0c242c0796767406d.png 

    fonte: https://www.keylength.com/en/4/

     

    Além disso, é importante notar que discussões acerca da segurança das curvas elípticas já foram levantadas por pesquisadores de maior relevância na área e processos de padronização também foram interrompidos. O NIST, por exemplo, atualmente está focado em padronizar soluções de assinatura digital e encapsulamento de chaves que sejam resistentes aos algortimos quânticos conhecidos, soluções essas que não incluem RSA, ECC ou DHE que utilizamos hoje.

    Share this comment


    Link to comment
    Share on other sites


    Join the conversation

    You can post now and register later. If you have an account, sign in now to post with your account.

    Guest
    Add a comment...

    ×   Pasted as rich text.   Paste as plain text instead

      Only 75 emoji are allowed.

    ×   Your link has been automatically embedded.   Display as a link instead

    ×   Your previous content has been restored.   Clear editor

    ×   You cannot paste images directly. Upload or insert images from URL.


×
×
  • Create New...