Interesting Approach by the Profiteering Malware Author

[Ehtyar]

It appears malware authors are getting more and more innovative in their approach to profiting from their activities. Kaspersky Labs have recently come across a new variant of the "Gpcode" virus. This little bastard first encrypts various file formats it finds on your computer, then drops a vbs file which deletes the primary executable, and subsequently recommends you email the author with a unique ID that will allow him to decrypt your files, a service for which you will be charged a sum at his/her whim.
For the previous 7 variants, the author has used RC4 to encrypt the files, and then encrypted the RC4 key with variable bit length RSA. The latest variant has moved up to using 1024 bit RSA, and now uses various emails to facilitate extortion of payment.
This virus seems to be proliferating at such an alarming rate that Kaspersky have taken the unprecedented step of asking the public for help in determining how best to combat this virus, and are even asking for suggestions on how to approach factorization of the keys. Providing that a fundamental weakness is not present in any aspect of implementation, the keys are, practically speaking, unbreakable.
I suppose it just goes to show that that mind of a good programmer is always seeking more efficient ways of achieving its goal.
More info here, here, and here.

Ehtyar.

[edit]
Added some extra info
[/edit]

[Renegade]

I don't think this is a new attack style. I remember a number of years ago hearing about "ransomware", which is the same as described above. It would lock things up, then demand a ransom for it.

The first example of it (from the Wikipedia article above) was from 1989.

The issue now is probably the number of infections is just higher. <cynicism>Oh, and that it makes for a great news story to plug your antivirus product.</cynicism>

 

[f0dder]

It's definitely not new, Renegade, and Ethyar does mention that there's 7 previous variants - I think it's some years since I heard about this particular malware last. But using 1024-bit RSA, hmm... that's "pretty hard" to factor. The best bet would probably be catching the malware while it's doing it's nasty crap, and doing a process memory dump to extract the keys.

That, or find out how to link the "unique ID" with the key. But that probably involves tracking down the author, checking his source code, and putting a bullet or two in his stomach.

[scancode]

Rubber hose cryptanalisys! 

[40hz]

Why am I suddenly in support of waterboarding? 

[Carol Haynes]

Can't the money trail be traced if people are paying?

Solution - backup up regularly and tell him to go f*** himself.

[Darwin]

Why am I suddenly in support of waterboarding? 

-40hz (June 11, 2008, 10:13 AM)

As Carol says, backup, backup, backup... To combat this sort of instanity, I suppose this means that disk imaging is the best way to go.

[nosh]

I'm sure the description of the malware that hit the DC server said it did something very similar. Apparently there weren't any casualties but if these clowns could generate effective code maybe they would have got a _real_ job?

[Darwin]

if these clowns could generate effective code maybe they would have got a _real_ job

-nosh (June 11, 2008, 11:01 AM)

  Very true. Still, it never hurts to OVERestimate your enemy.

[CWuestefeld]

<cynicism>Oh, and that it makes for a great news story to plug your antivirus product.</cynicism>

-Renegade (June 11, 2008, 09:31 AM)

I'm a Kaspersky fan, but I have to agree. It seems that cracking the key is impractical, and even if it weren't, it is trivial for the bad guy to release a new version using a new key, so this approach won't work. And why is it so difficult to catch the key with a debugger, as f0dder suggested?

[Carol Haynes]

It hardly plugs their AV product if they are appealing to the public for help to solve the problem 

[mwb1100]

The best bet would probably be catching the malware while it's doing it's nasty crap, and doing a process memory dump to extract the keys.

That, or find out how to link the "unique ID" with the key.

-f0dder (June 11, 2008, 09:34 AM)

I'd guess that the "unique ID" is the RC4 encryption key that has itself been encrypted with the RSA public key.  I'd also guess that the RC4 key is a randomly generated value that gets created right before the encryption of your data files.  If you're able to "catch" the malware at this point, it's probably best to simply stop it rather than extract the keys.

One key to solving this problem (pardon the pun) for people who get hit with finding their data files encrypted is if there's a vulnerability in the RC4 key generation process - if that's the case it may be possible to recreate those keys without the help of the extortionist.  For example, if the malware author makes a mistake similar to the flaw found not too long ago for SSH key generation on Debian distributions, recovering the data would be pretty easy.  But that's a big "if".

[Ehtyar]

In all fairness, I daresay cryptanalysis of RC4 as opposed to trying to factor 1024 bit RSA would yield far better results. RC4 is incredibly weak by comparison. Also, apologies for making the virus sound as though it were new, it was not my intention. As f0dder indicated, i did mention the seven previous variants at least.

Ehtyar.

[edit]

And why is it so difficult to catch the key with a debugger, as f0dder suggested?

-CWuestefeld (June 11, 2008, 11:32 AM)

I believe this indicates why this won't work, though it's far from an effective explanation. How the author can decrypt files protected by a randomly generated RSA private key I am unsure. Perhaps it is not his/her intention to ever provide the decrypter?

P.S. I do not use Kaspersky AV.
[/edit]

[mwb1100]

How the author can decrypt files protected by a randomly generated RSA private key I am unsure. Perhaps it is not his/her intention to ever provide the decrypter?

-Ehtyar (June 11, 2008, 03:52 PM)

Note: In the following, I'm speaking about how the malware works based on what I believe to be the case from very sketchy information - I could be missing the boat entirely...

The RSA key is not randomly generated - the RC4 key is.  Then that key is encrypted using the RSA public key.  At this point only a person who holds the corresponding RSA private key can recover the RC4 key.

The approach that Kaspersky seems to be advocating is trying to organize a distributed network of computers (similar to SETI@home) to brute force the RSA private key.

[Carol Haynes]

They will need a net as big as SETI if the virus proliferates! Guess what - that net would be the next target!

[jgpaiva]

Yeah, if someone "evil" got control of such network, much more interesting rsa keys would be broken, that's for sure.

[Ehtyar]

The RSA key is not randomly generated - the RC4 key is.  Then that key is encrypted using the RSA public key.  At this point only a person who holds the corresponding RSA private key can recover the RC4 key.

-mwb1100 (June 11, 2008, 04:38 PM)

Oh I see, so the "ID" they email the author is the encrypted RC4 key...duh *headsmack*. Which again begs the question, why is Kaspersky going after the RSA key instead of the RC4 key? Seems very misguided.

Ehtyar.

[mwb1100]

why is Kaspersky going after the RSA key instead of the RC4 key?

-Ehtyar (June 11, 2008, 05:07 PM)

Because the RC4 key applies to only a single instance of the infection.  If the RSA key is broken (actually it appears that there are 2 RSA keys - which one is used depends on the OS version of the machine that is infected) it will allow the recovery of any infection.

Now, if there's a flaw in how the RC4 key is generated (or in how the RC4 algorithm is implemented) then there might be another approach to recovering from the damage inflicted.  But I have no idea how likely that scenario is.

[Ehtyar]

why is Kaspersky going after the RSA key instead of the RC4 key?

-Ehtyar (June 11, 2008, 05:07 PM)

Because the RC4 key applies to only a single instance of the infection.  If the RSA key is broken (actually it appears that there are 2 RSA keys - which one is used depends on the OS version of the machine that is infected) it will allow the recovery of any infection.

-mwb1100 (June 11, 2008, 05:23 PM)

And yet what are the chances of factoring the RSA key as opposed to cracking the RC4 key? Seems like they're all talk...at least for the moment. I believe the two RSA keys are a product of the lack of an "enhanced" cryptography provider in earlier versions of windows.

Ehtyar.

[edit]
It would also be interesting to determine the length of the generated RC4 key, might even be practically brute-forceable, certainly more-so then the RSA key.
[/edit]

[f0dder]

Problem is, Ehtyar, how would you go about attacking the RC4 key? Unless there's a serious flaw in the PRNG used for generating the random RC4 key (like, using srand(time(0))), what would you do? I know there's some cryptographic problems with RC4 itself, but haven't read up on just how it affects it. Even with reduced complexity attacks, you still need some way of detecting if you've found the right key - unless you have a md5sum of at least one original file, how are you going to do this detection without manually looking at each "attempted decrypt"?

I'd guess that the "unique ID" is the RC4 encryption key that has itself been encrypted with the RSA public key.  I'd also guess that the RC4 key is a randomly generated value that gets created right before the encryption of your data files.  If you're able to "catch" the malware at this point, it's probably best to simply stop it rather than extract the keys.

-mwb1100 (June 11, 2008, 02:17 PM)

That's my guess as well. But just stopping the malware might not be enough - what if you realize it's active only after it's encrypted, say, 100 of your files?

Now, factoring RSA-1024... I wonder just how feasible that is, even with a SETI or Folding@Home size grid. Probably more realistic to track down the bastard.

[Ehtyar]

Now, factoring RSA-1024... I wonder just how feasible that is, even with a SETI or Folding@Home size grid. Probably more realistic to track down the bastard.

-f0dder (June 11, 2008, 05:52 PM)

It seems to me that, provided the arsehole isn't using an open proxy, or TOR etc., the assistance of his email providers, or his credit card processors etc. in this case could quite easily lead to his eventual identification.

On another note, after further googling it appears that Gpcode is generating what KL are calling a "master" key when it begins its work, then modifying the key for each file it encrypts, using some unique aspect of the file itself (its creation time, file name etc) thereby making the approach toward cracking the RC4 that much more complicated. KL are keeping extraordinarily tight-lipped about this process for an organisation claiming to want to put an end to this outbreak. Hypothetically, if KL were to release this kind of information, both the Fluhrer, Mantin & Shamir, and the Klein attack could be quite successful in breaking the encryption, provided the author had not defended against one or the other and that the key length was sufficiently small.

Ehtyar.

[edit]
Is he using the Microsoft cryptography provider for the RC4, or just the RSA i wonder. The Microsoft cryptography documentation does not supply information regarding defense against known attacks, so one can most likely safely assume it is not protected against either of the attacks listed above. Though if the author were to be using 3rd party code for the RC4, then he would be free to introduce any modification to the algorithm he wanted.
[/edit]

[mwb1100]

Probably more realistic to track down the bastard.

-f0dder (June 11, 2008, 05:52 PM)

Why am I suddenly in support of waterboarding? 

-40hz (June 11, 2008, 10:13 AM)

Rubber hose cryptanalisys! 

-scancode (June 11, 2008, 09:41 AM)

Maybe if the FBI or some other 'three letter agency' were to get infected...  I think this scheme would be 'broken' in short order.

[Ehtyar]

Maybe if the FBI or some other 'three letter agency' were to get infected...  I think this scheme would be 'broken' in short order.

-mwb1100 (June 11, 2008, 06:51 PM)

The RC4 perhaps, but from a conspiracy theorist's point of view, were the government capable of breaking 1024 bit RSA in short order, it would be in their best interests, regardless of whatever information was encrypted, to keep that fact a secret. The entire cryptography community could collapse into total mayhem were this sort of information to get out.

Ehtyar.

[edit]
At the risk of starting a flame war, why don't we all just forget about breaking the crypto and simply follow Symantec's excellent "removal" instructions
[/edit]

[f0dder]

Ehtyar: not only the cryptography community... I don't even dare think about the consequences of anybody being able to factor 1024-bit RSA in realistic time.

[mwb1100]

Maybe if the FBI or some other 'three letter agency' were to get infected...  I think this scheme would be 'broken' in short order.

-mwb1100 (June 11, 2008, 06:51 PM)

The RC4 perhaps, but from a conspiracy theorist's point of view, were the government capable of breaking 1024 bit RSA in short order, it would be in their best interests, regardless of whatever information was encrypted, to keep that fact a secret.

-Ehtyar (June 11, 2008, 06:59 PM)

I meant more from the point of view of being able to track down the blackmailer and using old fashioned methods of getting the key.