Introduction to Elliptic Curve Cryptography and Side Channel Attacks

Elliptic Curve Cryptography

In this article we provide an introduction to elliptic and hyperelliptic curve cryptosystems, which is one of the hot topic in computer data security. These are two important classes of public key cryptosystems, which can be implemented efficiently over a variety of platforms, starting right from small handheld devices like smart cards and mobile phones to large capacity work-stations. All known public key cryptosystems (PKC) derive their security from some computationally hard mathematical problems. The most popular ones are based mainly over two such problems:

1. Integer factorization problem,

2. Discrete logarithm problem.

The RSA cryptosystem is based on the hardness of integer factorization problem. Elliptic and hyperelliptic curve cryptosystems are based on discrete logarithm problem over their respective groups. Let G be a large cyclic multiplicatively written group with generator g.. Given any element y = gαin the group, computing α is called the discrete logarithm problem (DLP) over G
. Many groups have been proposed in literature over which the DLP is believed to be hard. Once such a group is fixed, an ElGamal type cryptosystem can be built over it.

In 1985, Koblitz and Miller independently proposed the set of elliptic curve points over a finite field to be used for cryptographic purposes. Prior to that, elliptic curves had a wide literature developed for over a century by mathematicians purely to satisfy their aesthetic sense. Only recently various applications of elliptic curves are being used in many applied areas like coding theory, number theoretic algorithms for integer factorization and primality testing and cryptography. The main advantage of elliptic curve cryptography is that for suitably chosen curves there is no known subexponential algorithm (like Number Field Sieve (NFS) algorithm for integer factorization) to solve ECDLP (elliptic curve discrete logarithm problem). This leads to smaller key length in comparison to other PKC’s like RSA and other systems based on DLP with equivalent security. The smaller key length, in turn, leads to faster encryption and decryption, savings in bandwidth and efficient implementation.

Thus ECC is a very suitable cryptosystem for resource constrained devices like smart cards and other mobile and wireless devices.

In 1987, Koblitz showed the Jacobians of hyperelliptic curves over finite fields to be a rich source of finite cyclic groups suitable for cryptographic use. Hyperelliptic curves are elliptic curves of higher genera. As with ECDLP, there is no known subexponential time algorithm to solve HCDLP for suitably chosen curve parameters (specifically for curves of lower genera). So hyperelliptic curve cryptosystems (HECC) have the same advantages as ECC. Moreover, in HECC the underlying finite field is smaller and there are many more curves to chose from. However, Addleman and Huang quickly showed that curves of higher genera are not suitable for cryptographic use.

Also, arithmetic in HECC is much more complex than that in ECC. Due to this inherent complexity in the group operations in the Jacobian of the hyperelliptic curves, HECC, with all its advantages has not yet been able to establish itself as a feasible commercial solution to current cryptographic needs. Several groups of researchers in different parts of the globe are working in this area in order to successfully employ hyperelliptic curves in the implementation of various cryptographic primitives.

Side-Channel Attacks

Initially, cryptanalysis was in the realm of mathematicians. The underlying computationally hard problems, which provide the security to each of the public key cryptographic schemes, pose a challenge to the genius of mathematicians. In 1996, Kocher [80] changed the cryptanalytic scenario. He extended cryptanalysis to application domain from the mathematical domain. In this path breaking work, he proposed side channel attacks (SCA). SCA instead of attacking the underlying hard problem, attacks the specific implementation by measuring and analyzing side channel information like timing, power consumption and electro-magnetic (EM) radiation traces of the computation. Side-channel attacks are believed to be the most potential threat to ECC and HECC, which are employed in hand-held mobile devices and used in hostile outdoor environments.

Thus modern security threat to ECC and HECC are two-fold: one based on the generic cryptanalytic attacks and the others based on side-channel attacks. The generic attacks can be avoided by carefully choosing the security parameters of the system, like the curve itself, the underlying field and its representation, the group order, the cofactor, the base point etc. Any naive implementation which neglects security aspects of these parameters can be broken by the generic attacks. For example, if the group order is large, but is divisible by only small primes, the DLP can be broken by Pohlig-Hellman attack.

The second threat to ECC and HECC is from side-channel attacks. As mentioned earlier, these were first proposed by Kocher in 1996. A stronger power based attack was proposed by Kocher et al . Many attacks based on analysis of side-channel information were proposed by various authors. Kocher, in his original work, had proposed timing attacks, which works on the basis of analysis of the timing of computation of various protocols in the system. Okeya and Sakurai observed that even if a system is secure against timing attacks, it may fail to withstand power attacks. In the authors have observed that systems secure against power analysis attacks may not be secure against EM based attacks. Goubin proposed a new attack based on naive choice of the base point. In the authors have discussed that fault analysis can be used for side-channel attacks and countermeasures.

To immunize a cryptosystem from SCA the various algorithms and protocols constituting the cryptosystem are to be designed carefully. Many proposals have come from the research community to immunize ECC and HECC against SCA. In the design of any cryptosystem, efficiency and security are two main concerns.

ΩΩΩ