Thinking Out Loud: A Cold Night For Cryptoviral Extortion

by Justin Troutman

Quite a few months have passed since my last post, as cryptography-related endeavors, and family matters, most importantly, have occupied about all of my time that's available for occupying. As far as cryptovirology research is concerned, results are coming together, and what began as a single paper a couple of years ago, has branched off into separate avenues of design philosophy. One particular branch deals with the development of a cryptovirus that is efficiency-oriented, with an emphasis on speed and reasonable security trade-offs. The original cryptoviral information extortion attack, by Dr. Adam L. Young and Dr. Moti M. Yung, was built on public-key cryptography and an on-board random number generator, with the latter proving to be the bottleneck, responsible for consuming over half of the time the attack takes (i.e., roughly 11 seconds). A couple of years ago, I looked into stripping these two components and playing around with different security trade-offs. Roughly speaking, what I ended up with is a structure that uses a symmetric block cipher and block cipher-based MAC, to satisfy confidentiality and integrity requirements, while sending the keys in - yes, you're reading correctly - plaintext.

The reasoning behind this is practical. The cryptovirus needs a carrier. All that is necessary is for the carrier to drop the cryptovirus onto the host, and for the cryptovirus to perform its operations. If the carrier is fast and discreet enough in getting the cryptovirus to the host, this should compensate for the plaintext keys that are riding shotgun with the cryptovirus. We've ditched asymmetric cryptography, and already regain over half of the attack's operational time, by generating key material beforehand, so we're already looking at an attack that takes less than half the time of the original. By using fast implementations of AES, we can achieve a completely standardized approach, complete with tight security bounds. As of now, I've chosen AES in CTR mode, which is IND-CPA secure, as well as CMAC-AES, which is a SUF-CMA MAC; if used in the Encrypt-then-Authenticate composition, this renders IND-CCA2 security and achieves INT-CTXT, for some constructions of this attack. The key to understanding all of these acronyms will grace the end of this post. The important thing to know here is that I've just described the basic setup for a cryptovirus that is just as stout as any good, defensive system that uses the same cryptography.

For those who aren't familiar with the idea of a cryptoviral information extortion attack, here's how it goes. We have an adversary and victim. The adversary desires some resource that the victim has; we'll call this "H." (I'm following the naming convention of the original attack by Dr. Adam L. Young and Dr. Moti M. Yung.) To get this resource, he'll need some leverage, so he designs the cryptovirus to look for some critical data on the host victim; we'll call this, "D." When the cryptovirus finds D, it encrypts it, using AES in CTR mode, overwriting the original. When it finds H, it computes a MAC on it, using CMAC-AES. (This implies that the cryptovirus houses two symmetric keys: one for encryption and one for authentication.) At this point, both keys have been overwritten in RAM, and the cryptovirus instructs the victim to send H, along with the corresponding MAC, to the adversary. Upon receiving this from the victim, the adversary will compute a MAC on H using the authentication key (remember, the keys are precomputed, so he has a copy) and CMAC-AES. If the MAC he computes matches the MAC that accompanied H, then H is valid. Otherwise, the victim tried to send some bogus substitute, H'. Because the victim hasn't any knowledge of the authentication key, he can't compute a valid MAC on a bogus file to send in place of H.

Theoretically, if the victim cooperates, the adversary sends the encryption key used to encrypt D, such that the victim can decrypt it, thus restoring the critical data. The problem here is that the trust model is based on a relationship between a victim and adversary. Traditionally, we look at channels between Alice and Bob, where trust is implied. However, there is no balance of trust between a victim and adversary. I've addressed this issue, theoretically, with an arbitrated, game-theoretic protocol (i.e., a trusted third party, who treats the exchange, between the victim and adversary, in terms of a non-zero-sum or zero-sum game.) I'll leave this for another rainy day, though. Now that you have the contextual gist of the attack, I'll pose my questions.

For those of you in charge of policies for handling adversarial attacks, how would you go about handling a cryptoviral information extortion attack? The obvious defense is a good back-up, of course. However, it seems plausible that with enough a priori information of the system (i.e., insider attack), a cryptovirus could be tailored to attack prior to a scheduled back-up. For information that is archived in relatively short time intervals, perhaps the cryptovirus' fast execution time can increase the viability of this tailored approach. After all, we're looking at seconds.

Some might be quick to respond, "You should just ignore the adversary and never give him what he wants." Failed attempts at cryptoviral information extortion attacks have been reported, where the "H" that the adversary demands is in the form of a monetary payment. If this demand will cost more than the data, being held for ransom, is worth, then sure, that's a good argument for ignoring it. However, what about when this isn't the case, and it'd be worth it to pay the ransom? Others might retort, "But what if the adversary doesn't follow through with his end of the bargain?" Theoretically, it's in the best interest of the adversary to play fairly. Keep in mind that attacks are often reported and publicized. If the media reports reflect the adversary as someone who never pays up, future victims are less likely to take the risk. However, if the reports reflect an adversary who always holds up his end of the bargain, future victims may give in, if statistics show them that there's a promise of hope in recovering their data. Again, this is just one theory.

Oh, and here's some alleviation from the acronym jungle you had to venture through, to get to this point:

  • AES = Advanced Encryption Standard (I know, I know; y'all probably know this one.)

  • MAC = Message Authentication Code

  • CTR = Counter Mode

  • CMAC = Cipher-based Message Authentication Code

  • IND-CPA = Indistinguishability under Chosen-Plaintext Attack

  • IND-CCA2 = Indistinguishability under Adaptive Chosen-Ciphertext Attack

  • INT-CTXT = Integrity of Ciphertexts

  • SUF-CMA = Strong Unforgeability under Chosen-Message Attack


If you want a friendlier treatment of introductory cryptoviral extortion, that even a kid might enjoy reading, I've written some things about it here. Pardon all the thinking-out-loud, but now that I've laid out the fundamental context, it'll be much easier to get to the point with future research. Until then, have a good one and stay warm, if it's winter where you are. It's downright cold, here in the South, tonight. Almost 10 degrees. Here's hoping that this research is as fruitful as my fireplace is toasty.

1 Comments

Josh Peters
2006-12-09 10:36:01
Since we're speaking of a machine accessible (in some way) to an internet the possibility of off-site backups exists. The addition of off-site backups would deter an attacker in that a recovery from a previous day eliminate the virus. Proper usage of backup technology _should_ offer a significant level of deterrent since the attacker would then have to consider all of the mechanisms used by the victim's system.


Of course as far as deterrents go backups are a poor one. If I am taking the time to craft a cryptovirus to attack a single network or single machine I would hopefully have the information of how their backup system works.


The best deterrent would likely be the threat of response with your own cryptovirus, but as the world learned from the cold war those sorts of arms build-ups can be very costly.