Using World War II techniques to fight ransomware

The best way to fight crypto-ransomware is to have backups. But what if you make backups once a month, but want to decrypt all of the new or modified files? Is it possible? Sometimes...

Recently, I had a lot of encounters with cryptography. Additionally, this year marks the 70th anniversary of the end of the Second World War. Rather unusually, this two facts combined can help us fight ransomware. We will also learn something about different kinds of ciphers and their weaknesses.

Some versions of the crypto-ransomware use streaming cipher (usually RC4) to encrypt the files found on the victim's machine. However, they make a serious mistake that would get them in trouble if they were working in the Nazi's communication department. But first, let me tell you something about the idea behind the streaming ciphers.

Most symmetric streaming ciphers are using on the same idea. Based on the password provided by the user, encryption/decryption algorithm creates a keystream. It is a constant, pseudo-randomly generated stream of characters that will be used to encrypt the file. Next, that keystream is combined with the plaintext using the XOR operation. This operation has one very interesting property - it is self-inverting, which means that for every byte (or bit) x XOR x will be equal to zero. And zero is a neutral element of the XOR operation. 

After all of this math talk, have a look at the example. P1, P2, ..., Pn is a plaintext, C1, C2, ..., Cn is the ciphertext and K1, K2, ..., Kn is the keystream.

P1 XOR K1 = C1
P2 XOR K2 = C2
...
Pn XOR Kn = Cn

Now, because x XOR x = 0 and x XOR 0 = x you can see that the following is true:

P1 = P1 XOR K1 XOR K1 = C1 XOR K1
P2 = P2 XOR K2 XOR K2 = C2 XOR K2
...
Pn = Pn XOR Kn XOR Kn = Cn XOR Kn

So, if we XOR the ciphertext with the keystream, we receive a plaintext. However, there is also one other interesting property, which is shown below:

P1 XOR C1 = P1 XOR (P1 XOR K1) = K1
P2 XOR C2 = P2 XOR (P2 XOR K2) = K2
...
Pn XOR Cn = Pn XOR (Pn XOR Kn) = Kn

But, if you know both the plaintext and the ciphertext, you can easily recreate a keystream. What is more, if you use the same keystream twice to encrypt two plaintexts P and P', we get:

C1 XOR C'1 = (P1 XOR K1) XOR (P'1 XOR K1) = P1 XOR P'1
C2 XOR C'2 = (P2 XOR K2) XOR (P'2 XOR K2) = P2 XOR P'2
...
Cn XOR C'n = (Pn XOR Kn) XOR (P'n XOR Kn) = Pn XOR P'n

OK, but what does it have to do with the World War II? Well, Nazis used a streaming cipher to encode some of the messages. Operators where ordered NOT to use the same keystream twice, because if the allies knew one of the messages (P) they could easily recreate the second one, because it's simply C XOR C' XOR P. Of course, some of the operators did disobey this order.

Some of the ransomware samples also did not obey this order. So, if ransomware encrypts every file with the same password and uses e.g. RC4, you can take one of the files in your backup, XOR it with the encrypted version and you'll have a keystream. With this keystream, you can decrypt all other files. Including the ones that were not present in your original backup.

What if you don't have any backup to work with? You could still take some of the original Windows files (e.g. wallpapers, sample pictures etc.) and XOR them with the encrypted version and get the keystream that will allow you to decrypt all other files.

Of course, this is not a method that can be used always or for every ransomware. But it works. Trust me.

P.S. This is the Computerphile video that inspired this post: https://www.youtube.com/watch?v=yxx3Bkmv3ck.

Comments

Popular posts from this blog

Having fun with AndroidManifest.xml

Android malware based on SMS encryption and with KitKat support

Android malware goes Mono (.NET) and Lua!