Abstract:
Cryptanalysis of symmetric and asymmetric ciphers is computationally 
extremely demanding. Since the security parameters (in particular 
the key length) of almost all practical crypto algorithms are chosen 
such that attacks with conventional computers are computationally 
infeasible, the only promising way to tackle existing ciphers 
(assuming no mathematical breakthrough) is to build special-purpose 
hardware. Dedicating those machines to the task of cryptanalysis holds
the promise of a dramatically improved cost-performance ratio so that 
breaking of commercial ciphers comes within reach. 

This contribution presents the design and realization of the COPACOBANA 
(Cost-Optimized Parallel Code Breaker) machine, which is optimized for 
running cryptanalytical algorithms and can be realized for less than 
US$ 10,000. It will be shown that, depending on the actual algorithm, 
the architecture can outperform conventional computers by several 
orders in magnitude. COPACOBANA hosts 120 low-cost FPGAs and is
able to, e.g., perform an exhaustive key search of the Data Encryption 
Standard (DES) in less than nine days on average. As a real-world 
application, our architecture can be used to attack machine readable
travel documents (ePass). COPACOBANA is intended, but not necessarily 
restricted to solving problems related to cryptanalysis.

The hardware architecture is suitable for computational problems which 
are parallelizable and have low communication requirements. The 
hardware can be used, e.g., to attack elliptic curve cryptosystems and 
to factor numbers. Even though breaking full-size RSA (1024 bit or more) 
or elliptic curves (ECC with 160 bit or more) is out of reach with 
COPACOBANA, it can be used to analyze cryptosystems with a 
(deliberately chosen) small bitlength to provide reliable security 
estimates of RSA and ECC by extrapolation.

Even more relevant is the fact that resource constrained applications, 
in particular mobile devices, sometimes settle with shorter parameters, 
such as the 112 bit and 128 bit ECC systems recommended by the SECG 
standard, which become vulnerable with our machine. Also, assuming 
Moore's law, we can predict the security margin of RSA and ECC in the 
years to come. 


BibTeX:
@InProceedings{I-KPPPS06,
author = {S. Kumar and C. Paar and J. Pelzl and G. Pfeiffer and M. Schimmler},
title = "{Breaking Ciphers with COPACOBANA - A Cost-Optimized Parallel Code Breaker}",
booktitle  = "{Cryptographic Hardware and Embedded Systems - CHES 2006, 8th International Workshop, 
              Yokohama, Japan, October 10 - October 13, 2006, Proceedings}",
pages = {},
year = {2006},
editor = {},
volume = {},
series = {LNCS},
month = {October},
publisher = {Springer-Verlag}
}