50

Encrypting a file to me is akin to dealing with a very long string, feeding it into the hashing or encryption function to get another long encrypted string (or a hash in the case of hashing).

This process takes some good amount of time. I know that because I use HashTab to verify the integrity of the files I download off the Internet.

How can ransomware like CTB-Locker or Crypt0l0cker encrypt their victims files instantly?

Recently a friend of mine was a victim of one of these ransomware and he could NOT open his files/photos from Ubuntu on his dual-OS machine even when the infection happened with MSWindows. This suggests the encryption does not happen on the fly when you open a file.

user2428118
  • 2,768
  • 16
  • 23
Ulkoma
  • 8,793
  • 16
  • 65
  • 95
  • 5
    You don't have to encrypt all of a file, just enough to prevent the application from opening it. Since many files are already binary encoded, to the end user, the file is effectively unusable. – bishop Jul 05 '15 at 17:28
  • It might be worth mentioning full disk encryption (my employer makes us use Symantec PGP) which can encrypt your disk while you use it, using (I assume) driver trickery. That said, that's encryption on a drive level, not a file level. – Matt Lyons-Wood Jul 06 '15 at 06:14
  • 1
    For many purposes it could even be enough to encrypt the File-system Metadata. So the FAT-Table or NTFS-Metadata in Windows. If I scramble that it would be hard enough for most users to recover their files, although the file-contents are fully intact. – Falco Jul 07 '15 at 11:51

8 Answers8

47

I was at an OWASP talk where the speaker decompiled and analyzed a ransomware executable (for Windows) in front of us. There are many flavours of ransomware out there, so I can't speak to ransomware in general, but I can certainly talk about the one I saw. The general idea is that the ransomware executable contains the encryption public key needed to encrypt files using an asymmetric algorithm, for example RSA. The corresponding private / decryption key stays with the hackers so that no amount of reverse-engineering of the executable can give you the decryption key.

To actually encrypt a file, it does something similar to:

  1. Skip the first 512 bytes of the file so that the file header stays intact.

  2. Encrypt the next 1 MB using the embedded encryption key.

  3. If the file is longer than this, leave the rest unencrypted.

The point is not to fully hide or protect the data, it's enough to make it un-parseable.

As for time, doing 1 MB of RSA is still slow and will still take several hours to crawl your HDD.

I suspect that this specimen that I saw was just a lazy imitation of the full RSA-AES ransomware that Steffen Ullrich talked about in his answer - which is the one that you should really be worried about.

Community
  • 1
Mike Ounsworth
  • 57,707
  • 21
  • 150
  • 207
  • 14
    Due to RSA being so slow, usually, a random key is chosen, encrypted with RSA, and then this random key is used to run a stream cipher - often something like AES/DES - which is many orders of magnitude quicker. – AMADANON Inc. Jul 06 '15 at 02:19
  • 1
    "Skip the first 512 bytes of the file so that the file header stays in tact ie Windows can still tell that it's a pdf, mp3 etc" -- do note that Windows only checks the extension, not it's contents. –  Jul 06 '15 at 11:14
  • @user2064000 seriously? Windows is still that dumb? I've been pure linux since 2006, I would have assumed that Windows had overcome that problem by now. Learn something every day... – Mike Ounsworth Jul 06 '15 at 13:14
  • 1
    @MikeOunsworth AFAIK, the Linux kernel doesn't care about file headers either. – nanny Jul 06 '15 at 13:24
  • @nanny From the `man` page for the `file` command ([link](http://linux.die.net/man/1/file)): "The concept of a “magic” has been applied by extension to data files. Any file with some invariant identifier at a small fixed offset into the file can usually be described in this way." -- sounds like a file header to me! – Mike Ounsworth Jul 06 '15 at 13:46
  • @nanny: That's because the Linux kernel doesn't care about file types at all. So far as the kernel is concerned, they're all just "files." There are a few exceptions (e.g. the shebang and other executable things), but otherwise, bytes are bytes. Now, your *GUI* may display file types, but that's at a much higher level of abstraction. – Kevin Jul 06 '15 at 15:24
  • 6
    ...and of course it's not the *kernel* that cares about shebangs and whatnot, but the shell. Just like it's not Windows that cares about the bitrate of your mp3s, but Windows Explorer. – Jon Jul 06 '15 at 19:03
  • This is a bit off-topic but there's loads of software on Linux that looks at file extensions and does not look at file headers. – Flimm Jul 07 '15 at 09:41
  • 5
    @jon Actually, Linux kernel checks first bytes to find the interpreter, see https://coderwall.com/p/pdg77q/how-the-shebang-is-processed-by-the-linux-kernel – Edheldil Jul 07 '15 at 12:12
  • 1
    @Jon: Actually, [the Unix kernel *does* interpret shebangs](https://en.wikipedia.org/wiki/Shebang_%28Unix%29#History). – Scott - Слава Україні Jul 07 '15 at 12:13
  • I stand corrected -- and quite confused as to why they felt doing that in the kernel is preferable. Thanks for the reference! – Jon Jul 07 '15 at 12:47
  • @Jon That's a feature that allows text files to actually be runnable, even outside shell. See [execve(2)](http://man7.org/linux/man-pages/man2/execve.2.html). – cubuspl42 Jul 07 '15 at 13:26
  • Do you haveI a link to the OWASP presentation? Or the name of the presenter? – ColBeseder Jul 07 '15 at 16:23
  • 1
    @ColBeseder I don't think the talk was recorded, but here's a link to the talk abstract and speaker bio (click "see all" to expand): http://www.meetup.com/OWASP-Ottawa/events/219842720/?a=uc1_vm&read=1&_af=event&_af_eid=219842720 – Mike Ounsworth Jul 07 '15 at 17:50
29

First symmetric encryption is pretty fast. AES in some modes is easily 200MB/s. Your claim that hashing is slow is a red herring. Hashing is incredibly fast. It is so fast on modern processors that is weakens the effective security of password hashes. That has led to the development of multi-round key derivation functions to "slow down" the hashing.

The "slow" speed you are seeing is mostly the effect of your slow hard drive. In memory hashing is something on the order of 500MB/s to 2 GB/s+.

Still the malware doesn't need to be "instant". The user's system is infected silently. Copies of the files can be encrypted without alerting the user and then once ready the originals deleted and the user notified "instantly". The entire process from infection to that point may have taken a significant amount of time despite seeming to occur instantly.

Gerald Davis
  • 2,250
  • 16
  • 17
  • 1
    Incidentally, it's also better for the alert to happen some time after infection, so that the victim can't easily figure out where / how he got infected. – duality_ Jul 06 '15 at 07:05
  • There's some confusion here too, where the OP is conflating encryption with hashing. Even though they share some similar mathematical theory, hashing IS NOT encryption, and the two serve very different purposes. Because of this, many hashing algorithms are slow BY DESIGN (to slow down brute-force attacks), whereas encryption algorithms tend to be streamlined as much as possible without compromising security. – loneboat Jul 06 '15 at 15:03
  • There was no confusion. I only included hashing performance because the OP reported hashing performance and believed it was slow and thus encryption should be even slower. The reality is both symmetric encryption and hashing algorithms are very fast. On long messages AES256 is about 2 to 13 cycles per byte (depending on mode) and SHA-512 is 8 cycles per byte. Most of the "delay" when hashing or encrypting is from the time to takes to read the data from disk. The actual cryptography is incredibly fast. KDFs are used to slow down password hashing because hashing operations are so fast. – Gerald Davis Jul 06 '15 at 15:29
  • I didn't mean confusion by you - I think your answer is excellent. :-) I meant confusion by the person who asked the question. It seems like they might be confused, if they're using hashing performance as a metric of encryption performance. – loneboat Jul 06 '15 at 16:30
  • 1
    @loneboat Hashing algorithms used to check file integrity aim to be as fast as possible without sacrificing security. It's Only password hashes are deliberately slow, but there is no reason to mention those here. Hashes and symmetric encryption have similar performance and both are usually IO bound. Since hashing only needs to read the file, but encryption needs to read and write data, encryption should be about twice as expensive in this context. – CodesInChaos Jul 07 '15 at 08:00
  • 2
    A friend of mine was hit by one of these attacks. It was *not* instant. He noticed early enough to shut it down after it had only encrypted about half of his extensive music/video library. OP was right that it *does* take several hours to do it's magic. It's the silence that allows it to complete its dirty task. – Rick Chatham Jul 09 '15 at 19:32
16

Hashing (like SHA-1 etc) and symmetric encryption (like AES) is relatively cheap, asymmetric encryption (like RSA) is much more expensive. That's why one usually does not use RSA to encrypt a large file, but instead uses symmetric cryptography with some random key and only encrypts this short key with RSA.

I know that because I use HashTab to verify the integrity of the files I download off the Internet.

Sounds like a very scientific method for me. Unless you have an old and slow processor the speed of hashing (and thus verifying the data) is mostly faster than you can read the data from disk (in case this is not obvious: of course you still need to read the data to hash it, but it will spend more time in waiting for the data from disk than in computing the hash).

How can ransomware like CTB-Locker or Crypt0l0cker encrypt their victims files instantly?

Modern operating systems support encrypted file systems and with today's processors (which often include hardware acceleration for AES) you will not notice much of a speed difference if you use an encrypted file system or not, because the bottleneck is not the encryption but the speed of the disk (in benchmarks you will see a performance drop but these don't reflect real-world usage for most people). Thus their is no reason why ransomware could not encrypt data fast too. Of course they might make it feel faster by hooking into the system so that the files you want to open get encrypted first and the rest in the background.

Community
  • 1
Steffen Ullrich
  • 184,332
  • 29
  • 363
  • 424
  • And the symmetric key used to encrypt the files is then deleted? This means that you could retrieve the symmetric key from memory during encryption, or isn't that the case? – Michael Jul 05 '15 at 10:15
  • @Michael: yes, you should be able to retrieve the symmetric key from memory during encryption, although there are probably ways to make this not too easy. And you could of course use a different key for each file to make it harder to recover the data. – Steffen Ullrich Jul 05 '15 at 10:49
  • cheap as in fast? expensive as in slow? so the files are actually symmetrically encrypted but the key is encrypted with RSA. How fast? it does not sound right to me. Even on a good PC I need a 30 seconds to calculate the MD5 for a file. – Ulkoma Jul 05 '15 at 11:24
  • The data are being read from the disk in order to get fed to the function right? how can the total time be less? or you were referring to the actual time needed to process the string/file in the memory by the hashing/ encryption function. – Ulkoma Jul 05 '15 at 11:26
  • 1
    @Ulkoma: cheap/expensive as in resources, i.e. memory, processing power etc. This translates in cheap being fast. And I never claimed that the total time is less (than what?). Of course you need to read the data from disk to feed it into the function, but the major part is the reading not the computing. And regarding "I need a 30 seconds to calculate the MD5 for a file." - how big is your file, how slow is your disk, how fast is your processor.... ? If you need 30 seconds to hash a file with 1 byte size than this is probably the time your systems needs to load your program. – Steffen Ullrich Jul 05 '15 at 11:51
  • I did a test on an old P4 machine running Debian Linux. It took 0.23 seconds to do an MD5 hash of a 15MB file. – mti2935 Jul 05 '15 at 12:39
  • @mti2935: yes, and according to `openssl speed` I can do about 500 MByte/s SHA-1 on an mobile Intel I5 (i5-4200U) processor. That way exceeds the speed of my disk. – Steffen Ullrich Jul 05 '15 at 12:51
11

The mistake you are making is thinking it's instant. Rather the malware sits there encrypting in the background and decrypting anything the user asks for. It's silent during this phase, it only demands the ransom after everything has been encrypted.

Loren Pechtel
  • 763
  • 4
  • 9
8

According to wikipedia :

When first run, the payload installs itself in the user profile folder, and adds a key to the registry that causes it to run on startup. It then attempts to contact one of several designated command and control servers; once connected, the server generates a 2048-bit RSA key pair, and sends the public key back to the infected computer.

It's not slow as you think, if your computer is fast and isn't doing heavy CPU usage at time of infection you could lose gigabytes of data in less than 15 minutes. Modern PC's can calculate hash and perform encryption operations faster than the hard disk/SSD disks can work. So i would say the modern limit on speed for hash/encryption speed is based more on the disk itself. I can generate a SHA-512 hash for a 2,5GB file in 2 minutes.

And also the malware can just wait till it encrypts everything it wants before displaying a message to the user.

Freedo
  • 2,253
  • 5
  • 18
  • 28
  • If this is the case then why do we use slow hashing functions to compare files and verify integrity? Why not just use RSA? I am quite sure the output is unique for each unique key. – Ulkoma Jul 05 '15 at 08:48
  • 2
    RSA is not typically employed to encrypt data directly (can it encrypt arbitrarily large data at all?). It is used to encrypt the key of symmetric encryption. – Siyuan Ren Jul 05 '15 at 13:24
6

The basic process is to read your file contents and write them back to disk using some form of asymmetric encryption to ensure that you have to pay to get your data back. Some will encrypt only small sections of the data to improve the speed, others will rewrite your entire hard drive if they can. As some of the other answers note some malware will simply encrypt a portion of your file in-place to speed up the process, since for many file formats even a slight change in the file makes the entire file unusable.

How can ransomware like CTB-Locker or Crypt0l0cker encrypt their victims files instantly?

They can't. Instead what they do is conceal their activity by making the files appear to be OK until the process is complete. By intercepting file-system calls you can change the user's view of what is actually present on the disk, making it appear that everything is still OK until you finish, then when you take away the intercepts the user can see the true state of the drive. The danger in doing this is that you have to have both parts of your asymmetric key pair in order to decrypt the files on-the-fly when the user opens one, which in principle means that something could find the private key that you want to sell the user later.

Other malware like CryptoWall (which I've had more experience with recently than I want to remember) doesn't bother to hide, it just blazes ahead encrypting everything as quickly as it can... and that's pretty much limited by the IO speed of the drive it's encrypting to.

Looking at a few benchmarks for AES - which is the encryption algorithm that CryptoWall purports to use - a modest modern CPU can encrypt data at rates well in excess of 100MB/sec, which means that the operation is likely to be IO-bound on anything other than an SSD. Add multiple threads running on separate CPU cores targeting different folders and/or drives and the process can complete fairly quickly.

I recently had to clean up a file server that had been processed by CryptoWall running on one of the user PCs. By the time the users had noticed something was wrong the malware had been running for about 1.75 hours. We pulled the thing off the network at just shy of the 2 hour mark and during cleanup I found around 230GB of encrypted files. That's an average of ~30MB/sec encryption, which is certainly doable in the environment. It took about 3 times that long to restore the files from the previous backup. Although I have some ideas on how to speed that up next time, most clients have their backups on crappy low-cost NASs or (shudder) USB drives.

Unfortunately we are unlikely to see an end to these things any time soon. A competent, decently configured backup solution is your best friend when one of these things hits. Doesn't hurt to have a programmer handy to script the restore.

Corey
  • 190
  • 5
5

From a social engineering perspective, the malware author could have written a program that replaced the contents of the data with random bits. The victim would have no way to verify if the contents were encrypted or just trashed. If they decide to pay the ransom and the "key" does not work, there is not much they could do, the guys are criminals after all.

Boluc Papuccuoglu
  • 579
  • 3
  • 6
  • That is exactly what I suspect – Ulkoma Jul 05 '15 at 13:06
  • 16
    If they would do that they would harm their own business model. If enough people report that they did not get their money back others would not pay. To get most of this shady business the victims most trust that they get their data back and this information must spread so others will pay too. And in fact their are enough reports that one gets its data back. – Steffen Ullrich Jul 05 '15 at 13:12
  • 1
    The bottleneck is the disk I/O, and writing random bits just halves the time because it doesn't require reading from the disk. That's probably not very significant for a malware. – user23013 Jul 05 '15 at 13:28
  • My feeling is that there ARE some crypto ransomware authors who work off a sustainable business model, like Evgeniy Bogachev. But it seems inevitable that there will be ones out to make a quick buck without having to deal with symmetric encryption keys, key databases, etc. – Boluc Papuccuoglu Jul 05 '15 at 13:32
  • @SteffenUllrich: It is well-known that hijackers will cut your wife's or child's throat the moment you pay them (they no longer need them, and they could possibly identify the hijackers). Still, almost everybody will pay. – Damon Jul 05 '15 at 17:10
  • 3
    @Damon: I doubt that this is well known and I doubt even that it is true. I would say that most victims of robberies actually continue to live. – Steffen Ullrich Jul 05 '15 at 17:21
4

Some ransomwere such as TorrentLocker only encrypt the first MB (plus add a trailing). That is enough for making most formats not to be recognised, but at the same time makes much more quick to encrypt a big number of files (also remember that only some filetypes are encrypted, like documents, photos…).

This was reported by Nixu in SANS blog, and also on (ESET whitepaper), although they reported 2MB.

And, as Loren mentioned, the ransomware only show the big banner asking for the ransom after everything has been encrypted (it's no good that you realise when only a few files have been "held"), although some ransomwares place while they go a ransomware demanding file on each folder / for each file they encrypted.

Ángel
  • 17,578
  • 3
  • 25
  • 60