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 additions/multiplications of 112-bit integers. This is significantly more than 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 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.