HW3: Elliptic Curve Information Leakage

CS 463, Dr. Lawlor

There's a serious problem with this function from my Elliptic Curve Crypto Library (see "ecc_lib.cpp" in bigint_OSL.zip/tar-gzip)

// Multiply us by this scalar, under the action of this curve.
ECpoint ECpoint::multiply(BigInteger scalar,const ECcurve &curve) const
{
	ECpoint sum=ECpoint::infinity; 
	ECpoint A=*this;
	for (int bit=0;scalar!=0;bit++) {
		if ( bi_is_odd(scalar.get()) ) // this bit is set--include value in sum
			sum=sum.add(A,curve); // do sum+=A;
		
		scalar = scalar/2; // shift right by 1 bit
		if (scalar!=0) // more data is available
			A=A.add(A,curve); // shift A up to next bit (A+=A)
		// possible optimization: save the table of A values...
	}
	return sum;
}

This function runs much faster when multiplying by a small scalar than when multiplying by a big scalar. On my machine, multiplying by 0 takes 80 nanoseconds; while multiplying by 0xffffff (a 24-bit value) takes 27 million nanoseconds! Because each bit costs about a millisecond, and millisecond-level timing information is pretty easy to observe over a local network, an attacker might be able to recover a 512-bit key using as few as 512 message exchanges (these could be generated as, for example, innocent-looking attempts to create an ECDSA signature).

For this assignment, simply modify the bigint_OSL/ecc_lib.cpp multiply function so its timing varies by no more than a few milliseconds (on your computer), for any scalar up to 32 bits in size. Turn in your modified source code, and a very short README.txt file listing your general approach and the new timing information. Due date is Monday, April 29 (postponed due to NCCDC and SpringFest).