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.

## 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}$.