/* */

06 November 2007

Home-brewed, open source cryptanalysis

Among the odder developments created by the inevitable trends in Moore’s Law of increasing computing power (at ever cheaper price points) has been the feasibility of private cryptanalysis capabilities functioning at effectiveness which only a few years ago would likely have been possible solely with the resources of the nation state.

These bootstrapped rigs as a rule tend to emphasize the lowest possible cost configurations – a natural consideration given that most are assembled on a shoestring budget by university researchers or other computer sciences academic types. They have been assembled for diverse purposes of privacy advocacy, systems research, and some simply for the sheer technical interest of the thing.

We particularly like the COPACOBANA system, a FGPA based parallel computing design optimized to attack symmetric ciphers, created entirely using commercial off the shelf components. The system can typically identify DES keys within less than a week of effort, at a cost of about $10,000 per machine. The now obsolete Data Encryption Standard cipher was a widely used algorithm between its approval in 1977 and its withdrawal in 2002, and remains in use in some legacy systems in the commercial environment to this day. A stronger derivative algorithm, 3DES, also remains more commonly in use in some applications, with end of life projected to 2030. DES did have a good long run, having survived the public disclosure of the previously secret technique of differential cryptanalysis to which it might have been vulnerable, had NSA and IBM not supposedly collaborated on a stronger implementation during its development phases. An earlier custom built FGPA rig - DeepCrack – was built to attack the cipher successfully, but at a cost of nearly a quarter million dollars.

These cryptanalysis systems may be jury rigged, but they are undeniably effective – and cheap. And more powerful implementations are no doubt easily within the budgets of smaller nation-states, if not wealthy non-state actors.

However, it is the development of the alternative track of home-brewed cryptanalysis that gives us pause. One competitor in the attack against the DES cryptosystem was a distributed computing network that relied on the contributions of unused capacity from volunteers’ personal boxen. The DESCHALL project achieved its successful break using 78,000 contributors over the course of three months. The project demonstrated the architecture – more advanced attacks are mostly a matter of optimization and scale.

It is from this that we begin to ponder our greater concerns. The development of very large scale botnets, made up of aggregated collections of individual systems compromised by malware, offer far greater potential computing capacity – both an individual basis per processor as well as in overall numbers of contributing systems. The widely discussed STORM botnet remains perhaps the largest of such malicious aggregates that has publicly identified. While exact numbers remain subject to debate, STORM is believed to consist of up to 50 million individual systems. And while recent indicators are that the botnet is being sub-divided into smaller segments for illicit commercial sale, this kind of capacity in the hands of non-state actors is truly revolutionary. Its potential applications to home-brewed cryptanalysis are clear.

Interestingly enough, the STORM botnet also appears to itself utilize encryption in order to secure its own control communications, and to permit more effective illicit commercialization. (Although surprisingly not a GOST standard cipher). The use of STORM, or the application of similar very large scale capabilities, to the flip side of the cryptographic equation is surely not far off.

If nothing else, it is good reason to accelerate those academic intelligence studies that might have an interest in cryptanalysis.

Labels: , , , ,