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 crypto-
systems 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 implemen-
tation is running on a contemporary low-cost FPGA which allows for a much 
better cost-performance ratio than conventional CPUs. With the implement
ation 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.


BibTeX:
@InProceedings{I-GPP06,
  author =	 {T.E. G{\"u}neysu and C. Paar and J. Pelzl},
  title =	 "{On the Security of Elliptic Curve Cryptosystems
                  against Attacks with Special-Purpose Hardware}",
  booktitle =	 "{International Workshop on Special-Purpose Hardware
                  for Attacking Cryptographic Systems --- SHARCS'06,
                  Cologne, Germany}",
  year =	 {2006},
  address =	 {\url{http://www.sharcs.org}},
  month =	 {April}
}