Gpcode.ak Cryptographic Challenge

On June 5, 2008, Kaspersky Lab has informed the public of a new virus, Gpcode.ak, that maliciously encrypts documents found on the victim's machines using 1024-bit RSA encryption, and attempts to extort money in return for decryption.

The following summarizes the known information, mainly from the Kaspersky Lab press release and the Viruslist entry.

Gpcode.ak encrypts files with typical document extensions (such as doc, txt and pdf) using an RSA encryption algorithm with a 1024-bit key. The encryption of each file is saved into FILE._CRYPT and the original is then deleted. A text file named !_READ_ME_!.txt is written to the same folder, containing the following:

Your files are encrypted with RSA-1024 algorithm.
To recovery your files you need to buy our decryptor.
To buy decrypting tool contact us at: ********@yahoo.com
Once the virus has delivered its payload, it creates a VBS file which deletes the main body of the virus from the victim machine, and displays the following MessageBox:

Kaspersky Lab has thwarted previous variants of Gpcode by "crack[ing] the private key after in-depth cryptographic analysis". The author of Gpcode has taken two years to improve the virus: the previous errors have been fixed and the key has been lengthened to 1024 bits instead of 660 bits.

At the time of writing, Kaspersky Lab is unable to decrypt files encrypted by Gpcode.ak since the key is 1024 bits long. Thus, the only way currently to decrypt the encrypted files is to use the private key which only the author has available at a fee.

This malicious program is a Windows PE EXE file 8030, bytes in size. The virus uses Microsoft Enhanced Cryptographic Provider v1.0 (built into Windows) to encrypt files. Files are encrypted using the RC4 algorithm. The encryption key is then encrypted using an RSA public key 1024 bits in length which is in the body of the virus. Kaspersky Lab has issued a Call for Cryptanalysis: 

Date: Fri, 6 Jun 2008 20:49:37 +0400
From: Aleks Gostev <Alexander.Gostev ... kaspersky.com>
To: Eran Tromer <tromer ... csail.mit.edu>
CC: Stopgpcode <Stopgpcode ... kaspersky.com>
Subject: Re: Analysis of Gpcode.ak's RSA encryption

Hi, Eran.

Thank you for your help! We've decided to share the gpcode "public keys".

This is our official annoucement:

Along with antivirus companies around the world, we're faced with the task of cracking the RSA 1024-bit key. This is a huge cryptographic challenge. We estimate it would take around 15 million modern computers, running for about a year, to crack such a key.

Of course, we don't have that type of computing power at our disposal. This is a case where we need to work together and apply all our collective knowledge and resources to the problem. 

So we're calling on you: crytographers, governmental and scientific institutions, antivirus companies, independent researchers…join with us to stop Gpcode. This is a unique project - uniting brain-power and resources out of ethical, rather than theoretical or malicious considerations.  

Here are the public keys used by the authors of Gpcode.

The first is used for encryption in Windows XP and higher.

Key type:  RSA KeyExchange
bitlength: 1024
RSA exponent: 00010001
RSA modulus:
c0c21d693223d68fb573c5318982595799d2d295ed37da38be41ac8486ef900aee78b4729668fc920ee15fe0b587d1b61894d1ee15f5793c18e2d2c8cc64b0539e01d088e41e0eafd85055b6f55d232749ef48cfe6fe905011c197e4ac6498c0e60567819eab1471cfa4f2f4a27e3275b62d4d1bf0c79c66546782b81e93f85d

The second is used for encryption in versions of Windows prior to XP. 

Key type:  RSA KeyExchange
bitlength: 1024
RSA exponent: 00010001
RSA modulus:
d6046ad6f2773df8dc98b4033a3205f21c44703da73d91631c6523fe735607247cc9a5e0f936ed75c75ac7ce5c6ef32fff996e94c01ed301289479d8d7d708b2c030fb79d225a7e0be2a64e5e46e8336e03e0f6ced482939fc571514b8d7280ab5f4045106b7a4b7fa6bd586c8d26dafb14b3de71ca521432d6538526f308afb

The RSA exponent for both keys is 0x10001 (65537).

The information above is sufficient to start factoring the key. A specially created utility could be of great help in factoring.

We're happy to provide additional information to anyone involved in stopping Gpcode. To keep everyone up to date, we've set up a dedicated forum (http://forum.kaspersky.com/index.php?showforum=90)
[quotes snipped]

As noted, Kaspersky Lab has set up a dedicated discussion forum (mostly in Russian).

Preliminary analysis

This is a malevolent but, alas, potentially all-too-effective use of cryptography.

If the virus is implemented correctly, a straightforward attempt to break its RSA keys would be extremely expensive. To date, the largest broken RSA challenge was a 663-bit key, and the latest cost projections for breaking 1024-bit RSA keys, using special-purpose cryptanalytic hardware (such as the the TWIRL device), estimate it would cost several million US$ to break such a key within a year, and moreover that constructing such hardware will be a non-trivial technological challenge. Furthermore, there is little to prevent the author of the virus (or his imitators) from using thousands of different keys, each of which would have to be broken separately.

Cryptanalysis could become more realistic and effective if some flaws exist in the virus's file encryption mechanism, or its key selection algorithm. Kaspersky Lab's press release hints that such flaws indeed existed in prior verions. For example, the per-file encryption uses RC4; there may be a weakness in the generation of these keys or the invokation of RC4.

At present Kaspersky Lab is yet to provide verifiable evidence that the announced public keys are indeed those used by the virus. Moreover, even if the public keys are correctly extracted and reported (which seems very likely given Kaspersky Lab's reputation), we have not seen proof that the virus's author indeed knows the corresponding private keys. This leaves open a remote but troubling possibility: these 1024-bit RSA public keys may actually be copies of someone else's public keys. For example, they could be copies of a root signing key of a prominent certificate authority. Thus, a well-meaning cryptanalytic effort to break such keys in order to help the virus's victims may end up causing considerable harm.

To alleviate these concerns, I urge Kaspersky Lab, and the other antivirus vendors, to release further information about the exact implementation of the file encryption mechanism, and to conduct a suitable challenge-and-response transaction with the virus's author to verify his ability to decrypt random-looking files and thus (under reasonable assumptions) prove his possession of the private key.

How does the decryption process work, and in particular how does it handle the specific RC4 keys used on each machine? Earlier versions used a 660-bit key and were broken, but apparently not by a generic RSA attack. Unless the 660-bit RSA key has some known weakness, it would be an interesting challenge by itself, and good sanity test for the distributed-codebreaking efforts being discussed.

One may wonder why the authors of the virus chose a key size that's marginally-feasible (1024 bits) rather than one that's well beyond current algorithms (e.g., 1536 bits). One explanation is the desire to keep the code size down, at a mere 8030 bytes.

This page formerly contained a mention of an expoitable cryptographic weaknesses in the virus code. Upon further analysis, that claim is withdrawn.
— Eran Tromer