Researchers at the École Polytechnique Fédérale (EPFL) in Lausanne, Switzerland, have succeeded in cracking 112-bit encryption based on elliptical curves (ECCp-112). They calculated the secret key associated with a public key by solving the Discrete Logarithm Problem (DLP) for elliptical curves, which displays a complexity of 260 for the numbers involved. The cracked ECC system is a set of parameters defined by the secp112r1 standard. That puts it at the lower end of the specifications for ECC encryption systems.
The computation required around half a year on the EPFL cluster, consisting of some 200 PlayStation 3s that had already served to calculate the MD5 collision for creating a fake SSL issuer certificate from RapidSSL. The ECC code designed for the cell processor of the PlayStation 3 was optimised several times during the computation period, and the researchers say that, if the optimised code had been running from the start, the computation would only have taken three and a half months. The previous record was set in 2002, when a distributed cluster consisting of around 10,000 PCs cracked an ECC key within 549 days. At that time, researchers at Notre Dame University cracked an ECCp-109 key, three bits shorter than the new record.
Dr. Arjen Lenstra, who took part in the EPFL project, told heise Security that this result isn't actually a threat to the EC encryption systems used in practice. He said the weakest encryption encountered is based on 160-bit ECC and future developments in encryption standards would in any case have to be based on at least 224-bit ECC. According to the NIST transition proposal, ECCp-160, whose encryption strength is comparable with RSA-1024, must be replaced with a stronger variant after 2010 in order to obtain FIPS certification.
- PlayStation 3 computing breaks 2^60 barrier, 112-bit prime ECDLP solved, publication by the EPFL researchers