Kaspersky Labs Trying to Crack 1024-bit RSA

I can’t figure this story out. Kaspersky Lab is launching an international distributed effort to crack a 1024-bit RSA key used by the Gpcode Virus. From their website:

We estimate it would take around 15 million modern computers, running for about a year, to crack such a key.

What are they smoking at Kaspersky? We’ve never factored a 1024-bit number—at least, not outside any secret government agency—and it’s likely to require a lot more than 15 million computer years of work. The current factoring record is a 1023-bit number, but it was a special number that’s easier to factor than a product-of-two-primes number used in RSA. Breaking that Gpcode key will take a lot more mathematical prowess than you can reasonably expect to find by asking nicely on the Internet. You’ve got to understand the current best mathematical and computational optimizations of the Number Field Sieve, and cleverly distribute the parts that can be distributed. You can’t just post the products and hope for the best.

Is this just a way for Kaspersky to generate itself some nice press, or are they confused in Moscow?

EDITED TO ADD (6/15): Kaspersky <a href=http://www.securityfocus.com/news/11523″>now says:

The company clarified, however, that it’s more interested in getting help in finding flaws in the encryption implementation.

“We are not trying to crack the key,” Roel Schouwenberg, senior antivirus researcher with Kaspersky Lab, told SecurityFocus. “We want to see collectively whether there are implementation errors, so we can do what we did with previous versions and find a mistake to help us find the key.”

Schouwenberg agrees that, if no implementation flaw is found, searching for the decryption key using brute-force computing power is unlikely to work.

“Clarified” is overly kind. There was nothing confusing about Kaspersky’s post that needed clarification, and what they’re saying now completely contradicts what they did post. Seems to me like they’re trying to pretend it never happened.

EDITED TO ADD (6/30): A Kaspersky virus analyst comments on this entry.

Tags: , , , , , , ,

Posted on June 12, 2008 at 12:30 PM • 62 Comments

Comments

2TryOrOtherAgenda • June 12, 2008 1:28 PM

Good snake oil or press to brag about skill in results, if you got the keys somehow, and put up enough work and ‘skill.’ What about some other agenda like mapping or ? Can’t see much market for this, and few care about crypto, so yeah ? Would be nice to have a legit distributed system though…
Good that this site brings perspective to current affairs.
DJB mentioned something about 1024 might be easier than thought if [fill in blanks/google is your friend, or Bruce might help out]
I’d like to smoke some of that hopeful stuff with ROI on trying to crack 1024. So easy to go to 16384, or less for practically nothing. Would be interesting to know if people are still really trying to crack the RSA challenges?

Peter • June 12, 2008 1:29 PM

Maybe (but I wouldn’t bet on it) they figured out some weakness in the trojan’s implementation. Previous version of the same thing had some weaknesses thanks to sloppy programming (in addition to smaller key) and they (=some AV vendor, I don’t know if Kasperski) managed to reconstruct the private key.

More likely, they’re just clueless about cryptography.

Mike • June 12, 2008 1:44 PM

Even if this did work it would take the authors about 4 seconds to make a new strain with a different private key

Pat Cahalan • June 12, 2008 1:56 PM

I’m guessing that Peter’s more right than he thinks. I imagine that Kaspersky expects that the crypto is implemented improperly. They’re certainly not clueless about cryptography.

Bruce is right, though… their “press release” version of this story doesn’t really explain what’s going on here.

MrvnMouse • June 12, 2008 2:36 PM

According to the article, the virus advises the person whose data was encrypted to “buy a decryptor [sic] and provides an e-mail address to contact.”

Why doesn’t Kapersky simply buy the decryption software covertly and simply reverse engineer the key out of that. To decrypt the files, there would have to be a private key within (or somehow retrieved) by the decryption software. Unless, of course, the decryption software simply sends the data to a decryption server somewhere to be decrypted. In which case, I guess at the very least you’d have a decryption oracle of sorts to play with.

If it is possible to reverse engineer it, it would be infinitely more simple than trying to factor a 1024-bit number.

Regardless, even if, by some miracle they were to break the key, it would be trivial for the criminals to simply change it to another one, and so the work would only be useful for old already lost data (after a year of work.)

Bryan • June 12, 2008 2:44 PM

Swa Frantzen at ISC raised some interesting questions about the idea.

http://isc.sans.org/diary.html?storyid=4544

“How do we know this public key (or his next key, or the one after that), is a key the attacker actually has the matching private key for? How do we know for sure this key doesn’t belong to somebody else and by giving out the private key to thwart the apparent attacker we’re actually helping him in his real attack against somebody else.”

Martin • June 12, 2008 2:47 PM

@MrvnMouse:

As I understand it, here’s how it works:

  • The virus encrypts your files with a random symmetric key
  • This symmetric key is then encrypted with the 1024-bit RSA public key
  • You send the encrypted symmetric key to the criminals
  • The criminals decrypt the symmetric key with the private RSA key and send it to you as soon as they pocket their ransom (including the decrypting application that uses this key)

Clive Robinson • June 12, 2008 2:48 PM

Not sure about the 15million CPU years to crack a truly randomly generated pq pair. The back of my “fag packet” differs somewhat.

One point to note from the (second link) is that a Kaspersky bod thinks/knows that the Microsoft API was used to generate the key…

Now even those with a short memory can probably remember that Microsoft does not have a particularly good past reputation with regards crypto and random number generators.

It may be possible that Kaspersky know of a weakness in the MS code that could vastly reduce the search space for p&q. That however still requires significant “grunt” to exploit.

As an example of deliberate key weakening, what if you know for instance that one of the primes is only 256bits in length and is itself RSA encoded with a 296bit key and then mapped into the top bits of the 1024bit key. Or that one of the primes is a simple count up from a (supposadly secret) start point.

In either of the above cases of key weakening there is no way to tell by looking at the 1024bit pq key. But to those in the know p is fairly quickly found and q falls nanoseconds later.

Also I sort of vaguly remeber that D.Coppersmith published a paper that indicated that knowing only 25% of the bits for p or q was enough to fataly weaken the composit (just wish I could remember what the details where).

As someone (Bruce?) will no doubt confirm with details there have been a number of “weak RSA key” systems discussed in the past. I think Adam Young and Moti Yung published one as part of their research into cryptovirology.

FNORD • June 12, 2008 2:48 PM

The press release, to me, reads more like a cry for help than an honest proposal.

Dave • June 12, 2008 3:29 PM

I read about this myself earlier this week. If I remember correctly, they mention something about a file decryption utility that the blackmailer sends back, which I think they assumed could reverse their key.

Skorj • June 12, 2008 3:30 PM

How do these Gpcode authors get paid in the first place? Money is very trackable. You’d think we’d have accounts frozen and US Marines kicking in doors by now (assuming a single federal computer was infected, making this an attack on the US Govt.).

DGenerateKane • June 12, 2008 4:03 PM

Groups have been trying to crack RSA Labs RC5-72 encyption challenge for over 5 years now, and have not even reached 1% completion, granted that is just from one group. At the rate that group is going it will take them over 1300 years to crack it. Needless to say over a year ago RSA withdrew the reward money and is no longer supporting it. Assuming no errors were made in the implementation of the encryption, I wouldn’t care to guess how long it would take to find the key. And that is assuming there is only one to begin with, for all we now each computer is encrypted with a new key.

MrvnMouse • June 12, 2008 4:11 PM

@Martin:

Well if that is true, then at very least we should have access to a chosen-ciphertext attack (and possible adaptive chosen-ciphertext attack) unless the key cannot be any bit-string whatsoever. It will be an expensive attack, but at least it provides an in that is more realistic than trying to factor a 1024-bit number.

MrvnMouse • June 12, 2008 4:13 PM

As well, if the key has a structure of some sort, it may be possible to use that structure in a similar fashion to the PKCS#1 attacks.

Again with the hope of cracking the key eventually.

Chris L • June 12, 2008 4:19 PM

It sounds like someone in executive management at Kaspersky or their family got hit with it.

Jurjen • June 12, 2008 4:50 PM

Even if all the relations are found quickly with a super-sophisticated version of GNFS, who is going to provide the 6 Terabyte RAM machine for the matrix step? O yes, this RAM should be instantaneously accesible to all processors, otherwise the computation will take too long (the current implementation uses at most about 10 processors for this reason).
Kaspersky probably has more money than I thought.

Anonymous • June 12, 2008 4:57 PM

Shouldn’t they be attacking the implementation of the key as opposed to the key itself? It is in errors in the implementation that they will find ways to by pass the key and access the data.

Brad Templeton • June 12, 2008 5:11 PM

Not to mention that since going full blast pushes the computer power draw up by about 40 to 70 watts on a typical system today — let’s say 50 — this amounts to 6.5 Billion kw-h, costing about 670 million dollars as the U.S. residential average of 10.3 cents/kwh, or 67 trillion BTUs at the generator (the equivalent of burning 500 million gallons of gasoline, though in the USA it’s mostly coal and natural gas, then nukes and hydro)

That’s not very responsible.

daSinicAlJoker • June 12, 2008 5:11 PM

Simple. The person who wrote the virus miscoded the public key and now they get lots of offers of cash, but they can’t decode the files. If they just take the cash and don’t decrypt, nobody will pay up for the next version of the virus. Somehow or other they got Kaspersky to front for their effort to get back the key and profit. Hopefully for them, the key they included does have a real private key to go with it 🙂

🙂 (I hope 🙂 🙂

Will • June 12, 2008 5:42 PM

A question, since I know zilch about cryptography… Does knowing the contents, in part of whole, of the encrypted file ease decryption in a case like this?

Presumably this virus recurses your drive, grabs all your documents, and encrypts them. It’s not likely that it skips all the sample documents and such that are included with software so the contents of those would be known in full. Many other documents would be known in part, particularly the beginning of them, because of their file structures. Could this be used to shortcut/speed decryption?

Primoris_Causa • June 12, 2008 6:18 PM

>Groups have been trying to crack RSA Labs RC5-72 encyption challenge for over 5 years now, and have not even reached 1% completion, granted that is just from one group. At the rate that group is going it will take them over 1300 years to crack it.

Groups have been – but if this threat proves severe enough, those groups and others may team together, thus providing the needed “umph”. I know the reward was withdrawn – if it was THAT secure, why withdraw it? I think their risk anal folks believe that given enough monkeys, it can be cracked before they can get the spare cash.

Before it was an intellectual exercise, the work was fragmented amongst teams – now, it is a possible threat and a company is asking for all the available help it can get to break it. While I do not doubt the altruism of the company in this endeavor, I do not know all of its employees – and if I wanted to stay on top of the “anti” algorithms, I’d work for one of them.

gotpasswords • June 12, 2008 6:53 PM

A question, since I know zilch about cryptography… Does knowing the contents, in part of whole, of the encrypted file ease decryption in a case like this?

Looking at the screenshot in the CNET article, it apparently just hits your “My Documents” directory, and encrypts the files’ contents.

If one or more of those documents is a plain text file, and you happen to know the exact composition of the file, down to the last space and line break, you could run a “known-plaintext” attack on the crypto.

Stuff like Word documents that subtly change every time you just look at them, (by doing things like storing the last date/time it was accessed) would be much harder to work with – changing just one bit of a file will give you a completely different encrypted file.

However, if you know the exact makeup of a file down to the last space and line break, you’re probably looking at a backup copy, at which point you say “Nice try, Gpcode.” Then you re-image the computer and restore from the backup, then get on with whatever you were doing before some would-be data kidnapper distracted you.

Will • June 12, 2008 7:29 PM

Backups… I hadn’t thought of those, but that’s cool because that makes it more likely that someone could have exact copies of files that had been encrypted by the virus.

So, suppose a person is hit by the virus and they provide Kaspersky (or other vendor) with encrypted documents and known to be current originals how would that affect this 15 million computer years figure for cracking the key? Halve it? Reduce it by an order of magnitude? Two? More?

Bruce • June 12, 2008 7:36 PM

yeah, let’s make an assumption that people behind Gpcode won’t switch to 2048bit RSA key. Nobody expects the Spanish inquisition.

Jan Schejbal • June 12, 2008 8:06 PM

AFAIK the explaination posted by Martin at June 12, 2008 02:47 PM is correct. The virus is said to use RC4 for file encryption, and from known plaintext/ciphertext pair samples published it seems that the virus uses a separate IV per file (at least the file grows by 16 byte when encrypted, and every encrypted file is different even if original content is identical). I’d say the virus maker did a very good job. I already suggested to try the standard RC4 breaking methods known from the attacks against WEP.

Jan Schejbal • June 12, 2008 8:10 PM

Additionally, Kaspersky seems to look for help finding weaknesses (without releasing information however…), not factoring the keys (although they published the moduli). Maybe they published the moduli so companies can check if their key matches it (see above #1 for theory about this)

Kermit the Frag • June 12, 2008 8:55 PM

If one or more of those documents is a plain text file, and you happen to know
the exact composition of the file, down to the last space and line break, you
could run a “known-plaintext” attack on the crypto.

This might help to recover the random symmetric key used on a particular victim, however it would not help in recovering the RSA private key needed to recover the symmetric keys used on other victims.

peri • June 12, 2008 8:56 PM

My understanding is whoever is behind the extortion scam used two (>XP,>=XP) private 1024-bit RSA keys. Kaspersky seems to want to break those keys so their software can decrypt the encrypted RC4 (master?) key left behind on a victim’s computer.

Obviously the people behind the scam can trivially create new private RSA keys. What could cause Kaspersky to believe that the hurdle for actually deploying these newly generated keys could be anywhere near the unimaginably massive task of breaking the private RSA key?

The only possibility I can imagine is if the current version is automatically propagating without phoning home. Is that the case?

Anthony • June 12, 2008 9:35 PM

Doesn’t look like anyone has mentioned one of the easy mistakes to make — did the malware manage to scrub every copy of the RC4 key from memory and swap?

Hell of a lot easier to try every memory offset as an RC4 key than to break 1024-bit RSA.

The Imp • June 12, 2008 10:55 PM

@ Suspicious

Can we really trust an anti-spyware company from Russia?

I don’t know? Can we really trust one from the USA? History, especially recent history, tends to suggest that we cannot.

Better question: Can we really trust a company? The fact that it’s a company and not a person we’re dealing with seems, after analysis, to be far more relevant than which country they’re in.

Russians are not our (the US) enemies. They’re actually our allies (through NATO, plus others more recently), though we do disagree on a number of relatively minor issues.

The Soviets were our enemies, but that was two decades ago. The Russians were, at the time, Soviets, but there aren’t any Soviets at all anymore.

The Soviets were Communists, but not all Communists were Soviets (see: China). Communists were not, technically, our enemies, although the original motivation for declaring the Soviets our enemies was because we didn’t like Communists.

Technically, the position of the US is that Communism is fine, as long as it’s not One-Party Communism (free and fair elections). But mixing these two is sufficiently difficult that it has never been successful. Plus, this detail is lost on most folks because it was much easier to train them to irrationally hate Communists than to explain the political theory.

I could go on, but I can’t cram enough into a single blog post to undo a half-century of government propaganda, so you’ll probably remain unconvinced.

Hugo • June 13, 2008 3:25 AM

Bruce, aren’t you wrong? Is Adi your friend?

“paper published by Adi Shamir and Eran Tromer entitled “On the Cost of Factoring RSA-1024″ [pdf] hypothesizes a device which could “break a 1024-bit RSA key in one year using a devices whose cost is about $10M”

Max • June 13, 2008 3:32 AM

i don’t get why there is so much fuss about a virus that’s encrypting files. remember the viruses that simply wiped your harddisk, leaving you without hope to ever see your files again? there are thousands of those. honestly this looks like a silly PR stunt from Kaspersky to me.

if they manage to crack the key though, i doubt it would be due to some new advances in cryptanalysis or weaknesses in RSA.. it would show us though, how hard it is to implement cryptographic algorithms correctly.

Max

ITI • June 13, 2008 3:33 AM

What’s a nice idea. Using crypto-key to generate buzz for my products ….
It’s a concept ! 😉

Sparky • June 13, 2008 5:06 AM

@Anthony: That would be one possible attack vector (searching for the key in memory or the swap file), but it won’t help those already infected, who turned off their computer.

The easiest defense against this particular virus, is ofcourse to just move your files out of the “my documents” folder.

Andy Dingley • June 13, 2008 5:09 AM

Announcing the start of a project works practically as well in a PR sense, whether the project is trivially or doomed by its complexity.

Are they selling any 1025 bit crypto that needs a stream of frightened potential customers for it?

Piotr • June 13, 2008 7:37 AM

@The Imp

I could go on, but I can’t cram enough into a single blog post to undo a half-century of government propaganda, so you’ll probably remain unconvinced.

Yes, I’m unconvinced. Not becasuse of US government propaganda, but beacuse I live in Central Europe and I lived in communist state, apparently in contrary to you.

Russians are not our (the US) enemies. They’re actually our allies (through NATO, plus others more recently),

When did Russia join NATO ?

though we do disagree on a number of relatively minor issues.

What is “relatively minor issue” ? Manipulated elections, destroying free press, political murders ?

The Soviets were our enemies, but that was two decades ago. The Russians were, at the time, Soviets, but there aren’t any Soviets at all anymore.

Nonsense. Russia is ruled by the same poeple it was ruled 20 years ago – OK, maybe their younger subordinates.

Communists were not, technically, our enemies, although the original motivation for declaring the Soviets our enemies was because we didn’t like Communists.

Interesting opinion.

Technically, the position of the US is that Communism is fine, as long as it’s not One-Party Communism (free and fair elections).

Have you ever seen communism with free and fair elections ? That’s funny.

Anyway, I agree that trusting any company is walking on thin ice.

Paeniteo • June 13, 2008 7:56 AM

@Will: “A question, since I know zilch about cryptography… Does knowing the contents, in part of whole, of the encrypted file ease decryption in a case like this?”

This would be called a “known plaintext attack” and any properly implemented modern algorithm will be immune to such a thing.

Clive Robinson • June 13, 2008 10:45 AM

If the virus is using RC4 (anybody got links to solid info?), with a (possible) rekey between files why are Kaspersky bothering with the 1024RSA?

I would have thought examining the virus code to find out how the rekey code selects it’s next key would be a more profitable line of attack if resources are limited (especially as this is an area of encryption systems that is most often got wrong (even by experts).

Further what is known about the 16byte (128bit) file size increase after encryption?

There may be the possibility of doing several different “attacks in depth” which for a stream cipher could be extreamly trivial. (Such as simple Xoring two cipher texts at the same offset together to remove the key stream and then untangeling the plain texts, or using known plaintext bytes [MS Word files are full of them] to determin the keystream and then using it to see if other encrypted files are using the same section of key stream ).

Much of the exploritory work for “in depth” attacks can be done fully automaticaly.

But I would still place my money on the likelyhood of breaking the “randomisation” used to re-seed the RC4 generator than on the somewhat remote possibility of breaking the 1024RSA keys…

Alexey • June 13, 2008 11:26 AM

Nonsense. Russia is ruled by the same poeple it was ruled 20 years ago – OK, maybe their younger subordinates.

@Piotr

You’re definitely right, but not every Russian (i.e. someone who belongs to the Russian culture) is ruled by these bastards and not every company with the Russian background is related to the current Russian “power”.

Could you distinct the regime and the fair citizens / companies?

peri • June 13, 2008 1:45 PM

Sorry this is just too strange a story not to have some fun
2^1024 / ln(2^1024) = .2532737277e306)

253,911,459,726,315,806,176,455,535,422,178,634,691,804,658,042,698,668,465,296,
724,799,057,451,702,684,976,176,141,917,122,044,542,402,712,025,254,055,640,335,
676,256,735,613,582,800,131,140,438,756,319,384,714,361,431,391,052,945,305,511,
609,606,279,793,954,029,778,180,911,025,097,229,026,387,489,354,352,364,284,054,
436,196,662,660,099,591,362,410,025,762,637,353,020,451,576,701,744,853,572,915,
570,815 primes on the wall. I try 2 and the key doesn’t fall…

253,911,459,726,315,806,176,455,535,422,178,634,691,804,658,042,698,668,465,296,
724,799,057,451,702,684,976,176,141,917,122,044,542,402,712,025,254,055,640,335,
676,256,735,613,582,800,131,140,438,756,319,384,714,361,431,391,052,945,305,511,
609,606,279,793,954,029,778,180,911,025,097,229,026,387,489,354,352,364,284,054,
436,196,662,660,099,591,362,410,025,762,637,353,020,451,576,701,744,853,572,915,
570,814 primes on the wall…

C’mon everybody, sing along and we’ll be done in no time!

Ronald van den Heetkamp • June 13, 2008 2:10 PM

Well, yeah that is the beauty of cryptograhpy, it isn’t kids-games it’s pure maths and clever understanding. I mean, everyone who just leanrs about cryptograhpy thinks he/she can solve it, or create his own secure algortihm.

Cryptograhphy learned me one thing: Watch what you say, because you do not understand how it works if you do not understand mathematics that deals with cryptography. No mistakes are allowed, you either have a secure algorithm or you don’t, there is no room between it.

Let alone the folks that ‘think’ they can ‘crack’ it. I mean, it really made my day. I am smiling all day long since I read this.

But anyway, let them continue, I think any respected scientist will happily look at the results if they do crack it. but untill that, it isn’t plausible thay will do so even with a tenfold of their resources.

bob • June 13, 2008 2:41 PM

I think they got attacked by a competitor with the virus, who WONT sell them the key and they need to get their business files unencrypted.

ranger • June 13, 2008 6:22 PM

Why not just try to retrieve the original files from the harddrive rather than retrieving the key fom memory/swap as suggested in some comment here? It’s not trivial to delete a file on modern file systems.

Suspicious • June 13, 2008 9:55 PM

@The Imp

Actually, no one is safe from software vendors who have rights to automatically upload and download information to and from computers.

An article posted on the Internet December 21, 2007 titled ‘The NSA 0wnz popular firewalls and ‘secure’ email services’ would make people question software companies’ intentions.

Link: http://www.theinquirer.net/gb/inquirer/news/2007/12/20/nsa-0wnz-popular-firewalls

The US government sued Microsoft Corporation several years ago for billions of dollars, but a closed-door meeting resolved the suit.

In 2002, John Thompson, chief executive of Symantec Corp, was appointed by President Bush to the National Infrastructure Advisory Committee (NIAC) as an advisor to the critical infrastructure of the United States.

Software companies that make pacts with governments should raise red flags.

When an anti-spyware software company is trying to figure out how to break a RSA encryption, then one should be concerned not matter for what reason.

Another article posted on the Internet June 11, 2008 titled ‘Experts: Spyware Legislation Needs More Work’ raises even further questions.

Link: http://www.cio.com/article/392113/Experts_Spyware_Legislation_Needs_More_Work

sooth sayer • June 15, 2008 10:32 AM

@Imp

You should actually go back to kindergarten to get some comprehension.

Your worldview is terribly skewed .. wonder what you are you doing reading/commenting here .. if you can’t understand “simpler” reality; it’s probably beyond your faculties to factor the 1024 bit number or worry about who will and how.

David Keech • June 15, 2008 8:44 PM

Why do they need help from the community ?

I would have thought that that the value of the private key would be enough to compensate them for the cost of buying 15 million CPU years.
They could just buy the computers themselves, determine the key and start decrypting people’s documents for a fee…

…as long as they were confident that they could determine the key in a reasonable time frame that is.

jay • June 16, 2008 12:53 AM

Why not simply track the guy and get hold of his private key . .Rather than spending billions and wasting other people’s time and processing power to crack the 1024 bit RSA!

OverQuantum • June 16, 2008 6:49 AM

AFAIK, estimate to break RSA-1024 is 10^12 MIPS-years. If we divide this number by 15 millions we get performance of 66667 MIPS for each PC – this is near to Core 2 Quad benchmark results. I assume “15 million modern computers” – is based on such calculation, nothing more.

Ross Snider • June 16, 2008 12:39 PM

Why don’t we ask our good friends, the botmasters of the Storm Worm, to help?

Seriously, estimates of 50 million computers in that botnet and I still don’t thinking a yearlong attack on the RSA key is going to be successful (although the authors of the Storm Worm have been very resourceful).

This is a PR stunt or something more suspicious is going on.

In the case of corporate secrets being ransomed by this malware, buy data recovery tools immediately. I garuntee the virus authors haven’t securely wiped the data from the disk.

Also, if the authors have RC4’ed the files and transferred the “randomly” (how much do you want to bet they just “srand(time(0))”ed) chosen symmetric keys after encrypting them with a public key, how would this help those already victimized? Unless we have copies of the encrypted symmetric keys, the millions of dollars put into cracking this beast has been wasted.

It's All Just Randomness • June 17, 2008 2:19 PM

This will probably be at least as effective as SETI@home, which has spent zillions of CPU hours and hasn’t found jack.

Kick10 • June 23, 2008 4:00 PM

I’ve recently reversed gpcode.ak binary EXE and found that encryption scheme was the following:

  1. Virus imports an open RSA key from its EXE by a call to CryptImportKey(using Microsoft Enhanced Cryptographic Provider library).
  2. Then it generates first RC4 key, i’ll name it RC4key_1.
  3. Then virus exports generated RC4key_1 with CryptExportKey api using previously imported open RSA key(RC4key_1 is being crypted by that open RSA key) and after that it writes the exported key to readme.txt file with bad news, then imported RSA key is being destroyed by CryptDestroyKey.
  4. After that virus searches hdd for files to encrypt and acts as following:
    4.1 Generates a sequence of 16 pseudo-random bytes(taken from system timer), i’ll name it RND;
    4.2 Those 16 bytes are then crypted by RC4 algo using RC4_key1.
    4.3 Crypted with RC4 RND sequence is then hashed by SHA1 hash-function.
    4.4 A second RC4 key(I’ll name it RC4_key2) is being generated using CryptDeriveKey api, the computed SHA1 hash of RND is used as base data to derive key. After key is derived, hash is destroyed immediately.
    4.5 The victim file is being crypted by RC4 algorithm using derived RC4_key2, then virus writes 16 bytes of RND to the resulting file followed by encrypted file content. Resulting file has _CRYPT extension, original file is then being deleted using DeleteFile api call.
    4.6 RC4_key2 is being destroyed.
    4.7 Steps 4.1-4.5 are repeated for every file to be crypted.

So the problem is to obtain RC4_key1, so we can use it to crypt “RND”, stored in every file using RC4, hash it with SHA1, derive the decryption key and save the world.

Now its time for cryptoanalysts to say their word…

Vitaly Kamluk • June 26, 2008 11:28 AM

Dear Mr Schneier,
My name is Vitaly Kamluk. I am a senior virus analyst from Kaspersky Lab. I was the one who found the first sample of Gpcode virus that uses RSA-1024 encryption.

First of all, let me apologize for the situation that happened. To be honest I admire people like you very much. I have been present at your speech “The Psychology of Security” at BlackHat in Las Vegas last year, and I was deeply impressed by the level of knowledge that you posses. To my concern, people who come to the questions of psychology and probably metaphysics in science are real experts in their areas. Anyone has to pass a long long way to reach this point and be able to speak about that without foolish speculations.

To be honest, when we discovered RSA-1024 in Gpcode virus, I thought of contacting you. But then something stopped me. Perhaps I am too modest and that let me think that the problem of single virus is not worth of such professional as you are.

I know that area of our expertise does not fully cover cryptography and that is why public request for help looked rather reasonable.

The facts are that lots of users all round the world got infected and we cannot help them. If that was a virus that totally destroyed user’s data we could answer: “we are sorry but nothing can be done”. Today users see their files in the folders and they have a chance to get them back if them pay the criminal. An unfortunately they do. It’s not worth of explanation how it stimulates the viruswriter.

We have been informed about hospital being infected with the virus and something hurt me inside for this state of being helpless. I tried to work hard, to work days and nights to find a solution. I should inform you that I was lucky enough and my search was not totally fruitless. I have offered affordable method of restoring files deleted by the virus. We have announced that in blogpost:
http://www.viruslist.com/en/weblog?weblogid=208187531
and also included tutorial in virus description:
http://www.viruslist.com/en/viruses/encyclopedia?virusid=313444#doc2

But that’s a poor solution and I believe it will not help in new versions of the virus.

After that I switched to reverse engineering approach and we were lucky enough to find a flaw in scheme that was used by the virus. This flaw allowed us to restore about 80% of encrypted files in the lab (the conditions were virtually ideal). In real world this conditions are not common so I believe that the real percentage of decrypted files will be much lower (to my concern less than 50%).

You are the first one who I informed about that, because I have seen your interest in the case of Gpcode virus by reading your critical comments on your blog. Here is our official announcement:
http://www.viruslist.com/en/weblog?weblogid=208187538
Full description and link for the tool can be found here (Chapter “Decrypting files using StopGpcode2”):
http://www.viruslist.com/en/viruses/encyclopedia?virusid=313444

I think that we will NOT disclose the idea of the flaw to public audience to delay the viruswriter on reversing and learning from his mistakes and improving the algorithm afterwards. And that is why I am asking every researcher who reads these lines and has already reversed or is going to reverse our solution: please, do not publish internals of the tool and do not discuss it publicly. I hope for your understanding and believe that intelligent people like you will not help evil.

We know that virus will return and there will be followers. That is why, Bruce, if I am allowed to speak here, I would like to offer you join us in this battle, because I strongly believe that it SHOULD NOT be a battle for the benefit of a single company, but it SHOULD be the battle for the sake of humankind.

Kind regards,
Vitaly Kamluk

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.