[openssl-dev] ecp_nistz256 correctness/constant-timedness

[Brian Smith]

Hi,

I have some questions regarding this implementation.

https://github.com/openssl/openssl/blob/e0e920b1a063f14f36418f8795c96f2c649400e1/crypto/ec/ecp_nistz256.c

1. In ecp_nistz256_points_mul, we have this code:

    if ((BN_num_bits(scalar) > 256) {
            ...
            if (!BN_nnmod(tmp_scalar, scalar, &group->order, ctx)) {...}
            scalar = tmp_scalar;
    }

I think it would be useful to add a comment about why this is OK in terms
of the constant-time-correctness of the code, because it isn't obvious.

2. Later in the same function, we have this code:

    bn_correct_top(r->X);
    bn_correct_top(r->Y);
    bn_correct_top(r->Z);

Again, it isn't clear why it is OK to call bn_correct_top given that
bn_correct_top isn't a constant-time function. I think either this code
should be changed so that it is constant time, or a comment should be added
explaining why it doesn't need to be.

3. When doing the initial adaptation of the code to get it working inside
of BoringSSL, I had to make this change:

    bn_correct_top(r->X);
    bn_correct_top(r->Y);
    bn_correct_top(r->Z);
+  r->Z_is_one = is_one(p.p.Z);

(Alternatively, maybe one can change BoringSSL's implementation
of EC_POINT_is_at_infinity to ignore r->Z_is_one like OpenSSL's
implementation does.)

Looking at the OpenSSL code, I can see that Z_is_one is only used for
optimization purposes in the "simple" ECC implementation. Even ignoring
BoringSSL being different, I found it confusing that sometimes Z_is_one
*must* be set correctly and other times it *must* be ignored. Perhaps it is
worth renaming this member to "simple_Z_is_one" and/or documenting more
clearly when it is maintained and when it can and cannot be used.

Alternatively, I noticed that BN_is_one is not a very expensive function,
and probably can be made even less expensive, so the optimization of using
the Z_is_one flag instead of just calling BN_is_one may not be worthwhile.
Perhaps it would be better to remove it completely?

4. There seems to be quite a bit of missing error checking in this code.
For example, the return values of calls to bn_wexpand are not checked in
multiple functions. Further, a lot of the error checking in the
probably-never-used ecp_nistz256_mult_precompute function is missing, e.g.
calls to EC_POINT_new, EC_POINT_copy, and
ec_GFp_simple_{add,dbl,make_affine}. I think this whole file needs to be
combed for missing error checks.

5. In ecp_nistz256_mult_precompute, if the ctx parameter is null, a new
context will be created with BN_CTX_new but BN_CTX_free is not called
anywhere in the file.

All that aside, this code is very fast, and it is awesome that it got
adapted to non-X64 platforms already!

Cheers,
Brian
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mta.openssl.org/pipermail/openssl-dev/attachments/20150423/8bf530a8/attachment.html>