"High Performance Computing" is traditionally the purview of universities, governments and Big Science. The difference between what most people have at home and high-performance computing (HPC) is the difference between bicycles and the space race.
But the scene has been changing for quite some time. Clusters of cheap desktops running Linux and one or another parallel-computing software interfaces were the first to come. A showcase example was Oak Ridge National Labs "Stone Souper Computer", put together from surplus PCs and components that would otherwise have been thrown away. It was used for real work, doing the computational heavy lifting for several ecological modeling projects. Over time clustering became the primary means of acheiving high performance. A quick look at the TOP500 list shows just how prevalent clustering is.
Over the last few years, multicore CPUs have expanded this in a somewhat new direction. First, by doubling or quadrupling the number of CPU cores in a computing node, and later by adding highly-parallel processors to the clusters. By highly-parallel, I refer to the TOP500's current #1 supercomputer, the Roadrunner, which combines standard multicore AMD Opteron processors (sibling to the Athlon 64 processors common in desktop computers) with IBM PowerXCell processors, which are a slightly modified version of the Cell processor that powers every Sony Playstation3. The PowerXCell features one normal PowerPC processor, and 8 "Synergistic Processing Engines," essentially smaller sub-processors which focus on simple parallelizable tasks.
With the recent attention of the HPC market seeing the utility of many small, simple processing cores, many turned their attention to modern graphics processing units (GPUs). Modern GPUs contain dozens or even hundreds of small processing pipelines, optimized for the types of math and operations that 3D graphics require. As time progressed, these 3D graphics, especially games, required more complex computation, to such a degree that each of the pipelines started to resember a general purpose, if graphics-optimized, CPU.
Soon, hobbyists and programmers started taking advantage of this, programming their GPUs to perform computations that would normally run on a CPU. By moving the highly-parallel parts of their computation to the GPU, they could perform dozens of operations in the time that a single CPU could do one.
ATI (now AMD) and nVidia smelled money. ATI released some of their low-level programming interfaces, and a set of software extensions that allowed programmers easier access to the GPU. nVidia developed a whole programming language called CUDA, that allows developers to write C code directly for their GPUs. Now nVidia even has a version of their most powerful graphics card, with all the graphics hardware removed. Called "Tesla", it's a pure computation engine. You can fill your PC with as many Tesla cards as you have slots to stick 'em in. They have dedicated chassis full of Tesla cards with dedicated high-performance connections to PCs. Tokyo Tech University has begun adding Tesla units to their Tsubame supercomputer. The US National Center for Atmospheric Research has begun testing Tesla for accelerating particularly obnoxious computation, and found significant gains.
And really, this is sort of taking us full circle. Some of the dead technological offshoots in computing's past looked in this direction. Many hundreds, even thousands of small processors were used in the Connection Machines computers, each processor being only one bit wide. INMOS developed a radically different type of computing with their transputer, each chip a small microprocessor with a small amount of RAM and several inter-transputer network links, they were designed from the ground up as massively parallel computing engines.
The Connection Machines started with the ideas introduced in variable-width "bit-slice" processors of their predecessors, and took them to their logical extreme: A machine an arbitrary number of bits wide, and code-reconfigurable. It proved to be unsuccessful in implementation, though. With their 5th generation CM-5, Connection Machines designed a large parallel machine powered by up to 512 Sun SPARC processors
The INMOS Transputer is the evolutionary forebear to today's massively parallel supercomputers, though. Each transputer was a small processor, memory and enough glue logic to allow the device to stand mostly on its own. With network links to multiple other transputers on the same board, in the same case, or even spread throughout multiple cases, a cluster of transputers could appear to be a single virtual system, with individual threads running on each transputer. It was only ahead of its time in so far as there was a great deal of headroom left in getting higher performance out of traditional computing, and programming for parallel computing is hard.
Today, the modern single-threaded microprocessor has hit a performance barrier. Power requirements and the laws of decreasing returns have made it difficult to wring higher performance out of more transistors and higher clockspeeds. To improve returns on Moore's Law, today's CPU makers divided their transistor budget across two or more fully functional CPU cores on a single die. Dual-core CPUs are commonplace, and quad-core CPUs are about to become so, as well.
With the ubiquity of multicore computing and the aforementioned implicitly parallel nature of graphics processing, parallel programming has been thrust into the forefront of development. In order to achieve adquate performance for any demanding task, developers now must parallelize their computing tasks. What was a good idea in hardware, and optional in software before, has become ubiquitous in hardware, and required in software now.
Friday, January 2, 2009
Wednesday, December 31, 2008
MD5 considered harmful... Update
Some updates after closer reading of the research material:
First: This is somewhat more dangerous than I first thought, because a bogus certificate that appears to be signed by a valid CA will by happily accepted by browsers regardless of which CA signed the valid cert used by the valid server.
Say John usually accesses his bank, Big Mutual bank at bigmu.com. John receives a phishing email that takes him to bigmu.net instead. The name is similar, and heck, he even sees the little lock icon, telling him he's got a good SSL connection, so the certificate is good, right? Wrong, the certificate is bogus, signed by a fake intermediate CA, that appears to be signed by a valid CA, but it's not the same CA that bigmu.com normally uses. That doesn't matter, because the browser doesn't know or care who bigmu.com's CA usually is. (And even if it did, bigmu.com isn't bigmu.net, so it wouldn't associate them anyway) All it cares about is a valid certificate and a good SSL connection, and it lights up the lock icon, make the user feel happy and shiny.
Second: I didn't really talk enough about the resources required to craft the bogus certs. This has only been tested with one CA, that happens to not only hash with MD5 and uses sequential serial numbers for their certs. It took them several attempts over the space of four weekends to get certs with the desired serial number and validity period. The various attempts cost over $650 in payments to the root CA. Of course, once they've got that cert on precious intermediate CA cert, they can sign all they want for whoever they want...
First: This is somewhat more dangerous than I first thought, because a bogus certificate that appears to be signed by a valid CA will by happily accepted by browsers regardless of which CA signed the valid cert used by the valid server.
Say John usually accesses his bank, Big Mutual bank at bigmu.com. John receives a phishing email that takes him to bigmu.net instead. The name is similar, and heck, he even sees the little lock icon, telling him he's got a good SSL connection, so the certificate is good, right? Wrong, the certificate is bogus, signed by a fake intermediate CA, that appears to be signed by a valid CA, but it's not the same CA that bigmu.com normally uses. That doesn't matter, because the browser doesn't know or care who bigmu.com's CA usually is. (And even if it did, bigmu.com isn't bigmu.net, so it wouldn't associate them anyway) All it cares about is a valid certificate and a good SSL connection, and it lights up the lock icon, make the user feel happy and shiny.
Second: I didn't really talk enough about the resources required to craft the bogus certs. This has only been tested with one CA, that happens to not only hash with MD5 and uses sequential serial numbers for their certs. It took them several attempts over the space of four weekends to get certs with the desired serial number and validity period. The various attempts cost over $650 in payments to the root CA. Of course, once they've got that cert on precious intermediate CA cert, they can sign all they want for whoever they want...
MD5 considered harmful NOW.
Yesterday, a significant attack against MD5-hashed X509 certificates was announced.
http://www.win.tue.nl/hashclash/rogue-ca/
It exploits existing known weaknesses of MD5 to certain collision attacks to create bogus X509 certificates. The researchers were even able to create bogus X509 CA certs, thus breaking the chain of trust for X509 certificates.
X509 certificates are used for establishing trust and authentication in SSL communication, as well as many types of encrypted email, VPN authentication, 802.1x authentication, etc. With the new attack, someone can create fake certificates that look perfectly valid to the party attempting to verify that they're talking to someone they trust. Certification Authorities (CAs) are trusted third-parties who verify that an entity is who they say they are, and issue certificates for entities to use, saying "This server that you're talking to, named server-x belongs to this entity-y, signed CA-z".
Every hash algorithm has collisions. When you're boiling down an arbitrary amount of data into a short, fixed length signature, it's going to happen eventually that some other chunk of data will end up with the same signature. The problem is when someone learns how to make a piece of data collide with another piece of data on purpose. Especially if they can make their own fake X509 certificate look like it was signed by a trusted authority, when in reality, it wasn't.
So this attack is doubly bad... an attacker using this method can not only create fake certificates, they can create fake CA certificates which can then be used to sign other fake certificates, and look just like a trusted CA.
How bad is this? Well, it's not as immediately bad as it seems. First, the attack took quite a bit of hardware and time. 200 PS3s and a high-end multi-CPU PC took about 24 hours for each successful attempt. Clearly, this is a lot of CPU time. However, it's not infeasible to do it with a distributed search spread across a few hundred collaborating PCs (such as a botnet or a zombie army) or a similarly constructed cluster.
Secondly, it doesn't allow anyone to actively attack you just yet. It allows them to masquerade as someone you trust, though. A phishing attempt with a valid but fake Wamu.com SSL cert would certainly appear more trustworthy.
The short term fix for you and me is to be yet again more careful of what we click on. The long term fix is for CAs to stop issuing MD5 certs, stop using MD5 internally, etc. Heck, they could even make the effort of revoking their MD5 CA certs and re-issuing with SHA1 or better. Buyers of certs from CAs (and folks who self-sign their own) must stop using MD5.
Now, there's known weaknesses in SHA1, too. It's weak enough that the NIST will no longer permit it for government use in 2010. It's still several orders of magnitude stronger than MD5, though. Better to be safe, though, and require SHA256 or SHA512.
http://www.win.tue.nl/hashclash/rogue-ca/
It exploits existing known weaknesses of MD5 to certain collision attacks to create bogus X509 certificates. The researchers were even able to create bogus X509 CA certs, thus breaking the chain of trust for X509 certificates.
X509 certificates are used for establishing trust and authentication in SSL communication, as well as many types of encrypted email, VPN authentication, 802.1x authentication, etc. With the new attack, someone can create fake certificates that look perfectly valid to the party attempting to verify that they're talking to someone they trust. Certification Authorities (CAs) are trusted third-parties who verify that an entity is who they say they are, and issue certificates for entities to use, saying "This server that you're talking to, named server-x belongs to this entity-y, signed CA-z".
Every hash algorithm has collisions. When you're boiling down an arbitrary amount of data into a short, fixed length signature, it's going to happen eventually that some other chunk of data will end up with the same signature. The problem is when someone learns how to make a piece of data collide with another piece of data on purpose. Especially if they can make their own fake X509 certificate look like it was signed by a trusted authority, when in reality, it wasn't.
So this attack is doubly bad... an attacker using this method can not only create fake certificates, they can create fake CA certificates which can then be used to sign other fake certificates, and look just like a trusted CA.
How bad is this? Well, it's not as immediately bad as it seems. First, the attack took quite a bit of hardware and time. 200 PS3s and a high-end multi-CPU PC took about 24 hours for each successful attempt. Clearly, this is a lot of CPU time. However, it's not infeasible to do it with a distributed search spread across a few hundred collaborating PCs (such as a botnet or a zombie army) or a similarly constructed cluster.
Secondly, it doesn't allow anyone to actively attack you just yet. It allows them to masquerade as someone you trust, though. A phishing attempt with a valid but fake Wamu.com SSL cert would certainly appear more trustworthy.
The short term fix for you and me is to be yet again more careful of what we click on. The long term fix is for CAs to stop issuing MD5 certs, stop using MD5 internally, etc. Heck, they could even make the effort of revoking their MD5 CA certs and re-issuing with SHA1 or better. Buyers of certs from CAs (and folks who self-sign their own) must stop using MD5.
Now, there's known weaknesses in SHA1, too. It's weak enough that the NIST will no longer permit it for government use in 2010. It's still several orders of magnitude stronger than MD5, though. Better to be safe, though, and require SHA256 or SHA512.
Subscribe to:
Posts (Atom)