Pesquisadores da Universidade da Califórnia em San Diego desenvolveram uma técnica avançada de ataque ao algoritmo RSA, permitindo falsificar assinaturas digitais sem a necessidade de fatorar os números primos subjacentes ao RSA e sem a necessidade de recuperar a chave privada. Os recursos necessários para realizar o ataque a uma chave RSA de 1024 bits são estimados em 1380 anos de cálculos em uma única unidade de processamento, o que permitiu, em um cluster da universidade, determinar em 5 meses os parâmetros necessários para gerar assinaturas RSA falsas (no experimento, não foram utilizados aceleradores de AI e GPUs; com seu uso, o tempo de cálculo pode ser substancialmente reduzido). Em comparação, o método clássico de fatoração requer entre 500 mil a um milhão de anos de cálculos em uma única unidade de processamento para reconstruir a chave privada RSA-1024.
Para realizar o ataque, é necessário ter a capacidade de enviar repetidamente solicitações para assinatura de dados criados pelo atacante, por exemplo, acessando um serviço de autorização ou um módulo HSM. Para determinar os parâmetros RSA-1024, é suficiente enviar 232 dessas solicitações, e para um ataque a chaves RSA-2048, usadas no protocolo Privacy Pass, são necessárias 243. Após receber um conjunto de dados assinados, inicia-se um longo processo de cálculo dos parâmetros (para RSA-1024, cerca de 265 operações); após a obtenção desses parâmetros, o atacante pode criar assinaturas falsas para quaisquer dados, gastando cerca de 180 horas de cálculos em uma única unidade.
O método é aplicável apenas a assinaturas RSA nas quais não é utilizado formatação e preenchimento adicional antes da criptografia (padding). O ataque é vulnerável em implementações de assinatura cega, incluindo aquelas usadas no protocolo Privacy Pass. A maioria das implementações comuns de RSA, incluindo PKCS#1v1.5 e RSA-PSS (utilizadas em TLS e SSH), aplicam preenchimento adicional e não são vulneráveis ao ataque.
A base da criptografia RSA é a operação de exponenciação módulo de um grande número. A chave pública contém o módulo e o expoente. O módulo é formado com base em dois números primos aleatórios, que são conhecidos apenas pelo proprietário da chave privada. O método proposto é baseado em uma pesquisa publicada em 2007, que demonstrou que a extração da raiz na potência indicada na chave pública de uma mensagem criptografada, sem informações sobre os fatores secretos, é uma operação menos exigente em recursos do que a fatoração dos próprios fatores.
Usando um método especial chamado fatoração de campo numérico (SNFS), os pesquisadores conseguiram reduzir a complexidade da compromissão das chaves RSA-1024 para 265 operações, o que permite realizar ataques práticos em clusters modernos. Para chaves RSA de 2048 bits, a complexidade do ataque é estimada em 290, o que é teoricamente viável para grandes corporações ou serviços de inteligência. Para chaves de 4096 bits, a complexidade do ataque é de 2119 operações, o que atualmente é inatingível, mas abaixo do mínimo 2128 recomendado pela NSA, pelo Instituto Nacional de Padrões e Tecnologia e pela Agência Europeia de Segurança de Redes e Informação.
Fonte: opennet.ru
