Which Computer Will Crack Every Single 12-character Alphanumeric Password in Less Than 8 Hours?

Disclaimer: This article is just a bit of fun ... there's nothing derived from this, and it is intended to outline some general principles.

In Hitchhiker's Guide to the Gallery, Deep Thought announced that:

"The Answer to the Great Question..."
"Yes..!"
"Of Life, the Universe and Everything..." said Deep Thought.
"Yes...!"
"Is..." said Deep Thought, and paused.
"Yes...!"
"Is..."
"Yes...!!!...?"
"Forty-two," said Deep Thought, with infinite majesty and calm.”

So meet Sunway TaihuLight ...

Introduction

The US is the home of the computer. It was the home of the invention of the computer program, transistor, the microchip, the microprocessor, the PC, and the Internet, so it doesn't like to lose out to other countries around having the best computer systems. There is thus a continual challenge to build the largest and most powerful computer around, especially around challenging areas which need a great deal of computing power such as cracking cryptography (distributed.net), improving climate change prediction models (climiteprediction.net), finding out what regulates the genes in DNA, and even in decoding radio signals for the signs of intelligent life (SETI@home).

So after continually leading the race for the best computer it was a shock when the US discovered that the fastest computer was based in: China. This is the Tianhe-2 (MilkyWay-2) and run by National Super Computer Center in Guangzhou. It gives rates of 33.9 petaflop/s:

Now there is a new Chinese supercomputer called Sunway TaihuLight which is more than three times faster than Tianhe-2, and giving a rate of 93 petaflops per second (93 million billion floating point operations per second). It has over 10 million computer cores, made up of nearly 41,000 nodes, has 1.3PB of memory, and consumes over 15 kW of power. The major change has been the move away from the Intel processors used in Tianhe-2 towards processors design and manufactured in China.

So, what about the cracking power of Sunway TaihuLight? 

The usage of parallel processing is one of the most important contributions to cracking cryptography. For example if we take a 12 character password with alphanumeric characters and additional characters [ !@#$%^&*()+_] we have 26,963,771,415,920,784,510,976 different passwords [here] and if we use 10 million cores and crack at 10 billion passwords per second, we see that it will take around 3 days to crack every password (as apposed to over 15 years without parallel processing):

If you are interested in some real hash cracking with hashcat, see here:

Benchmarking

There are many ways of measuring the performance of computer, such as the number of operations it can make in a second, or how fast it can move data around its memory, or even how fast it can make complex maths operations. One of the best units is a Flop, which is a floating point operation per second, and which relates to how fast the computer can operate on numbers.

With supercomputers, we are now measuring their performance in terms of Teraflop which is million million floating point operations per second. The Tianhe-2 super computer has a speed of 54,902.4 TFlop/s, which is around 10 million times faster than a desktop computer.

So to catch-up, President Obama has now committed to building the World's fastest computer by 2025. It will be 20 times faster than Tianhe-2, and will be built by the National Strategic Computing Initiative (NSCI) and be the first in the world to exceed one exaflop (one thousand million million floating point operations per second).

It comes at a time with increasing computing power in the Cloud, and also around issues in law enforcement struggling to crack encrypted content. The new computer is likely to consume over 60 megawatts of electrical power, with a yearly energy bill expected to run into hundreds of millions of dollars per year.

Many companies are now building new computer infrastructures by clustering their computers and data infrastructures, into centralised computing resources. This can be done either with a private Cloud - in their own networked infrastructure - or in the public cloud - such as using Amazon's Elastic MapReduce - and which implements a Hadoop cluster. These aim to robustly distribute processing and data storage across a clustered infrastructure, and make sure a failure in any part of it will not cause the task to end. The days of a computer running on a problem for months, and then saying:

Error in code execution. Shutting down program.

have gone, so no more Deep Thought problems of computers running for years and crashing.

A Bit of History

With IBM celebrating its 100 year birthday this year, we see that the computing industry is one of the US's largest economic drivers, and, as the country, the work has moved from being focused on building to creating software.

It was Herman Hollerith, at the end of the 19th century, who devised a machine that accepted punch cards with information on them. These cards allowed an electrical current to pass through a hole when there was a hole present (a 'true'), and did not conduct a current when it a hole was not present (a 'false'). This was one of the first uses of binary information, which represents data in a collection of one of two states (such as true or false, or, 0 or 1). The company that Herman initiated went on to become IBM.

During World War II, John Eckert, at the University of Pennsylvania, built the world's first large electronic computer. It contained over 19,000 and was called ENIAC (Electronic Numerical Integrator and Computer). It was so successful that it ran for over 11 years before it was switched off. He would be totally amazed with modern computers, especially in the way that it is now possible to integrate millions of digital devices onto a single piece of silicon, which is smaller than a thumbprint. For them you could actually hold a digital device in your hand, if it is was working it would burn your hand. 

Figure 1: ENIAC

Grace Hopper overcame one of the major problems in software development: how to write programs which could be easily written by humans, and easily converted into a form which a computer could understand. In the early-1950s work had begun on assemblers which would simply use simple text representations of the binary operations that the computer understood (such as ADD A, B to add two numbers). The assembler would convert them into a binary form. This aided the programmer as they did not have to continually look-up the binary equivalent of the command that they required. It also made programs easier to read.

The great advance occurred around 1956 when Grace Hopper (1906-1992), started to develop compilers for the UNIVAC computer. These graceful programs converted a language which was readable by humans into a form that a computer could understand. This work would lead to the development of the COBOL programming language.

In terms of the electronic computer, it all started when William Shockley, from Bell Labs, invented the electronic transistor and which allowed computers to migrate from re-enforced concrete floors which occupied whole floors of a building, and need special electrical generators to power them, to ones which could be fitted onto a pin-head. Robert Noyce, at Fairchild Semiconductor, then created the first microchip, which brought together several transistors on a chip, and created the integrated circuit. Ted Hoff, then working with Intel, created the first programmable chip with the Intel 4004, and created the first microprocessor.

Here is a quick history of the development of the transistor to the Cloud:

It's all going parallel 

There is only so fast that a microprocessor can go before it starts to fail. Clock speeds of around 3GHz (approximately 3 billion operations per second) is about as fast as you can push a microchip before it starts to fail. With a microprocessor a single bit in failure, even in a long time scale, can cause a devastating effect. So the natural way to scale-up is to split tasks into smaller tasks, and then run them in parallel. Obviously this doesn't work if the tasks are interlinked, where the input of one task depends on another, but in other cases, such as cracking cryptography, the tasks can run independently to each other.

So Tianhe-2 is made by NUDT and contains 3,120,000 cores, 1PB memory, and built around the processes normally used in computer servers: Intel Xeon processors.The shock for the US was that it completely trumped the US-based ones who had led the World for decades, and knocked Titan off top spot.

In the US, the three leading computer manufacturers for supercomputers are: Cray Inc, IBM and HP. So, for a while the leader was built by Cray Inc and named Titan. It is based in the DOE/SC/Oak Ridge National Laboratory, and has 560,640 cores and 710,144 GB, giving a throughput of 27 TFlops/sec.

A leader for a while too was built by IBM. It is named BlueGene/Q and run for a range of organisations including Department of Energy's (DOE) National Nuclear Security Administration's (NNSA). It has 1 PB memory, 1,572,864 cores, and uses using Power BQC 16C processors (the Power PC processors used to be used by Apple Mac computers, before Apple dumped them in favour for the Intel ones). An encryption algorithm which is cracked in a million minutes on a standard PC, could BlueGene less than a second to crack.

Cracking crypto

The use of parallel processing is now well-known in the industry, and the Electronic Frontier  Foundation (EFF) set out to prove that DES was weak, and created a 56-bit DES crack which had an array of 29 circuits of 64 chips (1856 elements), and processed 90,000,000 keys per seconds. It, in 1998, eventually cracked the code within 2.5 days. A more recent machine is the COPACOBANA (Cost-Optimized Parallel COde Breaker) which costs less than $10,000, and can crack a 64-bit DES code in less than nine days.

The ultimate in distributed applications is to use unused processor cycles of machines connected to the Internet. For this applications such as distributed.net allow the analysis of a key space when the screen saver is on (Figure 2). It has since used the method to crack a number of challenges, such as in 1997 with a 56-bit RC5 Encryption Challenge. It was cracked in 250 days, and has since moved on, in 2002, to crack 64-bit RC5 Encryption Challenge in 1,757 days (with 83% of the key space tested). The current challenge involves a 72-bit key.

Figure 2: Distributed.net focuses on cracking 72-bit encryption

Computing power has been growing fast, and we can see that if we estimate that a task, such as cracking a cipher, takes 2,500,000 million hours (or 285 years), takes less than one year after 17 years of computer advances:

Figure 3: Ever increasing computing power

Along with this we can apply parallel processing to break the task into smaller tasks and allocate each of the small task to each of our processors.

Figure 4: Using processing elements

So we can see that the usage of multiple processors significantly speeds up the cipher cracking process.

Cracking in the Cloud

Moore's Law predicted that computing power doubles every 18 months or so, so if we have a code which takes 100 years to crack, within 18 months, with the equivalent cost of a system, it will only take 50 years. To simplify things we must project that computing power doubles every year, so we find that a code which takes 100 years to crack, will, after 10 years, only takes a matter of weeks to crack (7 weeks). But the trend of improving hardware is now being overtaken by the Cloud, and the standard cryptography we have been using for years is now being push off-the-shelf.

The first to feel the heat is MD5, created by Ron Rivest, and has been a standard method for creating a digital fingerprint of data. It is used extensively in checking that data has not been changed and in providing identity. In the past it has been used to store hashed values of passwords, but its application in this area is reducing fast, as many of the common hashed MD5 values for words have been resolved.

One of the key things that is important for MD5 is that the different data does not produce a collision - where different data, especially in the same type of context does not produce the same hash signature. Mat McHugh showed that he could produce the same hash signature for different images, using hashclash, and for just 65 cents on the Amazon GPU Cloud, and took just 10 hours to process. For 10 hours of computing on the Amazon GPU Cloud, Mat created these two images which generate the same hash signature (Figure 5). If we check the hash signa-tures we get:

C:\openssl>openssl md5 hash01.jpg
MD5(hash01.jpg)= e06723d4961a0a3f950e7786f3766338

C:\openssl>openssl md5 hash02.jpg
MD5(hash02.jpg)= e06723d4961a0a3f950e7786f3766338

Figure 5 Application of one-way hashing

Creating a Supercomputer in your shed

Supercomputers such as the Cray 1 used to cost millions of dollars to purchase, in fact often companies could not afford to purchase them, and had to rent instead. The power of the public cloud showcases how quickly a supercomputer can be created when Amazon recently entered the Top 500 supercomputer list with a cluster which made it to 64th place. It ran at 0.5 Pflops (593.9 teraflop/s), and was created fully from standard high-powered instances in the Cloud. As it runs in the Cloud, it can be easily created and then ripped-down, and where the cost is based only on the usage of the cluster (typically on a per hour basis). Overall it had 26,496 cores with 106TB of memory - using c3.8xlarge instances with Intel Xeon processors.

The other move is to move away from complex and general purpose processors (such as Intel's Xeon processors) to use FPGAs ((Field Programmable Gate Arrays) which are designed and optimised on the processing problem. A good example of this is with bitcoin mining. In the diagram below we see graphics cards (GPUs) being used for cracking, but these consume a great deal of electrical power (Figure 6).

Figure 6: GPU cracker

Bitcoin miners, for example, often use FPGA which means that they are programmed with software to produce the required processing element, of which each processor focuses on the given task, such as in mining for bitcoins (Figure 6). FGPAs are less expensive to purchase and run than GPUs, and consume much less electrical power. If you have a look at the GPU array, you will see a fan to cool the chips, as it runs hot, and the hotter it gets the more electrical power it will consume.

The ASICMiner BE Prisma, for instance, can crack 1,400 Gigaahashes per second and costs just $600. Basically this hardware computes digest hashes, such as for SHA-256. It is the same methods used to crack hashed passwords.

Figure 7: FPGA cracker

Conclusions

The US lead has the lead the World in Computing, and still does. With the scaling of the cloud, many people have access to the equivalent of supercomputers, and their costs can be less than one hundred dollars per day. For scientists and engineers, there are still many issues which cannot be solve with traditional methods, and the next generator of super super computers will focus on these things. One thing that is sure, is that cryptography will be a "key" focal area.

So we're turning back the clock to the 1950s ... and building ... THE MAINFRAME ... but this time it is the most amazing mainframe ever ... The Cloud! 

Postscript

The computer in the lead graphic is a Cray 1 ... a supercomputer that didn't need to be cooled with air conditioning and that you could sit on. It cost over $8 million to purchase and had just 1MB of memory and ran at 160 MFlops. It also consumed over 100,000 Watts and weighed over 5 tons.

When I went to Washington to present a paper, one of the highlights on my visit was seeing a Cray 1 at the Smithsonian's National Air and Space Museum, and the "computer module" which flew to the moon. Here's my picture, taken in 2001, of the Cray (I couldn't sit on it though).  The second picture I took was of a 4Kbit magnetic memory array. It uses small magnetic toroids to stored data, arranged in 32-bit words. It was used up to 1982, which is three years after the IBM was first introduced.

The third graphic shows a magnetic memory which stored the program for an early Apollo mission. It's difficult to see from the picture, but there are long runs of wires which loop through the magnetic toroids. These days a single transistor takes-up less than a micron.