How does malicious software encrypt victims' files so quickly?
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:
Skip the first 512 bytes of the file so that the file header stays intact.
Encrypt the next 1 MB using the embedded encryption key.
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.
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.
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.