D. J. Bernstein
Authenticators and signatures
nistp224

Cryptanalysis

The elliptic-curve discrete-logarithm problem

An attacker, given Alice's (28-byte or 56-byte) nistp224 public key, can try to figure out Alice's secret key. The fastest known method to compute Alice's secret key takes, on average, more than 2^111 elliptic-curve additions. (The method may succeed sooner: it has approximately 1% chance of success after 10% of the time, for example.)

As of October 2001, a general-purpose CPU costing $100 can perform nearly one million elliptic-curve additions per second. One billion CPUs, costing 100 billion dollars (never mind the wiring costs), can perform 2^111 elliptic-curve additions in roughly 100 billion years.

Special-purpose CPUs should be much faster. Furthermore, there are constant improvements in chip-building technology. But the cryptographic community would be astounded to see this computation actually carried out.

This computation is roughly 2^60 (a quintillion: a billion billion) times more difficult than the ECC2K-108 computation. The ECC2K-108 computation was a 109-bit characteristic-2 elliptic-curve discrete-logarithm computation. A team led by Robert Harley carried out the ECC2K-108 computation in time equivalent to a few hundred years on one CPU.

The elliptic-curve Diffie-Hellman problem

An attacker, given Alice's public key and Bob's public key, can try to figure out the secret shared between Alice and Bob. There is no method known to do this more quickly than computing one of the two secret keys.

The elliptic-curve hash Diffie-Hellman problem

The precise security property needed for a typical application of nistp224 is the following: an attacker, given Alice's public key and Bob's public key, has negligible probability of distinguishing SHA-256(s) from an independent uniform random 256-bit string. Here s is the secret shared between Alice and Bob.

There is no known distinguishing algorithm faster than computing one of the two secret keys.

Are there better attacks?

There are no known proofs of security for short-key cryptographic systems. It is always possible that a faster attack will be found.

In 1985, when Miller and Koblitz proposed elliptic-curve cryptography, it was already known how to compute 224-bit elliptic-curve discrete logarithms in time comparable to 2^111 elliptic-curve additions. Since then, there have been successful attacks on special classes of elliptic curves, but nothing relevant to random curves such as NIST P-224.