[openssl-dev] ecp_nistz256 correctness/constant-timedness

[Emilia Käsper]

commit c028254b12 fixes 1., 2. and 3. (also applied to 1.0.2).
commit 53dd4ddf71 fixes 5 and some of 4.

Still ploughing my way through the rest of error checking.

Cheers,
Emilia

On Fri, Apr 24, 2015 at 3:15 PM, Emilia Käsper <emilia at openssl.org> wrote:

>
>
> On Fri, Apr 24, 2015 at 3:00 PM, Emilia Käsper <emilia at openssl.org> wrote:
>
>> Thanks for the report! Let me clarify a few points, and then I'll fix it.
>>
>> On Thu, Apr 23, 2015 at 11:07 PM, Brian Smith <brian at briansmith.org>
>> wrote:
>>
>>> 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.
>>>
>>>
>> Yes, this needs a comment. Basically we treat overlong scalars as
>> malformed, and don't guarantee constant-timeness for them. (It'd be too
>> hard.) In the ecp_nistp***.c modules, this is commented.
>>
>>
>>
>>> 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.
>>>
>>
>> I think that's fine and just needs a comment. It happens in the end and
>> basically strips leading zero-words from the (presumably public) output.
>> The ecp_nistp***.c code just calls
>> EC_POINT_set_Jprojective_coordinates_GFp() at this point.
>>
>>
>>>
>>> 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.)
>>>
>>
>> Yep, that's a bug because r->Z_is_one may remain incorrectly set.
>>
>> I don't know why BoringSSL does that extra check in
>> EC_POINT_is_at_infinity, though; it precedes their public git history. I'll
>> check with the authors.
>> I agree with you that this appears an optimization flag, so what should
>> always be guaranteed is that point->Z_is_one => BN_is_one(point->Z). But
>> !point->Z_is_one => inconclusive.
>>
>
> Oh, I think it's just an optimization on their end.
>
>
>>
>>
>>
>>>
>>> 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?
>>>
>>
>> Quite likely! This'll go on a TODO list somewhere...
>>
>>
>>>
>>> 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.
>>>
>>
>> Yep, these need fixing.
>>
>> Cheers,
>> Emilia
>>
>>
>>> All that aside, this code is very fast, and it is awesome that it got
>>> adapted to non-X64 platforms already!
>>>
>>> Cheers,
>>> Brian
>>>
>>> _______________________________________________
>>> openssl-dev mailing list
>>> To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mta.openssl.org/pipermail/openssl-dev/attachments/20150424/8e13ab3e/attachment-0001.html>