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
_______________________________________________
Tech mailing list
Tech@cryptech.is
https://lists.cryptech.is/listinfo/tech
