Criptografia: Ataques RSA 768 e 1024 bits & FRED-SC

[ Update - 07/03/2010 ]

Pesquisadores da Universidade de Michigan divulgaram um ataque bem sucedido (*) a criptografia RSA 1024 bits - para mais detalhes, veja o paper publicado (PDF).

"The RSA algorithm gives security under the assumption that as long as the private key is private, you can't break in unless you guess it. We've shown that that's not true," said Valeria Bertacco, an associate

professor in the Department of Electrical Engineering and Computer Science, in a statement.

Uma bom resumo: http://www.engadget.com/2010/03/09/1024-bit-rsa-encryption-cracked-by-carefully-starving-cpu-of-ele/

Since 1977, RSA public-key encryption has protected privacy and verified authenticity when using computers, gadgets and web browsers around the globe, with only the most brutish of brute force efforts (and 1,500 years of processing time) felling its 768-bit variety earlier this year. Now, three eggheads (or Wolverines, as it were) at the University of Michigan claim they can break it simply by tweaking a device's power supply. By fluctuating the voltage to the CPU such that it generated a single hardware error per clock cycle, they found that they could cause the server to flip single bits of the private key at a time, allowing them to slowly piece together the password. With a small cluster of 81 Pentium 4 chips and 104 hours of processing time, they were able to successfully hack 1024-bit encryption in OpenSSL on a SPARC-based system, without damaging the computer, leaving a single trace or ending human life as we know it. That's why they're presenting a paper at the Design, Automation and Test conference this week in Europe, and that's why -- until RSA hopefully fixes the flaw -- you should keep a close eye on your server room's power supply.

Outros detalhes: http://rdist.root.org/2010/03/08/attacking-rsa-exponentiation-with-fault-injection/

(*) For whatever reason, the OpenSSL programmers decided to retry with fixed-window exponentiation and trust that since there were no published fault attacks for it, they didn’t have to validate its result (...) This was a nice attack but nothing earth-shattering. The only thing I was floored by (yet again), was the willingness of crypto implementers to perform unsafe operations in the face of an almost certain attack. Shame on OpenSSL.

A RSA demorou, mas respondeu de forma quase realista =) :

(...) Bottom line, FBARA does not report an attack against the RSA algorithm. It describes a hardware-based attack. This essentially induces computational faults by manipulating the power supply on the target device. The resulting faulty output means that it is possible to extract a private RSA key.

The real-world applications of this are limited since it requires physical access to a device operating OpenSSL (or at least to its power supply). Since OpenSSL typically executes on a server (and not something like a smartcard or a light device or consumer device), the attacker would probably have to overcome significant physical obstacles to get to the target. (...)

Para informações em português, leia: http://www.crkportugal.net/?p=892

[ Post Original - 08/01/2010 ]

1) Fatoracao RSA 768 bits

A vasta maioria da criptografia utilizada hoje depende de números enormes (algo maior de 200 dígitos) que sejam resultado do produto de outros dois números primos. É possível criptografar e descriptografar dados a partir do conhecimento dos números. E - se você não os sabe e precisará fazer um ataque de força bruta, é bom que você tenha tempo livre, muitos computadores a disposição e muita paciência e conheça muita gente como você (espere... esta parece ser a perfeita descrição da condição de pesquisadores acadêmicos! =).

Pois então, em um paper (pdf) divulgado a apenas algumas horas atrás, um grupo de pesquisadores anunciou a fatoração de um módulo 768 bit RSA em 12 de dezembro de 2009 e aproveitaram para recomendar que se deixe de usar criptografia RSA 1024 bits dentro dos próximos 3 anos. O paper é leve e tem até link para o Youtube usando o filme Bastardos Inglórios do Tarantino para a hora do "Bingo".

Bem, na verdade é leve até um momento, quando você possivelmente vai dar alguns page-downs por não querer sobrecarregar seus neurônios tentanto compreender as descrições teóricas das fórmulas matemáticas utilizadas durante o processo =)

Mas, o que isto significa, afinal? Bem, não é fácil para um humano imaginar um número de 232 dígitos. Para ajudar, segue o número:

12301866845301177551304949583849627207728535695953347921973224521517264
00507263657518745202199786469389956474942774063845925192557326303453731
54826850791702612214291346167042921431160222124047927473779408066535141
9597459856902143413

e os fatores (multiplicadores primos) encontrados:

33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489 

X 

36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

Este número de 232 dígitos não foi escolhido a esmo, ele estava em uma lista de desafios da RSA já desativada.

O que acontence é que a com o tempo a dificuldade de quebra é reduzida com o aumento exponencial de velocidade dos processadores. (Moore´s Law). E pode ser ainda mais rápida com as novidades da utilização dos processadores gráficos (GPU), ou computação CUDA e/ou outros multiplos aceleradores gráficos integrados (ou 200 video-grames PS3, como no caso da colisão de hashes MD5 usados em certificados SSL que comentamos aqui há exatamente um ano atrás).

Para informações old-school - vá direto ao MIT do ano de 1978, quando Rivest, Shamir e Adleman - futuros RSA- publicaram o célebre documento "A Method For Obtaining Digital Signatures And Public Key Cryptosystems" (pdf).


2) FRED-SC

Aproveitando o assunto criptografia, e sendo muito comum em análises forenses nos depararmos com documentos criptografados, vale a notícia de um fabricante de hardware especializado para forense computacional que anunciou há poucos dias que está comercializando servidores com múltipas GPUs gráficas prontos para o trabalho de quebra especializada de senhas.

Trata-se da Digital Intelligence, que já fornece o sistema Fred-SC, que vem com quatro placas de vídeo NVIDIA GTX-295 customizadas para funcionar em paralelo (cada placa tem dois GPUs em um total de 1920 processadores!)

Isto possibilita uma velocidade de processamento MONSTRUOSO obviamente para aplicações especialmente construídas para este fim. Por exemplo, este sistema já vem embarcado com a ferramenta da empresa russa Elcomsoft chamado "Distributed Password Recovery (EDPR)" - e a licença permite que este sistema pode ser utilizado em até 20 servidores FRED-SC em paralelo.

Além de possibilitar uma maior eficiência em ataques de força bruta e dicionário, este poder computacional todo conseguir calcular rainbow tables para gerar hashes pré-calculados de forma rapidíssima.

Para deixar bem claro o tamanho da evolução (e também para entender porque dizem que o processamento com múltiplos GPUs explodiu com a lei de Moore), dê uma olhada nos gráficos comparativos de quebra de senha de arquivos do Office 2007, Vista e Win7 (NTLM) e Unix (MD5) em um sistema versus o "Fred-SC" da Digital Intelligence.

Exemplos:

Senhas do Vista (NTLM): CPU Quad-Core stand-alone: 177 mil senhas por segundo.
Senhas do Vista (NTLM): FRED-SC stand-alone: 3.9 bilhões de senhas por segundo.

Senhas do Linux (MD5): CPU Quad-Core stand-alone: 219 mil senhas por segundo.
Senhas do Linux (MD5): FRED-SC stand-alone: 5.3 bilhões de senhas por segundo.

Seguem os tipos de aplicações que são os "alvos-ideais" para trabalhos de quebra de senha com o FRED-SC + EDPR (todos otimizados / acelerados para GPU):

- Microsoft Word/Excel/PowerPoint/Project 2007 (.DOCX, .XLSX, .PPTX, .MSPX)

- PGP disks with conventional encryption (.PGD), whole disk encryption.

- Windows NT/2000/XP/2003/Vista logon passwords (LM/NTLM)

- Windows DCC (Domain Cached Credentials) passwords (password recovery).

- MD5 hashes (plaintext recovery).

- WPA and WPA2 passwords (password recovery).

[ Update - 31/12/2010 ]

Na BlackHat 2010 será apresentado um server capaz de processar "280 DES decryptions per second! permitting the full 56-bit key space to be searched in 3 days" Mais informações aqui.