COPACOBANA

A Codebreaker for DES and other Ciphers

A description of the hardware architecture and potential (and partially realized) implementations of COPACOBANA can be found in the papers and slides below.

documents

Cryptanalysis with COPACOBANA
Transactions on Computers, Nov. 2008, Volume 57, pp. 1498-1513.

Full paper: TC_COPACOBANA.pdf


Cryptanalysis of ciphers usually involves massive computations. The security parameters of cryptographic algorithms are commonly chosen so that attacks are infeasible with available computing resources. Thus, in the absence of mathematical breakthroughs to a cryptanalytical problem, a promising way for tackling the computations involved is to build special-purpose hardware exhibiting a (much) better performance-cost ratio than off-the-shelf computers. This contribution presents a variety of cryptanalytical applications utilizing the Cost-Optimized Parallel Code Breaker (COPACOBANA) machine, which is a highperformance low-cost cluster consisting of 120 field-programmable gate arrays (FPGAs). COPACOBANA appears to be the only such reconfigurable parallel FPGA machine optimized for code breaking tasks reported in the open literature. Depending on the actual algorithm, the parallel hardware architecture can outperform conventional computers by several orders of magnitude. In this work, we will focus on novel implementations of cryptanalytical algorithms, utilizing the impressive computational power of COPACOBANA. We describe various exhaustive key search attacks on symmetric ciphers and demonstrate an attack on a security mechanism employed in the electronic passport (e-passport). Furthermore, we describe time-memory trade-off techniques that can, e.g., be used for attacking the popular A5/1 algorithm used in GSM voice encryption. In addition, we introduce efficient implementations of more complex cryptanalysis on asymmetric cryptosystems, e.g., Elliptic Curve Cryptosystems (ECCs) and number cofactorization for RSA. Even though breaking RSA or elliptic curves with parameter lengths used in most practical applications is out of reach with COPACOBANA, our attacks on algorithms with artificially short bit lengths allow us to extrapolate more reliable security estimates for real-world bit lengths. This is particularly useful for deriving estimates about the longevity of asymmetric key lengths.


Enhancing COPACOBANA for Advanced Applications in Cryptography and Cryptanalysis, Sep. 2008 (FPL, Heidelberg, Germany)

Full Paper: FPL08_COPACOBANAv2.pdf
Poster: COPA_V2_A0.pdf

Cryptanalysis of symmetric and asymmetric ciphers is a challenging task due to the enormous amount of involved computations. To tackle this computa- tional complexity, usually the employment of special-purpose hardware is considered as best approach. We have built a massively parallel cluster system (COPACOBANA) based on low-cost FPGAs as a cost-efficient platform primarily targeting cryptanalytical operations with these high computational efforts but low communication and memory requirements. However, some parallel applications in the field of cryptography are too complex for low-cost FPGAs and also require the availability of at least moderate communication and memory facilities. Particularly, this holds true for arithmetic intensive application as well as ones with a highly complex data flow. In this contribution, we describe a novel architecture for a more versatile and reliable COPACOBANA capable to host advanced cryptographic applications like high-performance digital signature generation according to the Elliptic Curve Digital Signature Algorithm (ECDSA) and integer factorization based on the Elliptic Curve Method (ECM). In addition to that, the new cluster design allows even to run more supercomputing applications beyond the field of cryptography.


Cryptanalysis with a cost-optimized FPGA cluster
University of California, Los Angeles (UCLA), USA, Institute for Pure and Applied Mathematics (IPAM)

Slides: IPAM2006_slides.pdf

Presentation of the COPACOBANA architecture, applications and possible future work.


Getting Started Guide

The Getting Started guide briefly explains parts of the hardware, shows how to use COPACOBANA and how to build custom applications.

Breaking Ciphers with COPACOBANA - A Cost-Optimized Parallel Code Breaker
(CHES 2006, Yokohama, Japan)

Full paper: CHES2006_paper.pdf
Slides: CHES2006_slides.pdf

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


Exact Cost Estimates for Attacks on ECC with Special-Purpose Hardware
(ECC 2006, Toronto, Canada)

Slides: ECC2006.pdf.

Abstract: The utilization of Elliptic Curves (EC) in cryptography is very promising because of their resistance against powerful index-calculus attacks. Providing a similar level of security as RSA, ECC allows for efficient implementation due to a significantly smaller bit size of the operands. It is widely accepted that the only feasible way to attack actual cryptosystems, if at all, is the application of dedicated hardware. In times of continuous technological improvements and increasing computing power, the question of the security of ECC against attacks based on special-purpose hardware arises.
This talk presents an overview of hardware-based attacks against (generic) ECC over binary and prime fields. An architecture and the corresponding FPGA implementation of an attack against ECC over prime fields will be discussed in detail. The multi-processing hardware architecture is based on the Pollard-Rho method which is, to our knowledge, currently the most efficient attack against ECC. With a proof-of-concept implementation on an FPGA, a fairly accurate estimate about the cost of a hardware-based attack against ECC with current bit lengths can be given.


Kryptanalyse: Wie sicher ist Kryptographie?
(iX Magazine 10/2006, Heise Verlag, Germany)

Full article: copacobana_ix102006.pdf.


How to Break DES for 8,980 Euro
(SHARCS 2006, Cologne, Germany)

Full paper: copacobana_SHARCS2006.pdf.

Abstract: This contribution describes the design and realization of the reprogrammable machine COPACOBANA (Cost-Optimized Parallel Code Breaker), which is optimized for running cryptanalytical algorithms. The primary design goal was to produce a re-programmable low-cost design for less than Euro 10,000 which is applicable for attacking the Data Encryption Standard (DES) in less than nine days.
It will be shown that the architecture outperforms conventional computers by several orders of magnitude. Fully configured, COPACOBANA hosts 120 low-cost FPGAs and is able to perform an exhaustive key search of DES at a rate of more than 2^{35} keys per second, yielding an average search time of less than nine days. For this, we used the high-speed DES engine design of the Universite Catholique de Louvain's Crypto Group.
We provide a real-world example by giving an estimate of an attack with COPACOBANA against a formerly popular encryption tool (Norton Diskreet). Due to a cryptographical weak key derivation function it can be broken in very little time by applying a smart key search. As a further application, COPACOBANA can also be used to attack machine readable travel documents (ePass).
COPACOBANA 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. COPACOBANA is intended to, but not necessarily restricted to solving problems related to cryptanalysis.


On the Security of Elliptic Curve Cryptosystems against Attacks with Special-Purpose Hardware
(SHARCS 2006, Cologne, Germany)

Full paper: mppr_SHARCS2006.pdf.

Abstract: Since their invention in the mid 1980s, Elliptic Curve Cryptosystems (ECC) have become an alternative to common Public-Key (PK) cryptosystems such as, e.g., RSA. The utilization of Elliptic Curves (EC) in cryptography is very promising because of their resistance against powerful index-calculus attacks. For a similar level of security, ECC allows for efficient implementation due to a significantly smaller bit size of the operands. It is widely accepted that the only feasible way to attack actual cryptosystems is the application of dedicated hardware. In times of continuous technological improvements and increasing computing power, the question of the security of ECC against attacks based on special-purpose hardware arises.
This work presents an architecture and the corresponding FPGA implementation of an attack against ECC over prime fields. We describe an FPGA-based multi-processing hardware architecture for the Pollard-Rho method which is, to our knowledge, currently the most efficient attack against ECC. The implementation is running on a contemporary low-cost FPGA which allows for a much better cost-performance ratio than conventional CPUs. With the implementation at hand, a fairly accurate estimate about the cost of an FPGA-based attack can be given. We will project the results on actual ECC key lengths (160 bit and above) and estimate the expected runtimes for a successful attack. Since FPGA-based attacks are out of reach for actual key lengths, we provide estimates for an ASIC design.
As a result, we consider ECC over over prime fields to be far more secure than commonly believed. We show that the security of ECC-163 against hardware attacks is several orders of magnitude harder than that of RSA-1024. As a consequence, currently used elliptic curve cryptosystems are infeasible to break with available computational and financial resources.