Known Attacks against Elliptic Curve Cryptosystems

6.5.5Known Attacks against Elliptic Curve Cryptosystems

1. 
   Naive Exhaustive Search: The most simple approach to obtain is to compute successive multiples of until the result is equal to . In the worst case, this takes steps, where is the order of the point .
   

2. 
   Baby-Step Giant-Step Algorithm: This algorithm is a time-memory trade-off of the method of exhaustive search. It requires storage for about points, and its running time is roughly steps in the worst case.
   

3. 
   Pollard's Rho Algorithm: This algorithm is a randomized version of the baby step giant-step algorithm. With some modifications it can be sped up to have an expected running time of steps and it requires only a negligible amount of storage.
   

4. 
   Parallelized Pollard's Rho Algorithm: The original Pollard's rho algorithm can be parallelized so that when it is run in parallel on processors, the expected running time is roughly
   

5. 
   Pollard's Lambda Method: Pollard also presented a lambda method for computing discrete logarithms which is applicable when, the logarithm sought, is known to lie in a certain interval. In particular, when is known to lie in a subinterval , where , the parallelized version of Pollard's lambda method is faster than the parallelized Pollard's rho algorithm.
   

6. 
   Multiple Logarithms: It turns out that if a single instance of the ECDLP is solved using (parallelized) Pollard's rho method, the following instances (for the same curve and the same base point ) can be solved faster, since some of the necessary work has already been done in the previous steps. In fact, solving k instances of the ECDLP takes only as much work as it does to solve one instance.
   

Hence, the best known attack against a single instance of the ECDLP is Pollard's rho algorithm and has an expected running time of , which is fully exponential.

1. 
   Pohlig-Hellman Algorithm: This algorithm exploits the factorization of , the order of the point , and reduces the problem of recovering to the problem of recovering modulo each of the prime factors of . We can then recover by using the Chinese Remainder Theorem. As a countermeasure, one should select an elliptic curve whose order is a prime or almost a prime (i. e. a large prime times a small integer).
   

2. 
   Supersingular Elliptic Curves: In some cases, the ECDLP in an elliptic curve defined over a finite field can be reduced to the ordinary discrete logarithm problem (DLP) in the multiplicative group of some extension field for . The DLP is the underlying computationally hard mathematical problem for the DSA and one can solve it using the number field sieve algorithm, which has a subexponential running time. To ensure that the reduction algorithm does not apply to a particular curve, one only needs to check that does not divide for all small for which the DLP in is tractable. In practice, it suffices to check this for when .
   

3. 
   Prime-Field Anomalous Curves: If the number of points on a curve E over is equal to , the ECDLP can be solved efficiently. This attack can be avoided by verifying that the number of points on an elliptic curve is not equal to the cardinality of the underlying field.
   

4. 
   Curves Defined Over a Small Field: For elliptic curves with coefficients in , Pollard's rho algorithm for computing elliptic curve logarithms in can be further sped up by a factor of . For example, if is a Koblitz curve, then Pollard's rho algorithm for computing elliptic curve logarithms in ) can be sped up by a factor of .
   

5. 
   Curves Defined Over , Composite: The Weil descent might be used to solve the ECDLP for elliptic curves defined over where is composite. There exists some evidence that when has a small divisor , e.g. , the ECDLP can be solved faster than with Pollard's rho algorithm. Thus, elliptic curves over composite fields should not be used.
   

Let us take a look how secure elliptic curve cryptography is in practice. Certicom challenge is one source that gives a notion about the security of ECC. The challenge is to compute the ECC private keys from a given list of ECC public keys and associated system parameters. The challenge consists of two levels:

• 
  Level I: 109-bit and 131-bit challenge; considered to be feasible
  
• 
  Level II: 163-bit, 191-bit, 239-bit and 359-bit challenge; expected to be computationally Infeasible
  

Concrete recommendations based on the expected cost of the Certicom challenge have been presented. They predict which elliptic curve key sizes can be considered as secure until which year using a model that incorporates technological and cryptanalytical advances. Table presents their recommendations for future years.