<div dir="ltr">Thanks for the report! Let me clarify a few points, and then I'll fix it.<div><br><div><div class="gmail_extra"><div class="gmail_quote">On Thu, Apr 23, 2015 at 11:07 PM, Brian Smith <span dir="ltr"><<a href="mailto:brian@briansmith.org" target="_blank">brian@briansmith.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">Hi,<br><br>I have some questions regarding this implementation.<br><br><a href="https://github.com/openssl/openssl/blob/e0e920b1a063f14f36418f8795c96f2c649400e1/crypto/ec/ecp_nistz256.c" target="_blank">https://github.com/openssl/openssl/blob/e0e920b1a063f14f36418f8795c96f2c649400e1/crypto/ec/ecp_nistz256.c</a><br><br>1. In ecp_nistz256_points_mul, we have this code:<br><br> if ((BN_num_bits(scalar) > 256) {<div> ...<br><div> if (!BN_nnmod(tmp_scalar, scalar, &group->order, ctx)) {...}</div><div><div> scalar = tmp_scalar;</div></div><div> }</div><div><br></div><div>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.</div><div><br></div></div></div></blockquote><div><br></div><div>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.</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><div></div><div>2. Later in the same function, we have this code:</div><div><br></div><div><div> bn_correct_top(r->X);<br></div><div> bn_correct_top(r->Y);</div><div> bn_correct_top(r->Z);</div></div><div><br></div><div>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.</div></div></div></blockquote><div><br></div><div>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.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><div><br></div><div>3. When doing the initial adaptation of the code to get it working inside of BoringSSL, I had to make this change:</div><div><br></div><div><div><div> bn_correct_top(r->X);<br></div><div> bn_correct_top(r->Y);</div><div> bn_correct_top(r->Z);</div></div></div><div>+ r->Z_is_one = is_one(p.p.Z); </div><div><br></div><div>(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.)</div></div></div></blockquote><div><br></div><div>Yep, that's a bug because r->Z_is_one may remain incorrectly set.<br></div><div><br></div><div>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.</div><div>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.</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><div><br></div><div>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.</div><div><br></div><div>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?</div></div></div></blockquote><div><br></div><div>Quite likely! This'll go on a TODO list somewhere...</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><br></div><div>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.</div><div><br></div><div>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.</div></div></blockquote><div><br></div><div>Yep, these need fixing.</div><div><br></div><div>Cheers,</div><div>Emilia</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><br></div><div>All that aside, this code is very fast, and it is awesome that it got adapted to non-X64 platforms already!</div><div><br></div><div>Cheers,</div><div>Brian</div></div>
<br>_______________________________________________<br>
openssl-dev mailing list<br>
To unsubscribe: <a href="https://mta.openssl.org/mailman/listinfo/openssl-dev" target="_blank">https://mta.openssl.org/mailman/listinfo/openssl-dev</a><br>
<br></blockquote></div><br></div></div></div></div>