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.
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.