__mul__ leaks timing information?

[mehitabel]

The current implementation of mul leaks timing information, I suggest modifying it to use montgomery multiplication:

def bits(n): b = [] while n > 0: b.append(n % 2) n >>= 1 return reversed(b)

def mul(self, n): a, b = IDENTITY, self for x in bits(n): if x == 0: a, b = a + a, a + b else: a, b = a + b, b + b return a

Now regardless of the binary expansion of the exponent at each stage you will do one addition and one doubling.

http://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Montgomery_ladder

[mehitabel]

I'd submit a PR but I don't see how you represent the identity element.

[bwesterb]

Thank you for your interest in py-seccure.

Because of its origin as a port of a console utility, py-seccure has not been designed with timing attack resistance. I should and will note this more clearly in the README.

This adaptation of __mul__ is not enough to fix all timing attacks. One simple example: normal checks of equality between strings leak information.

How do you intend to use py-seccure, such that this becomes an issue?

[mehitabel]

I am not actually even a potential user, a friend was considering using it for a project and asked me to try to find problems with it. That said, I'm interested in clean, high-level implementations of EC crypto for teaching and demonstration purposes, and you've done something really nice here.

I agree that designing a system against timing attacks would involve more than fixing a few obvious lines of code, though I don't see that as a very strong argument against fixing this one.

[bwesterb]

Thank you. I hope py-seccure will catch on.

I would like to have timing attack resistance in py-seccure, but it is all or nothing: if it cannot be completely secured, then it is no use in the first place. And the issues might be tricky. For instance, there is no way (with acceptable performance) to safely test string equality with pure Python.

I have plans to write a Python wrapper for a very fast (and timing attack resistant) Elliptic Curve library by a colleague (who is an expert; I'm not) in my department. I'll let you know, if you're interested.