Pare de usar o RSA

Olá% username%!

O RSA é o primeiro algoritmo de criptografia assimétrica amplamente utilizado que ainda é popular na indústria. É relativamente simples à primeira vista. A criptografia e a assinatura RSA podem ser contadas em um pedaço de papel, o que os alunos costumam fazer no trabalho de laboratório.
Mas há simplesmente um grande número de nuances sem as quais até uma criança pode decifrar sua implementação de RSA.

Por alguma razão, as pessoas ainda pensam que o RSA é um bom algoritmo. Mas, na verdade, a possibilidade de um tiro na perna ao implementar o RSA é extremamente grande. Parâmetros fracos são difíceis de verificar, se não impossíveis. E o fraco desempenho do algoritmo incentiva os desenvolvedores a usar maneiras arriscadas para melhorá-lo.

Pior, os ataques de preenchimento de oráculos que foram inventados há mais de 20 anos ainda são relevantes hoje.
Mesmo que, em teoria, seja possível implementar o RSA corretamente, na prática esse "feito" é quase impossível de realizar. E as vulnerabilidades que surgem constantemente há décadas apenas confirmaram isso.

Algumas palavras sobre o algoritmo RSA

Se você souber como o RSA funciona, poderá pular esta parte.

O RSA é um sistema de criptografia de chave pública que possui dois usos.

A primeira é a criptografia, quando Alice publica sua chave pública e Bob, sabendo disso, pode criptografar uma mensagem que somente Alice pode ler, descriptografando-a com sua chave privada.

A segunda é uma assinatura digital, que permite que Alice assine a mensagem com sua chave privada para que todos possam verificar essa assinatura com sua chave pública.

Ambos os algoritmos diferem em detalhes insignificantes, portanto os chamaremos simplesmente de RSA.

Para começar a trabalhar com o RSA, Alice precisa escolher dois números primos peq , que juntos formam um grupo de números módulo N = pq . Então, Alice precisa escolher um expoente aberto e um expoente secreto d, de modo que $$$ed = 1 \ mod (p-1) (q-1)$. Em essência, ed devem ser mutuamente simples.

Depois que essas opções são selecionadas, Bob pode enviar uma mensagem para Alice M, calculando $$$C = M ^ e (mod \ N)$. Alice pode descriptografar a mensagem computando $$$M = C ^ d (mod \ N)$.
A assinatura digital é exatamente o oposto. Se Alice quiser assinar a mensagem, ela calculará a assinatura $$$S = M ^ d (mod \ N)$Bob pode verificar, certificando-se de que a mensagem $$$M = S ^ e (mod \ N)$

Isso é tudo, essa é a ideia principal. Voltaremos mais tarde aos oráculos Padding, mas por enquanto vamos ver o que pode ser feito se os parâmetros RSA forem selecionados incorretamente.

Começo do fim

Para que o RSA funcione, você precisa selecionar alguns parâmetros. Infelizmente, métodos aparentemente inocentes de sua escolha podem prejudicar a segurança. Vamos analisar cada um deles e ver que surpresas desagradáveis ​​esperam por você.

Geração Prime

A segurança da RSA é baseada no fato de que é difícil obter um número grande N , que é o produto de dois primos peq , decompondo N em fatores primos sem saber peq . Os desenvolvedores são responsáveis ​​por escolher os números primos que compõem o módulo RSA. Esse processo é extremamente lento comparado à geração de chaves para outros protocolos criptográficos, onde basta basta selecionar alguns bytes aleatórios. Portanto, em vez de gerar um número primo verdadeiramente aleatório, os desenvolvedores geralmente tentam criar números de uma determinada forma. Quase sempre termina mal. Existem muitas maneiras de escolher números primos, para que o fator N seja simples. Por exemplo, peq devem ser globalmente exclusivos. Se p ou q forem reutilizados em outros módulos RSA, ambos os fatores poderão ser facilmente calculados usando o algoritmo GCD. Geradores de números aleatórios ruins tornam esse cenário bastante provável e estudos mostraram que aproximadamente 1% do tráfego TLS em 2012 foi exposto a esse ataque.

Além disso, peq devem ser selecionados independentemente um do outro. Se p e q compartilham aproximadamente metade de seus bits mais significativos, N pode ser calculado usando o método Fermat. De fato, mesmo escolher um algoritmo de teste de simplicidade pode ter implicações de segurança. Talvez o ataque mais amplamente divulgado seja a vulnerabilidade ROCA no RSALib, que afetou muitos cartões inteligentes, módulos de plataforma confiáveis ​​e até chaves Yubikey. Aqui, ao gerar chaves, apenas números primos de uma determinada forma são usados ​​para acelerar os cálculos. Os números primos gerados dessa maneira são triviais para descobrir usando técnicas complicadas na teoria dos números. Depois que um sistema fraco é reconhecido, as propriedades algébricas especiais dos números primos permitem que um invasor use o método Coppersmith para decompor N.

Deve-se ter em mente que, em nenhum desses casos, a geração de números primos dessa maneira é um fato óbvio que leva a uma falha completa do sistema. Isso ocorre porque as propriedades teóricas dos números insignificantes dos números primos têm um impacto significativo na segurança do RSA. A expectativa de que um desenvolvedor comum navegue nesse campo minado matemático prejudica seriamente a segurança.

Expositor secreto d

Como o uso de uma chave privada grande afeta negativamente o tempo de descriptografia e assinatura, os desenvolvedores têm um incentivo para escolher um d pequeno, especialmente no caso de dispositivos com baixo consumo de energia, como cartões inteligentes. No entanto, um invasor pode recuperar a chave privada quando d é menor que a raiz do quarto grau de N. Em vez disso, os desenvolvedores devem escolher um grande valor de d , para que o teorema do restante chinês possa ser usado para acelerar a descriptografia. No entanto, a complexidade dessa abordagem aumenta a probabilidade de pequenos erros de implementação que podem levar à recuperação de chaves.

Você diz que, geralmente, durante a inicialização do RSA, primeiro gera um módulo, usa um expoente aberto fixo e depois escolhe um segredo?
Sim, isso evita ataques com um pequeno expoente secreto se você sempre usar um dos expoentes abertos recomendados e .
Infelizmente, isso também pressupõe que os desenvolvedores realmente farão isso. No mundo real, os desenvolvedores costumam fazer coisas estranhas, por exemplo, primeiro escolha d e depois considere e .

Expositor Aberto e

Assim como o expositor secreto, os desenvolvedores desejam usar pequenos expositores abertos para economizar na criptografia e na verificação de assinaturas. Normalmente, os primos Fermat são usados ​​neste contexto, em particular e = 3, 17 e 65537.

Apesar do fato de que os criptografadores recomendam o uso do 65537, os desenvolvedores geralmente escolhem e = 3, o que leva a muitas vulnerabilidades no sistema de criptografia RSA.


(Aqui, os desenvolvedores usaram e = 1, que na verdade não criptografa texto puro).

Quando e = 3 ou um tamanho semelhante, muita coisa pode dar errado. Pequenos expoentes abertos são frequentemente combinados com outros erros comuns que permitem ao invasor descriptografar certos textos cifrados ou fator N.

Por exemplo, um ataque da Franklin-Reuters permite que um invasor descriptografe duas mensagens conectadas por uma distância fixa conhecida. Em outras palavras, suponha que Alice envie Bob apenas para "comprar" ou "vender". Essas mensagens serão associadas a um valor conhecido e permitirão ao invasor determinar qual delas significa "comprar" e "vender" sem descriptografar a mensagem. Alguns ataques com e pequeno podem até levar à recuperação de chaves.

Se o expoente aberto for pequeno (não apenas 3), um invasor que conhece vários bits da chave secreta pode recuperar os bits restantes e interromper o sistema de criptografia. Embora muitos desses ataques e = 3 RSA possam ser corrigidos por preenchimento, os desenvolvedores que implementam o RSA eles mesmos se esquecem de usá-lo.

As assinaturas da RSA também são vulneráveis ​​a pequenos expositores públicos. Em 2006, Bleichenbacher descobriu um ataque que permite aos invasores falsificar assinaturas arbitrárias em muitas implementações de RSA, incluindo aquelas usadas no Firefox e Chrome. Isso significa que qualquer certificado TLS de uma implementação vulnerável pode ser violado. Esse ataque explora o fato de que muitas bibliotecas usam um pequeno expoente público e não fazem uma simples verificação de alinhamento ao processar assinaturas RSA. O ataque de Bleichenbacher à assinatura é tão simples que é incluído em muitos exercícios nos cursos de criptografia.

Escolher opções é uma tarefa difícil

Comum a todos esses ataques a parâmetros é que o número total de variantes possíveis dos parâmetros é muito maior que o número de variantes seguras.

Supõe-se que os próprios desenvolvedores gerenciarão esse complexo processo de seleção, pois tudo, exceto o expoente aberto, deve ser gerado durante a inicialização.
Não há maneiras fáceis de verificar a confiabilidade dos parâmetros . Em vez disso, os desenvolvedores precisam de uma base matemática séria, cuja presença não deve ser esperada dos funcionários comuns. Embora o uso do RSA com alinhamento possa salvá-lo se você tiver os parâmetros errados, muitos ainda preferem não.

Acolchoando ataques do Oracle

Como explicamos acima, o simples uso do RSA imediatamente não funciona. Por exemplo, o esquema RSA descrito na introdução criará textos cifrados idênticos se o mesmo texto simples já tiver sido criptografado mais de uma vez. Este é um problema porque permitirá que um invasor aprenda o conteúdo de uma mensagem a partir do contexto, sem poder descriptografá-lo. É por isso que precisamos alinhar as mensagens com alguns bytes aleatórios. Infelizmente, o esquema de alinhamento mais usado, o PKCS # 1 v1.5, é frequentemente vulnerável ao chamado ataque de preenchimento de oráculo.

O ataque inicial ao PKCS # 1 v1.5 foi descoberto em 1998 por Daniel Bleikhanbacher. Apesar de ter mais de 20 anos, hoje ela continua sendo relevante para muitos sistemas. As versões modernas desse ataque geralmente incluem um oráculo adicional, um pouco mais complexo do que o originalmente descrito por Bleikhanbacher, por exemplo, tempo de resposta do servidor ou a execução de qualquer downgrade de protocolo no TLS. Um exemplo particularmente chocante foi o ataque ROBOT , que foi tão terrível que uma equipe de pesquisadores conseguiu assinar mensagens com as chaves secretas do Facebook e do PayPal. Alguns podem argumentar que isso realmente não é culpa da RSA - a matemática básica é boa; as pessoas simplesmente estragaram um padrão importante décadas atrás. O fato é que já tínhamos , desde 1998, um esquema de alinhamento padrão com evidência estrita de segurança, OAEP. Mas quase ninguém usa. Mesmo quando isso acontece, é de conhecimento geral que a OAEP é difícil de implementar e geralmente é vulnerável a um ataque do Manger, que é outro ataque do oracle que pode ser usado para recuperar texto sem formatação.

O problema fundamental aqui é que o alinhamento é necessário ao usar o RSA, e essa complexidade adicional abre um grande escopo para ataques ao sistema de criptografia. O fato de que um pouco de informação, “se a mensagem foi alinhada corretamente”, pode ter um impacto tão grande na segurança que torna praticamente impossível o desenvolvimento de bibliotecas seguras. O TLS 1.3 não oferece mais suporte ao RSA, portanto, podemos esperar menos ataques desse tipo no futuro.

Porém, embora os desenvolvedores continuem usando o RSA em seus próprios aplicativos, os ataques do Padding Oracle continuarão ocorrendo.

O que fazer

As pessoas geralmente preferem usar o RSA porque acham conceitualmente mais simples que o protocolo DSA complicado ou a criptografia de curva elíptica (ECC). Mas, embora o RSA seja mais intuitivo, ele realmente carece de proteção contra o tolo.

Primeiro de tudo, um equívoco comum é que o elíptico é muito perigoso, porque escolher uma curva ruim pode anular tudo. É verdade que a seleção de curvas tem um grande impacto na segurança, mas um dos benefícios do uso do ECC é que a seleção de parâmetros pode ser feita publicamente. Os criptografadores fazem a escolha dos parâmetros para você, então os desenvolvedores precisam apenas gerar bytes aleatórios de dados para usar como chaves. Os desenvolvedores podem teoricamente criar uma implementação de ECC com parâmetros terríveis e não poderão verificar itens como pontos de curva incorretos, mas geralmente não o fazem. A provável explicação é que a matemática por trás do ECC é tão complexa que poucas pessoas se sentem confiantes o suficiente para implementá-lo. Em outras palavras, esse medo força as pessoas a usarem bibliotecas criadas por criptógrafos que conhecem suas coisas. O RSA, por outro lado, é tão simples que pode ser (mal) implementado em uma hora.

Em segundo lugar, qualquer correspondência de chave baseada no algoritmo Diffie-Hellman ou no esquema de assinatura (incluindo opções de curva elíptica) não requer alinhamento e, portanto, é totalmente resistente a ataques do Padding Oracle. Esta é uma grande vitória, já que a RSA tem um histórico muito longo de tentativas para evitar essa classe de vulnerabilidades.

Recomendamos o uso do Curve25519 para troca de chaves e ed25519 para assinaturas digitais. A criptografia deve ser realizada usando o protocolo ECIES, que combina a troca de chaves ECC com um algoritmo de criptografia simétrica. O Curve25519 foi projetado para impedir completamente as classes de ataque que podem acontecer com outras curvas, e também é muito rápido. Além disso, ele é implementado em muitas bibliotecas, por exemplo, libsodium, que é equipado com documentação de fácil leitura e está disponível na maioria dos idiomas.

Pare de usar o RSA. Sério.

(O Twilio ainda usa chaves RSA)


(O Travis CI ainda usa chaves de 1024 bits e não permite substituí-las)

A RSA foi um marco importante no desenvolvimento de comunicações seguras, mas as duas últimas décadas de pesquisa criptográfica a tornaram obsoleta. Os algoritmos nas curvas elípticas para troca de chaves e assinaturas digitais foram padronizados em 2005 e desde então foram integrados a bibliotecas intuitivas e resistentes ao uso indevido, como o libsodium. O fato de o RSA ainda ser amplamente utilizado hoje indica um erro por parte dos criptógrafos, devido a uma descrição inadequada dos riscos inerentes ao RSA e aos desenvolvedores que superestimam sua capacidade de implementá-lo com sucesso. A comunidade de segurança deve começar a pensar nisso como um problema de manada - embora alguns de nós possam navegar pelo processo extremamente perigoso de configurar ou implementar o RSA, as exceções deixam claro para os desenvolvedores que o RSA ainda é relevante em alguns aspectos. Apesar das muitas advertências e avisos no StackExchange e no GitHub README, pouquíssimas pessoas acreditam que são elas que estragam a RSA e, portanto, continuam a agir de forma imprudente. Por fim, seus usuários pagarão por isso. É por isso que todos devemos concordar que o uso do RSA em 2019 é completamente inaceitável. Sem exceções.

Artigo original em inglês.

VirgilSecurity, Inc. Desenvolve um SDK amigável ao desenvolvedor de código aberto e serviços de proteção de dados. Permitimos que os desenvolvedores usem algoritmos existentes com risco mínimo de segurança.

PS Eu recomendo que você também leia sobre a incorporação de um backdoor na chave pública RSA.