Trojan.Gpcoder is a particularly nasty threat that uses public key cryptography to encrypt files on a person’s computer and subsequently requests payment from the user in order to recover the files. It has had many variants over the years. While analyzing a recent version, I observed that it uses a short key. Would this make it possible to decrypt the infected files?
Public key cryptography uses two keys—a public key and a private key. In Trojan.Gpcoder the public key is encoded into the virus and is used to encrypt files. The author of Trojan.Gpcoder holds the private key which is used to decrypt files.
Last year we detected Trojan.Gpcoder.E. This version of Trojan.Gpcoder claimed to use a public key algorithm called RSA-4096 to encrypt files (in fact, it used a weaker algorithm). More recently we detected a new variant, Trojan.Gpcoder.F. Where RSA-4096 is considered secure—except to maybe the Klingons—there has been some speculation about the security of RSA-1024, which is used in this new variant.
So what about breaking RSA-1024 and getting back your recently encrypted files? Well, the public key is made up of two numbers: "n" and "e". n is 1024 bits long and e is typically short. The private key that the author holds also consists of two numbers, "n" and "d". If we can factor this n we can work out d, and thus we can recover the files.
The largest RSA type modulus (product of two primes) factored by a general-purpose factoring algorithm was 663 bits long. The CPU time spent on finding these factors by a collection of parallel computers amounted—very approximately—to the equivalent of 75 years work for a single 2.2 GHz computer. Trojan.Gpcoder.F uses a 1024 bit key, 361 bits longer then any RSA key that has ever been factored (in public).
Adi Shamir and Eran Tromer estimate that if their TWIRL machine (a dedicated RSA 1024 bit cracking machine) had been built it would be able to factor 1024-bit numbers in one year at the cost of "a few dozen million US dollars." Arjen Lenstra and Eric Verheul have claimed that a machine that could break one 1024-bit RSA key in about a day, would cost $160 billion when adjusted for today’s prices. This doesn’t leave us much hope for recovering our files. The virus author could easily convert to a secure 4096 bit key or release numerous variants with many different public keys to thwart any attempts to break his private key.
Given that sobering thought, the best recommendation is to keep your antivirus definitions up-to-date and to employ backup software, such as Symantec Backup Exec. If you do get infected and don’t use backups, you could try data recovery tools to restore the files that Trojan.Gpcoder.F has deleted. You may not be 100% successful, but you should be able to recover a good proportion of your files.
Message Edited by SR Blog Moderator on 06-18-2008 06:49 AM