Tala Blog

Simple ECC implementations and a Simple Approach to Side Channel Attacks

Rajesh Kanungo - Nov 14, 2017 10:11:00 AM

Side channel attacks as defined in the Wikipedia:

In cryptography, a side-channel attack is any attack based on information gained from the physical implementation of a cryptosystem, rather than brute force or theoretical weaknesses in the algorithms (compare cryptanalysis). For example, timing information, power consumption, electromagnetic leaks or even sound can provide an extra source of information, which can be exploited to break the system. Some side-channel attacks require technical knowledge of the internal operation of the system on which the cryptography is implemented, although others such as differential power analysis are effective as black-box attacks.

We have known for some time that Elliptical Curve Cryptography is pretty good but quantum computers may break them.

However, breaking simple implementations of Elliptical Curve crypto systems are far easier ...

First the analogy: 


You see a billiard ball in the center of the table.  You leave the table and I hit it against the opposite side and it bounces back and forth in a straight line and comes and rests along the line somewhere.  Your job is to guess the number of bounces. 

Well, what you can do is just listen in the adjacent room to the sounds and you can at once “deduce” the number of bounces.  You have your answer. 

A finite field is, first of all, a set with a finite number of elements. An example of finite field is the set of integers modulo p, where p is a prime number. It is generally denoted as ℤ/pZp, GF(p), GFp, or Fp.

The elliptical curve is:  y**2 = x**3 + ax +  b  where 4a**3 + 27b**2 ≠ 0

Now the real crypto side channel attack: 

The elliptical curve is:  y**2 = x**3 + ax +  b  where 4a**3 + 27b**2 ≠ 0

k is a random number and is considered the private key.

P is a point on the curve and is the generator.

  Q = (k.P) mod n  where n is a prime and Q and P are points on the Finite field curve, Fp. 

This is not simple math, it is group theory. The trick is to guess k even though P and Q are known.  The way you get Q is by adding P to itself k -1 times and doing a modulo on it.  Now, anyone looking at the RF signal, the energy consumption, etc. can quickly determine how many times the addition took place. We have just recovered the ECC private key.  Done. 

Almost all public domain software has this flaw. 

A well implemented ECC implementation will make sure the eavesdropper can't use side channel analysis to deduce what the key is.

You might read:


Previous Post

Crypto Armageddon: NSA says current asymmetric key algorithms are susceptible to quantum computing attacks in the near future with no alternatives.

Next Post

Secure Code: Why and How to get your teams to write secure code