Posted by: jonkatz | July 13, 2009

112-bit EC discrete logarithm problem solved

As recently announced on the cryptography mailing list, a discrete logarithm problem on an elliptic curve over a 112-bit prime field was recently solved using a cluster of over 200 PlayStation 3(!) game consoles. (The group order was also 112 bits.)

The computation was done using a parallelized version of Pollard’s rho method, with some speedups that they will describe in a forthcoming research paper.

Some things that struck me while reading the details:

  • The computational time was estimated to be only 3.5 months.
  • The computational effort was estimated to be 10^{18} additions/multiplications of 112-bit integers. This is significantly more than 2^{60} bit operations.
  • The computation required 0.6 Terabyte of disk space.
  • I could not find out the cost of the cluster, but 200 PlayStation 3 consoles would cost roughly $70,000.
  • By my calculations, they were carrying out roughly 2^{36} additions/multiplications of 112-bit integers per second.
  • They claim that the computational effort was equivalent to 14 brute-force key searches of DES. If true, that means that DES keys can be brute-forced in 1 week.

Of course, the natural question is what this means for elliptic curve parameters used in practice. They claim that for 160-bit prime fields the computation is expected to take 16 million times as long (and so there is no immediate threat). The current ECC standard uses 160-bit fields, though this is being phased out in favor of longer key lengths.

Advertisements

Responses

  1. Hi,

    Maybe it’s because I do not know the meaning of computational effort. But, to me the it translated that they needed 10^18 operations in total which divided by 105 days and 86400 seconds per day and 200 game consoles, means roughly 550 million operations per second per game console but not 10^36

    Am I right?

    Shahab

  2. Thanks. You are right; I meant 2^{36}.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: