Working backwards to the seeds! (OUTDATED)

Note: 
This article is technically accurate and it can be applied to rudimentary RSA implementations that only use time retrieval functions as seed as demonstrated by CS Students from Virginia University. 
However, CryptoDefense uses CrytoAPI which uses a robust PRNG based on process ID, thread ID,  system clock, system time, system counter, memory status, free disk clusters, etc. I dramatically changed the keys recovery approach as soon as I found out the keys were stored on disk.  Why keep this article then? Oh, we wanted the crooks to think we were down the wrong path ;)

Do NOT use somebody else's decryption program!
The reason why each key is unique and why you can't use somebody else's decryption program is because this ransomware randomly generates the keys for each victim. If there was a unique private key for everyone, there would be no need to panic!

But the is a problem...

Software alone is technically incapable of generating random numbers in its truest sense. This explains why the concepts of pseudorandom numbers generation (PRNG) and true random number generation (TRNG) exist and radically differ in the fields of computer science. The second is only -and better- securely employed through specialized hardware, which is not built-in in most desktop and laptop computers in the general consumer market. For the first one, however a strong random number generation algorithm is essential throughout the entire process of public key cryptography. 

Most PRNG's use the system clock as parameter (seed) to generate the pair of keys, and this is evident due the use of GetTickCount, QueryPerformanceCounter and GetSystemTimeAsFileTime found in the executable samples of this malware.

For example, TrueCrypt  (a disk encryption program) significantly circumvents the boundaries of Software PRNG by prompting the user to aimlessly move the mouse around the screen and to type any keys in the keyboard in the meanwhile during key generation. This well-recognized Open Source Software highlights the importance of secure PRNGs.
[See Official Documentation]

This pretty much emulates TRNG to considerable degree of cryptographic security.

Crypto Defense Ransomware does not meet this security criteria; not only because its deterministic PRNG is predictable, but rather because it generates a text file ("HOW_DECRYPT.TXT") shortly after it encrypts the first directory it finds during execution. This file's time stamp betrays fundamental information that potentially exposes the key generation phase to timing attacks that can be executed within a computationally reasonable amount of time. (Outdated)

It's important to note that this project does not seek to attack the (yet) undisputed mathematical strength of the RSA-2048 algorithm, instead it exploits its PRNG with essential seed parameters that are known in order to reduce the key-space in which the brute-force software will operate to manageable calculable levels.(Under development)

Testing the Malware (Timing)
* Where does the Key Generation take place?

1. 11:27:25 (00 seconds)
The precise execution time, which is often found in the following registry key:
[HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\UserAssist]
2. 11:27:45 (20 seconds)
First TCP connection to the Control Server is retrieved via a TCP/IP Sniffer
3. 11:27:48 (23 seconds)
Locally generated Private Key is SENT. (Again: TCP/IP Sniffer)
4. 11:27:51 (26 seconds)
First HOW_DECRYPT file is created.


Maximum Time Range (from 1 to 4): 
26 seconds (26,000 milliseconds)

Removing File Timestamp date (leaves 3-4)
(HOW_DECRYPT can't logically exist without the keys)
Reduces the workload by 3 seconds = (3,000 microseconds)

Note: This test was thoroughly run inside a Virtual Computer on Windows 7 64-bits edition. The Host computer's CPU is an Intel i7-4770. Thus the aforementioned procedures would be executed in less time, further reducing the time space to start brute-forcing. 

RSA-2048 benchmarks from http://bench.cr.yp.to/
(Click to enlarge)

And based on these benchmarks, it takes a Intel(R) Core(TM) i7-2637M CPU 9.98 seconds to generate a key.

Doing 1024 bit private rsa's for 10s: 39652 1024 bit private RSA's in 9.98s
Doing 1024 bit public rsa's for 10s: 607674 1024 bit public RSA's in 9.98s
Doing 2048 bit private rsa's for 10s: 5544 2048 bit private RSA's in 9.98s
Doing 2048 bit public rsa's for 10s: 179596 2048 bit public RSA's in 9.98s

These two sites will give you an rough idea about how long your CPU would need to generate RSA-2048 keys. I said 'rough' mainly because interpreted languages runs slower than machine code: 

1. http://ats.oka.nu/titaniumcore/js/crypto/RSA.sample1.html  

2. http://travistidwell.com/jsencrypt/demo/

Based on these time measurements, it all indicates that the keys are generated before the second connection with the control server is established [11:27:45]. Otherwise the timelines would illogically overlap onto each other.
Now we can rule out the two last stages. This by itself reduces our brute-force framework by at least 6 seconds (6,000 milliseconds) leaving just 20 seconds work for the cracker. 

This is good news, because between stage 2 and 3, additional seeding from the server might have potentially occurred, thwarting our efforts to brute-force the key within manageable levels. (Uploading .RAW TCP/IP data soon). 

Additionally, we only need to generate the public key given the mechanics of this cracker. Not only does it generate faster (on some processors), it also serves the purpose of encrypting original file samples whose results will be later compared with the encrypted sample. 


Fortunately, this was just a challenge response authentication. Further Replay Attacks will confirm this information.

To generate the Private and Public Keys Pair, it takes 10 seconds each. 
(On Intel(R) Core(TM) i7-2637M).



Way to go!

Now, let's set up the CryptoDefense Cracker execution flow and let's check the requirements to start cracking the PRNG seeds:

Parameters needed

1. Oldest HOW_DECRYPT time stamp.
Can be found by searching HOW_DECRYPT in the entire system and them sorting the results by Date. 
2. A small file that was never encrypted. The smaller, the faster it will go through the cracker.
One can easily find them inside any ZIP or .RAR file that was uncompressed into a folder, leaving the compressed backup intact.
3. The encrypted file version (point 2).
This file is required to compare the previous encrypted file with the output. Once the CryptoDefense Cracker finds a match: KEY FOUND!

Hardware needed:

Now, this is where it all becomes hard though not impossible.  Using the Intel  i7-2637M, we can calculate one key every 10 seconds (Remember we only need to generate the public key). This multiplies per millisecond (10,000). Which results in 100,000 seconds, i.e: 1666 minutes or 27 hours.


That is 166 minutes and roughly 2:45:00 

Is this over? NOT YET!

We still have to process the SAMPLE FILE with the ENCRYPTED FILE through the cracker using the generated keys and then compare the results. This is completely relative to the file size and other factors. Currently, I can not yet make time estimates though it would undoubtedly increase the amount of time needed per test.

Last but not least: The QueryPerformanceCounter API can retrieve the current time in up to microseconds and even nanoseconds resolution .If this is the case, the aforementioned estimates would multiply by 1000. That is about 2776 hours or 115 days. Those 2776 hours would multiply again by 1000 if microseconds were used:  2,766,666 hours = 115,277 days or 320 years only to generate the public key! (On one Intel(R) Core(TM) i7-2637M)

In such case, we plan to use OpenCL and CUDA in order to use GPUs (which are way faster than CPU performing parallel tasks) to further accelerate the cracking process. If it isn't fast enough, we may also add a distributed computing module, so that many computers can work together to crack a group of keys within a manageable amount of time.