This is not a problem with the algorithm or the protocol. It is a bug in the
implementation. Digest values that are zero are allowed by the ANSI X9.62 (and
there is no special case for them) and they work fine in other implementations.
The code is trying to compute u1 * P + u2 * Q, where u1 is the digest value, P
is the curve's base point and Q is the public key, and u2 is something else we
don't care about. It eventually calls ec_wNAF_mul (ec_mult.c:324). Apparenlty
this function computes scalar * basepoint + sum (scalars[i]*points[i] over i
from 0 to num). scalar is u1, num is 1 and the arrays are one element long
with scalars[0] being u2 and points[0] being Q.
In the case in question u1 is zero. In elliptic curve scalar multiplication 0
times anything is the infinite point, which is the additive identity. So lets
watch for this case is the algorithm proceeds.
In line 356 there is a quick exit: the infinite point is returned if scalar is
the null pointer and if num is zero. But
neither of these are satisified, since scalar is a non-null pointer to zero,
and num is 1.
Down in line 379 it is gettng the base point P (called the generator). Then it
checks for some procomputed values. I have no idea whether zero is in the
precomputed set. Let's follow the "not" branch---line 413. It sets numblocks
to 1 and num_scalar to 1, and affectively appends u1 and P to the end of the
list. (See the ?: operator in lines 439 and 443.)
In line 443 it calls compute_wNAF, and when i is 1 it is doing u1 * P, with u1
zero in the case in quesiton.
compute_wNAF is at ec_mult.c:188.and is called with scalar pointing to a zero
BIGNUM. But compute_wNAF, either by design or by accident, can't deal with a
scalar that is zero. It gets down to line 217. Since the value is zero,
scalar->top is zero, and it takes the error branch,
ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERR).
So it looks like we need to either fix compute_wNAF to deal with scalar being
zero, or discard <scalar, point> pairs with scalar pointing to a zero BIGNUM
before it is called. (Perhaps making sure zero is in the procomputed list
would effectively keep the zero valued scalars from getting to compute_wNAF.)
A simple fix that would work for this case only would be to change line 377 from
if (scalar != NULL)
to
if (scalar != NULL && !BN_is_zero(scalar))
But don't do that. That would take care of the scalar arg to ec_wNAF_mul being
zero, but would not take care of zeros in the *scalars array. A better
scheme would be to modify the loop body at ec_mult.c:436 to skip over entries
with a zero multiplier.
Something like
if (!BN_is_zero(i < num ? scalars[i] : scalar)) {
...
but I'm not sure what to put in the else branch, which has to put something
into wNAF[i]. I'll leave it to experts who understand this code.
"Victor B. Wagner" <[EMAIL PROTECTED]> wrote: On 2007.05.16 at 12:35:37 -0700,
[EMAIL PROTECTED] wrote:
> I'm running OpenSSL 0.9.8e. If I set up an ECDSA verify with
> EC_KEY_new_by_curve_name(NID_X9_62_prime256v1) and call ECDSA_do_verify
> with dgst (first arg) an array of all zeros and dgst=1 (second arg), the
> call fails with error 16.
As far as I understand, El Gamal signature scheme is not supposed to
work when digest is all zeros. GOST signature algorithms (which are
simular to DSA/ECDSA) treat this as
special case, and GOST R 34.10 specify that if digest (interpreted as
BIGNUM) is zero, it should be explicitely set to one. I always wondered
why DSA doesn't have such fallback.
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [email protected]
Automated List Manager [EMAIL PROTECTED]
