IEEE INTECH 2013, London
Paper download rank
Authors: Solely authored
Abstract: Cryptographic Hash functions find ubiquitous use in various applications like digital signatures, message authentication codes and other forms of digital security. Their associated vulnerabilities therefore make them a prevalent target for cyber criminals. Cracking a hash involves brute force which is generally extremely time or computing power intensive. Recent times have seen usage of GPUs for brute forcing hashes thus significantly accelerating the rate of hash generation during brute force. This has further been extended to simultaneous usage of multiple GPUs over multiple machines or building GPU clusters having multiple GPUs on a single machine. Attackers use these methods to crack hashes within practical durations of time, to the tune of hours or days, depending on the strength of the password. This paper quantifies the advantage of using the CPU simultaneously with the GPU for hash cracking and describes how a potential attacker, with respect to the size of the botnet used, could come to possess capabilities of hash rates of at least greater than 11 times the rate of the world’s fastest GPU cluster based MD5 brute forcing machine with no investment.
(Google Scholar) Citations earned:
- Blase Ur, Sean M. Segreti, Lujo Bauer, Nicolas Christin, Lorrie Faith Cranor, Saranga Komanduri, Darya Kurilova, Michelle L. Mazurek, William Melicher, and Richard Shay. 2015. Measuring real-world accuracies and biases in modeling password guessability. In Proceedings of the 24th USENIX Conference on Security Symposium (SEC’15), Jaeyeon Jung (Ed.). USENIX Association, Berkeley, CA, USA, 463-481. (2015)
- SANS Institute InfoSec (Pierce M Gibbs), “Botnet Tracking Tools” (2014).
- Blase Ur, “Supporting Password-Security Decisions with Data”, PhD Thesis (2016)
- Mukherjee, Bidyut, Roshan Lal Neupane, and Prasad Calyam. “End-to-End IoT Security Middleware for Cloud-Fog Communication.” (2017)
This paper follows up on the fundamental idea presented in my first paper. It also describes a constant cost function for job breakdown which can be applied to Botnets.
Though relatively simple in technical terms, the implications from the results demonstrate how attackers, could compromise passwords which were previously thought to be uncrackable due to impractically large keyspace bruteforcing. Since this paper is quite simple, I’ll get cut straight to the point.
The idea is to be able to efficiently split a bruteforce job to millions of participating bots in a botnet. These botnets should be able to make use of both the CPU and the GPU. This is to consider complete utility of computational resources. The following are the basic steps.The important part here is to find a constant cost function for work distribution. The following simple formula does just that:The Job split is defined as the range of characters to be tried by each node for each possible Key Length. Expressed as a base of the Character Set count, it denotes the corresponding characters assigned for each number in the Character Set count. For example, a password with Key length 1 and Character Set assigned as 26 denoting numbers [1-26] as [a-z] respectively, when split among 2 computers would give a Job Split of Cbase26. This means that the first node and second node would brute force [0base26 – Cbase26] and [Cbase26 – Pbase26] respectively. For passwords with greater key length, the process is repeated for each key length till the maximum length is reached. A diagrammatic example’s given below:I’m skipping out a lot of other details like dealing with machines in private networks, maintenance of a stable network recovering lost jobs etc. You can find all these details in the paper. I’m just focusing on the more “interesting” things in the paper. I guess I’ll cut straight to the results
The proposed approach was tested on both a centralized and P2P botnet with 4 machines. Two of the machines, called C1 and C2, had CPUs Intel I7-2600K @ 3.3 GHz, 4 Cores, 8 logical processors and GPUs NVIDIA GTX 550 TI. The other two, called C3 and C4, had CPUs Intel I5-3210M @ 2.5 GHz, 2 cores, 4 logical processors and GPUs NVIDIA GT 650M. The centralized botnet setup was tested with a 5th machine called K, having an Intel I7-3630QM @ 2.4 GHz being the C&C server. The results were found to be independent of the specifications of this machine. C1, C2, C3 and C4 were used as bots to this main C&C server.
The P2P botnet setup was tested with K being the main C&C Server and C1 mimicking a node publicly accessible from the internet and C3, being another public node having a private network behind it consisting of C2 and C4. The results were analyzed in terms of increase in hash generation rate upon combined usage of CPU and GPU as opposed to sole usage of the GPU, total hash generation rate obtained across the botnet, scalability and Job Distribution and Job recovery. The test input used for each test was an MD5 of a random string. The string was chosen to be random as the factors of result analysis do not depend on the nature of the string. All references to hash rates from hence forth refer to MD5 hash generation rates in specific.Thus, the overall hash rate generation when solely using C1 showed an additional generation of 20.79% of the hash generation rate of the GPU, an additional 303.5 Million hashes. C2 showed an additional generation of 35.32% of the hash generation rate of the GPU, an additional 134.2 Million hashes.
Hash rates were found to be practically equal when experimented with both Centralized and P2P botnet setups. Minor differences were observed to be measurement errors, hence, the average of both hash rates from both botnet setups were used for maximum accuracy. Individual hash generation rates of CPU and GPU of each node is shown in table III.The combined hash generation rate of nodes C1, C2, C3 and C4 was 3967.13 Million hashes per second. Job Calculation and distribution algorithms had successfully trickled down the Job to all the nodes in the network and the brute force attack on the given hash was performed as though distributed locally within a machine with multiple GPUs and CPUs. Furthermore, the CPU generated hashes accounted for 28.52% of the total hash rate generation. This
Scalability was studied by performing hash rate generation performance tests on C1 and C2 combined and comparison of results so obtained with that of C1’s solo hash generation rate.
Both machines have identical hardware configurations. Hash generation rates of each test configuration plotted against time elapsed is shown in the following graph:More on the Botnet attack theory:
As of present times, botnets, which are large number of compromised computers that are used to generate spam, harvest credit card details, etc., are used by malicious hackers for only directly harmful purposes. Future times could see attackers harnessing the computing power of botnets to brute force attack password hashed instead of sole exploitation of their internet resources. This has already been closely treaded up on by the rise of botnets that perform Bitcoin mining which involves iterative SHA calculations . A stat from 2006 says that an average botnet possesses around 20,000 machines , but more recent bots like  and  are known to have possessed machines many times this figure. Occasional super botnets possess computers by the millions . Recent botnets like Chamelon, TLD4, Kelihos and BredoLab had 120,000, 4,500,000, 300,000 and 30 Million bots respectively . Such large number of computers would consist of not only many high performance gaming machines but also powerful office or home computers. For approximation calculations, tests were conducted on an average Intel I5 processor @ 2.5 GHz and Core 2 duo @ 2.0 GHz. They yielded an average hash generation rate of 132 and 56 Million hashes/second respectively. When excluding powerful machines or even GPUs from consideration and taking a bare minimum average of 50 Million hashes/second per computer, even a relatively small sized botnet of 20,000 computers would yield 1000 Billion hashes/second. Inclusion of high performance computers could put this at greater figures. An attacker could use this mean of computing power to crack critical authentication messages and complex passwords etc. which cannot otherwise be cracked by even custom built high performance cluster machines. All the aforementioned predictions can easily hold true if the attacker manages to efficiently distribute the Job among such a large number of computers as proposed in this paper. Furthermore, instead of applying this computing power to breaking a single hash, an attacker could distribute a password database file to the botnet for cracking. In this way, the entire credential database of a site could be broken in a fraction of the time taken for brute forcing each password serially.