Re: [openssl-dev] ecp_nistz256 correctness/constant-timedness
On Sun, Apr 26, 2015 at 10:37 PM, Brian Smith br...@briansmith.org wrote:
On Fri, Apr 24, 2015 at 5:54 AM, Emilia Käsper emi...@openssl.org wrote:
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.
Great.
I want to call your attention to one particularly non-obvious failure to
handle errors correctly:
static void ecp_nistz256_windowed_mul([...], P256_POINT *r, [...])
{
[...]
if ((num * 16 + 6) OPENSSL_MALLOC_MAX_NELEMS(P256_POINT)
|| (table_storage =
OPENSSL_malloc((num * 16 + 5) * sizeof(P256_POINT) + 64)) ==
NULL
|| (p_str =
OPENSSL_malloc(num * 33 * sizeof(unsigned char))) == NULL
|| (scalars = OPENSSL_malloc(num * sizeof(BIGNUM *))) == NULL) {
ECerr(EC_F_ECP_NISTZ256_WINDOWED_MUL, ERR_R_MALLOC_FAILURE);
goto err;
}
[...]
err:
[...]
}
ecp_nistz256_windowed_mul checks for errors, but it doesn't report the
fact that an error occurred to the caller, because it has return type
|void|. And, the caller doesn't check that ecp_nistz256_windowed_mul
failed; it can't because of the void return type.
Thanks again, I would have missed that!
I hope I got it all now. Scroll past commit 5956b110e3 (master) or
07977739f0 (1.0.2) for all the changes.
Cheers,
Emilia
Cheers,
Brian
___
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
___
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Re: [openssl-dev] ecp_nistz256 correctness/constant-timedness
On Fri, Apr 24, 2015 at 5:54 AM, Emilia Käsper emi...@openssl.org wrote:
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.
Great.
I want to call your attention to one particularly non-obvious failure to
handle errors correctly:
static void ecp_nistz256_windowed_mul([...], P256_POINT *r, [...])
{
[...]
if ((num * 16 + 6) OPENSSL_MALLOC_MAX_NELEMS(P256_POINT)
|| (table_storage =
OPENSSL_malloc((num * 16 + 5) * sizeof(P256_POINT) + 64)) ==
NULL
|| (p_str =
OPENSSL_malloc(num * 33 * sizeof(unsigned char))) == NULL
|| (scalars = OPENSSL_malloc(num * sizeof(BIGNUM *))) == NULL) {
ECerr(EC_F_ECP_NISTZ256_WINDOWED_MUL, ERR_R_MALLOC_FAILURE);
goto err;
}
[...]
err:
[...]
}
ecp_nistz256_windowed_mul checks for errors, but it doesn't report the fact
that an error occurred to the caller, because it has return type |void|.
And, the caller doesn't check that ecp_nistz256_windowed_mul failed; it
can't because of the void return type.
Cheers,
Brian
___
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Re: [openssl-dev] ecp_nistz256 correctness/constant-timedness
On Fri, Apr 24, 2015 at 3:00 PM, Emilia Käsper emi...@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 br...@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
___
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Re: [openssl-dev] ecp_nistz256 correctness/constant-timedness
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 br...@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.
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
___
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Re: [openssl-dev] ecp_nistz256 correctness/constant-timedness
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 emi...@openssl.org wrote:
On Fri, Apr 24, 2015 at 3:00 PM, Emilia Käsper emi...@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 br...@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
___
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
