Distributed Hash Cracking on the Web

on 5 January, 2012

5 January, 2012

The web is constantly evolving with new technologies being added all the time, creating a platform completely unrecognisable from when the web first began.

MWR Labs recently carried out a research project to assess some of these new technologies and the possibilities they bring for helping to solve computationally intensive problems within security.

The main aim behind the project was to try to harness the power of two new technologies in particular, WebGL and WebCL, for retrieving passwords from hashes using a brute force technique. If this proved possible, the secondary aim was to assess how cost effective it would be to retrieve hashes in this way compared to using cloud computing. Let’s start with a brief introduction into these two new technologies.

WebGL & WebCL

WebGL extends the capabilities of JavaScript to allow the rendering of 3D graphics in the web browser. Based on the OpenGL ES standard, WebGL executes directly on the Graphics Processing Unit (GPU). The Khronos Group develops and maintains both WebGL and OpenGL ES. WebGL is currently implemented in the following browsers: Firefox, Chrome, Safari and Opera.

WebCL, announced in March 2011, provides JavaScript bindings to the OpenCL API. OpenCL is a framework for writing programs that can execute in parallel on GPUs and CPUs. Applications can achieve significant performance improvements through using OpenCL on problems that are suitable for parallelisation and thus through WebCL web applications will be able to do the same.

The WebCL specification is still under development by Khronos; however, Nokia and Samsung have both created implementations to act as starting points. Nokia have created a Firefox extension and Samsung have developed a WebKit implementation. Currently WebCL is only available through the above implementations.

Getting the Hash

Retrieving passwords from hashes using brute force is simply taking every combination of characters that comprise a password, hashing it and testing if it matches the original hash. Our starting point was to try to implement the MD5 hashing algorithm in WebGL and WebCL.

It was always going to be a challenge to implement a hashing algorithm in WebGL simply because WebGL is designed for rendering graphics, not general computation! Indeed even after overcoming the hurdles involved, packing input into textures, computing using a shader, and retrieving output from images it became clear it was not feasible. This is due to limitations in the WebGL shading language, 32 bit Integers are not supported and neither are bitwise operations. Those familiar with the MD5 hashing algorithm will know that it basically performs a bunch of bitwise operations on 32 bit Integers. We did try implementing these features ourselves through using arrays of bits; however, as expected, it proved much slower than just using normal JavaScript and was just not feasible.

WebCL on the other hand proved to be much simpler to implement. So with our fancy WebCL and boring JavaScript hashing algorithms we move onto our next stage, which is implementing a way to distribute the computation across the web.

Distribution

The basic idea behind the distribution platform was to have a centralised server that distributes computation between worker nodes. The server contains a list of the hashes trying to be cracked and gives worker nodes a range of character combinations along with the hash to be cracked. The worker nodes then hash all these character combinations and if one matches the original hash, they report the recovered password to the centralised server. The server was implemented using Ruby with communication to the Nodes through JSON requests. The following two diagrams show an overview of the system and a step by step run through of a hash being cracked.

Layout of the distributed platform:

Step by step process of cracking the hash:

The following features were implemented:

  • Detects malfunctioning nodes
  • A node’s chunk size changes depending on its speed
  • Remotely refresh nodes in cases of code update
  • Bans rogue nodes
  • System monitoring – Statistics on speed, number of nodes connected etc.
  • System design settings – Node refresh period
  • Modular to allow new hash types, currently:
    • MD5
    • SHA-1

Deployment

In order to assess our newly created Distributed Hash Cracker’s performance and cost effectiveness we decided to embed the worker node into a rich media advert and deploy it on an ad network. Using this ad network we paid $0.50 for 1000 impressions (advert displayed to user), each one of those users would then start cracking hashes providing they had JavaScript enabled. Below is the advert that was displayed to users.

Analysis

Firstly, let us compare the performance of our MD5 hashing algorithms. Speeds are shown in million hashes per second (MH/s). The benchmarks were run on the following CPU and GPU. CPU – Intel Core 2 Duo @ 2.53GHz, GPU – ATI HD5570.

 

Here we can see that the OpenCL HashCat implementation is by far the fastest, with WebCL being around 15 times slower, however our WebCL algorithm isn’t heavily optimised. It is also clear just how slow JavaScript is, with over 2000 Chrome-JavaScript nodes needed to equal the power of one GPU. However Chrome is by far the fastest browser and as we see in the graph below the number of nodes needed for other browsers rises dramatically.

 

For example, over 40,000 IE8-JavaScript nodes would be needed to give the equivalent power of one GPU.

Now for the deployment statistics. We weren’t really expecting to see any WebCL nodes since the technology is so new and an extension is needed for it to work. Indeed there weren’t any. The following statistics therefore are only for the JavaScript implementation.

Highest Speed Achieved110.280MH/s
Highest Number of Nodes Connected7615
Total Nodes Connected146,740
Average Speed20.49MH/s
Longest connected node3 Days, 13 Hrs. 25 Mins.
Fastest nodeChrome 13 0.563MH/s
Costs$102
Cost per 1 Billion MD5$0.028
Cost to recover 8 Char A-Za-z0-9~$6,250
Time needed to recover 8 Char A-Za-z0-9123 Days!

Based on these statistics we can estimate the performance of the DHC if we assume that we only have WebCL nodes.

JavaScript Average Node Speed0.05MH/s
WebCL Estimated Average Node Speed10MH/s
Amazon EC2 GPU Instance IGHashGPU Speed2790MH/s1
Amazon EC2 Cost$2.10 per hour

Using the above statistics, we have done just that, and compared the estimated WebCL performance to the JavaScript performance we achieved and the performance of an Amazon EC2 GPU instance running IGHashGPU.

From these estimates we can expect WebCL to be roughly 50% faster than using Amazon’s EC2 GPU instances. We can also see that based on our estimates WebCL is faster however, with this distributed platform speed can be varied depending on what the daily spend limit for the advertising campaign is set to. For example, if we doubled the daily spend limit we would expect to get double the number of impressions in the same amount of time, thus roughly doubling our speed. Of course, eventually there will be a limit on the speed that can be achieved due to the centralised server acting as a bottleneck.

Conclusion

We can see that currently, with WebGL and JavaScript, it is not possible / cost effective to crack hashes in a distributed manner over the web. However, WebCL looks very promising and given the industry backing it has, it seems likely it will become integrated into some browsers in the future. We can see that already in this early stage of its development, with our modest estimates and our MD5 algorithm it already outperforms the cloud. Whilst deploying such systems on advertising networks might not be the way forward it seems clear that with WebCL distributed computing on the web will become a reality opening up a realm of future possibilities.

References

1 http://blog.zorinaq.com/?e=42