Decrypting ransomware “for free” (sort of)

Everyone loves a feel-good cybersecurity story, and a recent ransomware recovery write-up out of Thailand made the news for just that reason.

A cybersecurity coder named Yohanes Nugroho was recently approached by the victim of an Akira ransomware variant.

The desperate victim was keen to know if Yohanes could hack together a decryptor, presumably in the hope that it would be cheaper than paying the criminals involved, as well as putting the recovery money into the hands of a legitimate programmer instead of paying extortion money to a wasps’ nest of odious crooks.

As Yohanes wryly remarked, “I usually decline requests to assist with ransomware cases. However, when my friend showed me this particular case, a quick check made me think it was solvable.”

So he decided to have a try, though he pertinently quoted the satirical Programmers’ Credo, a well-known parody of JFK’s famous remark about choosing to go to the moon: “We do this not because it is easy, but because we thought it would be easy.”

His goal was more tightly focused than a typical ransomware recovery of thousands of files across hundreds of laptops, namely to recover a small number of critical VMDKs (VMWare virtual machine disk files) on ransomware-scrambled servers.

Don’t be complacent about malware just because you’re not running Windows. Cybercriminals may not churn out as much malware for macOS and Linux, but the attack tools they do create for those platforms can be just as devastating as their Windows counterparts.

The cryptographic challenge

Greatly simplified, Yohanes discovered that the ransomware he was looking at:

• Used the stream cipher KCipher-2 for the first 64KB of the file, and regular 64KB chunks thereafter.
• Used the stream cipher ChaCha8 for other parts of file in chunks of variable size.
• Generated four random numbers to provide two keys and two initialization vectors (IVs) for each cipher for each file.
• Encrypted those random decryption keys with an RSA-4096 bit public key, and appended the result to each encrypted file.

In other words, there were three possible ways to attack the problem, given that none of the cryptographic algorithms involved have any known, exploitable weaknesses:

• Directly crack the RSA-4096 key to recover the private key, thus allowing all file-specific decryption keys in this attack to be recovered. (Much too hard.)
• Directly crack the KCipher-2 and ChaCha8 keys for each individual file. (Much too hard.)
• Crack the random generation process for each file to open a chink of light that might reduce the number of possible keys to try for each file.

The third of these seemed at least vaguely possible, given that the crooks had made a modest blunder, namely using the current Unix timestamp in nanoseconds as a random number seed, instead of using a strong pseudorandom number from the operating system itself.

The scale of the challenge

KCipher-2 keys are 128 bits long, so there are in theory 2¹²⁸ keys to try for each file.

ChaCha8 keys are 256 bits long, which is a yet more intractable problem to solve, with 2²⁵⁶ possible keys for each file.

Nanosecond timestamps are 128 bits log, returned as two 64-bit integers, one for the number of seconds since 1970-01-01T00:00:00Z, and the other for the number of nanoseconds since the start of the current second.

But if you can guess when each file was encrypted, you don’t have to try every second since 1970, and if you can guess within a second (which is sometimes possible), you get the first 64 bits of the timestamp “for free.”

And there are “only” 1 billion nanoseconds in a second, so you only have to try 2³⁰ different values, instead of 2⁶⁴ values, for the second 64 bits of the timestamp.

(Depending on your system, you might also find that not all 1 billion possible nanosecond values are generated by the system time counter, which may be rounded off to a lower precision.)

Woo hoo! Sounds easy!

But it still wasn’t easy at all, because each of the encryption systems needs two random values, key and IV, so even handling just the first 64KB of the file, which means finding the key-and-IV combination for the KCipher-2 decryptor, requires guessing two timestamps.

Although they’re generated in quick succession, system load and calculation time (the timestamp seed is put through the SHA-256 algorithm 1500 times to mix it up unpredictably) cause the elapsed time between the two timestamps to vary widely.

indeed, Yohanes found that the second seed generation started anywhere from about 1 millisecond to 5 milliseconds after the first, giving 4 milliseconds of variability.

So, for every possible 1 billion nanosecond values that the first seed could have, there were at least 4 million possible values for the other, because there are an astonishing 4 million nanoseconds in a 4-millisecond blink of the eye.

In other words, for each of the approximately 2³⁰ (close to 1 billion) different possible nanosecond values to try for the key, there were also 2²⁰ (close to 1 million) × 4 values to try for the IV to go with it.

That’s a whopping 2³⁰ × 4 × 2²⁰ = 2⁵² combinations (about 4 quadrillion) of random seeds.

For each seed pair, you need to perform two loops of of 1500 SHA-256 hash calculations, one for the key and one for the IV, followed by at least one cycle of the KCipher-2 stream cipher to see whether you get anything sensible out of the decryption to signal that you found the right key-and-IV pair.

(In case you’re wondering, KCipher-2 generates 64 bits of key material in each cycle, so it’s as much work to decrypt eight bytes as it is to decrypt one.)

As well as this, you need to have a good idea what the first eight bytes of the file are supposed to look like – a so-called known plaintext – so you can spot when you hit the jackpot.

Fortunately, that’s not as hard as it sounds, because many file types start with special “magic numbers” specifically to help you can recognize them quickly when you see them.

Mounting expenses

Suddenly, the “free decryptor” was becoming expensive.

Yohanes’s work did pay off for this victim, because they had comparative few VMDK files (virtual server images) to decrypt on comparatively few servers.

But even reducing the complexity of the key-and-IV brute-forcing job from 2¹²⁸ × 2¹²⁸ tries to 2⁵² tries, and even rewriting the code to try all those keys and IVs in parallel on high-powered GPUs (graphics cards, renowned for their hash-busting and cryptocracking speeds), he faced a cloud service cost of about $120 to decrypt one second’s worth of encrypted files, and still needed about 10 days of cracking time to get the job done.

If you had 100 files to decrypt that had taken a total of 10 seconds for the ransomware to encrypt, you’d need 10 seconds’ worth of key-and-IV cracking effort, costing $1200, which is how much Yohanes spent in the end, including experimentation and testing time.

If you wanted the answer within a single day instead of 10 days, the cloud service costs would multiply tenfold again to $12,000.

Make that 10,000 files across 100 different laptops, scrambled over a period of several minutes to an hour (about 100 seconds to more than 3000 seconds), Yohanes’s approach could add anywhere from $100,000 to $1,000,000 to your recovery costs, and that’s for a ransomware sample with a weakness in its random number generation.

What to do?

Most ransomware scramblers don’t have any exploitable holes in their encryption, and even those that are crackable in theory – like this one – may take too long, or just be too expensive, to tackle in real life.

Cybersecurity is too important to be left to chance:

• Prevention is better than cure. Sign up with SolCyber for proactive threat detection and prevention so you don’t have to try to build a 24/7 SOC of your own.
• Build a strong, human-centric security culture. This means cybercriminality of any sort is more likely to be spotted and reported. Signing up with SolCyber will actively help you to do this.
• Backup is always better than brute force. You need a backup anyway, for general business continuity reasons, and the same backup that will save you from fires, floods, thefts and more will protect you from ransomware, too.

Learn more about our mobile security solution that goes beyond traditional MDM (mobile device management) software, and offers active on-device protection that’s more like the EDR (endpoint detection and response) tools you are used to on laptops, desktops and servers:

More About Duck

Paul Ducklin is a respected expert with more than 30 years of experience as a programmer, reverser, researcher and educator in the cybersecurity industry. Duck, as he is known, is also a globally respected writer, presenter and podcaster with an unmatched knack for explaining even the most complex technical issues in plain English. Read, learn, enjoy!

Featured image of Captain Midnight Secret Decoder Rinf by Sobebunny under the CC BY-SA 3.0 license.