[Cryptech Tech] Update on ECDSA and ECDH cores

[Pavel Shatov]

Hi,

Last week I pushed two new cores to the repository: ecdhp256 and 
ecdhp384. These are in fact point multipliers for curves P-256 and 
P-384. While we already have ecdsa256 and ecdsa384 cores, the difference 
is that the older ones can only multiply the base point, so they can 
only be used to generate public keys and to sign (to multiply by the 
per-message [random] number). The newer cores can multiply any point, so 
they can be used for ECDH key agreement as well. There's certain overlap 
in functionality, so maybe it makes sense to get rid of the older cores 
in the future. Newer cores are a bit (~6%) slower though, I'm going to 
explain this a bit later. Note, that we currently don't have an API for 
key agreement yet.

I've also merged changes from the fix branch into master for ecdsa### 
cores. I would like to explain what the fix is about.

TL;DR
Before the fix ecdsa### cores produced wrong output when multiplying by 
n+2 (n is the order of the base point). This is a theoretical bug, 
because we always multiply by 0 < k < n, but I decided to fix it, 
because, I mean, who knows what attack can be mounted because of it. 
Moreover the patch is straightforward (only involves changing two lines 
of code per core) and easy to verify in hardware.

ecdsa### cores do Q = k * G multiplication using the double-and-add 
approach, bits of the multiplier are scanned left-to-right, the 
algorithm is:

R = 0
for i = msb to lsb
	T = double(R)
	R = add(T, G)
	if !k[i]:	R = T
	else:		R = R
Q = affine(R)

Now double(P) handles one special case, namely when P is at infinity, 
while add(P, Q) has to handle four special cases: a) P is at infinity, 
b) Q is at infinity, c) P == Q, d) P == -Q. In our particular case Q is 
the base point G, so b) does not apply. The problem is with c), because 
we need to do double(P) instead, which is very uncomfortable from the 
constant run-time point if view. The trivial solution is to return a 
precomputed point H = 2 * G instead. The problem is that I screwed up 
and stored wrong coordinates of point H in the cores' ROM. I think I 
used the H = double(G) routine, but then forgot to convert the result 
from projective coordinates.

If we look at the algorithm above, c) can happen only if we get the base 
point after doubling. This in its turn can happen only when multiplying 
by n + 2. The very last iteration (i = 0) of the multiplication 
algorithm for k = n + 2 looks like this (n is odd, n + 2 is odd, so k[0] 
= 1):

i = 0: after doubling: Q = 2 * ((n + 1) / 2 * G) = (n + 1) * G
        after addition: Q = (n + 1) * G + G = (n + 2) * G

After doubling we get (n + 1) * G, which is equivalent to G, so the 
special case c) is triggered and the adder returns invalid coordinates. 
The fix was straightforward, I changed precomputed coordinates of H = 2 
* G to correct values. To verify this patch, one needs to compute 2 * G 
and (n + 2) * G, the products should be equal. During the first 
multiplication the product comes from the doubling block, during the 
second multiplication the precomputed double of the base point will be 
returned. I've updated the sample driver for the STM32 to do this check.

For ECDH the situation is a bit different, because one has to multiply 
by an arbitrary point and it is impossible to store its precomputed 
double in advance. The newer ecdhp### cores first double the 
user-supplied point and store the result, then do the multiplication. 
That's where the 6% speed penalty comes from.

I'm not sure, that all those complications are necessary, because as far 
as I understand that problematic situation never happens in reality, but 
my understanding of mathematics is not enough to properly justify it. 
Given that the fix is very easy I decided to implement it. We have a 
(somewhat indecent) saying in Russia, that it's better to take more 
care, than less care...

I started working on 25519 core, it looks way more attractive in terms 
of all those doubling and addition exceptions.


-- 
With best regards,
Pavel Shatov