by Mark Rasch
Original Publish Date: February 11, 2020 - TLP RED
Revision Publish Date: November 15, 2022 - TLP WHITE
First off, we personally owe a huge shout-out to Cylance, for their analysis of a Zeppelin variant that was observed in December 2019. During our analysis of the report, we realized that there were a few flaws within the architecture of Zeppelin that would open an opportunity for recovery. What motivated us the most during the leadup to our action was the targeting of homeless shelters, nonprofits and charity organizations. These senseless acts of targeting those who are unable to respond are the motivation for this research, analysis, tools, and blog post. A general Unit 221B rule of thumb around our offices is: Don’t [REDACTED] with the homeless or sick! It will simply trigger our ADHD and we will get into that hyper-focus mode that is good if you’re a good guy, but not so great if you are an ***hole.
TL;DR CATCHUP ON ZEPPELIN
Zeppelin is a Russian ransomware written in Delphi that is a successor to the Buran family of Ransomware (considered an evolutionary successor to VegaLocker, and others that predate it). The reports we’ve read about the ransomware’s existence and mechanics postulate that Buran was considered slow by its customers. Now that even small organizations have relatively large quantities of data, we ironically see that performance has become a primary concern for malware – including Ransomware. This is to our advantage, which we will discuss in this blog post.
Zeppelin has a few unique technical features in the way that it operates. Let’s start with how it encrypts files from a cryptography perspective. The core encryption algorithms Zeppelin uses are 256-bit keys for ‘alleged‘ RC4 (ARC4), a stream cipher, AES-CBC-256, a 128-bit block, 256-bit key cipher in Cipher-Block-Chaining mode with a 16-byte IV (initialization vector). And finally, RSA, a popular asymmetric (public/private key) cryptosystem commonly used to facilitate the exchange of symmetric cryptographic keys.
Once Zeppelin finishes encrypting the files, it deletes all public keys it uses from the system. The executable itself is also removed to further hamper detection efforts. We found the main point of entry in the cases that we reviewed RDP. The use of RDP is prevalent at IT service companies, which can be exploited to hijack their clients en masse to bring in profits at scale. The average Ransom request is about $50,000 USD to get your files back. It leaves a lovely little message as a text file on your system right before the executable exits stage ‘that ain’t right!’:
!!! NOW YOU GET THE JOKE OF OUR BLOG SUBTITLE !!!
For speed, AES-256-CBC is used to encrypt each file. Each file has its own key hidden within the footer of the file that it encrypts. And when we say hidden, we mean encrypted with an ephemeral RSA-512 public key that is randomly generated on the machine it’s infecting. The Personal ID they assign you in the ransom note is the first 11 hexadecimal digits of this public key with “-” replacing the 4th and 8th digit.
Once encrypted, the ephemeral RSA-512 private key is then encrypted with a static RSA-2048 public key that is bound to the malware. All malware strains of Zeppelin we analyzed have this same exact key. Within all this mess, RC4 (32-byte key) was used for obfuscation, and we definitely wasted a few cycles chasing this red herring.
If you haven’t noticed the actual vulnerability within Zeppelin in the last two paragraphs, you will now as we visually analyze the encryption flow (we had to do this originally for ourselves to make sure we weren’t going crazy and just hoping we saw a vulnerability).
Our Next Step is to get that 512-bit RSA Public Key Recovered! Whee!
RSA-155 PUBLIC KEY NOT VERY PUBLIC
So where are we? Oh yeah. After analyzing the encryption flow, the theory we had was: “If we can recover the RSA-512 Public Key from the registry, we can crack it and get the 256-bit AES Key that encrypts the files! The challenge was that they delete the ‘HKCU\Software\Zeppelin\Public Key‘ once the files are fully encrypted. Memory analysis gave us about a 5-minute window after files were encrypted to retrieve this public key.
Registry Analysis – DFIR Style!
This section is important for performing incident response on environments that suffer a Zeppelin Ransomware attack. We advise starting with a memory dump (playing the odds) of the machines that are infected and an image of the partitions affected. You can’t analyze the registry live on a windows machine because it locks the NTUSER.dat files by the process id (PID) 104 known as Registry.exe. Any useful registry information will be found in that process, and we recommend getting a memory and VAD dump of the Registry.exe process as soon as possible. You can do this quite easily with the REKALL tool, which can perform live and dead memory analysis on Windows machines. And yes, we also love the fact that it quotes the Total Recall movie every time you quit the tool.
Alright, after memory and images are taken, it’s time to have some fun. Since Zeppelin deletes the registry key store, we will have to extract unallocated cells from the registry to recover the Public Key section. We use a combination of code and existing tools such as yarp and regipy to carve registry information from the hard drive, memory, registry backup, and transaction files. We also need to recover the deleted data. The most successful process used yarp-carve and yarp-print with the -deleted flag against NTUSER.DAT files, which are compressed. It is wise to do registry carving on the raw file system, the registry.exe memory dumps, and directly on the NTUSER.Dat in the /User/[user_account]/ directory of whoever’s account the Zeppelin executable was… executed from.
We have had 100% success carving the public key from NTUser.dat for live Zeppelin samples in the field, which will look like this when successful:
The output of this may vary, but the section that says Public Key… we want that!
Turning this gibberish into something useful!
So we have this large base64 string, and common sense will tell us to decode it… so we did. This will produce a set of bytes (or hex) that don’t give us the key just yet. This is where that annoying RC4 comes in that we mentioned earlier.
Grab the first 64 characters (32 bytes) and we have an RC4 key! I know… don’t get me started!
Using our RC4 key, we can now decrypt the message:
We found it! We feel better now. How are you?
CRACKING THE KEYS
We hear a lot of questions online about whether or not RSA is considered secure. It’s a good algorithm but it’s also very easy to do RSA wrong. There are awards given to those who can do the first factoring of a certain rank of RSA keys out there. Either way, if we check RSA history, we will find that RSA-768 was factored over the span of two years, and a result was published in 2009. Checking the calendar, one sec. Oh yeah! It’s the year 2020!
The best-proven method to optimally factor RSA is called the General Number Field Sieve (at least for digits higher than 100). This is a multi-phase sieving process that requires polynomial selection, lattice sieving, identifying smooth relations, and square root factoring. There’s more than that, but trust us, the technical paper on that is already written and is very very long. It is here if you want it, and it is 98 pages. Have fun with that! Our point is, there are certain phases that scale well, and distributing the workload across multiple CPU’s is ideal. So we did!
We took a cluster of 20 servers, each with 40 CPU’s and factored a 520 bit RSA key. Yes, we used 800 CPUs. But with that level of firepower, we were able to do it in 4-6 hours… which is great!
There were so many, they couldn’t all fit on the screen!
So we did some factoring, and in a few hours it came up with two prime factors (p,q), which we need to compute N (public key) in RSA, which in turn allows us to compute d (private key) which is what we really want to get to our next steps! All good things!
Now, all we need is to get d…. which stands for damage…that we are gonna do.
So we got everything. Bear with me, almost done…
File Footers with a Kick!
So, as we recall above, we have gotten through the gauntlets of finding the public key, climbing over the walls of RC4 to decrypt the gibberish, and then waiting 4-6 hours to factor the RSA P and Q. Oh! Don’t forget all that RSA math stuff to finally get the RSA private key… it’s time to get that darn AES key. And yes, it’s a trek!
This is where Cylance’s report was the most helpful. It pointed us toward the file footer/header information of each encrypted file. Thank you again! So, there are three more layers of RC4 within the file footers.
We don’t want to waste too much of your time explaining the file footers but the following are important to know:
- The last 8 bytes in the file tell you how to read the footer (length)
- Go from there and then you will get a length value so you can then decrypt the stripe offsets with RC4.
Wait, wait, stop the counting… what is a stripe offset? The file is partially encrypted in stripes located at designated offsets. Zeppelin doesn’t encrypt the entire files, it stripes sections of the files based on the original size (bad guys do math too apparently). Think of it as AES encryption sprinkled all over your files, but just to mess with you, not the whole file! We need the stripe offsets from the file footer to decrypt the files. You can also do this mathematically:
stripe_multiple_offset = original_filesize // 0x100 * 0x10
You can use this number as the base multiple to calculate the following stripe offsets
- Zeppelin has a 52-byte prepended header to consider when dealing with stripe offsets and stripe size. So if the stripe size is 16384, don’t start at 0-16384 to decrypt, but from byte 52-16384. Also, on the first offset, don’t exceed the 0x4000 offset, the bad guys want you to do that and are expecting it.
Don’t do this:
- The ‘666′ prepend was no accident, and it’s there to trick security researchers with the striping because AES requires 16-byte blocks evenly to decrypt. Also, you will need to delete the first 3 bytes from the decrypted file, since no one wants ‘666’ written in every file. Also, the files will be invalid.
- There is a hidden stripe in some files right before the footer. Between this and the ‘666′ prepend, decryption can be challenging., The stripes have to all be decrypted together and, the decrypted plaintext interleaved with the unencrypted original file content to reconstruct a successfully decrypted file.
THE KEY TO AES
After obtaining the stripe offset info from the footer, we move on to the AES Key, which is encrypted with the RSA-155 (512) Public key. And we just happen to have the private key this time. But…yet again…RC4. So extract 32 bytes to grab that key and decrypt the RC4 of the encrypted RSA message, and THEN you can decrypt the RSA message with a simple:
key = pow(ct,d,n)
We end up with a 48-byte string composed of the 32-byte AES Key and the 16-byte IV. This key will be applied to the stripe offsets we mentioned, and after a bit of a dance (interleaving), you will get decrypted files!
And we’re spent…
We would like to express a huge thank you to Digital Ocean for helping us with the firepower needed for the 800 CPU General Number Field Sieve cluster. They sponsored Unit 221B with the heavy artillery that enabled us to help victims get their data back in a timely and cost-efficient manner.
As stated above, thank you to Cylance for the report that helped us get here. Thank you, Neil Schwartzman, for putting this problem under our purview. Thank you, Erik Rasmussen, for bringing us the information we needed to test and confirm our theory! Thank you, Brandon Levene, you know why. And last but not least, a huge thank you to the community for the support and help along the way.
Thank you to the developers of CADO-NFS for all the work you put into the project. It was a game-changer for helping victims in a timely manner!
Description of Changes & Revision History
February 11, 2020
TLP Red Version Distributed to Law Enforcement and Selected Researchers
**Limited public release in order to support law enforcement and protect the victims of these attacks.
November 15, 2022
TLP White Version Edited For Public Release