[HGI-News] HGI-Seminar, Montag 15.05.06: Efficient Hardware Architectures for Solving the DLP on EC

[Newsletter des Horst Görtz Instituts]

                   Tim Güneysu, COSY-Group, RUB

           Montag 15. Mai 2006, 13:15 Uhr IC 4 / 39-41

         Efficient Hardware Architectures for Solving the
          Discrete Logarithm Problem on Elliptic Curves


The utilization of Elliptic Curves (EC) in cryptography is very promising
due to their resistance against powerful index-calculus attacks. Since
their invention in the mid 1980s, Elliptic Curve Cryptosystems (ECC) have
become an alternative to common Public Key (PK) cryptosystems such as RSA.
With a significantly smaller bit size, ECC provides similar security than
other PK systems (e.g. RSA). The effort of breaking a cryptosystem mainly
defines its security. Hence, a ”secure” cryptosystem will most likely not
be broken within the next decades even if we take technological progress
into account. As a consequence, conventional attacks based on software
implementations of cryptanalytical algorithms will most probably never
succeed in breaking actual ciphers. It is widely accepted, that the only
feasible way to attack such cryptosystems is the application of dedicated
hardware.

In times of improved hardware manufacturing and increasing computational
power, the issue arises how secure the small key lengths of ECC are, facing
a massively parallel attack based on special-purpose hardware. This is the
first work presenting an architecture and an FPGA implementation of an
attack on ECC. We present an FPGA based multi-processing hardware
architecture for the Pollard-Rho method for EC over GF(p) which is, to
our current knowledge, believed to be the most efficient attack against
ECC. The implementation is running on a conventional low-cost FPGA as it
can be found, e.g., in the parallel code breaker machine COPACOBANA. The
latter provides a parallel cluster of FPGAs, providing a large quantity of
computational power.

Furthermore, we will project the results on actual ECC key lengths (e.g.
k = 160 bit) and estimate the expected runtimes for a successful attack.
Since FPGA-based attacks are out of reach for such key lengths, we present
estimates for an ASIC design. As a result, ECC over GF(p) and bit sizes
of k > 160 can be considered to be infeasible to break with current
algorithms as well as computational and financial resources.


_____________________________________________________________________________
Die Webseite des HGI-Seminars mit allen Informationen zu vergangenen und
zukünftigen Vorträgen: http://www.hgi.rub.de/deutsch/lehrangebot/seminar.html